Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 729 vistas

    S6 - 10 - Teoremas de Dirac y Ore - Resized

    Cargado por

    JoseManuelSlater
    Este documento presenta aplicaciones de la teoría de grafos a problemas de la vida real, incluyendo mesas en una cena, colas, y caminos y ciclos hamiltonianos. También introduce los teoremas de Dirac y Ore, los cuales establecen condiciones sobre los grados de los vértices que garantizan la existencia de caminos o ciclos hamiltonianos.

    Copyright:

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

    S6 - 10 - Teoremas de Dirac y Ore - Resized

    Cargado por

    JoseManuelSlater
    729 vistas19 páginas
    Este documento presenta aplicaciones de la teoría de grafos a problemas de la vida real, incluyendo mesas en una cena, colas, y caminos y ciclos hamiltonianos. También introduce los teoremas de Dirac y Ore, los cuales establecen condiciones sobre los grados de los vértices que garantizan la existencia de caminos o ciclos hamiltonianos.

    Descripción original:

    grafos

    Título original

    S6_10_Teoremas de Dirac y Ore_Resized

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento presenta aplicaciones de la teoría de grafos a problemas de la vida real, incluyendo mesas en una cena, colas, y caminos y ciclos hamiltonianos. También introduce los teoremas de Dirac y Ore, los cuales establecen condiciones sobre los grados de los vértices que garantizan la existencia de caminos o ciclos hamiltonianos.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    729 vistas19 páginas

    S6 - 10 - Teoremas de Dirac y Ore - Resized

    Cargado por

    JoseManuelSlater
    Este documento presenta aplicaciones de la teoría de grafos a problemas de la vida real, incluyendo mesas en una cena, colas, y caminos y ciclos hamiltonianos. También introduce los teoremas de Dirac y Ore, los cuales establecen condiciones sobre los grados de los vértices que garantizan la existencia de caminos o ciclos hamiltonianos.

    Copyright:

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

    6.

    10 Teoremas de
    Dirac y Ore

    Aplicaciones de la
    Teora de Grafos
    a la vida real

    Alberto Conejero y Cristina Jordn


    Depto. Matemtica Aplicada
    E.T.S. Ingeniera Informtica
    Universitat Politcnica de Valncia

    Aplicaciones de la Teora de Grafos a la vida real

    Mesas en una cena

    En una cena hay 6 personas. Queremos sentarlas alrededor de una mesa redonda
    de manera que conozcan a las dos personas que tienen al lado.
    Ser posible si cada una de ellas conoce al menos a 3 personas?
    Y si sabemos que se cumple que la suma de las personas que conocen
    dos personas que no se conocen es mayor o igual que 6?
    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Colas

    Supongamos que un grupo de personas coinciden en la entrada de un cine y


    algunos se conocen entre s:
    Ser posible que hagan cola de manera que cada uno de ellos
    conozca al que tiene delante y al que tiene detrs?

    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Hamiltonianos
    Cundo y cmo hallar ciclos/caminos Hamiltonianos?
    Si hay vrtices de grado 2 se simplifica el problema ya que sus aristas adyacentes
    estn en el ciclo Hamiltoniano.
    Si de cada vrtice es adyacente a muchos otros, entonces tambin se puede
    hallar un ciclo Hamiltoniano.

    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Teorema de Dirac
    Dirac (1952).
    Sea G=(V,E) un grafo no dirigido, simple y con al menos 3 vrtices, |V| = n 3.
    Si cada vrtice tiene grado mayor o igual que n/2, entonces G es Hamiltoniano.
    No se puede hallar un ciclo Hamiltoniano en un grafo con slo 2 vrtices aunque se
    cumpla la condicin sobre los grados.

    En cambio en uno con 3 ya s que se puede.

    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Teorema de Dirac
    Dirac (1952).
    Sea G=(V,E) un grafo no dirigido, simple y con al menos 3 vrtices, |V| = n 3.
    Si cada vrtice tiene grado mayor o igual que n/2, entonces G es Hamiltoniano.
    Los siguientes ejemplos muestran cmo la estimacin es bastante precisa.

    C, D y E tienen grado igual a 2< 5/2


    No hay ciclo Hamiltoniano porque
    no se puede acabar en el lado del
    que se empieza.

    Todos tienen grado 3 6/2.


    S que hay un ciclo Hamiltoniano.

    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Teorema de Dirac
    Dirac (1952).
    Sea G=(V,E) un grafo no dirigido, simple y con al menos 3 vrtices, |V| = n 3.
    Si cada vrtice tiene grado mayor o igual que n/2, entonces G es Hamiltoniano.
    Los siguientes ejemplos muestran cmo la estimacin es bastante precisa.

    C, D y E tienen grado igual a 2< 5/2


    No hay ciclo Hamiltoniano porque
    no se puede acabar en el lado del
    que se empieza.

    Todos tienen grado 3 6/2.


    S que hay un ciclo Hamiltoniano.

    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Teorema de Dirac
    Dirac (1952).
    Sea G=(V,E) un grafo no dirigido, simple y con al menos 3 vrtices, |V| = n 3.
    Si cada vrtice tiene grado mayor o igual que n/2, entonces G es Hamiltoniano.
    La condicin es suficiente pero no necesaria como muestra el siguiente ejemplo:

    Es un grafo Hamiltoniano y sin embargo no cumple las hiptesis del teorema.

    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Teorema de Ore
    El Teorema de Dirac se puede deducir como corolario del siguiente resultado.
    Ore (1960).
    Sea G=(V,E) un grafo no dirigido con al menos 3 vrtices, |V| = n 3.
    Si para cada pareja de vrtices no adyacentes x,y se tiene que
    d(x)+d(y) n,
    entonces el grafo es Hamiltoniano.
    Ejemplo:

    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Teorema de Ore
    Ore (1960).
    Sea G=(V,E) un grafo no dirigido con al menos 3 vrtices, |V| = n 3.
    Si para cada pareja de vrtices no adyacentes x,y se tiene que
    d(x)+d(y) n,
    entonces el grafo es Hamiltoniano.
    Las hiptesis no se pueden mejorar:

    La suma de grados de A y B es 4<5


    No hay ciclo Hamiltoniano porque no
    se puede acabar en el lado del que se
    empieza.

    La suma de grados de dos


    vrtices no adyacentes es 6.
    S que hay un ciclo Hamiltoniano.
    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Teorema de Ore
    Ore (1960).
    Sea G=(V,E) un grafo no dirigido con al menos 3 vrtices, |V| = n 3.
    Si para cada pareja de vrtices no adyacentes x,y se tiene que
    d(x)+d(y) n,
    entonces el grafo es Hamiltoniano.
    Las hiptesis no se pueden mejorar:

    La suma de grados de A y B es 4<5


    No hay ciclo Hamiltoniano porque no
    se puede acabar en el lado del que se
    empieza.

    La suma de grados de dos


    vrtices no adyacentes es 6.
    S que hay un ciclo Hamiltoniano.
    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Teorema de Ore
    Ore (1960).
    Sea G=(V,E) un grafo no dirigido con al menos 3 vrtices, |V| = n 3.
    Si para cada pareja de vrtices no adyacentes x,y se tiene que
    d(x)+d(y) n,
    entonces el grafo es Hamiltoniano.
    La condicin es suficiente pero no necesaria como muestra el siguiente ejemplo:

    Es un grafo Hamiltoniano y sin embargo no cumple las hiptesis del teorema.

    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Mesas en una cena

    En este caso los vrtices son las personas y cada arista une a dos personas que se
    conocen entre s.
    La respuesta es afirmativa a ambas preguntas:
    Ser posible si cada una de ellas conoce al menos a 3 personas?

    Y si sabemos que se cumple que la suma de las personas que


    conocen dos personas que no se conocen es mayor o igual que 6?
    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Mesas en una cena

    En este caso los vrtices son las personas y cada arista une a dos personas que se
    conocen entre s.
    La respuesta es afirmativa a ambas preguntas:
    Ser posible si cada una de ellas conoce al menos a 3 personas?

    S, por el Teorema
    de Dirac

    Y si sabemos que se cumple que la suma de las personas que


    conocen dos personas que no se conocen es mayor o igual que 6?

    S, por el Teorema
    de Ore

    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Teorema de Dirac (para caminos)


    Dirac (1952).
    Sea G=(V,E) un grafo no dirigido, simple y con al menos 3 vrtices, |V| = n 3.
    Si cada vrtice tiene grado mayor o igual que (n-1)/2, entonces existe un camino
    Hamiltoniano en G.
    IDEA:

    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Teorema de Dirac (para caminos)


    Dirac (1952).
    Sea G=(V,E) un grafo no dirigido, simple y con al menos 3 vrtices, |V| = n 3.
    Si cada vrtice tiene grado mayor o igual que (n-1)/2, entonces existe un camino
    Hamiltoniano en G.
    IDEA:

    Aadimos un vrtice adicional y lo conectamos con todos los dems, para as poder
    aplicar el Teorema de Dirac.
    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Teorema de Dirac (para caminos)


    Dirac (1952).
    Sea G=(V,E) un grafo no dirigido, simple y con al menos 3 vrtices, |V| = n 3.
    Si cada vrtice tiene grado mayor o igual que (n-1)/2, entonces existe un camino
    Hamiltoniano en G.
    IDEA:

    Aadimos un vrtice adicional y lo conectamos con todos los dems, para as poder
    aplicar el Teorema de Dirac.
    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Teorema de Dirac (para caminos)


    Dirac (1952).
    Sea G=(V,E) un grafo no dirigido, simple y con al menos 3 vrtices, |V| = n 3.
    Si cada vrtice tiene grado mayor o igual que (n-1)/2, entonces existe un camino
    Hamiltoniano en G.
    IDEA:

    Aadimos un vrtice adicional y lo conectamos con todos los dems, para as poder
    aplicar el Teorema de Dirac.
    6.10. Teoremas de Dirac y Ore

    Aplicaciones de la Teora de Grafos a la vida real

    Colas

    La modelizacin es como en los problemas anteriores, los vrtices son las personas
    y cada arista une a dos personas que se conocen entre s.
    Ser posible que hagan cola de manera que cada
    uno de ellos conozca al que tiene delante y al que
    tiene detrs?

    S, a partir del Teorema de


    Dirac porque cada uno
    conoce al menos a dos
    personas
    6.10. Teoremas de Dirac y Ore

    También podría gustarte