Scribd
Cargar
19 vistas6 páginas

Caminos Eulerianos y Hamiltonianos en Grafos

El documento presenta un análisis sobre caminos eulerianos y hamiltonianos en grafos, incluyendo implementaciones en Python. Se define una clase 'Grafo' para manejar la estructura de un grafo y se implementan métodos para verificar la existencia de un camino euleriano y la conectividad del grafo. Además, se utiliza la biblioteca 'networkx' para determinar si existe un camino hamiltoniano en un grafo dado.

Cargado por

rodolfoquijada
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
19 vistas6 páginas

Caminos Eulerianos y Hamiltonianos en Grafos

El documento presenta un análisis sobre caminos eulerianos y hamiltonianos en grafos, incluyendo implementaciones en Python. Se define una clase 'Grafo' para manejar la estructura de un grafo y se implementan métodos para verificar la existencia de un camino euleriano y la conectividad del grafo. Además, se utiliza la biblioteca 'networkx' para determinar si existe un camino hamiltoniano en un grafo dado.

Cargado por

rodolfoquijada
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

República Bolivariana de Venezuela

Ministerio del Poder Popular para la Defensa


Universidad Nacional Experimental Politécnica de la Fuerza Armada Nacional
Bolivariana

Carrera: Ingeniería en Sistemas 5to semestre

Asignatura: Teoría de grafos

Camino euleriano
hamiltoniano

Profesor: Alumno:
Quijada Rodolfo Tovar Isaí CI:19.770.965

Chuao,de enero 2025


Camino euleriano

class Grafo:
def __init__(self):
self.grafo = {}

def agregar_arista(self, u, v):


if u not in self.grafo:
self.grafo[u] = []
if v not in self.grafo:
self.grafo[v] = []
self.grafo[u].append(v)
self.grafo[v].append(u)

def grado(self, vertice):


return len(self.grafo[vertice]) if vertice in self.grafo else 0

def tiene_camino_euleriano(self):
# Contar los vértices con grado impar
contador_impares = sum(1 for vertice in self.grafo if self.grado(vertice) % 2 !=
0)
return contador_impares == 0 or contador_impares == 2

def es_conexo(self):
# Verificar si el grafo es conexo
visitado = set()

def dfs(vertice):
visitado.add(vertice)
for vecino in self.grafo[vertice]:
if vecino not in visitado:
dfs(vecino)

# Encontrar un vértice con grado mayor que 0 para comenzar el DFS


for vertice in self.grafo:
if self.grado(vertice) > 0:
dfs(vertice)
break

# Verificar si todos los vértices con grado mayor que 0 han sido visitados
for vertice in self.grafo:
if self.grado(vertice) > 0 and vertice not in visitado:
return False
return True

# Crear un grafo y agregar aristas


grafo = Grafo()
grafo.agregar_arista(0, 1)
grafo.agregar_arista(1, 2)
grafo.agregar_arista(2, 0)
grafo.agregar_arista(1, 3)
grafo.agregar_arista(3, 4)
grafo.agregar_arista(4, 1)

# Verificar si el grafo tiene un camino euleriano


if grafo.es_conexo() and grafo.tiene_camino_euleriano():
print("El grafo tiene un camino euleriano.")
else:
print("El grafo NO tiene un camino euleriano.")

Camino hamiltoniano
import networkx as nx
import itertools

def es_hamiltoniano(grafo):
# Generar todas las permutaciones de los nodos
nodos = list(grafo.nodes())
for perm in itertools.permutations(nodos):
# Verificar si la permutación es un camino hamiltoniano
if all((perm[i], perm[i+1]) in grafo.edges() for i in range(len(perm) - 1)):
return True, perm
return False, None

# Crear un grafo
grafo = nx.Graph()

# Agregar nodos
grafo.add_nodes_from([1, 2, 3, 4, 5])

# Agregar aristas (conexiones)


grafo.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (2, 4)])

# Verificar si hay un camino hamiltoniano


resultado, camino = es_hamiltoniano(grafo)

if resultado:
print("El grafo tiene un camino hamiltoniano:", camino)
else:
print("El grafo no tiene un camino hamiltoniano.")

También podría gustarte