Gráficas Eulerianas y Hamiltonianas

Camino Euleriano

 

 Sea    G    una    gráfica    no    dirigida,    decimos    que    un    camino    es    euleriano    si    y    sólo    si    recorre    toda   la    gráfica    G    pasando    por    cada    una    de    sus    aristas   una    y    sólo    una    vez.   

A continuación, un ejemplo de un camino Euleriano:

Circuito Euleriano

Decimos    que    G    tiene    un    circuito    Euleriano    si    y    sólo    si    tiene    un    camino    euleriano    con   mismo    vértice    inicial    y    final.   

 

A continuación un ejemplo de un circuito Euleriano: 

Proposición1.    

Sea    G    una    gráfica    no    dirigida,    entonces    un    camino    de    Euler    o    camino Euleriano, existe  si todos los vértices    de    la    gráfica    G    tienen grado    o    valencia    par    excepto los vértices    inicial    y    final.   

Camino Hamiltoniano

Definición.    Un    camino    es    Hamiltoniano    si    recorre    todos    los    vértices    de    la    gráfica    G    pasando    una    y    sólo    una    vez    por    cada    vértice.    

A continuación, un ejemplo de cómo se hace una gráfica Hamiltoniana.

Ciclo Hamiltoniano

Definición.    Decimos    que    un    ciclo    es    Hamiltoniano    si    y    sólo    si    es    un    camino    Hamiltoniano    y  el    vértice    inicial    es    igual    al    vértice    final.    

A continuación, un ejemplo de cómo se hace un ciclo Hamiltoniano.

Conexidad.    Gráficas    conexas.

    

Una    gráfica    es    conexa    si    y    sólo    si    hay    un    camino    entre    cualesquiera    dos    vértices    de    la    gráfica.    

Aristo-conectividad

Es    el    mínimo    número    de    aristas    cuya    supresión    desconecta    a    la    gráfica    G    y    se    denota    por    λ(G).    

 Vértice-conectividad

Es    el    mínimo    número    de    vértices    cuya    supresión    desconecta    a    la    gráfica    G    y    se    denota    por    K(G).    

Ejemplo:

Ejercicio:

A continuación les mostraremos 6 gráficas, sobre ellas dibuja  y verifica si son Hamiltonianas, Eulerianas o solo son gráficas.

Ejercicio 2:

Para las siguientes gráficas mueve los puntos de la gráfica de la derecha y comprueba que son isomorfas 


Ejercicio 3:

Para las siguientes gráficas en la casilla correspondiente a aristo-conectividad L(G) y  vértice conectividad K(G), coloque el número necesario para que estas se cumplan, posteriormente, analice su respuesta con la respuesta correcta que se encontrará en la parte de hasta abajo. Respuestas ejercicio 3 = 1-(3)(3) 2-(2)(2) 3-(3)(3)