algo iii - grafos

8/18/2019 Algo III - Grafos

1/5

GRAFOS:

Camino Euleriano: Pasa por cada arista del grafo una y solo una vez.

Un grafo conexo es euleriano sii tiene exactamente 2 nodos de grado impar

Un dígrafo conexo es euleriano sii para todo nodo su grado de entrada es igual a su grado

de salida

Camino Hamiltoniano: Pasa por cada nodo del grafo una y solo una vez. No existen buenas caracterizaciones.

Todos los grafos completos son Hamiltonianos (wikipedia)

Para saber si un grafo es Hamiltoniano o no, debemos aplicar el Teorema de Dirac, que se

enuncia: "Sea G = (V,E) un grafo conexo con |V| ≥ 3. Si deg(v) ≥ |V|/2 para todo v∈V,

entonces G es hamiltoniano."

Sea un grafo al que llamaremos G, con sus vértices y aristas, conexo, y con nº total devértices mayor o igual a 3. Es decir, el grafo a tratar debe cumplir todas estas características

 para poder continuar aplicando el Teorema, si no las cumple entonces no será Hamiltoniano.

Ahora bien, suponiendo que se cumplen dichas características, proseguimos:

Si el grado de cada uno de los vértices de este grafo es mayor o igual que la mitad del

número total de vértices, y esto se cumple para todos y cada uno de los vértices de G,entonces este grafo es Hamiltoniano.

Teorema 2 Sea m el número de aristas Sea n el número de vértices⇒ G es un circuito

