Question

Que tienen en común los circuitos de euler y de hamilton?

Answer 1

Respuesta:

circuitos de euler

Explicación paso a paso:

Circuito Euler: Sea G un grafo sin vértices aislados. Un circuito que contiene todas las aristas de G recibe el nombre de circuito euleriano.

Un circuito euleriano es una trayectoria que empieza y termina en el mismo vértice

y recorre cada arista exactamente una vez.

Ejemplos:

Imagen

(a) No lo admite porque v4 es un vértice aislado.

(b) No lo admite porque cualquier ciclo utilizará la arista e1 dos veces.

(c) El circuito v1 – v2 – v1 es euleriano.

(d) El circuito v3 – v1 – v2 – v3 es euleriano.

(e) No admite ningún circuito euleriano.

(f) v1 – v2 – v3 – v4 – v2 – v5 – v1 es un circuito euleriano.

Existe un criterio preciso para saber cuando un grafo admite un circuito euleriano.

Este criterio lo proporciona el siguiente teorema.

Teorema. Sea G un grafo. G contiene un circuito euleriano sí y sólo sí:

• G es conexo.

• Cada vértice de G es de grado par.

Ciclo Hamilton: Un ciclo hamiltoniano es un ciclo simple que contiene todos los vértices de G.

Un ciclo hamiltoniano es una trayectoria que empieza y termina en el mismo

vértice y pasa por cada vértice una sola vez.