Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 83 vistas

    Teoria de Grafos

    Cargado por

    MariSanch
    El documento resume la historia de la teoría de grafos, comenzando con el problema de los puentes de Königsberg resuelto por Leonhard Euler en 1736. Euler modeló matemáticamente el problema usando un grafo con vértices para las áreas de tierra y aristas para los puentes. Luego, el documento explica conceptos básicos de la teoría de grafos como vértices, aristas, grafos dirigidos y no dirigidos, y el teorema de Euler sobre la existencia de caminos de Euler.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd

    Teoria de Grafos

    Cargado por

    MariSanch
    83 vistas12 páginas
    El documento resume la historia de la teoría de grafos, comenzando con el problema de los puentes de Königsberg resuelto por Leonhard Euler en 1736. Euler modeló matemáticamente el problema usando un grafo con vértices para las áreas de tierra y aristas para los puentes. Luego, el documento explica conceptos básicos de la teoría de grafos como vértices, aristas, grafos dirigidos y no dirigidos, y el teorema de Euler sobre la existencia de caminos de Euler.

    Descripción original:

    matematica discreta , teoría de grafos

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El documento resume la historia de la teoría de grafos, comenzando con el problema de los puentes de Königsberg resuelto por Leonhard Euler en 1736. Euler modeló matemáticamente el problema usando un grafo con vértices para las áreas de tierra y aristas para los puentes. Luego, el documento explica conceptos básicos de la teoría de grafos como vértices, aristas, grafos dirigidos y no dirigidos, y el teorema de Euler sobre la existencia de caminos de Euler.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    83 vistas12 páginas

    Teoria de Grafos

    Cargado por

    MariSanch
    El documento resume la historia de la teoría de grafos, comenzando con el problema de los puentes de Königsberg resuelto por Leonhard Euler en 1736. Euler modeló matemáticamente el problema usando un grafo con vértices para las áreas de tierra y aristas para los puentes. Luego, el documento explica conceptos básicos de la teoría de grafos como vértices, aristas, grafos dirigidos y no dirigidos, y el teorema de Euler sobre la existencia de caminos de Euler.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    Está en la página 1de 12

    Repblica Bolivariana de Venezuela

    Ministerio del Poder Popular Para la Educacin Universitaria


    Universidad Alejandro de Humboldt
    Matemtica Discreta
    Seccin BQN0304II

    Teora de Grafos

    Prof. Leonard Rangel

    Realizado por:
    Snchez Mara CI 21.013.905

    Caracas, Noviembre 2014

    ndice

    Introduccin

    Historia de la Teora de Grafos

    La teora de grafos es una de las ramas ms importantes de las matemticas


    modernas, comenz en el siglo XVIII por una de las mentes ms grandes que ha
    existido. En 1736 el matemtico suizo Leonhard Euler public un artculo llamado
    Solutio Problematis ad Geometrian Situs Pertinentis, que en espaol significa: La
    solucin de un problema referente a la geometra de posicin. En este artculo
    aparece la solucin al famoso problema de los puentes de Knigsberg.
    Knigsberg era un puerto en la antigua Alemania, que actualmente pertenece a
    Rusia y se llama Kaliningrado, situado en la costa sur el mar Bltico, cerca de la
    desembocadura del rio Pregel. El rio divida la ciudad en cuatro reas de tierra
    separadas, y haba siente puentes que le permitan a los habitantes de
    Knigsberg cruzar el rio para poder trasladarse de una parte a otra de la ciudad
    como lo muestra la figura:

    Puente de Knigsberg
    La pregunta que intrigaba a los habitantes de Knigsberg era: ser posible
    caminar por toda la ciudad cruzando cada uno de los siete puentes exactamente
    una vez?
    Cuando Euler se encontr con el problema de los puentes de Knigsberg sus
    habitantes pensaban que no se poda, pero hasta el momento no haba ningn
    argumento que comprobara sus presentimientos.
    La idea de Euler fue bastante sencilla pero genial para su poca. Euler hizo un
    modelo matemtico del problema. Es decir, solo tomo la informacin relevante de

    este y se deshizo de hechos como la longitud de los puentes, o el rea de cada


    regin, y se concentr en la relacin entre las ciudades y los puentes, nombrando
    a cada ciudad como un punto y a cada puente simplemente como una lnea que
    une dos ciudades, de la siguiente manera.

    Esto es lo que se va a conocer como grafo, ciertos puntos unidos con lneas. En
    el caso de los puentes de Knigsberg el grafo despoja de toda informacin
    superflua al problema y convierte la pregunta de sus ciudadanos en la siguiente:
    es posible trazar esta figura sin despegar el lpiz del papel y sin volver a trazar
    ninguna porcin de una lnea?
    Ms adelante se mostrara la respuesta que dio Euler a este problema, antes se
    explicaran algunos conceptos bsicos.
    Grafo
    Un grafo es un conjunto de puntos y un conjunto de lneas donde cada lnea
    une un punto con otro.
    Entonces se llama grafo, G, al par ordenado formado por un conjunto finito no
    vaco, V, y un conjunto, A, de pares no ordenados de elementos del mismo.
    V, es el conjunto de los vrtices o nodos del grafo.
    A, ser el conjunto de las aristas o arcos del grafo.
    La notacin que se utilizar ser: G= (V, A) para designar al grafo cuyos
    conjuntos de vrtices y aristas son, respectivamente, V y A.

    A cualquier arista de un grafo se le puede asociar una pareja de vrtices del


    mismo. Si u y v son dos vrtices de un grafo y la arista a esta asociada con este
    par, escribiremos a= uv.
    Ejemplo, si V= {v1, v2, v3, v4, v5} y A {v1v2, v1v3, v1v4, v2v4, v2v5}
    Entonces el grafo G= (V, A) tiene a v1, v2, v3, v4 y v5 como vrtices y sus aristas
    son v1v2, v1v3, v1v4, v2v4 y v2v5.

    Vrtices adyacentes
    Los vrtices u y v son adyacentes, si existe una arista a tal que a = uv. A los
    vrtices u y v los llamaremos extremos de la arista.
    Representacin grfica
    Un grafo se representa mediante un diagrama en el cual a cada vrtice le
    corresponde un punto y si dos vrtices son adyacentes se unen sus puntos
    correspondientes mediante una lnea.

    Ejemplo:

    Representacin grfica de un grafo.


    El grafo de la figura tiene como conjunto de vrtices V= {v1, v2, v3, v4, v5}
    Siendo su conjunto de aristas A = {v1v2, v2v3, v2v5, v3v4, v3v5}
    Vrtices adyacentes: v1 y v2; v2 y v3; v2 y v4; v4 y v5

    Vrtices no adyacentes: v1 y v3; v1 y v4; v2 y v4, v4 y v5.


    Multgrafos
    Se denomina de esta forma a los grafos en los que haya pares de vrtices
    unidos por ms de una arista.

    Pseudografos
    Se llama Pseudografos a los grafos en los que existen aristas cuyos extremos
    coinciden, es decir, aquellos en los que existen aristas que unan vrtices consigo
    mismos. A tales aristas las llamaremos bucles o lazos.
    Ejemplo:

    Figura (a) representa un multgrafo cuyo conjunto de vrtices es V = {V1, V2,


    V3} y el de aristas A = {v1v2, v1v2, v1v3, v1v3, v2v3}
    Figura (b), representa un Pseudografos cuyo conjunto de vrtices es V= {v1, v2,
    v3} y el de aristas A = {v1v2, v1v3, v2v3, v1v1}
    Figura (c), representa un grafo que es, a un tiempo, pseudo y multgrafo cuyo
    conjunto de vrtices es V = {v1, v2, v3} y que tiene por conjunto de aristas A =
    {v1v2, v1v2, v1v3, v1v3, v2v3, v1v1}
    Dgrafo

    Es un grafo en el cual el conjunto de las aristas A est formado por pares


    ordenados del conjunto de vrtices V. Tambin es conocido como grafo dirigido.
    Es decir es un grafo donde las aristas tienen una orientacin.
    Ejemplo:

    Isomorfismo entre grafos


    Un isomorfismo entre dos grafos G1 = (V1, A1) y G2= (V2, A2) es una
    aplicacin biyectiva entre los conjuntos de vrtices que preserva la adyacencia. Es
    decir, es una aplicacin biyectiva f: V1V2 para lo que se verifica que {a, b} es
    una arista de G1 si y solo si f(a), f (b)} es una arista de G2.
    Dos grafos son isomorfos si existe un isomorfismo entre ellos.
    Ejemplo: determinar si el grafo G1, son o no isomorfos:

    Ambos tienen 6 vrtices y 9 aristas, pero se puede ver que el vrtice 3 de G1


    salen 3 aristas a los vrtices 1,2 y 4, mientras que en el grafo G2 no hay ningn
    vrtice del que salgan 3 artistas ya que de todos salen 2 o 4. En consecuencia el
    vrtice 3 de G1 no puede trasladarse a ningn vrtice de G2 mediante un
    isomorfismo. En otras palabras los grafos no son isomorfos.

    Teorema 1 de la teora de grafos (existencia de trayectorias de Euler):


    1. Si un grafo tiene ms de dos vrtices de grado impar, entonces no puede
    tener una trayectoria de Euler.
    2. Si un grafo conexo tiene exactamente dos vrtices de grado impar,
    entonces tiene por lo menos una trayectoria de Euler. Cualquier trayectoria
    de Euler debe iniciar en uno de los vrtices de grado impar y terminar en el
    otro.
    Una explicacin sencilla de dicho teorema es la siguiente. Euler observo que
    para encontrar una trayectoria en un grafo que cruce una sola vez cada arista es
    necesario que cada vez que la trayectoria tome una arista para llegar a un vrtice,
    debe haber otra arista distinta que permita abandonarlo para poder continuar con
    el recorrido.
    De esta manera si un vrtice tiene grado impar existe una arista ms que llega
    al vrtice que las que salen de el, o viceversa, esto convierte al vrtice en un punto
    final o punto inicial. Por tanto para que exista una trayectoria de Euler es necesario
    que exista a lo ms dos vrtices de grado impar.

    Caminos de un grafo
    Un camino en un grafo es una sucesin finita en las que aparecen
    alternadamente vrtices y aristas de dicho grafo.
    Los extremos son los vrtices iniciales y final del camino.
    La longitud de un camino es el nmero de aristas que contiene.
    Un camino es cerrado si sus extremos coinciden.
    Un camino es simple si en la sucesin de vrtices no hay ninguno repetido.
    Un ciclo es un camino cerrado donde los nicos vrtices repetidos son el
    primero y los ltimos.
    Un circuito es un camino cerrado que no repite aristas.

    Si un grafo existe un camino que conecta dos vrtices distintos, entonces existe
    un camino simple con extremos en dichos vrtices.
    Un grafo es conexo si para cada par de vrtices, existe un camino con extremos
    en dichos vrtices.
    Tipos de caminos
    Camino euleriano: es un camino o circuito que contiene todas las aristas
    apareciendo cada una de ellas exactamente una vez. Un grafo que admite dicho
    circuito se denomina grafo euleriano, y sus vrtices o tiene grado par o dos de los
    vrtices tiene grado impar.
    Camino hamiltoniano: es un camino simple que contiene todos los vrtices
    apareciendo cada uno de ellos exactamente una vez. Un ciclo que a su vez es un
    camino hamiltoniano se denomina ciclo hamiltoniano, y un grafo que contiene un
    ciclo hamiltoniano se denomina grafo hamiltoniano.

    Conclusin

    Referencias bibliogrficas

    Referencias electrnicas
    http://ocw.upm.es/matematica-aplicada/matematicadiscreta/contenidos/material-de-clase/tema-5
    http://www2.uca.es/matematicas/Docencia/ESI/1711003/Apuntes/Lecci
    on14.pdf
    http://www.usergioarboleda.edu.co/matematicas/memorias/memorias1
    4/28.Teor%C3%ADa%20de%20Grafos.pdf
    http://www.academia.edu/7530808/Historia_de_grafos_Los_7_puentes_
    del_r%C3%ADo_Pregel_en_K%C3%B6nigsberg
    http://ma1.eii.us.es/Material/md_ii_Introduccion.pdf

    También podría gustarte