Zusammenfassung der Ressource
Grafos Dirigidos
- Que es?
- Un grafo dirigido o digrafo
es un tipo de grafo en el
cual las aristas tienen un
sentido definido, a
diferencia del grafo no
dirigido, en el cual las
aristas son relaciones
simétricas y no apuntan en
ningún sentido
- Las aristas son las
lineas y los vertices
los puntos
- Un grafo dirigido (o dígrafo) G
consta de un conjunto V de
vértices y un conjunto E de
lados, tal que e E esta
asociado a un par ordenado
único de vértices v y w y se
escribe e = (v, w)
- Algunos grafos
- En este dígrafo los lados dirigidos están
indicados por flechas. El lado e1 esta
asociado al par ordenado de vértices (v2 ,
v1) por lo que se escribe e1 = (v2 , v1) y el
lado e7 con el par ordenado (v6, v6), por lo
que se escribe e7 = (v6, v6)
- Terminos para saber
- Lados paralelos
Vértice lazo
Grafo simple
- Los dos lados distintos están relacionados con
el mismo par de vértices se llaman lados paralelos,
como e1 y e2 que están asociados con el par no
ordenado de vértices {v1 , v2}. Un lado de la forma
(v, v) que inicia y termina en el mismo vértice se
llama lazo, como ocurre en e3 = (v2, v2). En el grafo
G ningún lado es incidente a v4, un grafo que no
tiene lazos ni lados paralelos recibe el nombre de
grafo simple
- Donde empezo la teoria
- En la ciudad de Kaliningrado, antiguamente llamada
Königsberg. Habia un río atravesaba la ciudad, dividiendo
la zona en varias partes
- El juego
- Dado el mapa de Königsberg, con el río Pregel dividiendo el plano en cuatro
regiones distintas, que están unidas a través de los siete puentes, ¿es
posible dar un paseo comenzando desde cualquiera de estas regiones,
pasando por todos los puentes, recorriendo sólo una vez cada uno, y
regresando al mismo punto de partida
- Quien la resolvio?
- Para poder recorrer un sistema de este tipo, los vértices «intermedios» deben tener un número par de aristas. Es
decir, deben tener una vía para entrar y una vía para salir. Sólo los puntos de inicio y salida pueden tener un número
impar de aristas, porque, evidentemente, nunca «entramos» al punto de inicio y nunca «salimos» del punto de llegada
- El el mayor matemático
Leonhard Euler
- Dio origen
- Estos estudios realizados por Euler fueron el detonante de la teoría de grafos
- Resueltos
- Sea en i) G = (V, E), donde V = {a, b, c, d, e, f, g, h} y E = {e1, e2, e3, e4 .... , e12} Sea en ii) G' = (V', E'), donde V' = {b, c, d, e, f,
g, h} y E' = {e4, e5, e7, e8, e11, e12}, además se tiene que E' E y V' V tal que los lados de E'sean incidentes en los vértice de
V', por lo que G' es un subgrafo de G. Además en iii) G'' = (V'', E''), donde V'' = {a, b, c, d, f, g, h} y E'' = {e1, e2, e3, e6, e9,
e10}, además E'' = E - E' y V''contiene a los vértices con los cuales E'' son incidentes, por lo que G'' es el complemento del
subgrafo de G'
- Solucion de grafo
- Se tiene que: V' = {a, b, c, d, e, f, g, h} y E' =
{e1, e3, e5, e7, e8, e9, e11} y como V'
contiene todos los vértices de G, entonces G'
es un subgrafo generador de G