TEORÍA DE GRAFOS.

TEORÍA DE GRAFOS

CONDENSACIÓN DE UN DÍGRAFO

TUTOR:

MARIO RAMÓN MACEA ANAYA

INTEGRANTES:

RODOLFO ANAYA ROBLEDO

  JOJANN DE VARGAS ÁLVAREZ

                                ANTONIO LUIS BENÍTEZ LLORENTE

INGENIERÍA DE SISTEMAS IX

UNIVERSIDAD DE CÓRDOBA

SEDE LORICA

8 DE OCTUBRE DE 2015

Dado el siguiente dígrafo hallar su condensación:

[pic 1]

Primero comprobamos si el digrafo es conexo, para saber si lo es quitamos los arcos y los cambiamos por aristas y si el grafo resultante es conexo entonces el dígrafo es al menos débilmente conexo con lo que es suficiente para aplicar el algoritmo.

[pic 2]

Como podemos observar el grafo es conexo porque se puede ir de un vértice a todos los demás para todos los vértices.

Ahora que ya se comprobó que el grafo es conexo entonces procedemos a aplicar el algoritmo el cual consta de los siguientes pasos:

1. Hallar el conjunto de vértices descendentes de un vértice  del dígrafo. [pic 3]

2. Hallar el conjunto de vértices ascendentes del vértice del dígrafo. [pic 4]

3. Interceptas ambos conjuntos de vértices, los vértices que resulten de la intercepción son fuertemente conexos por lo tanto se fusionaran.

4. Quitar los vértices que se fusionaran y dejar los demás para repetir el paso 1,2 y 3.

5. Después de tener todos los conjuntos de vértices entonces proceder a armar el grafo resultante, esto se hace fusionando los vértices fuertemente conexos y fusionando las aristas de dichos vértices.

Recorrido  de los vértices ascendente:

Escogemos el vértice v1 para empezar con el recorrido

[pic 5][pic 6]

El resultado del recorrido es el siguiente:

[pic 7]

Recorrido de los vértices descendentemente: [pic 8]

El resultado del recorrido descendente es el siguiente:

[pic 9]

Ahora procedemos a realizar la intercepción de ambos recorridos:

[pic 10]

El resultado:

[pic 11]

Entonces ahora lo que hacemos es suprimir esos vértices con sus respectivas aristas para obtener un subgrago en donde repetir nuevamente el proceso.

Subdigrafo al suprimir los vértices  [pic 13][pic 12]

Aplicando nuevamente el procedimiento sobre el Subgrafo:

Tomando esta vez el vértice [pic 14]

Recorrido  de los vértices ascendente:

[pic 15]

El recorrido queda:

[pic 16]

Ya que de este vértice no tiene arcos o flechas que entren.

...