Exploración de Conceptos Fundamentales en Teoría de Grafos

Isomorfismo y Grado de un Vértice

Dos grafos no orientados G1=(W1,F1) y G2=(W2,F2) diremos que son isomorfos si existe una aplicación biyectiva tal que: {v,w} ∈ F1 si y solo si {f(v),f(w)} ∈ F2.

Sea G=(W,F) un grafo no dirigido, llamaremos grado de un vértice al número de lados incidentes a dicho vértice. Lo denotaremos por gr(v).

Tipos de Grafos

Grafos Regulares y Completos

Un grafo se dice k-regular si todos sus vértices son de grado k.

Un grafo no orientado se dirá completo si cada vértice es adyacente con todos los demás; esto es, el grado de cada vértice es p-1, o lo que es lo mismo, es (p-1)-regular. Lo denotaremos por Kp.

Grafos Conexos y Distancia

Un grafo no orientado se dirá conexo si para cada par de vértices existe un camino que los conecta.

Sea G un grafo, llamaremos distancia entre dos vértices d(v,u) a la longitud de cualquiera de los caminos más cortos que conectan v con u; a estos caminos se les llama geodésicas.

Coloración de Grafos

Dado un grafo G, colorear un grafo consiste en asignar colores a cada vértice de forma que a dos vértices adyacentes no se les asigne el mismo color. Si el número de colores usados es n, entonces diremos que el grafo es n-coloreable.

Al menor n, para el cual conseguimos una n-coloración, se le llama número cromático y el grafo es n-cromático.

Grafos Planos

Un grafo se dirá plano si podemos representarlo gráficamente en el plano de forma que sus lados no se corten.

Un grafo es plano si y solo si no contiene un subgrafo homeomorfo a K5 o K3,3.

Matriz de Adyacencia y Caminos

Sea G=(W,F) un grafo con matriz de adyacencia A para W={v1,v2…vn}. Entonces, el número de caminos de longitud l que conecten los vértices vi y vj coinciden con las coordenadas (i,j)-ésima de A^l. Consecuencias:

1. La entrada (i,i) de A² es el grado del vértice vi.
2. La entrada (i,i) de A³ es el doble de triángulos que contienen a vi.
3. La entrada (i,j) de A^l para l=1,…,p-1 es 0, entonces vi y vj se encuentran en componentes conexas distintas, es decir, no hay un camino que conecte a vi con vj.
4. Si vi está conectado con vj, entonces d(vi,vj) es el menor valor de l para el cual la entrada (i,j) no es nula. Además, para esta l, el elemento aij es el número de geodésicas de vi a vj.

Grafos de Euler y Hamilton

Sea G=(W,F) grafo conexo; es de Euler si el grado de sus vértices es par.

Sea G=(W,F) un grafo con más de 3 vértices. Un camino elemental que pase por todos los vértices del grafo se dice camino de Hamilton. Un camino de Hamilton cerrado es un ciclo de Hamilton. Un grafo que posea al menos un ciclo de Hamilton es un grafo de Hamilton.

Diagonalización de la Matriz de Adyacencia

Diagonalización:

1. Se calcula el polinomio característico p(λ)=|A-λI|.
2. Factorizarlo para calcular sus raíces, junto con sus multiplicidades algebraicas.
3. Calculamos las multiplicidades geométricas di=n-rg(A-λiI).
4. Aplicamos el Teorema de diagonalización; si no es diagonalizable, hemos terminado, pero en caso de que sí lo sea, vamos al paso 5:
   • i) Σai = n
   • ii) ai = di para i=1,..,n
5. Calculamos la base de los vectores propios, V_λi=ker(f-λiI).
6. La base de vectores propios de V, Bv = Bv_λ1 ∩ … ∩ Bv_λr, pues V = V_λ1 ⊕ … ⊕ V_λr. La matriz P regular es la matriz de cambio de base (x columnas). La matriz D diagonalizable de los autovalores. En efecto, D = P^-1AP.