Digrafos

Definición de digrafo: Un grafo orientado o grafo dirigido G (abreviadamente digrafo) consiste en un conjunto no vacío de elementos V, llamados vértices o nodos y un multiconjunto E de pares ordenados de V, llamados arcos o aristas.

• Denotemos al digrafo por D = <V,E>
• Si r y w son vértices de D, entonces un arco rw   se dice que esta orientado o dirigido de r a w o que une a r y w .
•  Denotemos por V(D) y E(D) a los conjuntos de vértices y aristas del grafo D respectivamente si estos no se mencionan explícitamente .

Definición de digrafo simple: Si un digrafo no tiene lazos ni arcos múltiples diremos que es un digrafo simple.

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.

Definición de arcos múltiples: Los arcos que unen el mismo par de vértices que tienen la misma dirección se llaman múltiples.

• El arco que une a un vértice con el mismo se denomina lazo.
• Un digrafo sin lazos ni arcos múltiples se dice que es simple.

Definición de subgrafo: Considere el digrafo D = <V, E>. Un subgrafo de D es un digrafo cuyos vértices son todos elementos de V y cuyos arcos son todos elementos de E.

Definición  de vértices adyacentes: Sean v y w vértices de un digrafo. Diremos que w es adyacente a v si existe un arco edesde v hasta w que los une. Además si e está dirigido de v a w diremos que e es incidente desde v e incidente desde w .

Definición de grado exterior e interior: Sea D un digrafo sin lazos y sea v un vértice de D. El grado exterior de v es el número de arcos incidentes desde v y lo denotaremos por extdeg ( v ). El grado interior de v es el número de arcos incidentes a v y lo denotaremos por indeg ( v ) .

• En caso de que el digrafo tenga lazos, cada lazo aporta uno al grado interior y uno al grado exterior del vértice correspondiente.
• Un vértice v es aislado si extdeg( v ) = indeg( v ) = 0.

Lema (Handshaking lema): Sea D un digrafo, entonces

Definición de digrafos isomorfos : Dos digrafos  D1 y D2 son isomorfos y denotaremos , si existen bisecciones 

 ,

tales que para toda arista 

Definición de camino: Un camino C en un digrafo D es una secuencia de vértices de D tal que cumple al menos una de las condiciones siguientes:

1. hay un solo vértice en la secuencia
2. si k > 1 entonces 
• Diremos que C conecta  y 
• Llamaremos longitud del camino C a la cantidad de aristas que hay en él (en este caso k – 1)
• Diremos que el camino es simple si, excepto el primero y el último, todos los vértices y aristas son diferentes.
• Diremos que el camino C es un ciclo (circuito) si su longitud es al menos uno y coinciden el primero y el último vértice.

Proposición :   Sean v y w vértices de un digrafo D. Si hay un camino que conecta a v y w entonces también hay un camino simple que los conecta.

Se plantea el siguiente problema: Dado un digrafo D=<V,E> (E conjunto de arcos) con una función de pesos sobre E(D) y se desea hallar el costo del menor camino desde uno de esos vértices hasta otro cualquiera de V(D).[Ver algoritmos de Dijkstra y Floyd ]

Definición de digrafo conexo: Un digrafo D es conexo si su grafo subyacente es conexo.

Definición de digrafo fuertemente conexo: Un digrafo es fuertemente conexo si para todo par ordenado de vértices hay un camino que los conecta.

• Una componente fuertemente conexa del digrafo D es un subgrafo de D que es fuertemente conexo maximal, es decir, un subgrafo fuertemente conexo que no es subgrafo de ningún otro subgrafo fuertemente conexo.

Definición de torneo: Un torneo es un digrafo cuyo grafo subyacente es un grafo completo.

Definición de grafo orientable: Un grafo G se dice que es orientable si es grafo subyacente de algún digrafo fuertemente conexo, es decir, es posible orientar las aristas de modo tal que el digrafo obtenido es fuertemente conexo.

