Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 69 vistas

    Grafos Eulerianos y Grafos Hamiltonianos

    Cargado por

    Félix Rosendo Ticse Gamarra
    Este documento describe los conceptos de grafos eulerianos y hamiltonianos. Resume lo siguiente: 1) Un grafo euleriano es un grafo conexo que no tiene vértices de grado impar y por lo tanto admite un recorrido que pasa por todas las aristas una sola vez. 2) Un grafo es hamiltoniano si existe un ciclo que recorre todos sus vértices. Los teoremas describen condiciones sobre los grados de los vértices y el número de aristas para que un grafo tenga un circuito hamiltoniano. 3)

    Copyright:

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

    Grafos Eulerianos y Grafos Hamiltonianos

    Cargado por

    Félix Rosendo Ticse Gamarra
    69 vistas10 páginas
    Este documento describe los conceptos de grafos eulerianos y hamiltonianos. Resume lo siguiente: 1) Un grafo euleriano es un grafo conexo que no tiene vértices de grado impar y por lo tanto admite un recorrido que pasa por todas las aristas una sola vez. 2) Un grafo es hamiltoniano si existe un ciclo que recorre todos sus vértices. Los teoremas describen condiciones sobre los grados de los vértices y el número de aristas para que un grafo tenga un circuito hamiltoniano. 3)

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

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

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento describe los conceptos de grafos eulerianos y hamiltonianos. Resume lo siguiente: 1) Un grafo euleriano es un grafo conexo que no tiene vértices de grado impar y por lo tanto admite un recorrido que pasa por todas las aristas una sola vez. 2) Un grafo es hamiltoniano si existe un ciclo que recorre todos sus vértices. Los teoremas describen condiciones sobre los grados de los vértices y el número de aristas para que un grafo tenga un circuito hamiltoniano. 3)

    Copyright:

    © All Rights Reserved
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    69 vistas10 páginas

    Grafos Eulerianos y Grafos Hamiltonianos

    Cargado por

    Félix Rosendo Ticse Gamarra
    Este documento describe los conceptos de grafos eulerianos y hamiltonianos. Resume lo siguiente: 1) Un grafo euleriano es un grafo conexo que no tiene vértices de grado impar y por lo tanto admite un recorrido que pasa por todas las aristas una sola vez. 2) Un grafo es hamiltoniano si existe un ciclo que recorre todos sus vértices. Los teoremas describen condiciones sobre los grados de los vértices y el número de aristas para que un grafo tenga un circuito hamiltoniano. 3)

    Copyright:

    © All Rights Reserved
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    de 10

    GRAFOS EULERIANOS Y

    GRAFOS HAMILTONIANOS
    DOCENTE: ING. DE LA CRUZ ROCCA, MARCO
    INTEGRANTES: SALAZAR ESPINOZA, TATIANA
    TICSE GAMARRA, FELIX
    RECORRIDOS EULERIANOS

    • Representación propuesta por Leonard Euler en 1736:

    2
    RECORRIDOS EULERIANOS

    • A estos circuitos se les llama circuitos eulerianos, y a


    los grafos que los contienen grafos eulerianos
    • Grafo o multígrafo euleriano: admite un recorrido
    que pasa por todas las aristas una sola vez, empezando
    y terminando en el mismo vértice. Los vértices sí se
    pueden repetir

    3
    RECORRIDOS EULERIANOS
    • Ejemplo: Grafo euleriano.

    Circuito euleariano: a,b,c,d,b,f,d,e,a,c,e,f,a


    RECORRIDOS EULERIANOS
    • ¿Cómo saber si un grafo (o multigrafo) es euleriano?
    • Teorema de Euler: Un grafo conexo es euleriano  no tiene vértices de grado impar
    • Ejemplo:

    A tiene grado 3el grafo de los puentes no es euleriano.


    5
    RECORRIDOS EULERIANOS

    • Si el grafo/multigrafo tiene sólo dos vértices de grado impar se llama semi-


    euleriano. Se puede convertir en euleriano añadiéndole una arista:

    Semi-euleriano Euleriano
    6
    Circuitos eulerianos
    Un circuito de Euler (Euleriano) es un circuito que incluye todos los lados - y por lo tanto todos los
    vértices - de un grafo dado una y solo una vez.
    Condiciones para saber si un grafo dado tiene un circuito de Euler.
    1)Si un grafo no dirigido G tiene un circuito de Euler entonces todo vértice de G tiene valencia par,
    demás de ser conexo.
    2) Si G es un grafo no dirigido con vértices {v1, v2, ... , vn} y la suma
    (v1),  (v2), ... ,  (vn) es par, entonces el grafo tiene un circuito de Euler.
    Ejemplo: 
    Verificar si los siguientes grafos no dirigidos tienen un paseo o circuito de Euler.
    RECORRIDO Y CIRCUITO HAMITONOANO

    • Una trayectoria Hamiltoniana para un grafo G es aquella que contiene todos los
    vértices de G una vez.
    • Un circuito Hamiltoniano para un grafo G es un circuito que contiene todos los
    vértices de G una vez.
    G1 G2 G3

    • G1 y G2 poseen circuito de Hamilton pero G3 solo posee trayectoria hamiltoniana


    RECORRIDOS HAMILTONIANOS

    • Un grafo se dice hamiltoniano si existe un ciclo que recorre todos sus


    vértices. Al ciclo se le llama ciclo hamiltoniano
    • Ejemplos:

    9
    TEOREMAS
    Sea G un grafo con n vértices, n>2, sin bucles ni aristas paralelas
    • Teorema1: G posee un circuito hamiltoniano si para cualesquiera dos
    vértices u y v de G que no sean adyacentes, el grado de u más el grado de v
    es mayor o igual que n.
    • Corolario
    G tiene circuito hamiltoniano si cada vértice tiene grado mayor o igual que n/2
    • Teorema 2
    Sea m el número de aristas de G. Entonces G tiene un circuito hamiltoniano si
    m >=1/2(n2-3n+6)

    También podría gustarte