trees.md

Grafos 1: Trees

Un grafo en matematicas discretas es una estructura discreta compuesta por un conjunto de vertices y un conjunto de aristas, el conjunto de aristas esta incluido en el conjunto de pares de elementos del conjunto de vertices.

ejemplo:

vertices: {1, 2, 3, 4}

aristas: {{1, 2}, {3, 4}}

Preguntas:

• Si la arista {x, y} es igual a la arista {y, x}, cuantas aristas como maximo hay si la cantidad de vertices es 3? (nota: por ahora no consideraremos el caso cuando x = y).

• y si la cantidad de vertices es n?

grado de un vertice

El grado de un vertice v se define como la cantidad de veces que aparece v en una arista.

nodos adjacentes.

Son nodos que aparecen en una misma arista.

preguntas:

• se define una triangulo {x, y, z} en un grafo, si las aristas {x, y}, {y, z} y {x, z} aparecen a la vez. Cuanta es la cantidad maxima de triangulos que puede tener un grafo. Mantel's Theorem

Paths

• Un path es una secuencia de vertices distintos tal que dos consecutivos son adjacentes.

Conexidad:

• Un grafo es conexo si para todo par de nodos existe un path entre ellos.

Ciclos:

• Un ciclo es igual a un path, pero se repite un unico vertice x1 = xn.

Preguntas:

• que condiciones tiene que tener un grafo para que se pueda particionar por ciclos?

Tree

• Un tree es un grafo conexo y sin ciclos.

• un tree es maximamente aciclico?

• un tree es minimamente conexo?

• un tree tiene n-1 aristas y es conexo?

• un tree cumple que para cada par de nodos existe un unico path?

como recorrer un tree?

• Primero nosotros debemos orientar nuestro tree, orientar o plantar un tree, es asignarle un orden parcial (raices, tallo, ramas, hojas...). Orientar un arbol es bien facil, intuitivamente podemos ver que crea una relacion de padre a hijo (la raiz es la primera, luego sus nodos vecinos, luego los vecinos de los vecinos...).

• Esto da motivo para realizar el siguiente algoritmo:

void dfs(int node, int parent) {
  for (int u : g[node]) {
    if (u == parent) continue;
    dfs(u, node);
  }
}

• simple? La pregunta es, como guardo un arbol en memoria???

La forma mas simple de guardar un arbol para luego recorrerlo es por medio de su lista de adjacencia, una lista de adjacencia, guarda para cada nodo, los nodos que son adjacentes a ese.

cin >> n;
for (int i = 1; i < n; ++i) {
  int u, v;
  cin >> u >> v;
  g[u].emplace_back(v);
  g[v].emplace_back(u);
}

Distancia entre nodos

La distancia entre dos nodos en un arbol, dado que el path es unico, es igual a la cantidad de aristas en el path entre esos dos nodos.

Diametro de un arbol.

El diametro de un arbol se define como la distancia entre los nodos mas alejados.

Hallando el diametro de un arbol

int diameter = 0;
int dfs(int node, int parent) {
    vector<int> best = {0, 0};
    for (int u : g[node]) {
      if (u == parent) continue;
      best.push_back(dfs(u, x) + 1);
      sort(rbegin(best), rend(best));
      best.pop_back();
    }
    diameter <?= best[0] + best[1];
    return best[0];
}

Exite una forma mas simple (de codear)??

diameter of a tree