Grafos Dirigidos

Que es?
1. 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
  1. Las aristas son las lineas y los vertices los puntos
  2. 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
1. 1. 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)
2. 1. Terminos para saber
    1. Lados paralelos Vértice lazo Grafo simple
  2. 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
1. En la ciudad de Kaliningrado, antiguamente llamada Königsberg. Habia un río atravesaba la ciudad, dividiendo la zona en varias partes
  1. El juego
    1. 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
    2. Quien la resolvio?
      1. 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
      2. El el mayor matemático Leonhard Euler
        Dio origen
        Estos estudios realizados por Euler fueron el detonante de la teoría de grafos
Resueltos
1. 1. 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
1. 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

Siguiente

Grafos Dirigidos

Descripción

Resumen del Recurso

Recursos multimedia adjuntos

Similar

	Creado por Oscar Eduardo Perez Rodriguez hace casi 5 años