Temel Kavramlar
Çizge teorisinin omurgası: tanımlar, özel çizgeler, temel teoremler.
G = (V, E)
| Tür | Döngü | Katlı Kiriş |
|---|---|---|
| Basit çizge | ✗ | ✗ |
| Katlı çizge (multigraph) | ✗ | ✓ |
| Pseudograph | ✓ | ✓ |
| Yönlü çizge (digraf) | ✓ | ✗ |
| Yönlü katlı çizge | ✓ | ✓ |
| İşlem | Komşuluk Listesi | Komşuluk Matrisi |
|---|---|---|
| Hafıza | Θ(V+E) | Θ(V²) |
| (u,v) kiriş var mı? | O(deg(u)) | O(1) |
| u'nun tüm komşularını listele | Θ(deg(u)) | Θ(V) |
| Tercih edilir | Seyrek (sparse) çizge | Yoğun (dense) çizge |
Havel-Hakimi Algoritması
BFS — Genişlik Öncelikli Arama
Sözde Kod — BFS
BFS(G, s) for each u ∈ V[G] − {s} color[u] ← WHITE d[u] ← ∞ π[u] ← NIL color[s] ← GRAY d[s] ← 0 Q ← ∅ ENQUEUE(Q, s) while Q ≠ ∅ u ← DEQUEUE(Q) for each v ∈ Adj[u] if color[v] = WHITE color[v] ← GRAY d[v] ← d[u] + 1 π[v] ← u ENQUEUE(Q, v) color[u] ← BLACK // Time: O(V + E)
DFS — Derinlik Öncelikli Arama
Sözde Kod — DFS
DFS(G) for each u ∈ V[G] color[u] ← WHITE π[u] ← NIL time ← 0 for each u ∈ V[G] if color[u] = WHITE DFS-VISIT(u) DFS-VISIT(u) color[u] ← GRAY time ← time + 1; d[u] ← time for each v ∈ Adj[u] if color[v] = WHITE π[v] ← u DFS-VISIT(v) color[u] ← BLACK time ← time + 1; f[u] ← time // Time: O(V + E)
Topolojik Sıralama
Sözde Kod — TOPOLOGICAL-SORT
TOPOLOGICAL-SORT(G) 1. DFS(G) // her v için f[v] hesaplanır 2. Köşeleri f[v] değerinin azalan sırasına göre sırala 3. Sıralı listeyi döndür // Time: Θ(V + E)
Sıralama
Prim Algoritması — Minimum Örten Ağaç
Sözde Kod — MST-PRIM
MST-PRIM(G, w, r) for each u ∈ V[G] key[u] ← ∞ π[u] ← NULL key[r] ← 0 Q ← BuildMinHeap(V, key) while Q ≠ ∅ u ← ExtractMin(Q) for each v ∈ Adj[u] if v ∈ Q and w(u, v) < key[v] π[v] ← u key[v] ← w(u, v) // Time: O(E lg V)
Kruskal Algoritması — Minimum Örten Ağaç
Sözde Kod — MST-KRUSKAL
MST-KRUSKAL(G, w) A ← ∅ for each v ∈ V[G] Make-Set(v) Kirişleri ağırlığa göre artan sırayla sırala for each (u, v) ∈ E // artan ağırlık if Find-Set(u) ≠ Find-Set(v) A ← A ∪ {(u, v)} Union(Find-Set(u), Find-Set(v)) return A // Time: O(E lg E)
Oyun Alanı
Sınav Notu
Karmaşıklık Özeti
| Algoritma | Veri Yapısı | Zaman | Çıktı |
|---|---|---|---|
| BFS | FIFO Queue | O(V+E) | En kısa yol, BFS ağacı |
| DFS | Stack / Recursion | O(V+E) | DFS ormanı, d/f zamanları |
| Topological Sort | DFS (f[v] sırası) | Θ(V+E) | DAG köşe sırası |
| Kruskal | Union-Find | O(E lg E) | Minimum Örten Ağaç |
| Prim | Min-Heap | O(E lg V) | Minimum Örten Ağaç |
Temel Teoremler
Temel Tanımlar
- Cut vertex —
- Bridge —
- Block —
- Spanning tree —
- MST —
- DAG —