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)
Restaurante
Secretaria
Bar
Librero
(Gp:) Alan
(Gp:) Beatriz
(Gp:) Carlos
(Gp:) Diana
(Gp:) Secretario
Librero
(Gp:) Restaurante
Secretaria
Bar
Librero
(Gp:) Secretario
(Gp:) Secretaria
Librera
Alan
Beatriz
Carlos
Diana
(Gp:) Alan
(Gp:) Beatriz
(Gp:) Carlos
(Gp:) Diana
(Gp:) Secretario
Librero
(Gp:) Restaurante
Secretaria
Bar
Librero
(Gp:) Secretario
(Gp:) Secretaria
Librera
(Gp:) Restaurante
(Gp:) Secretaria
(Gp:) Bar
(Gp:) Alan
(Gp:) Beatriz
(Gp:) Carlos
(Gp:) Diana
(Gp:) Libreria
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?
(Gp:) Tomas
(Gp:) Susana
(Gp:) Linda
(Gp:) Javier
(Gp:) Daniel
(Gp:) Javier
(Gp:) Linda
(Gp:) Tomas
(Gp:) Susana
(Gp:) Daniel
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?
(Gp:) León
(Gp:) Hurón
(Gp:) Conejo
(Gp:) Hámster
(Gp:) Tigre
(Gp:) León
(Gp:) Tigre
(Gp:) Hámster
(Gp:) Conejo
(Gp:) Hurón
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).
(Gp:) X
(Gp:) Y
(Gp:) Z
(Gp:) U
(Gp:) W
(Gp:) V
V(G)={X, Y, Z, U, V, W}
E(G)={YX, XZ, XW, WU, UV}
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.
(Gp:) X
(Gp:) Y
(Gp:) Z
(Gp:) U
(Gp:) W
(Gp:) V
Orden=6
Tamaño=5
U y V son adjacentes
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.
(Gp:) Barcelona
(Gp:) Sant Cugat
(Gp:) Rubí
(Gp:) 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 e V(G) | vu e 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
(Gp:) Y
(Gp:) X
(Gp:) V
(Gp:) Z
(Gp:) U
(Gp:) 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.
(Gp:) 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
(Gp:) Par
Par
Impar
Par
Impar Vértice Extremo
(Par) Vértice aislado
Ejemplo: Hallar el orden, tamaño y grado de los vértices del siguiente grafo:
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
Página siguiente  |