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 |