Ejercicios de Grafos.

Si existe una cadena C–(Vi, Vj) o Vi=Vj en un grafo G, diremos que Vi esta conectado con Vj. La relación “estar conectado”, definida sobre el grafo V(G) es una relación de equivalencia (¿porque?).

Respuesta:

Es una relación de equivalencia porque si existe al menos un camino para ir de Vi a Vj, entonces también existe al menos un camino para ir de Vj a Vi. Ambos caminos usando los mismos vértices y aristas.

Sabemos que un camino de Vi a Vj esta dado por:

R = V0a1V1a2V2… ak-1Vk-1akVk

Lo que también podemos escribir como:

R = VkakVk-1ak-1…V2a2V1a1V0

Lo anterior cumple que:

“Cuyos términos son alternadamente vértices y aristas, tal que toda arista de R tiene como sus extremos el vértice precedente y el siguiente de la sucesión.”

Por lo tanto se puede concluir que el camino de Vk a V0 existe, demostrando así que es una relación de equivalencia.

Teoría de Grafos – Lorica

Jojann De Jesús De Vargas Álvarez

DEFINICIÓN DE GRAFO: Estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y el conjunto de aristas, líneas o lados que pueden ser orientados o no.

¿QUE TIPO DE GRAFO ES?

El tipo de grafo al que corresponde el grafo anterior es tripartito por que usando tres colores podemos colorear cada vértice con un color diferente sin que dos vértices seguidos tengan el mismo color.

SUBGRAFOS[pic 1]

 SUBGRAFO 1

[pic 2]

 SUBGRAFO 2

SUBGRAFO COBERTOR:

El subgrafo posee el mismo número de vértices que padre original.

[pic 3]

SUBGRAFO VÉRTICES DISYUNTOS:

Son los subgrupos que no poseen vértices comunes, al recorrer el grafo no pasa dos veces por el mismo vértice. [pic 4][pic 5]

[pic 6][pic 7]

Si queremos recorrer de cualquiera de los vértices del grafo y regresar al mismo vértice nos damos cuenta que no repetimos ningún vértice en cualquiera de los dos subgrafos, es decir si partimos del vértice 1 y queremos llegar al mismo vértice, nos damos cuentas que no hay necesidad de repetimos ninguno de los vértices por que partimos del vértice 1 luego al 2 luego al 3 luego al 4 luego al 5 luego al 6 y llegamos al 1.    Lo mismo ocurre cuando partimos de un vértice para llegar a otro distinto del inicial, si partimos del vértice 7 para llegar al 9 pasamos por el vértice 8 y vemos que no se repite ningún vértice por lo cual podemos decir que son subgrafos con vértices disyuntos.  

SUBGRAFO ARISTAS DISYUNTAS:

Son los subgrupos que no poseen aristas en comunes, al recorrer el grafo no pasas dos veces por la misma arista.[pic 8]

[pic 9]

[pic 10][pic 11]

Si queremos recorrer cualquiera de los vértices del grafo y regresar al mismo u otro distinto nos damos cuenta que no repetimos ninguna arista en cualquiera de los dos subgrafos.  

OPERACIONES: 

UNION: Es la fusión de vértices y aristas de dos subgrafos  que paseen un vértices en común 

[pic 12][pic 13][pic 14]

[pic 15]

[pic 16]

[pic 17][pic 18]

INTERSECCIÓN: Son los vértices y aristas  que tienen en común dos subgrafos. [pic 19]

SUBGRAFO  4

[pic 20][pic 21]

GRAFO RESULTANTE[pic 22]

SUMA DE ANILLOS: Es la unión de dos subgrafos  menos la intersección de estos.

SUBGRAFO  5

[pic 23]

SUBGRAFO  4

[pic 24]

GRAFO RESULTANTE

[pic 25]

FUSIÓN DE VÉRTICES

[pic 26][pic 27][pic 28][pic 29][pic 30]

Se combinan dos vértices, en este caso los vértices 2 y 3, la arista que los comunicaba  pasa hacer conectada sobre el vértice resultante y aristas exteriores quedan conectadas al nuevo vértice.

CONEXIÓN ENTRE GRAFOS.

RUTA: Repite aristas pero no vértices

Partimos del punto 1 al 7,  longitud = 6

[pic 31]

CADENA: Repite vértices pero no aristas

Partimos del punto 1 al 6. Longitud = 5

[pic 32] 

CADENA SIMPLE: No repite  vértices ni aristas

Partimos del vértice 6 al 9. Longitud = 3

[pic 33]

RUTA CERRADA: partimos de un punto y volvemos al mismo sin repetir vértices ni aristas

Partimos del vértice 7 y volvemos a él.

Ruta cerrada 1 longitud = 3  identificada con el color negro, Ruta cerrada 2  longitud = 7 identificada con el color azul.

[pic 34] 

CICLO: Consiste en un camino cerrado en el que no se repite ningún vértice a excepción del primero que aparece dos veces como principio y fin del camino.

[pic 35]

CICLO SIMPLE: Un ciclo simple es un ciclo que tiene como longitud al menos 3 y en el que el vértice inicial coincide con el vértice final.

[pic 36]

CONEXO: nuestro grafo es conexo porque existe al menos una trayectoria para llegar de un vértice a otro.

[pic 37]

HAKIMI:

Para realizar Hamiki primero tenemos que representar el grafo como una secuencia de números. Al realizar lo anterior, quedo la siguiente secuencia de números:

...