Euler ve Hamilton Yolları/Devreleri
Her kenar 1 kez
Başlangıca dön
Her düğüm 1 kez
P vs NP-Complete
Her KENARDAN tam bir kez geç
✅ Polinom zamanda çözülebilir - O(E)
Her DÜĞÜMDEN tam bir kez geç
⚠️ NP-Complete - Verimli algoritma yok!
Königsberg şehrinde (bugünkü Kaliningrad, Rusya) Pregel Nehri üzerinde 7 köprü vardı. Halk merak ediyordu: "Tüm köprülerden tam bir kez geçerek şehri dolaşmak mümkün mü?"
Leonhard Euler bu problemi analiz etti ve:
Bu analiz, Graf Teorisi'nin doğuşu olarak kabul edilir.
| Koşul | Euler Yolu | Euler Devresi |
|---|---|---|
| Graf bağlı mı? | ✅ Evet (izole düğümler hariç) | ✅ Evet |
| Tek dereceli düğüm sayısı | 0 veya 2 | 0 (tüm düğümler çift dereceli) |
| Başlangıç/Bitiş | 2 tek dereceli varsa: onlardan başla/bitir | Herhangi bir düğümden başla, aynı yere dön |
Bir düğüme her girişte çıkış da gerekir. Eğer düğümün derecesi tek ise:
from collections import defaultdict, deque
class EulerGraph:
"""
Euler yolu ve devresi bulma
Hierholzer algoritması - O(E)
"""
def __init__(self):
self.graph = defaultdict(list)
self.edges_count = 0
def add_edge(self, u, v):
"""Yönsüz kenar ekle"""
self.graph[u].append(v)
self.graph[v].append(u)
self.edges_count += 1
def degree(self, v):
"""Düğümün derecesi"""
return len(self.graph[v])
def is_connected(self):
"""Graf bağlı mı? (BFS ile kontrol)"""
if not self.graph:
return True
# Kenarı olan bir düğümden başla
start = None
for v in self.graph:
if self.degree(v) > 0:
start = v
break
if start is None:
return True
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node in visited:
continue
visited.add(node)
for neighbor in self.graph[node]:
if neighbor not in visited:
queue.append(neighbor)
# Kenarı olan tüm düğümler ziyaret edildi mi?
for v in self.graph:
if self.degree(v) > 0 and v not in visited:
return False
return True
def check_euler(self):
"""
Euler yolu/devresi var mı kontrol et
Returns: (has_path, has_circuit, message, start_node)
"""
if not self.is_connected():
return False, False, "Graf bağlı değil!", None
odd_degree_nodes = []
for v in self.graph:
if self.degree(v) % 2 == 1:
odd_degree_nodes.append(v)
odd_count = len(odd_degree_nodes)
if odd_count == 0:
return True, True, "Euler DEVRESİ var (tüm dereceler çift)", None
elif odd_count == 2:
return True, False, f"Euler YOLU var (tek dereceli: {odd_degree_nodes})", odd_degree_nodes[0]
else:
return False, False, f"Euler yolu YOK ({odd_count} tek dereceli düğüm)", None
def find_euler_path(self):
"""
Hierholzer algoritması ile Euler yolu bul
Returns: (path, message)
"""
has_path, has_circuit, message, start = self.check_euler()
if not has_path:
return None, message
# Çalışma kopyası oluştur
temp_graph = defaultdict(list)
for v in self.graph:
temp_graph[v] = self.graph[v].copy()
# Başlangıç düğümü
if start is None:
start = next(iter(temp_graph))
stack = [start]
path = []
while stack:
v = stack[-1]
if temp_graph[v]:
# Henüz kullanılmamış kenar var
u = temp_graph[v].pop()
temp_graph[u].remove(v) # Yönsüz: karşı kenarı da sil
stack.append(u)
else:
# Tüm kenarlar kullanıldı, yola ekle
path.append(stack.pop())
return path[::-1], message
# ===== DEMO =====
print("=" * 50)
print("EULER YOLU ANALİZİ")
print("=" * 50)
# Örnek 1: Euler devresi olan graf (kare + çapraz)
print("\n📊 Graf 1: Kare + Çapraz")
g1 = EulerGraph()
edges1 = [(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)]
for u, v in edges1:
g1.add_edge(u, v)
print(f"Kenarlar: {edges1}")
print(f"Dereceler: {[g1.degree(v) for v in range(4)]}")
path, msg = g1.find_euler_path()
print(f"Sonuç: {msg}")
if path:
print(f"Euler yolu: {' → '.join(map(str, path))}")
# Örnek 2: Euler yolu olan graf (devre değil)
print("\n" + "-" * 50)
print("\n📊 Graf 2: Üçgen + Kuyruk")
g2 = EulerGraph()
edges2 = [(0, 1), (1, 2), (2, 0), (2, 3)]
for u, v in edges2:
g2.add_edge(u, v)
print(f"Kenarlar: {edges2}")
print(f"Dereceler: 0:{g2.degree(0)}, 1:{g2.degree(1)}, 2:{g2.degree(2)}, 3:{g2.degree(3)}")
path, msg = g2.find_euler_path()
print(f"Sonuç: {msg}")
if path:
print(f"Euler yolu: {' → '.join(map(str, path))}")
# Örnek 3: Euler yolu olmayan graf
print("\n" + "-" * 50)
print("\n📊 Graf 3: Yıldız (merkez + 3 yaprak)")
g3 = EulerGraph()
edges3 = [(0, 1), (0, 2), (0, 3)]
for u, v in edges3:
g3.add_edge(u, v)
print(f"Kenarlar: {edges3}")
print(f"Dereceler: 0:{g3.degree(0)}, 1:{g3.degree(1)}, 2:{g3.degree(2)}, 3:{g3.degree(3)}")
path, msg = g3.find_euler_path()
print(f"Sonuç: {msg}")Belediye çöp kamyonları: Her sokaktan bir kez geçerek tüm çöpleri topla. Euler yolu = minimum tekrar ile maksimum kapsama.
Postacı problemi: Her caddeye uğrayarak mektupları dağıt. Çinli Postacı Problemi bu konseptin genellemesidir.
De Bruijn grafları: k-mer parçalarını birleştirerek genom assembly. Euler yolu ile DNA dizisi oluşturma.
Kalemi kaldırmadan şekil çizme. Çocukluk bulmacaları aslında Euler yolu problemleri!
PCB üzerinde tüm bağlantıları minimum trace ile yapma.
Belediye kar küreme araçları: Her yolu bir kez temizleyerek minimum yakıt tüketimi.
Hamilton yolu/devresi bulma problemi NP-Complete'dir:
P = NP? sorusu: Eğer bu problem polinom zamanda çözülebilirse, bilgisayar biliminin en büyük açık problemlerinden biri çözülmüş olur!
| Varlık Kontrolü | Yol Bulma | |
|---|---|---|
| Euler | O(V) - Derece say | O(E) - Hierholzer |
| Hamilton | NP-Complete | O(n!) veya O(n²2ⁿ) |
def find_hamiltonian_path(graph, n):
"""
Hamilton yolu bul - Backtracking
Karmaşıklık: O(n!) - NP-Complete
Küçük graflar için (n ≤ 15-20)
Args:
graph: Adjacency list {node: [neighbors]}
n: Düğüm sayısı
Returns:
Hamilton yolu varsa liste, yoksa None
"""
def backtrack(path, visited):
# Base case: Tüm düğümler ziyaret edildi
if len(path) == n:
return path.copy()
current = path[-1]
# Mevcut düğümün komşularını dene
for neighbor in graph[current]:
if neighbor not in visited:
# Seç
visited.add(neighbor)
path.append(neighbor)
# Keşfet
result = backtrack(path, visited)
if result:
return result
# Geri al (backtrack)
path.pop()
visited.remove(neighbor)
return None
# Her düğümden başlamayı dene
for start in range(n):
path = [start]
visited = {start}
result = backtrack(path, visited)
if result:
return result
return None
def find_hamiltonian_cycle(graph, n):
"""
Hamilton devresi bul (başlangıca dönmeli)
"""
def backtrack(path, visited):
if len(path) == n:
# Son düğümden başlangıca kenar var mı?
if path[0] in graph[path[-1]]:
return path + [path[0]]
return None
current = path[-1]
for neighbor in graph[current]:
if neighbor not in visited:
visited.add(neighbor)
path.append(neighbor)
result = backtrack(path, visited)
if result:
return result
path.pop()
visited.remove(neighbor)
return None
# Düğüm 0'dan başla (devre olduğu için nereden başladığımız önemli değil)
path = [0]
visited = {0}
return backtrack(path, visited)
# ===== DEMO =====
print("=" * 50)
print("HAMİLTON YOLU ANALİZİ")
print("=" * 50)
# Örnek 1: Pentagon (5 düğümlü döngü)
print("\n📊 Graf 1: Pentagon")
n1 = 5
graph1 = {
0: [1, 4],
1: [0, 2],
2: [1, 3],
3: [2, 4],
4: [3, 0]
}
print("Yapı: 0-1-2-3-4-0 döngüsü")
path = find_hamiltonian_path(graph1, n1)
cycle = find_hamiltonian_cycle(graph1, n1)
print(f"Hamilton Yolu: {' → '.join(map(str, path)) if path else 'YOK'}")
print(f"Hamilton Devresi: {' → '.join(map(str, cycle)) if cycle else 'YOK'}")
# Örnek 2: Tam Graf K4
print("\n" + "-" * 50)
print("\n📊 Graf 2: Tam Graf K4 (4 düğüm, hepsi birbirine bağlı)")
n2 = 4
graph2 = {
0: [1, 2, 3],
1: [0, 2, 3],
2: [0, 1, 3],
3: [0, 1, 2]
}
path2 = find_hamiltonian_path(graph2, n2)
cycle2 = find_hamiltonian_cycle(graph2, n2)
print(f"Hamilton Yolu: {' → '.join(map(str, path2)) if path2 else 'YOK'}")
print(f"Hamilton Devresi: {' → '.join(map(str, cycle2)) if cycle2 else 'YOK'}")
# Örnek 3: Hamilton yolu olmayan graf
print("\n" + "-" * 50)
print("\n📊 Graf 3: Yıldız (Hamilton yolu yok)")
n3 = 5
graph3 = {
0: [1, 2, 3, 4], # Merkez
1: [0],
2: [0],
3: [0],
4: [0]
}
print("Yapı: Merkez (0) + 4 yaprak (1,2,3,4)")
path3 = find_hamiltonian_path(graph3, n3)
cycle3 = find_hamiltonian_cycle(graph3, n3)
print(f"Hamilton Yolu: {' → '.join(map(str, path3)) if path3 else 'YOK'}")
print(f"Hamilton Devresi: {' → '.join(map(str, cycle3)) if cycle3 else 'YOK'}")
print("\n💡 Neden yok? Merkeze her geçişte 1 yaprak ziyaret edilir,")
print(" ama merkez sadece 1 kez geçilebilir!")Tüm şehirleri ziyaret edip başlangıca dön. Hamilton devresi + minimum ağırlık. (Sonraki bölümde detaylı)
Şövalye Turu (Knight's Tour): Satranç atının 64 kareyi de tam 1 kez ziyaret etmesi.
Drone/kurye teslimatı: Her müşteriye tam 1 kez uğra.
Fabrikada iş istasyonları: Her istasyondan 1 kez geçecek şekilde üretim hattı tasarımı.
| Özellik | Euler | Hamilton |
|---|---|---|
| Ne geçilir? | Her kenar 1 kez | Her düğüm 1 kez |
| Varlık kontrolü | Derece sayma - O(V) | NP-Complete |
| Yol bulma | Hierholzer - O(E) | Backtracking - O(n!) |
| Pratik boyut | Milyonlarca kenar | ~20 düğüm (exact) |
| Klasik problem | Königsberg Köprüleri | Gezgin Satıcı (TSP) |