Teoría de grafos: transitabilidad
Un gráfico es transitable si puede trazar una ruta entre todos los vértices sin volver a trazar la misma ruta. Sobre la base de esta ruta, hay algunas categorías como la ruta de Euler y el circuito de Euler que se describen en este capítulo.
Camino de Euler
Un camino de Euler contiene cada borde de 'G' exactamente una vez y cada vértice de 'G' al menos una vez. Se dice que un gráfico conectado G es transitable si contiene un camino de Euler.
Example
Camino de Euler = dcabde.
Circuito de Euler
En una trayectoria de Euler, si el vértice inicial es el mismo que su vértice final, entonces se llama circuito de Euler.
Example
Euler’s Path = abcdagfeca.
Teorema del circuito de Euler
Un grafo conectado 'G' es transitable si y solo si el número de vértices con grados impares en G es exactamente 2 o 0. Un grafo conectado G puede contener un camino de Euler, pero no un circuito de Euler, si tiene exactamente dos vértices con un grado extraño.
Note - Este camino de Euler comienza con un vértice de grado impar y termina con el otro vértice de grado impar.
Example
Euler’s Path- beabdca no es un circuito de Euler, pero es un camino de Euler. Claramente tiene exactamente 2 vértices de grados impares.
Note - En un gráfico conectado G, si el número de vértices con grado impar = 0, entonces existe el circuito de Euler.
Gráfico hamiltoniano
Se dice que una gráfica conectada G es una gráfica hamiltoniana, si existe un ciclo que contiene todos los vértices de G.
Cada ciclo es un circuito, pero un circuito puede contener varios ciclos. Tal ciclo se llamaHamiltonian cycle de G.
Camino Hamiltoniano
Se dice que una gráfica conectada es hamiltoniana si contiene cada vértice de G exactamente una vez. Tal camino se llamaHamiltonian path.
Example
Hamiltonian Path- edbac.
Note
El circuito de Euler contiene cada borde del gráfico exactamente una vez.
En un ciclo hamiltoniano, se pueden omitir algunos bordes del gráfico.
Example
Eche un vistazo al siguiente gráfico:
Para el gráfico que se muestra arriba:
El camino de Euler existe - falso
El circuito de Euler existe - falso
El ciclo hamiltoniano existe - cierto
El camino hamiltoniano existe - verdadero
G tiene cuatro vértices con grados impares, por lo que no es transitable. Al omitir los bordes internos, el gráfico tiene un ciclo hamiltoniano que pasa por todos los vértices.