Definición de puente: Una arista en un grafo conexo G se llama puente si al removerla el grafo deja de ser conexo.

Teorema (Orientabilidad ): Un grafo conexo G es orientable si y sólo si no tiene puentes.

Para demostrar este teorema probemos primero el siguiente lema :

Lema: En un grafo sin puentes toda arista está contenida en algún ciclo.

Demostración del lema:

Sea la arista vw en un grafo G conexo sin puentes. Puesto que G no tiene puentes, si suprimimos a vw G seguirá siendo conexo y por lo tanto existirá un camino simple vu…w que no contiene a vw . Luego en G existe al menos el ciclo vu…wv .

Procedamos ahora a demostrar el teorema sobre la orientabilidad de un grafo:

Demostración :

Supongamos primero que G es orientable. Demostremos que G no tiene puentes. Supongamos por el contrario que G tiene una arista e que es un puente. Como al suprimir e G deja de ser conexo tenemos que e une a dos componentes conexas disjuntas S1 y S2. Después de orientar a G, la arista e tendrá uno y solo uno de los dos sentidos posibles:

Pero esto contradice el echo de que, siendo G orientable debe ser también fuertemente conexo. Luego lo supuesto es falso y en consecuencia G no tiene puentes.

Supongamos ahora que G no tiene puentes,  probemos que es orientable. Puesto que G es conexo, según el lema demostrado arriba G tiene al menos un ciclo C. Orientemos las aristas de C a dextrorso (no tiene relevancia el sentido, solo se necesita el ciclo orientado) después de esto el digrafo G* formado por las aristas orientadas de C será fuertemente conexo.

Prosigamos de manera constructiva, en todo momento G* será el digrafo formado por todas las aristas de G.

Si G* contiene todos los vértices de G entonces ya tenemos a G. En caso contrario, puesto que G es conexo, existirá una aristae , no orientada aún, que parte de un vértice v de G*  a uno que no está en G* . Según el lema demostrado, la arista e estará contenida en un ciclo del grafo G. Orientemos a las aristas de dicho ciclo comenzando por orientar la arista e desde v y parando en el primer vértice que pertenece a G* ; esto es totalmente realizable pues a lo sumo nos encontraremos con v . Puesto que G*  es fuertemente conexo, se hace evidente que después de esta operación lo seguirá siendo.

Si aun quedan vértices en G que no están en G*  volvemos a realizar la operación descrita. Puesto que V (G) es finito, después de un número finito de aplicar este procedimiento habremos orientado el grafo G.

Definición de cadena: Un camino  en un digrafo D se dice que es una cadena si k = 1 o k > 1y las aristas  son distintas dos a dos.

• Una cadena que contiene todas las aristas de D se llama cadena de Euler.
• Una cadena cerrada es una cadena en la que el primer y último vértice coinciden.
• Una cadena cerrada de Euler es una cadena de Euler que es cerrada.
• El digrafo D se dice que es Euleriano si contiene una cadena de Euler.

Teorema (Conexidad y cadenas de Euler ): Sea D un digrafo conexo, luego:

• D tiene una cadena cerrada de Euler si y sólo si el grado exterior y el grado interior de cada vértice son iguales.
• D tiene una cadena de Euler que no es cerrada si y sólo si hay dos vértices v y w de D tales que:

Definición de ciclo Hamiltoniano: Un ciclo de un digrafo D se dice que ciclo de Hamilton o ciclo Hamiltoniano si contiene todos los vértices de D.

• Si el digrafo D es conexo se dice que es Hamiltoniano si contiene un ciclo de Hamilton.
• Diremos que un camino es Hamiltoniano si contiene todos los vértices del digrafo.

Proposición: Todo torneo tiene un camino Hamiltoniano.

Teorema( Caminos de Hamilton ): Sea D un digrafo simple con |V(D)| = n :

• Si se cumple que  D es Hamiltoniano.
• Si para cualquier par de vértices no adyacentes v y w se tiene que  entonces D es Hamiltoniano.