TEORIA DE
GRAFOS
El nacimiento del concepto GRAFOS se puede situar, por
el año 1730, cuando Euler (matemático) se convirtió en el padre de la Teoría de
Grafos al modelar un famoso problema no resuelto, llamado el "problema de
los puentes de Königsberg".
En matemáticas y ciencias de la computación, la teoría
de grafos estudia las propiedades de los grafos, que son colecciones de objetos
llamados vértices (o nodos) conectados por líneas llamadas aristas (o arcos)
que pueden tener orientación (dirección asignada). Típicamente, un grafo está
diseñado por una serie de puntos (los vértices) conectados por líneas (las
aristas).
Grafo
Un grafo es una pareja G = (V, A), donde V es un
conjunto de puntos, llamados vértices, y A es un conjunto de pares de vértices,
llamadas aristas. En teoría de grafos, sólo queda lo esencial del dibujo: la
forma de las aristas no son relevantes, sólo importa a qué vértices están
unidas. La posición de los vértices tampoco importa, y se puede variar para
obtener un grafo más claro.
Generalmente, se considera que colocar los
vértices en forma de polígono regular da grafos muy legibles. Prácticamente
cualquier red puede ser modelada con un grafo: una red de carreteras que
conecta ciudades, una red eléctrica o un alcantarillado.
Grafos
conexos y no conexos
Grafo conexo. En matemáticas y ciencias de la
computación es aquel grafo que entre cualquier par de sus vértices existe un
Camino (Grafo) que los une.
Sea el grafo G=<V,A>, donde V es el conjunto de
los nodos o vértices y A es la colección de sus arcos o aristas en dependencia
de si es un grafo orientado o no orientado, se dice que Ges conexo si y solo si
entre cualquier par de vértices x, y de V existe un camino que comience en x y
termine en y.
En el caso de los grafos no orientados simples que
entre cualquier par de vértices existe una arista que los une se hacen llamar
grafos completos y los que |V|=k se denominan Kn.
Grafo no conexo. Es lo opuesto a un grafo conexo, ya
que este grafo tiene algún vértice que no se relaciona con el resto.
Algunos
grafos particulares
COMPLETO
Un grafo no dirigido G= es COMPLETO si existe
arista entre todo par de vértices de V. Sea n=|V|, el número de aristas de un
grafo completo no dirigido es exactamente |E|=n. (n-1)/2. Si se trata de un
grafo dirigido entonces |E|=n. (n-1).
Aristas
dirigidas y no dirigidas
En algunos casos es necesario asignar un sentido
a las aristas, por ejemplo, si se quiere representar la red de las calles de
una ciudad con sus inevitables direcciones únicas. El conjunto de aristas será
ahora un subconjunto de todos los posibles pares ordenados de vértices, con (a,
b) ≠ (b, a). Los grafos que contienen aristas dirigidas se denominan grafos
orientados, como el siguiente: Las aristas no orientadas se consideran
bidireccionales para efectos prácticos (equivale a decir que existen dos
aristas orientadas entre los nodos, cada una en un sentido). Se considera la
característica de "grado" (positivo o negativo) de un vértice, como
la cantidad de aristas que llegan o salen de él; para el caso de grafos no
orientados, el grado de un vértice es simplemente la cantidad de aristas que
tocan este vértice. Por ejemplo, el grado positivo (salidas) de d es 3,
mientras que el grado negativo (llegadas) de b es 1.
Grafos de
Euler
Camino de
Euler
Se dice que un grafo no dirigido G= es EULERIANO si
existe un camino cerrado, propio, simple (no se repiten aristas) pero no
necesariamente elemental que incluye todas las aristas de G. Los siguientes
lemas permiten determinar si un grafo dado es euleariano: Lema 1: Un grafo no
dirigido y conexo es euleriano si y sólo si el grado de todo vértice es par.
Lema 2: Un grafo dirigido y fuertemente conexo es euleriano si y sólo si el
grado de todo vértice es cero. Averiguar si un grafo no dirigido y conexo es
euleriano tiene un coste de θ(n), si se supone conocido el grado de cada
vértice; gracias al lema 1 basta con recorrer el conjunto de vértices y
comprobar si el grado de cada uno de ellos es par o no lo es.
Dado G(V,E) no orientado y conexo (sin vértices
aislados). Un camino de Euler es una trayectoria que contiene todas las aristas
de G y recorre cada arista exactamente una vez.
ejemplo de un grafo de camino de Euler.
Ciclo o
circuito de Euler
Es un camino de Euler con la diferencia que empieza y
termina en el mismo vértice es decir es un camino cerrado que recorre
cada arista exactamente una vez. El problema de encontrar dichos caminos fue
discutido por primera vez por Leonard Euler.
Teorema 1. Sea G un grafo o multigrafo no dirigido.
Entonces G tiene un ciclo de Euler si, y solo si, es conexo y todo vértice
tiene grado par. Diremos que es un grafo Euleriano.
Teorema 2. Sea G un grafo o multigrafo no dirigido.
Entonces G tiene un camino de Euler si, y solo si, es conexo y tiene solo dos
vértices de grado impar. Diremos que el grafo es semi-Euleriano.
Ejemplo del grafo Circuito de Euler
Grafos Hamiltonianos.
Definición: Un
circuito o ciclo hamiltoniano es un ciclo simple que contiene todos los
vértices de G. Un circuito hamiltoniano es una trayectoria que empieza y
termina en el mismo vértice y pasa por cada vértice una sola vez.
Teorema 1. Sea G un
grafo conexo con n vértices, donde n≥3. Si la suma de los grados de cada par de
vértices no adyacentes es mayor o igual a n, entonces G tiene un circuito
hamiltoniano.
Teorema 2. Sea
"m" el número de aristas. Sea "n" el número de vértices ⇒ "G" es un circuito hamiltoniano si :
Matriz de
adyacencia
Matriz de adyacencia. Matriz
cuadrada de orden "NxN"
asociada a un grafo de orden N, donde sus filas y
columnas se identifican con los vértices del grafo y en las celdas se indican
la cantidad de aristas (o arcos salientes si es un dígrafo) a los nodos
asignado a la fila y columnas en cuestión.
Definición.
Sea el grafo G=<V,A> de orden N al mismo se
asocia una matriz cuadrada M de NxN tal que:
• A cada
fila se asocia un nodo de V.
• A cada
columna se asocia un nodo de V.
• La
celda Mi,j contiene la cantidad de aristas de A de la forma {i,j} ó (i, j).
Ejemplo.
Dada la relación:
• G=<{0,
1, 2, 3, 4, 5, 6, 7, 8}, ((0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2,
3), (2, 4), (2, 5), (3, 6), (3, 7), (8, 3), (4, 6), (4, 7), (8, 4), (5, 6), (5,
7), (8, 5))>.
la matriz de adyacencia asociada al grafo sería:
N 0 1 2 3 4 5 6 7 8
0 0 0 0 1 1 1 0 0 0
1 0 0 0 1 1 1 0 0 0
2 0 0 0 1 1 1 0 0 0
3 1 1 1 0 0 0 1 1 1
4 1 1 1 0 0 0 1 1 1
5 1 1 1 0 0 0 1 1 1
6 0 0 0 1 1 1 0 0 0
7 0 0 0 1 1 1 0 0 0
8 0 0 0 1 1 1 0 0 0
Ejercicio 1:
En un torneo Nieve venció a los Faisanes una vez, el Rascacielos venció a la Tuna una vez, el Nieve venció al Rascacielos dos veces, los Faisanes vencieron a la tuna una vez y los Faisanes vencieron a Rascacielos una vez. En los ejercicios 1 al 4 use una gráfica para modelar el torneo, los equipos son los vértices. Describa el tipo de grafica usada.
1) Hay una arista entre los equipos si los equipos jugaron.
2) Hay una arista entre los equipos si los equipos para cada juego jugado.
3) Hay una arista del equipo t al equipo j si t venció a j al menos una vez.
4) Hay una arista del equipo t al equipo j para cada victoria de t sobre j.
Respuestas:
1
2
3
4
Ejercicio 2:
Determine el circuito de Euler en el siguiente grafo:
Respuesta:
(f,c)
(f,c,a)
(f,c,a,b)
(f,c,a,b,d)
(f,c,a,b,d,e)
(f,c,a,b,d,e,b)
(f,c,a,b,d,e,b,c)
(f,c,a,b,d,e,b,c,e)
(f,c,a,b,d,e,b,c,e,f)
Ejercicio 3:
Determinar el circuito de Hamilton del siguiente grafo.
Circuito de Hamilton (d,g,c,a,b,e,i,j,h,f,d)
Ejercicio 4:
Del siguiente grafo determinar:
1 ¿Tiene un camino de Euler?
2 ¿Tiene un circuito de Euler?
3 ¿Tiene circuito de Hamilton?
4 Obtener:
a) El conjunto de vértices.
b) El conjunto de aristas.
c) El conjunto de lazos.
d) El conjunto de lados paralelos.
5 Obtener la matriz adyacente.
1.- No tiene camino de Euler porque para poderlo desarrollar, se necesita que sus vértices terminen en valencia impar.
2.- No tiene circuito de Euler porque para poderlo desarrollar se necesita que todos sus vértices terminen en valencia par.
3.- No tiene circuito de Hamilton porque no cumple teorema de Dirac.
4.-
a) V={1,2,3,4,5,6,7,8,9,10}
b) E={a,b,c,d,e,f,g,h,i,j,k,l,m,n,ñ,o,p,q}
c) L={f,p}
d) LP={e,q}
5.-
ejemplo de un grafo de camino de Euler.
En un torneo Nieve venció a los Faisanes una vez, el Rascacielos venció a la Tuna una vez, el Nieve venció al Rascacielos dos veces, los Faisanes vencieron a la tuna una vez y los Faisanes vencieron a Rascacielos una vez. En los ejercicios 1 al 4 use una gráfica para modelar el torneo, los equipos son los vértices. Describa el tipo de grafica usada.
1) Hay una arista entre los equipos si los equipos jugaron.
2) Hay una arista entre los equipos si los equipos para cada juego jugado.
3) Hay una arista del equipo t al equipo j si t venció a j al menos una vez.
4) Hay una arista del equipo t al equipo j para cada victoria de t sobre j.
Respuestas:
1
2
3
4
Ejercicio 2:
Determine el circuito de Euler en el siguiente grafo:
Respuesta:
(f,c)
(f,c,a)
(f,c,a,b)
(f,c,a,b,d)
(f,c,a,b,d,e)
(f,c,a,b,d,e,b)
(f,c,a,b,d,e,b,c)
(f,c,a,b,d,e,b,c,e)
(f,c,a,b,d,e,b,c,e,f)
Ejercicio 3:
Circuito de Hamilton (d,g,c,a,b,e,i,j,h,f,d)
Ejercicio 4:
Del siguiente grafo determinar:1 ¿Tiene un camino de Euler?
2 ¿Tiene un circuito de Euler?
3 ¿Tiene circuito de Hamilton?
4 Obtener:
a) El conjunto de vértices.
b) El conjunto de aristas.
c) El conjunto de lazos.
d) El conjunto de lados paralelos.
5 Obtener la matriz adyacente.
1.- No tiene camino de Euler porque para poderlo desarrollar, se necesita que sus vértices terminen en valencia impar.
2.- No tiene circuito de Euler porque para poderlo desarrollar se necesita que todos sus vértices terminen en valencia par.
3.- No tiene circuito de Hamilton porque no cumple teorema de Dirac.
4.-
a) V={1,2,3,4,5,6,7,8,9,10}
b) E={a,b,c,d,e,f,g,h,i,j,k,l,m,n,ñ,o,p,q}
c) L={f,p}
d) LP={e,q}
5.-