Fundamentos
Matemáticos IV
David Delgado Gómez
[email protected]
Despacho 321
Historia de la teoría de Grafos




1736: Solución de los puentes de Konigsberg por Euler.
1936: Konig escribe el primer libro sobre teoría de grafos
(en alemán)
1962: Oystein Ore escribe el primer libro en ingles sobre
la teoría de grafos:”Theory of Graphs”.Tambien escribe:
Graphs and Their Uses (1963) y The Four-Color
Problem (1967)
2007: Multiples aplicaciones debido a su relacion con
ciencias de la computacion: optimizacion de redes o
clasificacion de datos.
Ejemplo de Grafo (Matching)
Alan
Beatriz
Carlos
Diana
Alan
Secretario
Librero
Beatriz
Restaurante
Secretaria
Bar
Librero
Restaurante
Secretaria
Bar
Librero
Carlos
Secretario
Diana
Secretaria
Librera
Alan
Beatriz
Secretario
Librero
Restaurante
Alan
Restaurante
Secretaria
Bar
Librero
Carlos
Secretario
Secretaria
Bar
Beatriz
Carlos
Diana
Secretaria
Librera
Libreria
Diana
Ejemplo Grafo (Hamiltoniano)
Tomas, Daniel, Susana, Linda y Javier van a una cena. Se sabe que:
Tomas conoce a Susana y Linda.
Daniel conoce a Susana y Linda.
Javier conoce a Daniel y Linda.
¿Es posible sentarlos en una mesa redonda de forma que personas que
estén sentadas juntas se conozcan?
Daniel
Tomas
Susana
Linda
Daniel
Javier
Susana
Javier
Linda
Tomas
Ejemplo de Grafo (Coloracion)







Imaginemos que tenemos que mover los siguientes
animales de un zoo a otro
León
Conejo
Hámster
Tigre
Hurón
¿Cuál seria el mínimo numero de compartimentos
necesario para poder desplazarlos sin que se coman?
Hámster
León
León
Conejo
Tigre
Hurón
Hurón
Hámster
Conejo
Tigre

Definición: Un grafo G esta formado por un par
de elementos (V,E), donde V es un conjunto de
elementos llamados vértices ( o nodos o puntos)
y E es un conjunto (que puede ser vacío) de
subconjuntos de dos elementos de V llamado
aristas (bordes, ramas o líneas).
U
Z
V
V(G)={X, Y, Z, U, V, W}
Y
E(G)={YX, XZ, XW, WU, UV}
W
X
Definiciones:



El número de vértices se denomina el orden p
de un grafo.
El número de aristas es el tamaño q del grafo.
Dos vértices unidos por una arista se dice que
son adyacentes.
U
Z
V
Y
Orden=6
Tamaño=5
U y V son adjacentes
W
X
Observación: q es menor o igual a p (p-1)/2.
Observación: Durante el curso analizaremos propiedades y aplicaciones de
“grafos”. Multi-grafos y Pseudo-grafos serán tratados únicamente en
momentos puntuales.
Rubí
Sant Cugat
Barcelona
Multi-Grafo
Pseudo-Grafo
Definiciones(2):
Dado un vértice v de un grafo G se define
la vecindad de v, N(v) como
N(v)={u ε V(G) | vu ε E(G)}
 Se define el grado ‘grad(v)’ de un vértice
v como el numero de vecinos que tiene.
 Si G tiene tamaño p entonces
0 ≤ grad(v) < p

Ejemplo: Hallar el orden, tamaño y grado de los vértices del siguiente grafo:
Z
Y
X
V
U
Orden=p=6
Tamaño=q=5
Grad(x)=2
Grad(y)=2
Grad(z)=3
Grad(v)=2
Grad(u)=1
Grad(w)=0
Par
Par
Impar
Par
Impar Vértice Extremo
(Par) Vértice aislado
W
Observación: grad(x)+grad(y)+grad(z)+grad(u)+grad(v)+grad(w)=10= 2q.
Observación: El numero de vértices de grado impar es un numero par.
Teorema. Sea G un grafo de orden p y tamaño q, con V(G)={v1, v2, …, vp}.
Entonces
∑ grad(vi)=2q
Consecuencia. Todo grafo G tiene un numero par de vértices de grado impar
∑ grad(vi) = ∑par grad(vj) + ∑impar grad(vz) =2q
∑impar grad(vz) =2q- ∑par grad(vj)=par
Ejemplo: Si tenemos 20 aristas y queremos construir un grafo donde todos los
vértices tienen grado 4, cuantos vértices debería tener el grafo
∑ grad(vi) =2 q=40
4p=40
p=10
El grafo tendría 10 vértices.
Ejemplo: ¿Es posible que en un grupo de 7 personas cada una conozca
exactamente a 3 del grupo?
∑ grad(vi) =2 q
3*7=2q
21=2q
q=21/2 lo cual es absurdo. Por tanto no es posible
Grafos especiales

