Scribd
Cargar
183 vistas4 páginas

Teoría de Grafos: Caminos y Ciclos

Este documento describe diferentes tipos de caminos en un grafo, incluyendo circuitos eulerianos, caminos eulerianos, circuitos hamiltonianos y componentes conexas. Un circuito euleriano es un camino cerrado que incluye cada arista exactamente una vez. Un grafo es conexo si existe un camino entre cada par de vértices.

Cargado por

Javi Alvarez
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
183 vistas4 páginas

Teoría de Grafos: Caminos y Ciclos

Este documento describe diferentes tipos de caminos en un grafo, incluyendo circuitos eulerianos, caminos eulerianos, circuitos hamiltonianos y componentes conexas. Un circuito euleriano es un camino cerrado que incluye cada arista exactamente una vez. Un grafo es conexo si existe un camino entre cada par de vértices.

Cargado por

Javi Alvarez
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

Caminos o Trayectorias

Si en un grafo simple se van recorriendo sucesivamente sus aristas de modo tal


que dos sucesivas sean adyacentes, es decir que concurran al mismo vèrtice por
el que se pasa de una a la otra, se está recorriendo o determinando una
trayectoria o camino.

Cuando cierta trayectoria comienza y termina en el mismo nodo decimos que es


un circuito. Cuando una trayectoria pasa sólo una vez por todas y cada una de las
aristas o lados se dice que la trayectoria es semi- euleriana, y si esta trayectoria
fuera un circuito se la denomina circuito euleriano. En el problema del ingeniero de
caminos necesitamos saber si hay trayectorias semi-eulerianas y por qué vértices
pueden comenzar y terminar.
Tipos de caminos

Circuito Euler o Euleriano

Leonard Euler – matemático suizo que resolvió el problema de que un grafo


tuviese un solo camino cerrado que contenga a cada una de las aristas.

Por lo tanto, el camino cerrado que contiene exactamente cada una de las aristas
se conoce como circuito de Euler o euleriano.

Si todos los vértices de un grafo conexo tienen valencia o grado par, entonces el
grafo tiene un circuito euleriano. Euler demostró que un grafo que tiene un circuito
euleriano tiene valencia par en todos sus vértices. Si exactamente 2 de los
vértices son impares (y el resto es par) entonces es un camino euleriano.
Camino Hamiltoniano

Un circuito hamiltoniano es un camino cerrado que utiliza cada vértice del grafo
exactamente una vez, exceptuando el último que es igual al primero, o sea

Vértice inicial = vértice terminal

Ejemplo:
Grafo Conexo

Sea G= (V, A) un grafo no dirigido, entonces G es conexo si existe un camino


entre cada par de vértices de G.

Por otra parte, sea G un grafo dirigido, y sea G’ su grafo no dirigido asociado,
entonces si G’ es conexo, G se considera conexo.

La figura muestra un grafo no conexo sin embargo está conformado por dos
partes conexas denominadas componentes conexas.

Circuito o ciclo

Un circuito o ciclo es una trayectoria o camino que empieza y termina en el mismo


vértice y no tiene aristas repetidas. El circuito se llamará simple si no tiene aristas
ni vértices repetidos, excepto el primero y el último. Ejemplo en la figura anterior
de caminos.

También podría gustarte