Grafos

Curso de doctorado “Problemas de optimizaci´n sobre grafos” o Departament de Matem`tica a

Conceptos b´sicos sobre grafos y digrafos a

Definici´n de grafo o
Un grafo G = (V, E) est´ formado por un conjunto finito y no vac´ V y por un conjunto E de a ıo pares no ordenados de elementos distintos de V . Elementos de V : v´rtices (o nodos). e Elementos de E: aristas. Si e = {u, v} (e = uv) esuna arista, entonces u y v son adyacentes (u ∼ v); e es incidente con los v´rtices u y v. e El orden de G es el n´mero de v´rtices (|V |) y la medida de G es el n´mero de aristas (|E|). u e u Ejemplo: G = (V, E), con V = {a, b, c, d, e, f } y E = {ab, ac, bc, bd, cd, de}.

Grado de un v´rtice e
El grado de un v´rtice v en un grafo G, que se denota por g(v), es el n´mero de aristas de G e uincidentes con v. Teorema 1 (Lema de las encajadas de manos). La suma de todos los grados de los v´rtices de un grafo G = (V, E) es igual al doble de su medida; es decir, e g(v) = 2|E|.
v∈V

Corolario 1. Todo grafo tiene un n´mero par de v´rtices de grado impar. u e Ejemplo:

Grados de los v´rtices: g(a) = 2, g(b) = g(c) = g(d) = 3, g(e) = 1 y g(f ) = 0. e

Representaci´n de un grafo o
Sea G =(V, E) un grafo con conjunto de v´rtices V = {v1, v2, . . . , vn} y conjunto de aristas e E = {e1, e2, . . . , em} (representaci´n ‘inicial’ de un grafo). o La matriz de adyacencia de G es la matriu A = (aij ) de orden n × n definida por   1, si v y v son adyacentes, i j aij =  0, en caso contrario. La matriz de incidencia de G es la matriu B = (bij ) de orden n × m definida por   1, si e esincidente con v j i bij =  0, en caso contrario. La lista de listas de adyacencia de G es una n-tupla formada per n ‘sublistas’ (conjuntos), una por cada v´rtice vi, donde figuran los v´rtices adyacentes al correspondiente v´rtice vi. e e e Actividad: Analizar las propiedades y comparar las ventajas (y desventajas) de cada una de estas representaciones.

Representaci´n de un grafo: ejemplo oSea G = (V, E) el grafo con V = {a, b, c, d, e, f } y E = {ab, ac, bc, bd, cd, de}.

Matriz de adyacencia:
      A=       0 1 1 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0             

Lista de listas de adyacencia: L = ({b, c}, {a, c, d}, {a, b, d}, {b, c, e}, {d}, {}).

Isomorfismo de grafos
Idea intuitiva: Dos grafos son isomorfos si unopuede obtenerse a partir del otro ‘reetiquetando’ sus v´rtices. e Definici´n: Dos grafos G = (V, E) y G = (V , E ) son isomorfs, G ∼ G , si existe una o = aplicaci´n biyectiva f entre sus respectivos conjuntos de v´rtices, V y V , que preserva las o e adyacencias; es decir, ∀u, v ∈ V, u ∼ v ⇐⇒ f (u) ∼ f (v). Un invariante de un grafo G es un par´metro (propiedad) asociado a G que toma el mismo valora en todos los grafos isomorfos a G. (Ejemplos: orden, medida, secuencia de grados, ...). Problemas abiertos: Determinar un sistema de invariantes de un grafo que lo determine completamente. No se sabe la complejidad algor´ ıtmica del problema del isomorfismo: • No se conoce un test de isomorfismo cuyo coste sea polin´mico (no se sabe si el problema o del isomorfismo es de la llamada clase P). • Nose ha probado que el problema del isomorfismo sea de la llamada clase NP-completo.

Isomorfismo de grafos: ejemplos
Determinar cu´les de las siguientes parejas de grafos son isomorfos entre s´ a ı:

Actividad: Enumerar todos los grafos no isomorfos de orden 3 y 4.

Clases importantes de grafos (I)
El grafo nulo de orden n, que se denota por Nn, es un grafo que tiene n v´rtices y ningunaarista. e El grafo completo de orden n, que se denota por Kn, es un grafo con n v´rtices, donde cada v´rtice es adyacente a todos los dem´s. e e a Un grafo es regular (de grado d) si todos sus v´rtices tienen el mismo grado e (d).

Actividad: Deducir la medida de un grafo regular de orden n y grado d. ¿Cu´l a es la medida del grafo completo Kn?

Clases importantes de grafos (II)
Un grafo G =...