---
title: "Quiz 2 Gözden Geçirme"
subtitle: "Çizge bloğu toplu tekrarı — modelleme ve indirgeme, çizge algoritma haritası, SSSP hiyerarşisi, Johnson, graf değiştirme stratejileri ve dört gerçek sınav problemi"
---
::: {.callout-note title="Oturum bilgisi"}
- **Ku'nun videosu:** [YouTube — Quiz 2 Review](https://www.youtube.com/watch?v=vCIa2h1C9UQ) (≈82 dk)
- **OCW sayfası:** [MIT 6.006 Quiz 2 Review](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/quiz-2-review/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 22 (Quiz 2 Review)
- **Hoca:** Jason Ku
- **Okuma süresi:** ≈28 dk
> Bu **normal bir ders değil** — Quiz 2 öncesi **toplu tekrar** oturumudur (çizge bloğu). Kursun ağırlıklı/ağırlıksız çizge derslerini tek çatı altında toparlar ve sınavda nasıl düşünüleceğini öğretir.
:::
## Bu Quiz Review Ne Hakkında? {#sec-bu-quiz-review-ne-hakkinda-d22}
Bu, Jason Ku ile **Quiz 2 öncesi toplu tekrar** oturumudur. Kursun **çizge bloğunu** (Ders 13-21: iki ağırlıksız + dört ağırlıklı çizge dersi, PS5 + PS6) tek çatı altında toparlar ve **sınavda nasıl düşünüleceğini** öğretir. Quiz 1 materyali "fair game"dir ama vurgu **çizge algoritmalarındadır**. İçerik üç eksende ilerler: (1) çizge algoritma haritası, (2) modelleme + graf-değiştirme stratejileri, (3) dört gerçek sınav problemi çözümü.
> *"there's really a small number of graph algorithms but they can solve a lot of different problems."* — Ku, 1:27
Ku'nun ana mesajı: çizge ünitesi "**indirgeme**" ünitesidir — az sayıda güçlü kara kutu (BFS, DFS, Dijkstra, Bellman-Ford, Johnson) var; iş, problemi doğru bir çizgeye **modelleyip** o kara kutulardan birine indirgemektir.
> *"defining a graph is an important aspect of that problem solving."* — Ku, 9:50
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 22'nin (Quiz 2 Review) kavram haritası: kök = Quiz 2 Review. Beş dal — (1) modelleme ve indirgeme: sözel problemi bir çizgeye çevir (düğüm/kenar/ağırlık/yön tanımla), sonra bilinen kara kutuya indirge, algoritmayı asla modifiye etme. (2) çizge algoritma haritası: erişilebilirlik, full BFS ve DFS ile bağlı bileşen, DAG araçları (topolojik sıra ve çevrim), Bellman-Ford ile negatif çevrim. (3) SSSP hiyerarşisi: BFS sonra DAG relaxation sonra Dijkstra sonra Bellman-Ford — artan genellik. (4) APSP ve Johnson: potansiyel ile yeniden ağırlıklandır, sonra her düğümden Dijkstra. (5) graf değiştirme stratejileri: düğüm çoğaltma ile durum izleme, süpernode ile çok kaynak ya da çok hedef, ön işleme ile filtreleme. Sonuç: Quiz 2 = icat değil modelleme sınavı."
flowchart TD
A["Ders 22: Quiz 2 Review"] --> B["Modelleme ve indirgeme<br/>çizgeye çevir · kara kutuya indirge"]
A --> C["Çizge algoritma haritası"]
C --> C1["erişilebilirlik · full BFS/DFS<br/>DAG araçları · Bellman-Ford"]
A --> D["SSSP hiyerarşisi"]
D --> D1["BFS → DAG → Dijkstra<br/>→ Bellman-Ford"]
A --> E["APSP ve Johnson"]
E --> E1["potansiyel ile yeniden ağırlıklandır<br/>→ V kez Dijkstra"]
A --> F["Graf değiştirme"]
F --> F1["düğüm çoğaltma · süpernode<br/>ön işleme (filtreleme)"]
classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937
classDef branch fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937
classDef leaf fill:#ffffff,stroke:#9ca3af,stroke-width:1px,color:#1f2937
class A root
class B,C,D,E,F branch
class C1,D1,E1,F1 leaf
```
::: {.callout-tip title="Builder Notu — Bu = Çizge Midterm"}
Quiz 2, kursun **çizge bloğu sınavıdır**: erişilebilirlik, bileşenler, topolojik sıralama, SSSP (dört algoritma), APSP/Johnson. Veri yapıları ve sıralama Quiz 1'de kaldı; dinamik programlama Quiz 3'e kalır.
- **Bu = ikinci sınav.** OMSCS CS 6515 (Graduate Algorithms) ekseninde Quiz 2, çizge algoritmaları + indirgeme refleksidir — lisansüstü dersin giriş varsayımı.
- **Modelleme = gerçek dünya refleksi.** "Sözel problemi bir çizgeye çevir" becerisi, lisans sonrası en sık kullanılan algoritmik beceridir.
- **İleriye → graduate algorithms:** "algoritmayı modifiye etme, kara kutuya indirge" disiplini, lisansüstü derste ve gerçek sistemde temeldir.
Tek cümle: *Quiz 2, "yeni çizge algoritması yaz" demez; "problemi doğru bir çizgeye modelle, ne sakladığını ve aradığını net söyle, BFS/Dijkstra/Bellman-Ford/Johnson kara kutusuna indirge, sonra süreyi grafın boyutundan analiz et" der.*
:::
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 22 (Quiz 2 Review, Ku) motoru INLINE.
# Kitap taşınabilir olsun diye _engine.py / _engine_PS6.py / _engine_QR2.py
# içinden GEREKEN her şey buraya GÖMÜLÜR (dosyadan import YOK). Aşağıdaki
# figür hücreleri bu hücrede tanımlanan globalleri (build_blob_example,
# tree_plus_one_shortest, build_atleast_example, dijkstra, ... + COL_*'ı)
# IMPORT ETMEDEN kullanır.
#
# NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama
# backend'ini ezer (plt.show() 0 figür üretir). Quarto render'da jupyter
# inline backend'i ayarlar; yalnız QR2 gerekenler gömülür.
# ============================================================================
from collections import deque
import matplotlib.pyplot as plt
from matplotlib.patches import (
Circle, FancyBboxPatch, FancyArrowPatch,
)
# ---------------------------------------------------------------------------
# _viz.py — Slate+Amber stil sabitleri (HEX birebir)
# ---------------------------------------------------------------------------
COL_PRIMARY = "#374151" # slate-700 — birincil çizgi/çerçeve
COL_ACCENT = "#f59e0b" # amber-500 — vurgu
COL_TEXT = "#1f2937" # slate-800 — metin
COL_BG = "#f3f4f6" # slate-100 — arka plan / kutu dolgusu
COL_AMBER_700 = "#b45309" # bağlantı/okunur kontrast
COL_AMBER_600 = "#d97706" # koyu amber
COL_AMBER_300 = "#fcd34d" # açık amber
COL_AMBER_100 = "#fef3c7" # en açık amber (dolgu)
COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin
COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara
COL_WHITE = "#ffffff"
# ---------------------------------------------------------------------------
# _engine.py — çizge altyapısı (Ders 13-21). Quiz P1-P4 için gerekenler.
# ---------------------------------------------------------------------------
INF = float("inf")
def bfs(adj, s):
"""BFS (L9 §8): kaynaktan katman katman; (delta, parent) döndürür. O(V+E)."""
delta = {s: 0}
parent = {s: None}
queue = deque([s])
while queue:
u = queue.popleft()
for v in adj[u]:
if v not in delta: # henüz görülmemiş
delta[v] = delta[u] + 1
parent[v] = u
queue.append(v)
return delta, parent
def make_undirected(edges):
"""Yönsüz kenar listesi → komşuluk sözlüğü (her kenar iki yönde)."""
adj = {}
for u, v in edges:
adj.setdefault(u, []).append(v)
adj.setdefault(v, []).append(u)
for u in adj:
adj[u] = sorted(adj[u]) # deterministik gezinme
return adj
def connected_components(adj):
"""Yönsüz çizgede bileşen kümeleri (sıralı listeler — deterministik)."""
seen, comps = set(), []
for s in adj:
if s in seen:
continue
comp = {s}
stack = [s]
while stack:
u = stack.pop()
for v in adj[u]:
if v not in comp:
comp.add(v)
stack.append(v)
seen |= comp
comps.append(sorted(comp))
return comps
def relax_edge(d, weight, u, v):
"""Kenar gevşetme (L11 §8): üçgen eşitsizliği ihlali varsa tahmini düşür."""
if d[u] + weight[(u, v)] < d[v]:
d[v] = d[u] + weight[(u, v)]
return True
return False
def dag_relaxation(adj, weight, s, topo_order):
"""DAG relaxation (L11 §10): d=∞, d[s]=0; topolojik sırada gevşet. O(V+E)."""
d = {v: INF for v in adj}
d[s] = 0
for u in topo_order:
for v in adj[u]:
relax_edge(d, weight, u, v)
return d
def _reachable_from(adj, start):
"""start kümesinden erişilebilen düğümler (tanık → −∞ yayma)."""
seen = set(start)
stack = list(start)
while stack:
u = stack.pop()
for v in adj[u]:
if v not in seen:
seen.add(v)
stack.append(v)
return seen
def bellman_ford_classic(adj, weight, s):
"""Klasik Bellman-Ford (L12): V−1 tur kenar gevşetme; V. turda hâlâ
gevşeyen düğümler TANIK → erişilenlere −∞ yay. O(V·E)."""
d = {v: INF for v in adj}
d[s] = 0
n = len(adj)
for _ in range(n - 1): # V−1 tur
for u in adj:
if d[u] == INF:
continue
for v in adj[u]:
relax_edge(d, weight, u, v)
witnesses = set()
for u in adj: # V. tur: tanık tespiti
if d[u] == INF:
continue
for v in adj[u]:
if d[u] + weight[(u, v)] < d[v]:
witnesses.add(v)
for v in _reachable_from(adj, witnesses):
d[v] = -INF
return d
class ChangeablePQ:
"""Değiştirilebilir min-öncelik kuyruğu (L13 §5): binary min-heap +
id→konum sözlüğü. build O(n), delete_min / decrease_key O(log n)."""
def __init__(self, items=()):
self.a = [(k, i) for i, k in items] # (key, id)
self.pos = {item[1]: idx for idx, item in enumerate(self.a)}
for j in range(len(self.a) // 2 - 1, -1, -1): # heapify O(n)
self._sift_down(j)
def __len__(self):
return len(self.a)
def _swap(self, i, j):
self.a[i], self.a[j] = self.a[j], self.a[i]
self.pos[self.a[i][1]] = i
self.pos[self.a[j][1]] = j
def _sift_up(self, j):
while j > 0:
p = (j - 1) // 2
if self.a[p][0] <= self.a[j][0]:
break
self._swap(p, j)
j = p
def _sift_down(self, j):
n = len(self.a)
while True:
l, r, small = 2 * j + 1, 2 * j + 2, j
if l < n and self.a[l][0] < self.a[small][0]:
small = l
if r < n and self.a[r][0] < self.a[small][0]:
small = r
if small == j:
return
self._swap(j, small)
j = small
def delete_min(self):
"""En küçük anahtarlı id'yi çıkar. O(log n)."""
top_key, top_id = self.a[0]
last = self.a.pop()
del self.pos[top_id]
if self.a:
self.a[0] = last
self.pos[last[1]] = 0
self._sift_down(0)
return top_id, top_key
def decrease_key(self, vid, new_key):
"""id'li öğenin anahtarını DÜŞÜR (konumu O(1) bul, yukarı süz)."""
j = self.pos[vid]
assert new_key <= self.a[j][0], "decrease_key yalnız düşürür"
self.a[j] = (new_key, vid)
self._sift_up(j)
def dijkstra(adj, weight, s):
"""Dijkstra (L13 §6): en yakını çıkar, kenarlarını gevşet, decrease_key
ile güncelle. Ağırlıklar ≥ 0 ŞART."""
d = {v: INF for v in adj}
d[s] = 0
Q = ChangeablePQ((v, d[v]) for v in adj)
while len(Q):
u, _ = Q.delete_min()
for v in adj[u]:
if d[u] + weight[(u, v)] < d[v]:
d[v] = d[u] + weight[(u, v)]
Q.decrease_key(v, d[v])
return d
# ---------------------------------------------------------------------------
# _engine_PS6.py — süpernode/sensör mesafesi (D20 PS6 kara kutusu). P3'te
# donut filtreleme aynı kalıba (sensör = donut) indirgenir.
# ---------------------------------------------------------------------------
def nearest_sensor_dist(adj, weight, sensors):
"""Süpernode x → tüm sensörlere 0-ağırlık; x'ten Dijkstra → her düğümün
en yakın sensör mesafesi (PS6, Solomon 31:10)."""
x = ("sensor-super", "*")
adj2 = {x: list(sensors)}
w2 = dict(weight)
for u in adj:
adj2[u] = list(adj[u])
for sn in sensors:
w2[(x, sn)] = 0
d = dijkstra(adj2, w2, x)
return {v: d[v] for v in adj}
# ---------------------------------------------------------------------------
# _engine_QR2.py — P1-P4 problem fonksiyonları + build_*_example (QR2 motoru).
# ---------------------------------------------------------------------------
# --- P1: Blob sayma = bağlı bileşen ---
def grid_to_graph(grid):
"""n×m piksel grid'i çizgeye çevir: '#' = beyaz (blob) piksel; düğüm =
beyaz piksel (r, c); kenar = 4-komşu iki beyaz piksel."""
adj = {}
for r, row in enumerate(grid):
for c, ch in enumerate(row):
if ch != "#":
continue
adj[(r, c)] = []
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
rr, cc = r + dr, c + dc
if 0 <= rr < len(grid) and 0 <= cc < len(grid[rr]) \
and grid[rr][cc] == "#":
adj[(r, c)].append((rr, cc))
return adj
def build_blob_example():
"""QR2 P1 figür örneği: 5×7 grid, elle sayılır 4 blob."""
return ["##..#..",
"#...##.",
"....#..",
".#.....",
"##....#"]
# --- P2: Ağaç + bir kenar (E = V) ---
def find_undirected_cycle(adj):
"""Bağlı yönsüz E=V çizgedeki TEK çevrimi bul (Ku 37:21). BFS yayılma
ağacı; ağaç-dışı kenar (u, v) çevrimi kapatır. O(V)."""
s = next(iter(adj))
parent = {s: None}
queue = deque([s])
extra = None
while queue:
u = queue.popleft()
for v in adj[u]:
if v not in parent:
parent[v] = u
queue.append(v)
elif v != parent[u] and extra is None:
extra = (u, v) # ağaç-dışı kenar (ilk görüş)
u, v = extra
def path_to_root(x):
out = [x]
while parent[out[-1]] is not None:
out.append(parent[out[-1]])
return out
pu, pv = path_to_root(u), path_to_root(v)
su = set(pu)
i = 0
while pv[i] not in su: # son ortak ata
i += 1
m = pv[i]
return pu[:pu.index(m) + 1] + pv[:i][::-1]
def attachment_node(adj, s, cycle):
"""s'in çevrime bağlandığı düğüm s′: BFS mesafesi en küçük çevrim düğümü."""
delta, _ = bfs(adj, s)
return min(cycle, key=lambda v: delta[v])
def tree_path_weight(adj, weight, s, t, banned):
"""'banned' çevrim kenarı silinmiş AĞAÇTA s→t TEK basit yolun ağırlığı."""
ban = {banned, (banned[1], banned[0])}
stack = [(s, None, 0)]
while stack:
u, par, w = stack.pop()
if u == t:
return w
for v in adj[u]:
if v == par or (u, v) in ban:
continue
stack.append((v, u, w + weight[(u, v)]))
return INF
def tree_plus_one_shortest(adj, weight, s, t):
"""QR2 P2: E=V → ağaç + 1 kenar = TAM BİR çevrim. s′'nin İKİ çevrim
kenarını teker teker sil → her silme ağaç → tek basit yol; ikisinin
min'i. Sabit sayıda O(V) tarama → O(V). Döndürür: (mesafe, çevrim, s′)."""
cycle = find_undirected_cycle(adj)
sp = attachment_node(adj, s, cycle)
i = cycle.index(sp)
e1 = (sp, cycle[(i + 1) % len(cycle)])
e2 = (sp, cycle[(i - 1) % len(cycle)])
best = min(tree_path_weight(adj, weight, s, t, e1),
tree_path_weight(adj, weight, s, t, e2))
return best, cycle, sp
def build_tree_plus_one_example():
"""QR2 P2 figür örneği: V = E = 7. Çevrim b-c-d-e; iki aday:
s-a-b-c-d-t = 2+1+4+1+3 = 11 (kısa yay), s-a-b-e-d-t = 2+1+7+2+3 = 15."""
edges = [("s", "a", 2), ("a", "b", 1), ("b", "c", 4), ("c", "d", 1),
("d", "e", 2), ("e", "b", 7), ("d", "t", 3)]
adj = make_undirected([(u, v) for u, v, _ in edges])
weight = {}
for u, v, w in edges:
weight[(u, v)] = w
weight[(v, u)] = w
return adj, weight
# --- P3: Donut süpernode filtreleme ---
def donut_filtered_graph(adj, weight, shops, k):
"""QR2 P3 adım 1-2 (Ku 1:01:30): süpernode → shop'lara 0-ağırlık, TEK
Dijkstra → her düğümün en yakın donut mesafesi; ≤ k düğümleri ÇIKAR."""
nd = nearest_sensor_dist(adj, weight, shops)
sub = {v: [u for u in adj[v] if nd[u] > k] for v in adj if nd[v] > k}
return sub, nd
def donut_safe_shortest(adj, weight, shops, k, p, h):
"""QR2 P3 adım 3: kalan çizgede p→h Dijkstra → O(n log n)."""
sub, nd = donut_filtered_graph(adj, weight, shops, k)
if p not in sub or h not in sub:
return INF, nd
return dijkstra(sub, weight, p)[h], nd
def build_donut_example():
"""QR2 P3 figür örneği: üst koridor p-a-b-c-h (8), alt dolambaç
p-d-e-h (9); donut q, b'ye 2 uzakta → k = 3 ile b YASAK → cevap 9."""
edges = [("p", "a", 2), ("a", "b", 2), ("b", "c", 2), ("c", "h", 2),
("p", "d", 3), ("d", "e", 3), ("e", "h", 3), ("q", "b", 2)]
adj = make_undirected([(u, v) for u, v, _ in edges])
weight = {}
for u, v, w in edges:
weight[(u, v)] = w
weight[(v, u)] = w
return adj, weight, ["q"]
# --- P4: En az V kenarlı en küçük ağırlıklı yol ---
def build_exact_layered_dag(adj, weight, kx):
"""KALMASIZ katmanlı çizge: kalma kenarı YOK → katman i'ye her yol TAM i
kenar. kx+1 katman; (u,i)→(v,i+1) yalnız orijinal kenarlar → DAG."""
adj2, w2 = {}, {}
for i in range(kx + 1):
for v in adj:
adj2[(v, i)] = []
for i in range(kx):
for u in adj:
for v in adj[u]:
adj2[(u, i)].append((v, i + 1))
w2[((u, i), (v, i + 1))] = weight[(u, v)]
return adj2, w2
def exact_k_distances(adj, weight, s, kx):
"""δ₌ₖₓ(s, v): TAM kx kenarlı en hafif walk. Katmanlı DAG + DAG relaxation
(katman sırası = topolojik sıra)."""
adj2, w2 = build_exact_layered_dag(adj, weight, kx)
topo = [(v, i) for i in range(kx + 1) for v in adj]
delta = dag_relaxation(adj2, w2, (s, 0), topo)
return {v: delta[(v, kx)] for v in adj}
def at_least_k_shortest(adj, weight, s, t, kmin=None):
"""QR2 P4: EN AZ kmin (varsayılan V) kenarlı min ağırlıklı s→t walk.
(1) TAM-kmin mesafeler (DAG relaxation); (2) süpernode s* → v kenarı
ağırlık δ₌ₖₘᵢₙ(v); (3) orijinal çizgede s*'den Bellman-Ford → kalan
sonek herhangi walk; negatif çevrim → −∞. O(V³). Döndürür: d_BF[t]."""
if kmin is None:
kmin = len(adj)
dk = exact_k_distances(adj, weight, s, kmin)
star = ("atleast", "*")
adj2 = {star: [v for v in adj if dk[v] < INF]}
for u in adj:
adj2[u] = list(adj[u])
w2 = dict(weight)
for v in adj2[star]:
w2[(star, v)] = dk[v]
return bellman_ford_classic(adj2, w2, star)[t]
def brute_at_least_k(adj, weight, s, t, kmin, kmax):
"""Bağımsız tanık: doğrudan DP — her k için tam-k mesafe tablosu,
min_{kmin ≤ k ≤ kmax} dₖ(t)."""
prev = {v: INF for v in adj}
prev[s] = 0
best = prev[t] if kmin == 0 else INF
for k in range(1, kmax + 1):
cur = {v: INF for v in adj}
for u in adj:
if prev[u] == INF:
continue
for v in adj[u]:
if prev[u] + weight[(u, v)] < cur[v]:
cur[v] = prev[u] + weight[(u, v)]
if k >= kmin and cur[t] < best:
best = cur[t]
prev = cur
return best
def build_atleast_example():
"""QR2 P4 figür örneği (V = 4): doğrudan s→t = 1 (1 kenar — sayılmaz);
pozitif çevrim s→a→b→s. ≥4 kenar zorunluluğu yolu çevrimde tur atmaya
zorlar: s-a-b-s-t = 4 kenar, ağırlık 4."""
adj = {"s": ["a", "t"], "a": ["b", "t"], "b": ["s", "t"], "t": []}
weight = {("s", "a"): 1, ("s", "t"): 1, ("a", "b"): 1, ("a", "t"): 1,
("b", "s"): 1, ("b", "t"): 5}
return adj, weight
def build_atleast_negcycle_example():
"""P4 negatif-çevrim dalı: a⇄b çevrimi −2 → ≥V kenarlı min ağırlık −∞."""
adj = {"s": ["a"], "a": ["b"], "b": ["a", "t"], "t": []}
weight = {("s", "a"): 2, ("a", "b"): -3, ("b", "a"): 1, ("b", "t"): 1}
return adj, weight
```
## 1. Quiz 2 Neyi Ölçer — Modelleme ve İndirgeme {#sec-modelleme-indirgeme}
Sınav, çizge algoritması **icat etmeni** beklemez (onların doğruluğunu derslerde sayfalarca kanıtladık). İki refleks öne çıkar:
- **Modelleme:** sözel problemde çizge *verilmemiş* olabilir — onu **sen tanımlarsın** (düğüm? kenar? ağırlık? yönlü mü?). Önce temiz bir **soyut problem** ifade et: "bu soyut problemi çözebilseydim, sözel problemi kolayca çözerdim."
> *"see if you can state cleanly an abstract problem."* — Ku, 10:54
- **İndirgeme, modifiye etme değil:** verilen algoritmaları *değiştirmeye* çalışma; onları kara kutu olarak kullan. Karmaşıklık, **grafı "bariz-olmayan" yapmaktan** gelir (girdi grafı $\ne$ çözümde kullanacağın graf).
> *"the way in which we introduce complexity into problems is to make the graph non-obvious."* — Ku, 13:19
## 2. Çizge Algoritmaları Haritası {#sec-algoritma-haritasi}
Az algoritma, çok problem. Ana kara kutular:
- **Erişilebilirlik (tek kaynak):** s'den nereye ulaşılır; bir bağlı bileşen, $\le \lvert E \rvert$ düğüm.
- **Full BFS/DFS:** tüm grafı gez, **bağlı bileşenleri** say — $O(V + E)$.
- **DAG araçları:** full DFS ters bitiş sırası $\to$ **topolojik sıralama**; geri kenar $\to$ **çevrim tespiti**.
- **Bellman-Ford:** negatif ağırlıklı çevrim **tespit/bul**.
> *"there's really a small number of graph algorithms but they can solve a lot of different problems."* — Ku, 1:27
## 3. SSSP Hiyerarşisi: BFS → DAG → Dijkstra → Bellman-Ford {#sec-sssp-hiyerarsisi}
Tek-kaynak en kısa yol için, **artan genellik** (azalan kısıt) sırasıyla:
- **BFS** — ağırlıksız; $O(V + E)$.
- **DAG relaxation** — çevrimsiz, *herhangi* ağırlık; $O(V + E)$.
- **Dijkstra** — ağırlık $\ge 0$; $O(V \log V + E)$.
- **Bellman-Ford** — *herhangi* (negatif çevrim dahil); $O(V \cdot E)$.
> *"in general you want to choose an algorithm that's higher on this list but sometimes the algorithms higher on this list don't apply."* — Ku, 5:41
Kritik sınav tuzağı: listede yukarıdakini seç **ama yalnız uygulanabilirse**. Bir DAG değilken DAG relaxation kullanırsan **yanlış** olur (sıfır puan). Sıkışınca, doğru-ama-yavaş Bellman-Ford yaz — yanlış-ama-hızlıdan iyidir.
> *"you'll get more points because it is a correct algorithm than if you apply a faster algorithm that doesn't apply."* — Ku, 6:13
::: {.callout-tip title="Builder Notu — Modelleme = Gerçek-Dünya Refleksi"}
"Sözel problemi bir çizgeye çevir" becerisi sınıf dışında her yerde: bağımlılık çözümü (paket yöneticisi = topolojik sıra), navigasyon (en kısa yol = Dijkstra), sosyal/öneri grafları (BFS ile erişilebilirlik). Quiz 2'nin sana öğrettiği refleks tam olarak budur: önce **düğüm/kenar/ağırlık** tanımla, sonra hangi kara kutunun uygulandığını söyle. "En kısıtlı uygulanabilir algoritmayı seç" disiplini, pratikte performans bilincidir.
:::
## 4. APSP ve Johnson {#sec-apsp-johnson}
Tüm-çiftler en kısa yol: en basiti her düğümden SSSP ($V \times$ Bellman-Ford veya $V \times$ Dijkstra). **Johnson**, negatif ağırlıklı çizgede $V \times$ Bellman-Ford'un yavaşlığından kurtarır: süpernode'dan Bellman-Ford ile potansiyel $h = \delta(s, v)$ bul, kenarları $w' = w + h(u) - h(v)$ ile negatif-olmayana çevir (üçgen eşitsizliği garanti eder, en kısa yollar korunur), $V \times$ Dijkstra çalıştır $\to O(V^2 \log V + V \cdot E)$.
## 5. Graf Değiştirme Stratejileri {#sec-graf-degistirme}
Girdi grafı, çözümde kullanacağın graf olmayabilir. Üç klasik dönüşüm:
- **Düğüm çoğaltma (state):** gezerken bir "durum" izlemek gerekiyorsa, düğümleri çoğalt — her olası durum için ayrı düğüm (örneğin kalan kapasite, kaç adımda bir mola).
> *"you can expand the number of vertices in your graph to keep track of what state I'm in."* — Ku, 13:47
- **Süpernode / yardımcı düğüm:** birçok kaynaktan/hedefe aynı anda aramak için, hepsine kenarlı bir yardımcı düğüm ekle, tek SSSP çalıştır.
> *"adding an auxiliary node... run a single source shortest path algorithm from that super node."* — Ku, 14:30
- **Ön işleme (preprocessing):** bazı kenarları yasakla, yön ver veya grafı filtrele (yasak düğümleri at, çevrimi kır, gereksiz kısmı buda).
::: {.callout-tip title="Builder Notu — Süpernode ve Düğüm Çoğaltma Sistem Örnekleri"}
İki dönüşüm gerçek sistemlerde sürekli görünür:
- **Süpernode** = çok-kaynak/çok-hedef indirgemesi. Bir veri merkezinde "en yakın herhangi bir CDN düğümü" sorusu, tüm CDN düğümlerine sıfır-ağırlıklı bağlı tek yardımcı kaynaktan tek SSSP'ye iner. Bu derste Problem 3 (donut filtreleme) tam olarak bu kalıbı kullanır.
- **Düğüm çoğaltma** = durum-augmentasyonu. Zaman-genişletilmiş çizge (her düğüm × zaman dilimi), mod/kapasite katmanları (her düğüm × kalan yakıt). PS6'da "kaç boş küre taşıyorum" durumu bu şekilde katmanlandı; bu derste Problem 4 (≥V kenarlı yol) katmanlı çizge ile çözülür.
:::
## 6. Sınav Taktiği ve Puan Kaybı {#sec-sinav-taktigi}
- **Önce grafı tanımla.** Sözel problemde graf yoksa, "düğüm = …, kenar = …, ağırlık = …" diye açıkça kur. (En sık puan kaybı: graf tanımlamamak.)
- **Grafı tam belirt:** kaç düğüm/kenar, çevrimsiz mi, ağırlıklar ne. Graderın işini kolaylaştır.
- **Çözdüğün problemi söyle:** "bu grafta en kısa yol / bağlı bileşen / topolojik sıra arıyorum." Yanlış algoritma seçsen bile, doğru *problemi* belirtmek puan getirir.
- **Doğruluk cümlesi:** "yeni graftaki X, orijinal problemdeki Y'ye karşılık gelir."
- **Süreyi analiz et:** grafın boyutu ($V$, $E$) + algoritmanın o boyuttaki süresi. (Unutmak büyük kayıp.)
> *"almost any question in this class can... get 80 to 90 percent of the points by writing maybe three lines."* — Ku, 1:03:03
## Bu Quiz Review'in Özeti {#sec-ozet-d22}
1. **Quiz 2 = çizge bloğu** (Ders 13-21); az algoritma, çok problem; ana iş **modelleme + indirgeme**.
2. **Algoritma haritası**: erişilebilirlik, full BFS/DFS (bileşen), DAG (topolojik/çevrim), Bellman-Ford (negatif çevrim).
3. **SSSP hiyerarşisi**: BFS $\to$ DAG relaxation $\to$ Dijkstra $\to$ Bellman-Ford; yukarıyı seç ama uygulanabilirse.
4. **APSP/Johnson**: potansiyel ile yeniden ağırlıklandır $\to V \times$ Dijkstra $\to O(V^2 \log V + V \cdot E)$.
5. **Graf değiştirme**: düğüm çoğaltma (state), süpernode (çok kaynak/hedef), ön işleme (filtrele/yönlendir).
6. **Taktik**: grafı tanımla + tam belirt + çözdüğün problemi söyle + doğruluk cümlesi + süre analizi.
::: {.callout-important title="Tek Bir Cümle"}
Quiz 2, icat değil **modelleme** sınavıdır: problemi doğru bir çizgeye çevir, ne sakladığını ve aradığını açıkça yaz, BFS/Dijkstra/Bellman-Ford/Johnson kara kutusuna indirge — algoritmayı asla modifiye etme — ve süreyi grafın boyutundan analiz et.
:::
## Quiz-tarzı Problemler {#sec-quiz-problemleri-d22}
Aşağıda dört quiz-tarzı problem var; her birinin çözümünü açmadan önce kendin dene. Her problem aynı reçeteyi izler: **grafı tanımla → kara kutuya indirge → süreyi analiz et**. Tüm sayılar QR2 motoruyla doğrulanmıştır.
@fig-blob-components Problem 1'in modelini gösterir: beyaz pikseller düğüm, 4-komşu beyaz çiftler kenar; blob sayısı = bağlı bileşen sayısı.
```{python}
#| label: fig-blob-components
#| fig-cap: "Blob sayma = bağlı bileşen (QR2 Problem 1, Ku 31:10): n×m beyaz/siyah piksel grid → çizge; düğüm = beyaz piksel (r,c), kenar = 4-komşu beyaz çift. Doğruluk cümlesi: görüntüdeki blob sayısı = bu çizgedeki bağlı bileşen sayısı. SOL panel: 5×7 grid, 11 beyaz piksel dört bileşene göre renkli (amber + üç slate tonu); siyah pikseller açık gri. SAĞ panel: çizge modeli — bileşen başına kesikli hale + numara rozeti; toplam 4 bileşen = 4 blob. Motordan: V = 11 beyaz piksel, nm = 35, bileşenler {(0,0),(0,1),(1,0)}, {(0,4),(1,4),(1,5),(2,4)}, {(3,1),(4,0),(4,1)}, {(4,6)}. E = O(nm) (her piksel en çok 4 komşu) → full BFS/DFS O(nm); girdi nm piksel olduğundan DOĞRUSAL."
#| fig-width: 11.0
#| fig-height: 5.2
# fig-blob-components (QR2 P1): piksel grid + çizge modeli, motordan.
grid = build_blob_example() # 5×7 piksel grid
adj = grid_to_graph(grid) # beyaz piksel → çizge
comps = connected_components(adj) # bağlı bileşenler
n_rows = len(grid) # 5
n_cols = len(grid[0]) # 7
V = len(adj) # beyaz piksel (düğüm) sayısı
n_comp = len(comps) # bileşen (blob) sayısı
nm = n_rows * n_cols # 35
# Her beyaz pikseli ait olduğu bileşen indeksine eşle
pix_to_comp = {}
for ci, comp in enumerate(comps):
for p in comp:
pix_to_comp[p] = ci
# --- motor tanığı: brief gereksinimleri ---
assert n_rows == 5 and n_cols == 7, "grid 5×7 olmalı"
assert n_comp == 4, "tam 4 bileşen beklenir"
assert V == 11, "V=11 beklenir"
COMP_COLORS = [COL_ACCENT, COL_PRIMARY, COL_SLATE_500, COL_AMBER_600]
COMP_FILL = [COL_AMBER_100, "#cbd5e1", "#e2e8f0", "#fde68a"]
COL_BLACK_PIXEL = "#d1d5db" # siyah piksel → açık gri
def comp_color(p):
return COMP_COLORS[pix_to_comp[p] % len(COMP_COLORS)]
def comp_fill(p):
return COMP_FILL[pix_to_comp[p] % len(COMP_FILL)]
fig, (axL, axR) = plt.subplots(1, 2, figsize=(11, 5.2))
fig.patch.set_facecolor(COL_WHITE)
def cell_xy(r, c):
return c, (n_rows - 1 - r)
# === SOL PANEL: piksel grid ===
cw = 1.0
drawn_edges = set()
for (r, c), nbrs in adj.items():
x0, y0 = cell_xy(r, c)
for (rr, cc) in nbrs:
key = frozenset({(r, c), (rr, cc)})
if key in drawn_edges:
continue
drawn_edges.add(key)
x1, y1 = cell_xy(rr, cc)
axL.plot([x0 + cw * 0.5, x1 + cw * 0.5],
[y0 + cw * 0.5, y1 + cw * 0.5],
color=comp_color((r, c)), linewidth=1.6, zorder=2, alpha=0.9)
for r in range(n_rows):
for c in range(n_cols):
x, y = cell_xy(r, c)
is_white = (grid[r][c] == "#")
if is_white:
fc = comp_fill((r, c))
ec = comp_color((r, c))
lw = 2.2
else:
fc = COL_BLACK_PIXEL
ec = COL_SLATE_400
lw = 1.0
axL.add_patch(FancyBboxPatch(
(x + 0.04, y + 0.04), cw * 0.92, cw * 0.92,
boxstyle="square,pad=0.0", fc=fc, ec=ec, linewidth=lw, zorder=3))
if is_white:
axL.text(x + cw * 0.5, y + cw * 0.5, f"{r},{c}",
ha="center", va="center", fontsize=8.5,
color=COL_TEXT, weight="bold", zorder=5)
axL.set_title("Piksel grid (5×7) — beyaz blob pikselleri bileşene göre renkli",
color=COL_TEXT, fontsize=11.5)
axL.set_xlim(-0.3, n_cols + 0.3)
axL.set_ylim(-0.3, n_rows + 0.3)
axL.set_aspect("equal")
axL.axis("off")
# === SAĞ PANEL: çizge modeli ===
node_r = 0.30
for key in drawn_edges:
(a, b) = tuple(key)
xa, ya = cell_xy(*a)
xb, yb = cell_xy(*b)
axR.plot([xa + cw * 0.5, xb + cw * 0.5],
[ya + cw * 0.5, yb + cw * 0.5],
color=comp_color(a), linewidth=2.0, zorder=2, alpha=0.95)
for ci, comp in enumerate(comps):
xs = [cell_xy(*p)[0] + cw * 0.5 for p in comp]
ys = [cell_xy(*p)[1] + cw * 0.5 for p in comp]
cx, cy = sum(xs) / len(xs), sum(ys) / len(ys)
rad = max(((x - cx) ** 2 + (y - cy) ** 2) ** 0.5 for x, y in zip(xs, ys))
rad = max(rad, 0.0) + 0.55
halo = Circle((cx, cy), rad, fill=False, linestyle=(0, (4, 3)),
edgecolor=COMP_COLORS[ci % len(COMP_COLORS)],
linewidth=2.0, zorder=4, alpha=0.9)
axR.add_patch(halo)
bx, by = cx + rad * 0.88, cy + rad * 0.40
axR.add_patch(Circle((bx, by), 0.30, fc=COMP_COLORS[ci % len(COMP_COLORS)],
ec=COL_WHITE, linewidth=1.6, zorder=6))
axR.text(bx, by, str(ci + 1), ha="center", va="center",
fontsize=10.5, color=COL_WHITE, weight="bold", zorder=7)
for (r, c) in adj:
x, y = cell_xy(r, c)
axR.add_patch(Circle((x + cw * 0.5, y + cw * 0.5), node_r,
fc=comp_fill((r, c)), ec=comp_color((r, c)),
linewidth=2.0, zorder=5))
axR.set_title(f"Çizge modeli — blob sayısı = bağlı bileşen sayısı = {n_comp}",
color=COL_TEXT, fontsize=11.5)
axR.text((n_cols) * 0.5, n_rows + 0.55,
"düğüm = beyaz piksel · kenar = 4-komşu beyaz çift",
ha="center", va="center", fontsize=9, color=COL_SLATE_500, style="italic")
axR.set_xlim(-0.9, n_cols + 0.9)
axR.set_ylim(-0.9, n_rows + 1.1)
axR.set_aspect("equal")
axR.axis("off")
fig.text(0.5, 0.015,
f"V = {V} ≤ nm = {nm}; E = O(nm); full BFS/DFS → O(nm) doğrusal.",
ha="center", va="bottom", fontsize=10.5, color=COL_AMBER_700,
weight="bold")
fig.subplots_adjust(left=0.02, right=0.98, top=0.92, bottom=0.08, wspace=0.05)
plt.show()
```
::: {.callout-note collapse="true" title="Problem 1 (Blob sayma — bağlı bileşenler): n×m beyaz/siyah piksel grid; kenar paylaşan iki beyaz piksel aynı blobda. Blob sayısını O(n·m)'de bul."}
**Çözüm.**
"Blob" tanımı transitiftir (a–b, b–c bitişikse a, c aynı blob) $\to$ bu bir **bağlı bileşen** problemidir. Çizge kur: **düğüm = her beyaz piksel** (x,y koordinatıyla kimliklendir); **kenar = bitişik (kenar paylaşan) iki beyaz piksel**. $V \le n \cdot m$, $E \le 4 \cdot n \cdot m$ (her piksel $\le 4$ komşu).
**Doğruluk cümlesi:** görüntüdeki **blob sayısı = bu çizgedeki bağlı bileşen sayısıdır**.
> *"the number of blobs in the image corresponds to the number of connected components in this graph."* — Ku, 31:10
**Full BFS/DFS** ile bağlı bileşenleri say. (Girdi karesel görünse de — $n \cdot m$ piksel — girdi *boyutu* $n \cdot m$ olduğundan bu **doğrusaldır**.)
**Karmaşıklık.** $V = O(n \cdot m)$, $E = O(n \cdot m)$ $\to$ full BFS/DFS **$O(n \cdot m)$**.
:::
@fig-tree-plus-one Problem 2'nin imza fikrini gösterir: $E = V$ olduğunda çizge ağaç + bir kenardır (tam bir çevrim); s′'nin iki çevrim kenarını teker teker silerek iki aday yol elde edilir.
```{python}
#| label: fig-tree-plus-one
#| fig-cap: "Ağaç + bir kenar (QR2 Problem 2, İMZA figür, Ku 37:21): bağlı yönsüz çizge, pozitif ağırlık, E = V → ağaç (V−1 kenar) + bir fazladan kenar = TAM BİR çevrim. Çevrim b-c-d-e (motordan); s kuyruğu s-a-b, t kuyruğu d-t. s′ = b (s'in çevrime bağlandığı düğüm). İmza fikir: s′'nin iki çevrim kenarını (b-c ve b-e) teker teker sil → her silme çevrimi kırar → ağaç → tek basit yol; iki adayın min'i. KAZANAN kısa yay s-a-b-c-d-t = 2+1+4+1+3 = 11 (amber); kaybeden uzun yay s-a-b-e-d-t = 2+1+7+2+3 = 15 (kesikli slate). Dijkstra çapraz tanık = 11 (sağ alt). Sabit sayıda O(V) tarama → O(V)."
#| fig-width: 11.0
#| fig-height: 6.5
# fig-tree-plus-one (QR2 P2 İMZA): ağaç + 1 kenar, motordan.
_t2_adj, _t2_w = build_tree_plus_one_example()
_t2_best, _t2_cycle, _t2_sp = tree_plus_one_shortest(_t2_adj, _t2_w, "s", "t")
_t2_cross = dijkstra(_t2_adj, _t2_w, "s")["t"] # çapraz tanık
def _t2_path_w(path):
return sum(_t2_w[(path[i], path[i + 1])] for i in range(len(path) - 1))
_t2_short = ["s", "a", "b", "c", "d", "t"]
_t2_long = ["s", "a", "b", "e", "d", "t"]
_t2_sw = _t2_path_w(_t2_short)
_t2_lw = _t2_path_w(_t2_long)
assert _t2_best == 11, _t2_best
assert _t2_best == _t2_sw == _t2_cross, (_t2_best, _t2_sw, _t2_cross)
assert _t2_lw == 15, _t2_lw
assert set(_t2_cycle) == {"b", "c", "d", "e"}, _t2_cycle
assert _t2_sp == "b", _t2_sp
_t2_pos = {
"s": (0.0, 0.0), "a": (1.6, 0.0), "b": (3.2, 0.0),
"c": (4.7, 1.25), "e": (4.7, -1.25), "d": (6.2, 0.0), "t": (7.9, 0.0),
}
fig, ax = plt.subplots(figsize=(11, 6.5))
fig.patch.set_facecolor(COL_WHITE)
_T2_R = 0.34
def _t2_node(name, hot_badge=False):
x, y = _t2_pos[name]
fc = COL_AMBER_100 if hot_badge else COL_BG
ec = COL_ACCENT if hot_badge else COL_PRIMARY
ax.add_patch(Circle((x, y), _T2_R, fc=fc, ec=ec,
linewidth=2.8 if hot_badge else 2.0, zorder=6))
ax.text(x, y, name, ha="center", va="center", fontsize=13,
color=COL_TEXT, weight="bold", zorder=7)
def _t2_shrink(p, q, r=_T2_R):
import math
dx, dy = q[0] - p[0], q[1] - p[1]
L = math.hypot(dx, dy)
return (p[0] + dx / L * r, p[1] + dy / L * r)
def _t2_edge(u, v, color, lw, ls="-", rad=0.0, z=2, alpha=1.0):
p, q = _t2_pos[u], _t2_pos[v]
p2 = _t2_shrink(p, q)
q2 = _t2_shrink(q, p)
ax.add_patch(FancyArrowPatch(
p2, q2, arrowstyle="-", linewidth=lw, color=color,
linestyle=ls, zorder=z, alpha=alpha,
connectionstyle=f"arc3,rad={rad}"))
def _t2_wlabel(u, v, dx=0.0, dy=0.0, color=COL_TEXT):
p, q = _t2_pos[u], _t2_pos[v]
mx, my = (p[0] + q[0]) / 2 + dx, (p[1] + q[1]) / 2 + dy
ww = _t2_w[(u, v)]
ax.text(mx, my, str(ww), ha="center", va="center", fontsize=11.5,
color=color, weight="bold", zorder=8,
bbox=dict(boxstyle="round,pad=0.16", fc=COL_WHITE,
ec=color, lw=1.1, alpha=0.95))
# çevrim kenarları (kalın amber)
for u, v in [("b", "c"), ("c", "d"), ("d", "e"), ("e", "b")]:
_t2_edge(u, v, COL_ACCENT, 5.0, z=3)
# kuyruk kenarları (slate)
for u, v in [("s", "a"), ("a", "b"), ("d", "t")]:
_t2_edge(u, v, COL_SLATE_500, 2.6, z=2)
# KAZANAN yol (kısa yay)
for u, v in [("s", "a"), ("a", "b"), ("b", "c"), ("c", "d"), ("d", "t")]:
_t2_edge(u, v, COL_AMBER_700, 7.5, z=1, alpha=0.30)
# KAYBEDEN yol (uzun yay)
for u, v in [("s", "a"), ("a", "b"), ("b", "e"), ("e", "d"), ("d", "t")]:
_t2_edge(u, v, COL_SLATE_400, 4.5, ls="--", z=0, alpha=0.55)
_t2_wlabel("s", "a", dy=0.26)
_t2_wlabel("a", "b", dy=0.26)
_t2_wlabel("b", "c", dx=-0.30, dy=0.18)
_t2_wlabel("c", "d", dx=0.30, dy=0.18)
_t2_wlabel("d", "e", dx=0.30, dy=-0.18)
_t2_wlabel("e", "b", dx=-0.30, dy=-0.18)
_t2_wlabel("d", "t", dy=0.26)
for name in _t2_pos:
_t2_node(name, hot_badge=(name == _t2_sp))
_t2_bx, _t2_by = _t2_pos[_t2_sp]
ax.text(_t2_bx - 0.55, _t2_by - 1.05, "s′ = çevrime giriş", ha="center",
va="center", fontsize=10.5, color=COL_AMBER_700, weight="bold", zorder=9,
bbox=dict(boxstyle="round,pad=0.30", fc=COL_AMBER_100,
ec=COL_ACCENT, lw=1.8))
def _t2_scissors(u, v, t=0.32):
p, q = _t2_pos[u], _t2_pos[v]
mx = p[0] + (q[0] - p[0]) * t
my = p[1] + (q[1] - p[1]) * t
s = 0.15
ax.plot([mx - s, mx + s], [my - s, my + s], color="#b91c1c", lw=3.0,
zorder=10, solid_capstyle="round")
ax.plot([mx - s, mx + s], [my + s, my - s], color="#b91c1c", lw=3.0,
zorder=10, solid_capstyle="round")
_t2_scissors("b", "c")
_t2_scissors("b", "e")
ax.text(_t2_pos["b"][0] + 0.55, _t2_pos["b"][1] + 1.55,
"✂ teker teker sil → ağaç → tek yol",
ha="left", va="center", fontsize=10.5, color="#b91c1c",
weight="bold", zorder=11)
ax.text(4.7, 2.55, "KAZANAN: s-a-b-c-d-t = 2+1+4+1+3 = %d" % _t2_sw,
ha="center", va="center", fontsize=12, color=COL_AMBER_700,
weight="bold", zorder=11,
bbox=dict(boxstyle="round,pad=0.40", fc=COL_AMBER_100,
ec=COL_ACCENT, lw=2.4))
ax.text(3.95, -2.55, "uzun yay: s-a-b-e-d-t = 2+1+7+2+3 = %d" % _t2_lw,
ha="center", va="center", fontsize=11.5, color=COL_SLATE_500,
weight="bold", zorder=11,
bbox=dict(boxstyle="round,pad=0.36", fc=COL_BG,
ec=COL_SLATE_400, lw=1.8, linestyle="--"))
ax.text(3.95, 3.35,
"Ağaç + 1 kenar (E = V): tek çevrim → s′'nin iki çevrim kenarını "
"teker teker sil → her seferinde ağaç",
ha="center", va="center", fontsize=12.5, color=COL_TEXT, weight="bold")
ax.text(3.95, -3.45,
"E = V → TAM bir çevrim (Ku 37:21). s′'nin 2 çevrim kenarı için "
"sabit sayıda O(V) tarama → toplam O(V).",
ha="center", va="center", fontsize=11, color=COL_SLATE_500,
style="italic")
ax.text(7.9, -2.50, "çapraz tanık:\nDijkstra(s)[t] = %d" % _t2_cross,
ha="center", va="center", fontsize=9.5, color=COL_PRIMARY, zorder=11,
bbox=dict(boxstyle="round,pad=0.28", fc=COL_WHITE,
ec=COL_PRIMARY, lw=1.4))
ax.set_xlim(-0.9, 9.0)
ax.set_ylim(-4.0, 3.8)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
::: {.callout-note collapse="true" title="Problem 2 (Ağaç + bir kenar): bağlı yönsüz çizge, pozitif ağırlık, E = V. s→t en kısa yolu O(V)'de bul."}
**Çözüm.**
$E = V$ gözlemi kilit: bir ağaç $V - 1$ kenarlıdır, demek ki bu çizge **ağaç + bir fazladan kenar** = tam olarak **bir çevrim** içerir.
> *"this graph is a tree plus an extra edge."* — Ku, 37:21
Pozitif ağırlık $\to$ en kısa yollar basit. Çevrim yoksa (ağaçta) iki düğüm arasında **tek** basit yol vardır $\to$ ağırlıksız erişilebilirlik (BFS/DFS) ağacı o yolu verir. Çevrim varsa s→t için **iki** olası basit yol (çevrimin iki yarısı). Algoritma: BFS/DFS ile bir yayılma ağacı kur; ağaçta olmayan kenar $(u, v)$ çevrimi belirler; s'ten u ve v'ye yolların **son ortak düğümü** s′ (çevrimde s'e en yakın). s′'nin çevrim kenarlarını teker teker kaldırıp her seferinde s→t erişilebilirliğini çalıştır, en kısasını seç. Sabit sayıda ($\le$ derece) BFS/DFS.
**Karmaşıklık.** Sabit sayıda $O(V)$ erişilebilirlik araması + ön-ek bulma $O(V)$ $\to$ **$O(V)$**.
:::
Problem 3'ün figürü yoktur — süpernode kalıbı, [PS6'daki sensör problemi](20-problem-oturumu-6.qmd#sec-problem-3-d20) görselinde zaten ayrıntılı görselleştirildi (donut shop = sensör, aynı süpernode + tek Dijkstra şeması). Aşağıda doğrudan çözüme geçiyoruz.
::: {.callout-note collapse="true" title="Problem 3 (Donut — süpernode filtreleme): n konum, derece ≤ 5, d donut shop, mesafe k. p→h, donut'a k'dan yakın olmayan en kısa yol, O(n log n)."}
**Çözüm.**
Çizge: düğüm = konum (n tane), kenar = yol (ağırlık = pozitif sürüş mesafesi); derece $\le 5$ $\to E = O(n)$. Bir donut'a $\le k$ mesafedeki *her* düğüm yasaktır. d donut'tan teker teker Dijkstra $O(d \cdot n \log n)$ — d sınırsız, yavaş. **Süpernode** ile paralelleştir.
> *"filter forbidden vertices by using supernode plus one run of Dijkstra."* — Ku, 1:01:30
(1) Süpernode x $\to$ tüm donut shop'lara 0-ağırlıklı kenar; x'ten **tek Dijkstra** $\to$ her düğümün en yakın donut mesafesi ($O(n \log n)$). (2) Mesafesi $\le k$ olan düğümleri **çıkar** (filtrele). (3) Kalan grafta p→h Dijkstra $\to$ istenen en kısa yol. (Genelleme: her donut farklı yarıçap $\to$ giriş kenar ağırlığını maks_yarıçap − yarıçap yap.)
Bu, [PS6'daki sensör problemiyle](20-problem-oturumu-6.qmd#sec-problem-3-d20) **aynı kara kutudur** — orada "her an sensörlerden $\ge k$ uzakta kal", burada "donut'lardan $> k$ uzakta kal". Motorda da `nearest_sensor_dist` aynen yeniden kullanılır: bu derste deterministik örnek (donut q, b'ye 2 uzakta; $k = 3$ ile b yasak) en yakın mesafeleri a=4, c=4, p=6, h=6, d=9, e=9 verir; üst koridor 8 kapanır $\to$ alt dolambaç **9**. $k = 1$ ile b serbest (2 > 1) $\to$ üst koridor açılır $\to$ **8**.
**Karmaşıklık.** İki Dijkstra + filtreleme $\to$ **$O(n \log n)$**.
:::
@fig-atleast-v-layers Problem 4'ün üç adımını gösterir: orijinal çizgede kısa yolun neden geçersiz olduğu, kalmasız katmanlı DAG ve süpernode + Bellman-Ford soneki.
```{python}
#| label: fig-atleast-v-layers
#| fig-cap: "En az V kenarlı en küçük ağırlıklı yol (QR2 Problem 4, Ku): yönlü, keyfi ağırlık; en az V kenarlı en küçük ağırlıklı s→t yolu. SOL panel: orijinal çizge (V=4); doğrudan s→t ağırlık 1 ama yalnız 1 kenar < V → GEÇERSİZ (kesikli kırmızı + yasak işareti); pozitif çevrim s→a→b→s yolu tur atmaya zorlar. ORTA panel: kalmasız katmanlı DAG (k=0..4, kalma kenarı YOK) → katman 4 = TAM 4 kenar; optimal s₀→a₁→b₂→s₃→t₄ (amber rota, ağırlık 4). SAĞ panel: süpernode s* → δ₌₄ sonlu düğümler (a=4, t=4; s ve b sonsuz) + orijinal çizgede Bellman-Ford soneki → cevap = 4. Motordan: δ₌₄ = {s sonsuz, a=4, b sonsuz, t=4}, optimal yol s→a→b→s→t (tam 4 kenar, ağırlık 4); doğrudan s→t (ağırlık 1) tek kenar olduğu için geçersiz. Negatif çevrim varyantında (a ile b arası çift −2) cevap −∞; brute kmax 16→32 hâlâ düşer (−12→−28), iraksamanın sayısal izi."
#| fig-width: 12.5
#| fig-height: 6.0
# fig-atleast-v-layers (QR2 P4): ≥V kenar zorunluluğu, motordan.
_p4_adj, _p4_w = build_atleast_example()
_p4_V = len(_p4_adj) # = 4
_p4_dk = exact_k_distances(_p4_adj, _p4_w, "s", _p4_V) # {s:∞,a:4,b:∞,t:4}
_p4_ans = at_least_k_shortest(_p4_adj, _p4_w, "s", "t")
_p4_brute = brute_at_least_k(_p4_adj, _p4_w, "s", "t", _p4_V, 12)
_p4_nadj, _p4_nw = build_atleast_negcycle_example()
_p4_neg = at_least_k_shortest(_p4_nadj, _p4_nw, "s", "t")
_p4_neg16 = brute_at_least_k(_p4_nadj, _p4_nw, "s", "t", _p4_V, 16)
_p4_neg32 = brute_at_least_k(_p4_nadj, _p4_nw, "s", "t", _p4_V, 32)
assert _p4_dk == {"s": INF, "a": 4, "b": INF, "t": 4}, _p4_dk
assert _p4_ans == 4 == _p4_brute, (_p4_ans, _p4_brute)
assert _p4_neg == -INF, _p4_neg
assert (_p4_neg16, _p4_neg32) == (-12, -28), (_p4_neg16, _p4_neg32)
_P4_OPT = ["s", "a", "b", "s", "t"] # TAM 4 kenar, ağırlık 4
_p4_opt_w = sum(_p4_w[(_P4_OPT[i], _P4_OPT[i + 1])] for i in range(len(_P4_OPT) - 1))
assert _p4_opt_w == 4 == _p4_ans, _p4_opt_w
def _p4_edge(ax, p0, p1, color, lw, z=3, rad=0.0, scale=15, ls="-"):
ax.add_patch(FancyArrowPatch(
p0, p1, arrowstyle="-|>", mutation_scale=scale, color=color,
linewidth=lw, zorder=z, shrinkA=13, shrinkB=13,
connectionstyle=f"arc3,rad={rad}", linestyle=ls))
def _p4_node(ax, x, y, label, r=0.30, fc=COL_BG, ec=COL_PRIMARY, lw=2.0,
fs=12, tc=COL_TEXT, z=5):
ax.add_patch(Circle((x, y), r, fc=fc, ec=ec, linewidth=lw, zorder=z))
ax.text(x, y, label, ha="center", va="center", fontsize=fs,
color=tc, weight="bold", zorder=z + 1)
fig, (axL, axM, axR) = plt.subplots(1, 3, figsize=(12.5, 6.0))
fig.patch.set_facecolor(COL_WHITE)
# --- SOL PANEL: orijinal çizge (s→t 1 kenar YASAK + pozitif çevrim) ---
_p4_pos = {"s": (0.0, 0.0), "a": (1.6, 1.05), "b": (1.6, -1.05), "t": (3.2, 0.0)}
_p4_cycle_edges = {("s", "a"), ("a", "b"), ("b", "s")}
for u in _p4_adj:
for v in _p4_adj[u]:
p0, p1 = _p4_pos[u], _p4_pos[v]
if (u, v) == ("s", "t"):
continue
hot = (u, v) in _p4_cycle_edges
rad = 0.0
if (u, v) in {("a", "t"), ("b", "t")}:
rad = 0.18 if v == "t" and u == "a" else -0.18
_p4_edge(axL, p0, p1, COL_ACCENT if hot else COL_SLATE_400,
2.8 if hot else 1.6, z=4 if hot else 2, rad=rad)
mx, my = (p0[0] + p1[0]) / 2, (p0[1] + p1[1]) / 2
axL.text(mx, my + 0.22, str(_p4_w[(u, v)]), ha="center", va="center",
fontsize=9.5, color=COL_AMBER_700 if hot else COL_SLATE_500,
weight="bold", zorder=6)
axL.add_patch(FancyArrowPatch(
_p4_pos["s"], _p4_pos["t"], arrowstyle="-|>", mutation_scale=15,
color="#b91c1c", linewidth=1.8, zorder=3, shrinkA=13, shrinkB=13,
connectionstyle="arc3,rad=0.55", linestyle=(0, (5, 3))))
_p4_bx, _p4_by = 1.6, -1.48
axL.add_patch(Circle((_p4_bx, _p4_by), 0.16, fc=COL_WHITE, ec="#b91c1c",
linewidth=2.2, zorder=8))
axL.plot([_p4_bx - 0.11, _p4_bx + 0.11], [_p4_by + 0.11, _p4_by - 0.11],
color="#b91c1c", linewidth=2.2, zorder=9)
axL.text(_p4_bx, _p4_by - 0.36, "s→t: 1 kenar < V=4 → GEÇERSİZ", ha="center",
va="center", fontsize=8.6, color="#b91c1c", weight="bold", zorder=9)
axL.text(0.78, -0.92, "1", ha="center", va="center", fontsize=9,
color="#b91c1c", weight="bold", zorder=9)
for name, (x, y) in _p4_pos.items():
_p4_node(axL, x, y, name,
fc=COL_AMBER_100 if name in ("s", "t") else COL_BG,
ec=COL_ACCENT if name in ("s", "t") else COL_PRIMARY)
axL.text(0.80, 1.55, "pozitif çevrim s→a→b→s\n«tur atmaya zorlar»",
ha="center", va="center", fontsize=8.8, color=COL_AMBER_700,
weight="bold", zorder=9)
axL.set_title("Orijinal çizge — kısa yol yasak",
fontsize=11.5, color=COL_TEXT, weight="bold")
axL.set_xlim(-0.7, 3.9)
axL.set_ylim(-2.15, 2.1)
axL.set_aspect("equal")
axL.axis("off")
# --- ORTA PANEL: kalmasız katmanlı DAG ---
_p4_nodes = ["s", "a", "b", "t"]
_p4_yrow = {"s": 3, "a": 2, "b": 1, "t": 0}
_p4_xcol = {k: k * 1.30 for k in range(_p4_V + 1)}
def _p4_mpos(v, k):
return (_p4_xcol[k], _p4_yrow[v] * 0.92)
_p4_opt_layer = {(("s", 0), ("a", 1)), (("a", 1), ("b", 2)),
(("b", 2), ("s", 3)), (("s", 3), ("t", 4))}
for i in range(_p4_V):
for u in _p4_adj:
for v in _p4_adj[u]:
p0, p1 = _p4_mpos(u, i), _p4_mpos(v, i + 1)
hot = ((u, i), (v, i + 1)) in _p4_opt_layer
axM.add_patch(FancyArrowPatch(
p0, p1, arrowstyle="-|>", mutation_scale=12 if hot else 8,
color=COL_ACCENT if hot else COL_SLATE_400,
linewidth=3.0 if hot else 0.9, zorder=6 if hot else 2,
shrinkA=8, shrinkB=8, alpha=1.0 if hot else 0.55))
for k in range(_p4_V + 1):
for v in _p4_nodes:
x, y = _p4_mpos(v, k)
on_opt = (v, k) in [("s", 0), ("a", 1), ("b", 2), ("s", 3), ("t", 4)]
_p4_node(axM, x, y, v, r=0.20, fs=8.5,
fc=COL_AMBER_100 if on_opt else COL_WHITE,
ec=COL_ACCENT if on_opt else COL_SLATE_400,
lw=2.2 if on_opt else 1.1,
tc=COL_AMBER_700 if on_opt else COL_SLATE_500, z=7)
for k in range(_p4_V + 1):
axM.text(_p4_xcol[k], 3 * 0.92 + 0.52, f"k={k}", ha="center", va="center",
fontsize=9.5, color=COL_TEXT, weight="bold")
axM.text((_p4_xcol[0] + _p4_xcol[_p4_V]) / 2, -0.62,
"optimal: s₀→a₁→b₂→s₃→t₄ (TAM 4 kenar, ağırlık 4)",
ha="center", va="center", fontsize=9.2, color=COL_AMBER_700,
weight="bold")
axM.text((_p4_xcol[0] + _p4_xcol[_p4_V]) / 2, -1.04,
"kalma kenarı YOK → katman 4 = TAM 4 kenar\n(D18 graf-çoğaltmadan FARKI)",
ha="center", va="center", fontsize=8.4, color=COL_SLATE_500,
style="italic")
axM.set_title("Kalmasız katmanlı DAG — δ₌₄(s,·)",
fontsize=11.5, color=COL_TEXT, weight="bold")
axM.set_xlim(-0.45, _p4_xcol[_p4_V] + 0.45)
axM.set_ylim(-1.45, 3.55)
axM.set_aspect("equal")
axM.axis("off")
# --- SAĞ PANEL: süpernode s* + Bellman-Ford ---
_p4_posR = {"s*": (0.0, 0.0), "a": (1.7, 1.0), "t": (1.7, -1.0),
"s": (3.0, 1.0), "b": (3.0, -1.0)}
for v in ("a", "t"):
_p4_edge(axR, _p4_posR["s*"], _p4_posR[v], COL_ACCENT, 2.6, z=4,
rad=0.0, scale=15)
mx, my = (_p4_posR["s*"][0] + _p4_posR[v][0]) / 2, \
(_p4_posR["s*"][1] + _p4_posR[v][1]) / 2
axR.text(mx, my + (0.26 if v == "a" else -0.26),
f"δ₌₄={_p4_dk[v]}", ha="center", va="center", fontsize=9,
color=COL_AMBER_700, weight="bold", zorder=6)
for (u, v) in [("a", "t"), ("a", "b"), ("b", "t"), ("b", "s")]:
if u in _p4_posR and v in _p4_posR:
_p4_edge(axR, _p4_posR[u], _p4_posR[v], COL_SLATE_400, 1.2, z=2,
rad=0.22 if (u, v) in {("a", "b"), ("b", "s")} else 0.0)
_p4_node(axR, *_p4_posR["s*"], "s*", fc=COL_AMBER_100, ec=COL_ACCENT, lw=2.4, r=0.34)
for name in ("a", "t", "s", "b"):
fin = _p4_dk[name] < INF
_p4_node(axR, *_p4_posR[name], name,
fc=COL_AMBER_100 if name == "t" else COL_BG,
ec=COL_ACCENT if name == "t" else COL_PRIMARY)
dlabel = "∞" if not fin else str(_p4_dk[name])
axR.text(_p4_posR[name][0], _p4_posR[name][1] - 0.50,
f"δ₌₄={dlabel}", ha="center", va="center", fontsize=7.8,
color=COL_SLATE_500, zorder=6)
axR.add_patch(FancyBboxPatch(
(0.45, -2.30), 2.55, 0.66, boxstyle="round,pad=0.05,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=8))
axR.text(1.72, -1.97, f"cevap = {_p4_ans}", ha="center", va="center",
fontsize=13, color=COL_AMBER_700, weight="bold", zorder=9)
axR.text(1.5, 2.05, "Bellman-Ford(s*) → t", ha="center", va="center",
fontsize=9, color=COL_SLATE_500, style="italic")
axR.set_title("Süpernode s* + Bellman-Ford",
fontsize=11.5, color=COL_TEXT, weight="bold")
axR.set_xlim(-0.7, 3.9)
axR.set_ylim(-2.55, 2.3)
axR.set_aspect("equal")
axR.axis("off")
fig.text(0.5, 0.025,
f"Negatif çevrim varsa (a ile b arası çift −2): cevap −∞ · brute kmax "
f"16→32 hâlâ düşer ({_p4_neg16}→{_p4_neg32}), tur sayısı sınırsız",
ha="center", va="center", fontsize=8.6, color=COL_SLATE_500,
style="italic")
fig.suptitle("En az V kenarlı en küçük ağırlıklı yol — ≥V kenar zorunluluğu (QR2 P4)",
fontsize=13, color=COL_TEXT, weight="bold", y=0.99)
plt.tight_layout(rect=(0, 0.04, 1, 0.96))
plt.show()
```
::: {.callout-note collapse="true" title="Problem 4 (Uzun-kısa yol): yönlü, keyfi ağırlık; en az V kenarlı en küçük ağırlıklı s→t yolunu O(V³)'te bul."}
**Çözüm.**
"En az V kenar" $\to$ yol **basit olamaz** ($V + 1$ düğüm gerekir). Önce **Bellman-Ford**: negatif çevrim s→t yolunda ise cevap $-\infty$ (sonsuz kenarlı yol mevcut). Yoksa: "tam V kenarlı" mesafeyi düşün. **Graf çoğaltma**: $V + 1$ katman, kenarları yalnız bir alt katmana yönlendir (kalma-kenarı *yok*) $\to$ katman 0'dan katman V'ye yol = orijinalde **tam V kenarlı** yol; çizge bir **DAG** $\to$ DAG relaxation $O(V^3)$ (G′ boyutu $V \cdot (V + E) = O(V^3)$).
"En az V" için: tam-V-kenarlı mesafeleri (DAG relaxation çıktısı) bir **süpernode** ile alt katmana bağla, sonra orijinal graf üzerinde **Bellman-Ford** çalıştır (kalan kısım basit yol — negatif çevrim yok). Üst kısım (DAG) ucuz, alt kısım (çevrimli) küçük $\to$ karmaşıklık ayrıştırılır. Deterministik örnek bunu doğrular: $\delta_{=4} = \{s: \infty,\, a: 4,\, b: \infty,\, t: 4\}$, optimal yol s→a→b→s→t (tam 4 kenar, ağırlık 4); doğrudan s→t ağırlık 1 ama tek kenar olduğu için **geçersiz**. Negatif çevrim varyantında ($a$ ile $b$ arası çift toplam $-2$) cevap $-\infty$; kaba kuvvet $k_{\max}$ 16'dan 32'ye çıkınca değer $-12$'den $-28$'e düşer — iraksamanın sayısal izi.
**Karmaşıklık.** Bellman-Ford $O(V \cdot E)$ + DAG relaxation $O(V^3)$ + son Bellman-Ford $O(V \cdot E)$ $\to$ **$O(V^3)$**.
:::
## Quiz Hazırlığı Egzersizleri {#sec-quiz-hazirligi-d22}
**Egzersiz 1.** Bir sözel problemi (örneğin labirent, ağ, oyun) çizgeye modelle: düğüm/kenar/ağırlık/yön tanımla, çözeceğin soyut problemi (en kısa yol / bileşen / topolojik) ifade et.
**Egzersiz 2.** SSSP hiyerarşisi tablosunu (BFS/DAG/Dijkstra/Bellman-Ford) ezberden çıkar; her biri için "hangi kısıt + hangi süre" yaz.
**Egzersiz 3.** Üç graf-değiştirme stratejisini (düğüm çoğaltma, süpernode, ön işleme) birer örnek problemle eşle.
**Egzersiz 4.** Bir "durum izleme" problemini düğüm çoğaltmayla çöz (örneğin kapasite/mod katmanları); $V$ ve $E$'nin nasıl büyüdüğünü hesapla.
**Egzersiz 5.** Johnson'ın 5 adımını ezberden anlat; her adımın süresini ve neden $V \times$ Dijkstra'nın baskın olduğunu açıkla.
## Quiz 3 Öncesi Kapsam Genişlemesi {#sec-quiz-3-kapsam}
Quiz 2 buraya kadar; sıradaki blok (Ders 23+, **Quiz 3** kapsamı) **dinamik programlamaya (DP)** geçer:
- **Ders 23-27 (L15-L18; araya Ders 25 = PS8 girer):** DP temelleri — alt problem tanımı, ilişki (recurrence), topolojik sıra, taban durum, çözüm kurma.
- DP, "kendi algoritmanı tasarla" ünitesidir; en kısa yolların **optimal alt yapı** ve **örtüşen alt problem** sezgileri DP'nin habercisidir.
Bağ: çizge bloğu "kara kutuya indirge" iken, DP "alt problemleri birleştir" der — ama ikisi de aynı optimal-alt-yapı omurgasını paylaşır.
## Ders 13-21 Toplu Cheat Sheet (L9-L14 + PS5-6) {#sec-toplu-cheat-d22}
| Konu | Özü | Kaynak (L/PS) |
|------|-----|---------------|
| Çizge G = (V, E) | Komşuluk listesi; $O(1)$ kenar sorgu | L9 |
| BFS | Seviye kümeleri; ağırlıksız en kısa yol; $O(V+E)$ | L9 |
| DFS / full DFS | Erişilebilirlik $O(E)$; bileşen / topolojik / çevrim $O(V+E)$ | L10 |
| DAG relaxation | Topolojik sırada gevşet; herhangi ağırlık; $O(V+E)$ | L11 |
| Bellman-Ford | Genel SSSP; negatif çevrim $-\infty$; $O(V \cdot E)$ | L12 |
| Dijkstra | Ağırlık $\ge 0$; öncelik kuyruğu; $O(V \log V + E)$ | L13 |
| Johnson (APSP) | Potansiyel ile yeniden ağırlıklandır $\to V \times$ Dijkstra; $O(V^2 \log V + V \cdot E)$ | L14 |
| Graf değiştirme | Düğüm çoğaltma / süpernode / ön işleme | PS5-6 |
::: {.callout-warning title="Sonraki Ders"}
**Ders 23 (L15): Dinamik Programlama 1 — SRTBOT**
Erik Demaine ile **dinamik programlama (DP)** ünitesine geçiyoruz: SRTBOT çerçevesi (Subproblem, Relation, Topological order, Base case, Original problem, Time). Çizge bloğunun "kara kutuya indirge" disiplini biter; DP "alt problemleri tanımla ve birleştir" disiplinine geçer — ama optimal-alt-yapı omurgası aynı kalır.
:::
## Builder ve OMSCS Bağlantıları {#sec-builder-omscs-d22}
::: {.callout-tip title="6 köprü"}
Bu tekrar oturumu, "problemi doğru bir çizgeye modelle, kara kutuya indirge, sakladığını ve aradığını yaz" disiplinini kurar — köprülerin özeti:
1. **Quiz 2 = çizge midterm** $\to$ OMSCS CS 6515: çizge algoritmaları + indirgeme, graduate dersin giriş varsayımıdır.
2. **Modelleme $\to$ gerçek dünya $\to$ çizge:** sosyal graf, bağımlılık grafı, ağ topolojisi, durum-uzayı.
3. **Süpernode** $\to$ çok-kaynak/çok-hedef indirgemesi; veritabanı, ağ akışı, kümeleme.
4. **Düğüm çoğaltma** $\to$ durum-augmentasyonu: zaman-genişletilmiş çizge, mod/kapasite katmanları.
5. **SSSP hiyerarşisi** $\to$ "en kısıtlı uygulanabilir algoritmayı seç": pratik performans bilinci.
6. **Doğru ama yavaş > yanlış ama hızlı** $\to$ mühendislikte önce doğruluk, sonra optimizasyon.
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
Quiz 2 senden çizge algoritması icat etmeni değil, **problemi doğru bir çizgeye modellemeni** ister. Düğüm/kenar/ağırlığı açıkça tanımla, çözeceğin soyut problemi (en kısa yol, bileşen, topolojik sıra) söyle, BFS/Dijkstra/Bellman-Ford/Johnson kara kutusuna **indirge** — algoritmayı asla modifiye etme — ve süreyi grafın boyutundan analiz et. Karmaşıklık, algoritmadan değil, "doğru grafı görmekten" gelir.
:::