hamiltoniano si (m >= (n^2 -3 n + 6)/2

Cobertura de vértices: de un grafo no dirigido G=(V,E) es un subconjunto S de V (el

conjunto de vértices) tal que para cada arista ab del conjunto E, ya sea el

vértice a o b pertenece a S.

Matching

Definición de grafo subyacente: Sea D un digrafo. El grafo subyacente de D es el grafo que se obtiene reemplazando cada arco (orientado)de D por una arista no orientada

Un multigrafo o pseudografo es un grafo que está facultado para tener aristas múltiples; es decir, aristas que

relacionan los mismos nodos. De esta forma, dos nodos pueden estar conectados por más de una arista.

Comentario:Completar

8/18/2019 Algo III - Grafos

2/5

En teoría de grafos, un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista.

Un grafo completo de n vértices tiene aristas, y se nota . Es un grafo regular  con todos sus

vértices de grado  . La única forma de hacer que un grafo completo se torne disconexo a través de la

eliminación de vértices, sería eliminándolos todos.

En teoría de grafos, un isomorfismo entre dos grafos G y H es una biyección f  entre los conjuntos de

sus vértices  que preserva la relación de adyacencia. Es decir, cualquier par de

vértices u y v de G son adyacentes si y solo si lo son sus imágenes, f(u) y f(v), en H.

 A pesar de su diferente aspecto, los dos grafos que se muestran a continuación son isomorfos:

En teoría de grafos, un grafo bipartito es un grafo G=(N,E) cuyos vértices se pueden separar en dos conjuntos

disjuntos U y V, es decir, tal que se cumple:

de manera que las aristas sólo pueden conectar vértices de un conjunto con vértices del otro; es decir:

  no existe

ninguna arista  ni

Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices y las aristas

uniendo vértices de columnas (o filas) diferentes.

Los dos conjuntos U y V pueden ser pensados como un coloreo del grafo con dos colores: si pintamos los

vértices en U de azul y los vértices de V de verde obtenemos un grafo de dos colores donde cada arista

tiene un vértice azul y el otro verde. Por otro lado, si un gráfico no tiene la propiedad de que se puede

colorear con dos colores no es bipartito.

Un grafo bipartito con la partición de los vértices en U y V suele denotarse G = (U, V, E). Si |U| =|V|, esto

es, si los dos subconjuntos tiene la misma cantidad de elementos o cardinalidad, decimos que el grafo

bipartito G esbalanceado.

El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor

mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.

En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices,

donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el

algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no

conexo.

Prim (Grafo G )

/* Inicializamos todos los nodos del grafo.

8/18/2019 Algo III - Grafos

3/5

  La distancia la ponemos a infinito y el padre de cada nodo a NULL

Encolamos, en una cola de prioridad

donde la prioridad es la distancia,

todas las parejas del grafo*/

 por cada u en

V[G] hacer 

distancia[u] = INFINITO

padre[u] = NULL

Añadir(cola,)

distancia[u]=0

 mientras !esta_vacia(cola) hacer 

// OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es

menor. 

u = extraer_minimo(cola) //devuelve el minimo y lo elimina de la cola.

 por cada v adyacente a 'u' hacer 

si ((v  ∈ cola) && (distancia[v ] > peso(u, v)) entonces 

padre[v ] = u 

distancia[v ] = peso(u, v)

Actualizar(cola,)

El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un

grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los

vértices y donde el valor total de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca

un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa). El algoritmo de Kruskal

es un ejemplo de algoritmo voraz.

Un ejemplo de árbol expandido mínimo. Cada punto representa un vértice, el cual puede ser un árbol por sí mismo. Se usa el

 Algoritmo para buscar las distancias más cortas (árbol expandido) que conectan todos los puntos o vértices.

Funciona de la siguiente manera:

  se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado

8/18/2019 Algo III - Grafos

4/5

  se crea un conjunto C que contenga a todas las aristas del grafo

  mientras C es no vacío 

  eliminar una arista de peso mínimo de C 

  si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en

un solo árbol

  en caso contrario, se desecha la arista

 Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo.

function Kruskal(G )

Para cada v  en V[G] hacer 

Nuevo conjunto C(v ) ← {v }.

Nuevo heap Q que contiene todas las aristas de G, ordenando por su peso.

Defino un árbol T ← Ø

// n es el número total de vértices

 Mientras T tenga menos de n-1 vertices hacer 

(u,v ) ← Q.sacarMin()

// previene ciclos en T. agrega (u,v ) si u y v  están diferentes componentes en el

conjunto.

// Nótese que C(u) devuelve la componente a la que pertenece u.

if C(v ) ≠ C(u) then

Agregar arista (v ,u) a T.

Merge C(v ) y C(u) en el conjunto

Return arbol T

Un grafo autocomplementario es un grafo que es isomorfo a su complemento. Los grafos autocomplementariosmás simples son el camino de 4 vértices y el ciclo de 5 vértices.

Prim

  Técnica: Goloso

  Complejidad: ó .

  adjacency matrix, searching

  binary heap (as in pseudocode below) and adjacency list

  Fibonacci heap and adjacency list

  Invariante: Conecta iterativamente un conjunto de nodos conexo eligiendo siempre la arista de menor peso que no cierraun ciclo.

[editar ]Kruskal

  Técnica: Goloso

  Complejidad:  Invariante: Selecciona el mínimo eje (siempre que no cierre un circuito) n-1 veces.

8/18/2019 Algo III - Grafos

5/5

[editar ]Camino mínimo desde un nodo

[editar ]Dijkstra

  Técnica: Goloso

  Complejidad: . con Fibonacci Heap.  Invariante: Relaja(*) ejes iterativamente, tomando vértices en orden creciente de distancia a .

  Consideraciones: No es correcto si existen aristas con peso negativo.

[editar ]Bellman-Ford

  Complejidad:  Invariante: Para cada vértice, recorre sus aristas relajando(*) ejes. Caso general (con posibles ciclos de peso negativo).

[editar ]Relax (*)

for i from 1 to size(vertices)-1:

for each edge uv in edges: // uv is the edge from u to v

if u.distance + uv.weight < v.distance:

v.distance := u.distance + uv.weight

v.predecessor := u

[editar ]Camino mínimo entre todo par de nodos

[editar ]Dantzig

  Técnica: Dinámico.

  Complejidad:

  Invariante: En cada paso considera el subgrafo inducido por los vértices .

[editar ]Floyd-Warshall

  Técnica: Dinámico

  Complejidad:

  Invariante: Toma camino mínimo entre y pasando por nodos ( ).

foreach :