TEORÍA DE GRAFOS.
Enviado por Daniel Contreras Almanza • 14 de Junio de 2016 • Apuntes • 491 Palabras (2 Páginas) • 225 Visitas
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.
...