CONCEPTOS FUNDAMENTALES, DEFINICIONES Y EJEMPLOS 1.1 Definición de Grafos, nodos, vértice 1.2 Tipos de grafos 1.2.1 Grafos Direccionales 1.2.2 Grafos no direccionales
M. Ing. Norma Angélica Ochoa Ávila
¿Cuántos colores para iluminar un mapa?
Los siete puentes de Königsberg:
• Un ciudadano de Königsberg (Prusia) se propuso dar un paseo cruzando cada uno de los siete puentes que existensobre el río Pregel una sola vez. Los dos brazos del río rodean a una isla llamada Kneiphof. ¿Cómo debe cruzar los puentes para realizar el paseo?
Los siete puentes de Königsberg
• El problema es simplemente encontrar un trayecto, alrededor de una serie de puentes, que cruce solamente una vez cada uno de ellos. • El mapa a continuación muestra la disposición de siete puentes y dos islas en laciudad de Königsberg
EULER
• En 1736, el matemático suizo radicado en San Petersburgo Leonhard Euler publicó “Solutio Problematis ad Geometriam Situs Pertinentis”, un artículo en el que resolvía el problema en el caso general. Este trabajo es considerado como el nacimiento de la Teoría de Grafos, utilizada hoy en día en múltiples aplicaciones
EULER
• La idea de Euler fue considerar loscuatro lugares terrestres, que se deseaban comunicar (hay 4 de ellos), como puntos de destino y, a los famosos puentes, como trayectorias entre esos puntos. En consecuencia, el mapa de Königsberg –en esencia matemática– puede ser entonces reducido al siguiente diagrama, que es un ejemplo de lo que se suele llamar un grafo
Euler demostró que el problema no tiene solución
?
Grafo(definición)
• Sea V un conjunto finito, no vacío, y sea A ? V x V . El par (V , A) es un grafo, donde V es el conjunto de vértices o nodos y A es su conjunto de aristas. • Escribimos G = ( V, A) para denotar tal grafo • Tenemos dos tipos de grafos: • Digrafos o grafos dirigidos • Grafos que son por definición no dirigidos
Tipos de grafos
Grafos no-dirigidos no•Grafos dirigidos •Grafos de cadenas(chaingraphs) –dirigido y no (chaingraphs) dirigido •Grafo simple –no tiene ciclos ni arcos paralelos •Multigrafo– •Multigrafo–no hay restricciones en el # de arcos entre nodos •Grafo completo –arcos entre cada par de nodos •Grafo bipartita –dos subconjuntos de nodos •Grafo pesado –pesos asociados a nodos y/o arcos
b f
a
EJEMPLO
¿Cómo definiremos entonces este grafo?
e
c
V =(a, b,c, d, e)
d
En Vértices y Aristas por supuesto pero ¿como?
E = {(a ,a), (a, b), (a, c), (b, c), (a, e), (d, e), (d, f), (c, d), (b ,f)}
Grafo dirigido
b f a
c e
d
Dado un grafo G = (V, A) a) se llama a toda arista de la forma (v, v) b) se llaman aristas
bucle
múltiples a las aristas
que aparecen repetidas en A c) se dice que dos vértices son adyacentes si están unidospor una arista d) se dice que dos aristas son adyacentes si tienen un vértice en común,
Incidente
b f a sale del nodo e es incidente hacia a
c e
Adyacente
Entra al nodo a es adyacente hacia e
d
Origen
e es el origen
INCIDENTE ADYACENTE ORIGEN
LAZO Lazo
(a, a)
tipos
e) se dice que un vértice es si no es adyacente a ningún otro vértice.
aislado
f)
se dice que ungrafo es
simple si no tiene bucles
ni aristas múltiples
Grado de un vértice
deg (a) = 5
b f a
deg (b) = 3 deg (c)= 3
e
c
deg (d) = 3
d ¿Qué sucede con el bucle?
deg (f)= 2
b f c
SUBGRAFOS
a f c e f b c d a d e a c d e b a e
d
Grafo??? Subgrafo???
f
2
Grafo regular de grado ??????
3
GRADO.
• En vértices es el numero de aristas que llegan a unvértice • En un grafo dirigido, es la suma de las aristas (de entrada)+ las aristas (de salida) • El grado de un grafo es la suma de los grados de sus vértices.
Grafo completo ¿?
Porque cada par de vértices está unido por una arista
Conexo // disconexo
CAMINO x-y
• Sean x,y vértices ( no necesariamente distintos) de un grafo no dirigido G = (V, A). Un camino x-y en G es una…