Un grafo se dice regular de grado r si todo vértice de G
tiene grado r.
P=4
Regular 0
P=4
Regular 1
P=4
Regular 2
P=4
Regular 3
Observación:
- SI G tiene orden p y es regular de grado r entonces 0 < r < p-1.
- Si G tiene orden p y r es un numero entero puede ocurrir que no existan grafos
regulares para este orden p y grado r.
Por ejemplo p=5 y r =3.(numero impar de vértices impares) (ver Havel-Hakimi)

Un grafo de orden p se dice completo si cada vértice de
G es adyacente a todos los demás. Es decir, es un
grafo regular de grado p-1 y tiene tamaño p (p-1)/2. Se
denotara por Kp
K2
K1
K4
K3
K5

Un grafo G se dice bipartito si V(G) pueden ser
separado en dos conjuntos no vacíos V1 y V2 tales que
todo vértice de G une un vértice de V1 con uno de V2.
X
U
V
U
Y
Z
W
V
X
Z
Y
W

Un grafo G se dice bipartito completo si es bipartito y
cada vértice de V1 es adyacente a todos los de V2. Se
representara por Km,n
V
U
X
Z
Y
Bipartito
W
V
U
X
Z
Y
W
Bipartito completo K2,4
Ejemplo: Dibujar los grafos K5 y K1,5
K5
K1,5
Secuencia de grados
Dado un cierto numero de vértices y sus grados, ¿Cómo decidir si existe un grafo
con ese numero de vértices y con esos grados?
Definición: Dado un grafo G de orden p, la sucesión s=grad(v1), grad(v2), grad(vp)
se denomina sucesión de grados del grafo. Por convenio asumiremos que
grad(v1) ≥ grad(v2) ≥ … ≥ grad(vp)
s=4,4,3,2,2,1
Definición: Decimos que una secuencia de enteros no negativa es grafica
si es la secuencia de grados de algún grafo
La secuencia 4,4,3,2,2,1 es grafica.
Anteriormente vimos que 3,3,3,3,3 no es gráfica.
¿Cómo determinar que una sucesión es grafica?
Para que sea grafica dos condiciones necesarias son:
-grad(vi) ≤ p-1
- ∑ grad(vi) sea par
Sin embargo estas condiciones no son suficientes.
(Es decir si no se cumplen la secuencia no es grafica pero si se
cumplen puede que lo sea puede que no)
Ejemplo: Cinco invitados van a una fiesta. ¿Es posible que cada una de ellas
conozca a un numero diferente de invitados?
Si esto fuese posible se tendría que
s: 0,1,2,3,4
Lo cual es absurdo ya que un invitado no conoce a nadie (grado 0) pero
habría otro de los invitados (grado 4) que si la conocería. Con lo cual esta
secuencia no puede ser grafica. Sin embargo cumple las
dos condiciones necesarias.
Teorema de Havel - Hakimi: Supongamos que tenemos p vértices
con una secuencia de grados s: d1, d2,…, dp de enteros no negativos ,
y sea d1≥ d2 ≥ …. ≥ dp con p ≥ 2 y d1 ≥ 1.
La secuencia s es grafica si y solo si la secuencia
s1: d2-1 , d3 -1, … , d d1+1-1,d d1+2, dd1+3, … , dp
es grafica.
Algoritmo para determinar si una secuencia es grafica
( If ) Si no cumple las dos condiciones necesarias
entonces no es grafica.
( Else ) Si las cumple
(If) Si todos los grados son 0
entonces es grafica.
(Else) Si no
(While) Mientras existan grados distintos de 0 y no haya
elementos negativos.
Aplicar Havel –Hakimi.
Reordenar términos si no están decreciendo.
(If) Si todos los grados son 0
entonces es grafica.
(Else)Si no
entonces no es grafica.
Ejemplo: Determinar si la secuencia 4 4 3 3 2 2 es grafica.
Tiene 6 vértices y todos los grados son menores que 6.
La suma de los grados es 18 que es un numero par
Entonces puede ser grafica
Paso 1: 3 2 2 1 2
Paso 1-Reordenamiento: 3 2 2 2 1
Paso 2: 1 1 1 1
Paso 3: 0 1 1
Paso 3 – Reordenamiento : 1 1 0
Paso 4: 0 0 entonces es grafica
Ejemplo (Continuación): Sabiendo que la sucesión 4 4 3 3 2 2 es grafica,
dibujar un grafo que tenga esta secuencia
Paso 4: 0 0
Paso 3: 0 1 1
Paso 3 – Reordenamiento : 1 1 0
Paso 2: 1 1 1 1
Paso 1: 3 2 2 1 2
Paso 1-Reordenamiento: 3 2 2 2 1
Sucesión: 4 4 3 3 2 2
Ejemplo: Determinar si la secuencia 5 4 3 2 1 1 es grafica.
Tiene 6 vértices y todos los grados son menores que 6.
La suma de los grados es 16 que es un numero par
Entonces puede ser grafica
Paso 1: 3 2 1 0 0
Paso 2: 1 0 -1 0. Entonces no es grafica.
Subgrafos
Definición. Un grafo H es un subgrafo de un grafo G si V(H) están incluidos en
V(G) y E(H) están incluidos en E(G).
Grafo G
Subgrafo G
NO es subgrafo G
Subgrafos especiales
Definición: Un subgrafo H de G se dice recubridor, cobertor o generador
si V(H) = V(G).
Grafo G
Subgrafo
Recubridor
de G
NO es
Subgrafo
Recubridor
de G
NO es
Subgrafo
Recubridor
de G
Se define el subgrafo inducido por un conjunto de vértices S de G
<S>, como el MAXIMO subgrafo de G que tiene los vértices de S.
Grafo G
NO es un subgrafo
inducido por un
subconjunto
de vértices de G
NO es un subgrafo
inducido por un
subconjunto
de vértices de G
SI es un subgrafo
inducido por un
subconjunto
de vértices de G
Se define el subgrafo inducido por un conjunto de aristas X de G
<X>, como el MINIMO subgrafo de G que tiene las aristas en X .
Grafo G
SI es un subgrafo
inducido por un
subconjunto
de aristas de G
NO es un subgrafo
inducido por un
subconjunto
de aristas de G
SI es un subgrafo
inducido por un
subconjunto
de aristas de G
Programación: representación de grafos
Matriz de adyacencia
Definición: Dado un grafo G de orden p y tamaño q con V(G)={v1, v2, …, vp}
se define la matriz de adyacencia A=[aij] de G como la matriz p X p definida por
v1
v3
v4
aij= 1 si vivj pertenece a E(G)
aij=0 si vivj no pertenece a E(G)
v2
v1
v1
0
v2
v6
1
v3
1
v4
0
v5
0
v5
v6
0
v2
v3
1
0
1
0
0
0
1
1
0
1
1
0
v4
0
0
1
0
0
0
v5
v6
0
0
1
0
0
0
0
0
0
0
0
0
Observación: Una matriz de adyacencia es simétrica y la diagonal esta formada
por ceros
Lista de adyacencia
Una matriz de adyacencia necesita p2 posiciones de memoria. Si un grafo tiene pocas
aristas y muchos vértices esto supone un mal uso de la memoria.
v1
v2
2
3
0
2
1
3
0
3
1
2
4
3
0
5
3
0
6
0
v6
v3
v4
1
v5
4
Una lista de adyacencia necesita (p+q)*2 posiciones de memoria
5
0
Tabla de adyacencia
Una forma mas ordenada de presentar la lista de adyacencia es mediante
una tabla de adyacencia. Requiere (p+2q)*2 posiciones de memoria.
1
2
3
0
2
1
3
0
3
1
2
4
3
0
5
3
0
6
0
4
5
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
1
3
1
2
4
5
3
0
7
9
11
15
16
0
8
0
10
0
12
13
14
0
0
0
Isomorfismo de grafos
Los tres grafos tienen p=5, q=6 y s= 3,3,2,2,2
El tercer grafo no es isomorfo por que los vértices de grado 3 están unidos.
El grafo 1 y 2 son isomorfos. Podríamos preferir el grafo 2 si estamos dibujando
un circuito ya que sus aristas no se cruzan.
Definición: Dos grafos G1 y G2 son isomorfos si existe una función biyectiva
f :V(G1)->V(G2)
De forma que si uv pertenece a E(G1) entonces f(u)f(v) pertenece a E(G2).
Observación: Para probar que dos grafos son isomorfos hay que dar el isomorfismo
Para probar que no son isomorfos basta con ver que uno no tiene una
propiedad que el otro tiene y que se conserva bajo el isomorfismo.
Por ejemplo:
Ambos deben tener el mismo numero de vértices.
Ambos deben tener el mismo numero de aristas.
Ambos deben tener la misma secuencia de grados
Grafos no isomorfos de orden 3
Descargar

grado 0