---
title: "Problem Oturumu 5"
subtitle: "Ders 13-15'in uygulaması: beş çizge problemi BFS/DFS'e iner — yarıçap ve 2-yaklaşım, süpernode router gecikmesi, büyülü kapılar bileşen sayımı, sabitten yararlanan 3-şehir turu, durum-uzayı ve ortada buluşma"
---
::: {.callout-note title="Oturum bilgisi"}
- **Solomon'un videosu:** [YouTube — Problem Session 5](https://www.youtube.com/watch?v=ZLdooNwP7Pw) (≈88 dk)
- **OCW sayfası:** [MIT 6.006 Problem Session 5](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/problem-session-5/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 17 (Problem Oturumu 5)
- **Hoca:** Justin Solomon
- **Okuma süresi:** ≈24 dk
:::
## Bu Problem Oturumu Ne Hakkında? {#sec-hakkinda-d17}
Beşinci problem oturumu (Justin Solomon) **BFS ve DFS** üzerine kurulu beş çizge problemini çözer (@fig-concept-map). Hepsinin ortak teması şudur: problem ilk bakışta "ağırlıklı en kısa yol" veya "gezgin satıcı" gibi *zor* görünür, ama doğru **indirgeme** ile ağırlıksız BFS/DFS'e veya basit bir sayıma iner.
> *"we're going to cover some problems in graph theory related to depth-first search and breadth-first search."* — Solomon, 0:20
Solomon'un tekrarladığı meta-ders üç adımda toplanır:
- **Süslemeyi soy.** 6.006 problemleri basit hesaplama problemlerini bol metinle süsler; ilk iş paragrafı madde madde ayıklamaktır.
- **Asıl soruyu çıkar.** "Asıl ne soruluyor?" — en kısa yol mu, sadece bir sayım mı, yoksa bir min-maks mı?
- **Verilen sabitleri çıkar.** "Verilen sabitler neler?" — "tam 3 şehir", "tel ≤ 100r", "derece ≤ 4" gibi sabitler indirgemenin anahtarıdır.
Her problem bu ayıklamadan sonra "İfade → Yaklaşım → Çözüm → Karmaşıklık" akışıyla işlenir.
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Problem Oturumu 5'in kavram haritası: kök (PS5) beş probleme dallanır ve ortadaki ortak tema düğümü beşini birden yönlendirir. Problem 1 yarıçabı eksantriklikle hesaplar, sonra üçgen eşitsizliğiyle tek BFS'lik 2-yaklaşıma iner; Problem 2 ağırlıklı router hattını zincir-açmayla ağırlıksızlaştırıp süpernode ile tek BFS'e indirger; Problem 3 büyülü kapı problemini bedava-kapı çizgesinin bağlı bileşen sayısı eksi bir olarak çözer; Problem 4 üç-şehir turunu sabit sayıda BFS ve permütasyona indirir; Problem 5 cep küpünü durum-uzayı çizgesi olarak modelleyip ortada buluşmayla arar. Ortak tema — zor görünen problemi doğru indirgemeyle ağırlıksız BFS/DFS'e veya basit sayıma çevir — Solomon'un her probleme aynı kapıdan girmesini sağlar."
flowchart TD
R["Problem Oturumu 5<br/>(Ders 13-15 uygulaması)"] --> P1["Problem 1<br/>Yarıçap + 2-yaklaşım<br/>(eksantriklik, üçgen eşitsizliği)"]
R --> P2["Problem 2<br/>Router gecikmesi<br/>(zincir-açma + süpernode)"]
R --> P3["Problem 3<br/>Büyülü kapılar<br/>(bağlı bileşen − 1)"]
R --> P4["Problem 4<br/>Üç-şehir turu<br/>(sabitten yararlan)"]
R --> P5["Problem 5<br/>Cep küpü<br/>(durum-uzayı + ortada buluşma)"]
CORE["Ortak tema:<br/>zor görünen problemi<br/>DOĞRU İNDİRGEMEYLE<br/>ağırlıksız BFS/DFS'e indir"]
CORE -.-> P1
CORE -.-> P2
CORE -.-> P3
CORE -.-> P4
CORE -.-> P5
classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937
classDef prob fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937
classDef core fill:#fcd34d,stroke:#b45309,stroke-width:2px,color:#1f2937
class R root
class P1,P2,P3,P4,P5 prob
class CORE core
```
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 17 (PS5) motoru (_engine_PS5.py) + D13/D15 BFS/DFS altyapısı
# (_engine.py'den bfs, make_undirected, connected_components) + Slate+Amber
# sabitleri (_viz.py). Bu hücre gizlidir (#| echo: false). Aşağıdaki TÜM figür
# hücreleri bu hücrede tanımlanan fonksiyonları (radius_exact, radius_2approx,
# total_latency_supernode, expand_weighted_edges, bidirectional_bfs,
# single_bfs_distance ...) + COL_* globallerini IMPORT ETMEDEN kullanır.
# Notion'daki öğretim içeriği (görünür display python blokları) bu motorun
# tarif seviyesidir; burada tam, deterministik, test edilmiş sürüm yaşar.
#
# NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama
# backend'ini ezer (plt.show() 0 figür üretir; brief §2/§4). Standalone testte
# savefig kullanılır; Quarto render'da jupyter inline backend'i ayarlar.
#
# Dosyadan import YOK: tüm BFS/DFS altyapısı + 5 problem fonksiyonu burada
# self-contained INLINE → render dizininden bağımsız (kurs paritesi: PS4/11
# emsali, düz INLINE).
# ============================================================================
import math
from collections import deque
from itertools import permutations
import matplotlib.pyplot as plt
from matplotlib.patches import (Circle, FancyArrowPatch, FancyBboxPatch, Arc,
Polygon, Wedge)
# ---------------------------------------------------------------------------
# _viz.py — Slate + Amber stil sabitleri (HEX birebir brief §1/§8)
# ---------------------------------------------------------------------------
COL_PRIMARY = "#374151" # slate-700 — birincil çizgi/çerçeve
COL_ACCENT = "#f59e0b" # amber-500 — vurgu (aktif düğüm / kaynak / hedef)
COL_TEXT = "#1f2937" # slate-800 — metin
COL_BG = "#f3f4f6" # slate-100 — arka plan / callout / kutu dolgusu
# Türev amber tonları
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)
# Türev slate tonları
COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin
COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara
COL_WHITE = "#ffffff"
# ===========================================================================
# D13/D15 BFS/DFS ALTYAPISI (_engine.py'den birebir; PS5 motoru bunları import
# eder, burada INLINE). bfs + make_undirected + connected_components.
# ===========================================================================
def bfs(adj, s):
"""BFS (L9 §8): kaynaktan katman katman; (delta, parent) döndürür.
'Henüz görülmemiş' kontrolü ilk (= en kısa) uzaklığı sabitler. 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
# ===========================================================================
# _engine_PS5.py — PS5 problem motoru (D13/D15 üstüne; INLINE).
# ===========================================================================
# --- Problem 1: yarıçap + eksantriklik + 2-yaklaşım (Solomon 3:25, 24:43) ---
def eccentricity(adj, v):
"""ε(v) = en uzak düğüme BFS mesafesi (bağlı çizge varsayımı)."""
delta, _ = bfs(adj, v)
return max(delta.values())
def radius_exact(adj):
"""(a) R(G) = min_u ε(u) — V kez BFS, O(V·E). Döndürür (R, merkez)."""
best, center = None, None
for u in adj:
e = eccentricity(adj, u)
if best is None or e < best:
best, center = e, u
return best, center
def radius_2approx(adj, u=None):
"""(b) 2-yaklaşım: HERHANGİ u için R* = ε(u); R ≤ R* ≤ 2R (üçgen
eşitsizliği — Solomon 24:43). Tek BFS, O(E)."""
if u is None:
u = next(iter(adj))
return eccentricity(adj, u)
# --- Problem 2: router gecikmesi: zincir-açma + süpernode (Solomon 40:18) ---
def expand_weighted_edges(n_nodes, wires):
"""Ağırlık-l telini l adet birim-kenar zincirine aç (Solomon: ağırlıklı →
ağırlıksız). wires: [(u, v, l)]. Döndürür: adj (yardımcı düğümler
('aux', i) etiketli)."""
adj = {v: [] for v in range(n_nodes)}
aux = 0
for u, v, l in wires:
prev = u
for step in range(l - 1):
mid = ("aux", aux)
aux += 1
adj.setdefault(mid, [])
adj[prev].append(mid)
adj[mid].append(prev)
prev = mid
adj[prev].append(v)
adj[v].append(prev)
return adj
def total_latency_supernode(n_nodes, wires, entries):
"""Süpernode çözümü (Solomon 40:18): s'i tüm giriş noktalarına bağla;
tek BFS; gecikme(i) = dist(s, i) − 1; toplamı döndür. O(r)."""
adj = expand_weighted_edges(n_nodes, wires)
s = ("super", 0)
adj[s] = []
for e in entries:
adj[s].append(e)
adj[e].append(s)
delta, _ = bfs(adj, s)
return sum(delta[i] - 1 for i in range(n_nodes))
# --- Problem 3: büyülü kapılar: bedava-bileşen − 1 (Solomon 58:08) ---
def min_enchanted_doors(n_rooms, free_doors):
"""Bedava kapı çizgesinin bağlı bileşen sayısı − 1 (Solomon 58:08:
yayılma ağacı argümanı). O(n)."""
adj = make_undirected(free_doors) if free_doors else {}
for r in range(n_rooms):
adj.setdefault(r, [])
return len(connected_components(adj)) - 1
# --- Problem 4: 3-şehir turu: 12 BFS + 6 permütasyon (Solomon 1:09:06) ---
def best_three_city_tour(adj, home, cities):
"""Ev → 3 şehir → ev; toplam aktarma (= Σ yol-uzunluğu − bacak sayısı)
minimum. 'Tam 3' sabiti: ≤12 çift BFS + 3! = 6 permütasyon (Solomon
1:09:06). Döndürür: (min_aktarma, en_iyi_sıra)."""
pts = [home] + list(cities)
dist = {}
for p in pts: # 4 BFS yeter (her ilgili kaynaktan)
delta, _ = bfs(adj, p)
for q in pts:
dist[(p, q)] = delta.get(q)
best, order = None, None
for perm in permutations(cities):
legs = [(home, perm[0]), (perm[0], perm[1]),
(perm[1], perm[2]), (perm[2], home)]
if any(dist[l] is None for l in legs):
continue
total = sum(dist[l] - 1 for l in legs) # aktarma = yol uzunluğu − 1
if best is None or total < best:
best, order = total, perm
return best, order
# --- Problem 5: durum-uzayı + ortada buluşma (çift-yönlü BFS, 1:27:08) ---
POCKET_CUBE_UPPER = 3 ** 7 * 5040 # 3⁷ · 7! = 11.022.480 < 12 milyon
def bidirectional_bfs(adj, s, t):
"""Ortada buluşma (Solomon 1:27:08): kaynak VE hedeften paralel BFS;
seviyeler kesişince dur. Yönsüz/simetrik geçişli durum çizgesi varsayımı.
Döndürür: (mesafe, ziyaret_sayısı) — tek-yönlüyle kıyas için."""
if s == t:
return 0, 1
ds, dt = {s: 0}, {t: 0}
qs, qt = deque([s]), deque([t])
visited = 2
def expand(q, mine, other):
nonlocal visited
for _ in range(len(q)): # bir seviye genişlet
u = q.popleft()
for v in adj[u]:
if v in other: # kesişim → toplam mesafe
return mine[u] + 1 + other[v]
if v not in mine:
mine[v] = mine[u] + 1
q.append(v)
visited += 1
return None
while qs and qt:
r = expand(qs, ds, dt) if len(qs) <= len(qt) else expand(qt, dt, ds)
if r is not None:
return r, visited
return None, visited # bağlantısız
def single_bfs_distance(adj, s, t):
"""Tek-yönlü tanık: (mesafe, ziyaret_sayısı)."""
delta, _ = bfs(adj, s)
return delta.get(t), len(delta)
```
::: {.callout-tip title="Yaklaşım — ortak strateji: zoru kolaya indirgemek"}
Beş problemin tamamı aynı refleksle başlar: önce metni soyup "asıl ne soruluyor" ve "hangi sabitler verildi" diye çıkar; sonra problemi **bildiğin bir araca** (ağırlıksız BFS, full DFS/bağlı bileşenler, bir sayım) indirge. Bu oturumun beş indirgeme tekniği — eksantriklik + üçgen eşitsizliği, zincir-açma + süpernode, bedava-kapı bileşenleri, sabit-sayıda BFS, ortada buluşma — algoritma tasarımının "tanıdık alt-yapıya yönlendir" kasını çalıştırır.
:::
## Problem 1: Çizge Yarıçapı ve Eksantriklik {#sec-problem-1-d17}
**İfade.** Bağlı bir yönsüz çizge $G$ verilir. Bir düğümün **eksantrikliği** $\varepsilon(v) = \max_w \operatorname{dist}(v, w)$ (en uzaktaki düğüme mesafe); çizgenin **yarıçapı** $R(G) = \min_u \varepsilon(u)$. (a) $R(G)$'yi $O(V \cdot E)$'de hesapla. (b) $R$'yi daha hızlı ($O(E)$) **2-yaklaşımla** tahmin et: $R \le R^* \le 2R$.
::: {.callout-tip title="Yaklaşım — min-maks: merkezi bul, sonra üçgen eşitsizliğiyle gevşet"}
Bu bir **min-maks** problemidir: metrik geometride bir dairenin merkezini bulmak gibi — her noktanın en uzak noktaya mesafesi minimumda merkezde gerçekleşir. (a) şıkkında tanımı doğrudan kodla: her düğümden BFS, en uzak mesafe = eksantriklik, bunların minimumu = yarıçap. (b) şıkkında ise *tek bir* düğümün eksantrikliğinin yeterli bir tahmin olduğunu **üçgen eşitsizliğiyle** göster — kesin merkezi bulmak zorunda kalmadan.
:::
> *"the radius... is the min over all of the different vertices, u, of the eccentricity of u."* — Solomon, 3:25
**Çözüm.**
**(a) Kesin yarıçap.** Her $v$ için BFS ile tüm mesafeleri bul, maksimumunu al (= $\varepsilon(v)$), bunların minimumunu tut.
```python
def radius_exact(adj): # (a) kesin R — O(V·E)
best, center = None, None
for u in adj: # V kez BFS
e = max(bfs(adj, u)[0].values()) # ε(u) = en uzak mesafe
if best is None or e < best:
best, center = e, u
return best, center # (R, merkez)
```
**(b) 2-yaklaşım.** *Herhangi* bir $u$ seç, $R^* = \varepsilon(u)$ döndür (tek BFS). İki sınır:
- **Alt sınır.** $R = \min_u \varepsilon(u) \le \varepsilon(u) = R^*$ (minimum, herhangi bir değerden küçük-eşittir).
- **Üst sınır.** $u_0 = \arg\min \varepsilon$ gerçek merkez, $\bar{v}$ ise $u$'dan en uzak düğüm olsun. Üçgen eşitsizliği: $R^* = \operatorname{dist}(u, \bar{v}) \le \operatorname{dist}(u, u_0) + \operatorname{dist}(u_0, \bar{v}) \le R + R = 2R$.
```python
def radius_2approx(adj, u=None): # (b) 2-yaklaşım — O(E)
if u is None:
u = next(iter(adj)) # HERHANGİ bir düğüm
return max(bfs(adj, u)[0].values()) # R* = ε(u); R ≤ R* ≤ 2R
```
> *"Justin's favorite inequality is the triangle inequality."* — Solomon, 24:43
@fig-radius-2approx bu sınırı bir **yol çizgesi** $0\text{-}1\text{-}2\text{-}3\text{-}4$ üzerinde motordan **gerçek** verilerle gösterir: kesin merkez düğüm $2$'dir ve $\varepsilon(2) = R = 2$ (üst panel); keyfi $u = 0$ seçilince $R^* = \varepsilon(0) = 4 = 2R$ olur (alt panel) — bu çizge tam olarak sınırın doyduğu kötü durumdur. Üçgen eşitsizliği $R \le R^* \le 2R$ tek BFS'in kesin yarıçabın en çok iki katı olduğunu garanti eder.
**Karmaşıklık.** (a) $V$ kez BFS = $O(V \cdot (V + E))$; **bağlı** çizgede $V = O(E)$ olduğundan $V + E = O(E)$ → **$O(V \cdot E)$**. (b) tek BFS → **$O(E)$** ($V$ faktörü düşer).
```{python}
#| label: fig-radius-2approx
#| fig-cap: "Yarıçap ve 2-yaklaşım — tek BFS ε(u) kesin R'nin en çok 2 katı (R ≤ R* ≤ 2R) — Problem 1 İMZA. Yol çizgesi 0-1-2-3-4 (motordan GERÇEK). ÜST panel (a) KESİN MERKEZ: gerçek merkez düğüm 2 amber dolgu; iki uca mesafe yayları (her ikisi 2) → ε(2) = R = 2 rozeti; merkez = en küçük eksantrikliğe sahip düğüm. ALT panel (b) KEYFİ u=0: keyfi seçilen u=0 (slate dolgu); en uzak düğüm 4'e tek BFS yolu vurgulu → R* = ε(0) = 4 = 2R rozeti — bu çizge sınırın DOYDUĞU kötü durum. ORTADA üçgen eşitsizliği kutusu (Solomon 24:43): R* = dist(u, en-uzak) ≤ dist(u, merkez) + dist(merkez, en-uzak) ≤ R + R = 2R. ALT şerit maliyet: (a) kesin R = V kez BFS → O(V·E) | (b) 2-yaklaşım = TEK BFS → O(E), V faktörü düşer."
#| fig-width: 10.5
#| fig-height: 7.0
# fig-radius-2approx — PS5 Problem 1 İMZA: yarıçap + üçgen-eşitsizliği 2-yaklaşımı.
# Veri MOTORDAN: radius_exact(path5) == (2, 2), radius_2approx(path5, u=0) == 4.
# networkx KULLANILMAZ — elle koordinat. Setup globalleri: plt, Circle,
# FancyBboxPatch, FancyArrowPatch, COL_*, make_undirected, bfs, radius_exact,
# radius_2approx, eccentricity.
_NODES = [0, 1, 2, 3, 4]
_DX = 1.65 # düğümler arası yatay aralık
_R = 0.30 # düğüm dairesi yarıçapı
def _xpos(v):
return v * _DX
def _draw_path(ax, y, center=None, source=None, far=None, path_edges=None):
path_edges = path_edges or set()
for a, b in zip(_NODES, _NODES[1:]):
x0, x1 = _xpos(a), _xpos(b)
hot = (a, b) in path_edges or (b, a) in path_edges
ax.plot([x0 + _R, x1 - _R], [y, y],
color=COL_AMBER_600 if hot else COL_SLATE_400,
linewidth=3.0 if hot else 1.7,
zorder=3 if hot else 2, solid_capstyle="round")
for v in _NODES:
x = _xpos(v)
if v == center:
fc, ec, lw, tcol = COL_ACCENT, COL_AMBER_700, 3.0, COL_WHITE
elif v == source:
fc, ec, lw, tcol = COL_BG, COL_SLATE_500, 2.8, COL_TEXT
elif v == far:
fc, ec, lw, tcol = COL_AMBER_100, COL_ACCENT, 2.8, COL_TEXT
else:
fc, ec, lw, tcol = COL_WHITE, COL_SLATE_400, 1.8, COL_TEXT
ax.add_patch(Circle((x, y), _R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, y, str(v), ha="center", va="center",
fontsize=13, color=tcol, weight="bold", zorder=6)
def _dist_brace(ax, va, vb, y, label, *, above=True, color=COL_AMBER_700):
xa, xb = _xpos(va), _xpos(vb)
sgn = 1 if above else -1
yoff = sgn * (_R + 0.34)
rad = -0.30 if above else 0.30
ax.add_patch(FancyArrowPatch(
(xa, y + sgn * _R * 0.6), (xb, y + sgn * _R * 0.6),
arrowstyle="<|-|>", mutation_scale=11, color=color,
linewidth=1.8, zorder=4,
connectionstyle=f"arc3,rad={rad}", shrinkA=6, shrinkB=6))
ax.text((xa + xb) * 0.5, y + yoff + sgn * 0.16, label,
ha="center", va="center", fontsize=9.5, color=color,
weight="bold", zorder=5)
# --- motor verisi + iç tutarlılık (figür yalnız bunu çizer) ---
path5 = make_undirected([(0, 1), (1, 2), (2, 3), (3, 4)])
R, center = radius_exact(path5)
Rstar = radius_2approx(path5, u=0)
assert (R, center) == (2, 2), (R, center)
assert Rstar == 4, Rstar
delta0, _ = bfs(path5, 0)
far0 = max(delta0, key=lambda k: delta0[k])
assert delta0[far0] == Rstar, (far0, delta0)
delta_c, _ = bfs(path5, center)
assert eccentricity(path5, center) == R
fig, ax = plt.subplots(figsize=(10.5, 7.0))
fig.patch.set_facecolor(COL_WHITE)
y_top = 3.4
y_bot = 0.0
xL = _xpos(_NODES[0])
xR = _xpos(_NODES[-1])
xmid = (xL + xR) * 0.5
# ÜST panel — GERÇEK merkez düğüm 2 (amber); iki uca mesafe yayları
ax.text(xL - _R - 0.55, y_top + 0.78, "(a) kesin merkez", ha="left",
va="center", fontsize=11, color=COL_TEXT, weight="bold", zorder=6)
_draw_path(ax, y_top, center=center)
_dist_brace(ax, center, _NODES[0], y_top,
f"dist = {delta_c[_NODES[0]]}", above=True)
_dist_brace(ax, center, _NODES[-1], y_top,
f"dist = {delta_c[_NODES[-1]]}", above=True)
ax.add_patch(FancyBboxPatch(
(xR + 0.55, y_top - 0.32), 2.45, 0.66,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=4))
ax.text(xR + 0.55 + 1.22, y_top, f"ε(2) = R = {R}", ha="center", va="center",
fontsize=12, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(xmid, y_top - _R - 0.50,
"merkez = en küçük eksantrikliğe sahip düğüm",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=5)
# ALT panel — keyfi u=0 (slate); 0'dan en uzak 4'e yol vurgusu
ax.text(xL - _R - 0.55, y_bot + 0.78, "(b) keyfi u = 0", ha="left",
va="center", fontsize=11, color=COL_TEXT, weight="bold", zorder=6)
full_path = {(a, b) for a, b in zip(_NODES, _NODES[1:])}
_draw_path(ax, y_bot, source=0, far=far0, path_edges=full_path)
xa, xb = _xpos(0), _xpos(far0)
ax.add_patch(FancyArrowPatch(
(xa, y_bot - _R * 0.6), (xb, y_bot - _R * 0.6),
arrowstyle="<|-|>", mutation_scale=11, color=COL_AMBER_700,
linewidth=1.8, zorder=4, shrinkA=6, shrinkB=6))
ax.text((xa + xb) * 0.5, y_bot - _R - 0.30, f"dist = {Rstar}",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.add_patch(FancyBboxPatch(
(xR + 0.55, y_bot - 0.32), 2.45, 0.66,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_AMBER_300, ec=COL_AMBER_700, linewidth=2.4, zorder=4))
ax.text(xR + 0.55 + 1.22, y_bot, f"R* = ε(0) = {Rstar} = 2R",
ha="center", va="center", fontsize=12, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text(xmid, y_bot + _R + 0.62,
"u keyfi seçilir → en uzak düğüme TEK BFS",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=5)
# ORTADA — üçgen eşitsizliği kutusu (Solomon 24:43)
y_box = (y_top + y_bot) * 0.5
box_l, box_w = xL - _R - 0.45, (xR + 3.10) - (xL - _R - 0.45)
ax.add_patch(FancyBboxPatch(
(box_l, y_box - 0.40), box_w, 0.80,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.8, zorder=2))
ax.text(box_l + box_w * 0.5, y_box + 0.10,
"üçgen eşitsizliği: R* = dist(u, en-uzak) "
"≤ dist(u, merkez) + dist(merkez, en-uzak) ≤ R + R = 2R",
ha="center", va="center", fontsize=9.5, color=COL_TEXT,
weight="bold", zorder=4)
ax.text(box_l + box_w * 0.5, y_box - 0.18,
"→ herhangi u'dan ε(u) kesin yarıçapın en çok 2 katı: R ≤ R* ≤ 2R",
ha="center", va="center", fontsize=8.5, color=COL_AMBER_700,
style="italic", zorder=4)
# ALT şerit — maliyet karşılaştırması
y_strip = y_bot - 1.55
cards = [
("(a) kesin R", "her düğümden BFS: V kez", "O(V·E)",
COL_BG, COL_PRIMARY, COL_SLATE_500),
("(b) 2-yaklaşım", "tek düğümden BFS: 1 kez", "O(E)",
COL_AMBER_100, COL_ACCENT, COL_AMBER_700),
]
card_w = (box_w - 0.40) * 0.5
for k, (head, body, cost, fc, ec, tcol) in enumerate(cards):
cx0 = box_l + k * (card_w + 0.40)
ax.add_patch(FancyBboxPatch(
(cx0, y_strip - 0.50), card_w, 1.00,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=fc, ec=ec, linewidth=2.2, zorder=3))
ax.text(cx0 + card_w * 0.5, y_strip + 0.28, head, ha="center",
va="center", fontsize=10.5, color=tcol, weight="bold", zorder=5)
ax.text(cx0 + card_w * 0.5, y_strip - 0.02, body, ha="center",
va="center", fontsize=8.8, color=COL_SLATE_500, zorder=5)
ax.text(cx0 + card_w * 0.5, y_strip - 0.32, cost, ha="center",
va="center", fontsize=12, color=tcol, weight="bold", zorder=5)
ax.text(box_l + box_w * 0.5, y_strip - 0.82,
"2-yaklaşım V faktörünü düşürür — tek geçişle yarıçap tahmini",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=5)
fig.suptitle(
"Yarıçap ve 2-yaklaşım: tek BFS ε(u) kesin R'nin en çok 2 katı (R ≤ R* ≤ 2R)",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.set_xlim(xL - _R - 0.75, xR + 3.35)
ax.set_ylim(y_strip - 1.05, y_top + 1.15)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Problem 2: Router Gecikmesi ve Süpernode {#sec-problem-2-d17}
**İfade.** $r$ router, bazıları **giriş noktası (entry point)**; çift yönlü teller, her biri pozitif tamsayı uzunluk $l_i$. Bir router'ın **gecikmesi** = en yakın giriş noktasına en kısa yol. Toplam tel $\le 100r$ ve her router bir giriş noktasına ulaşır. Tüm router'ların gecikme toplamını **$O(r)$**'de hesapla.
::: {.callout-tip title="Yaklaşım — iki klasik hile: zincir-açma (ağırlıksızlaştır) + süpernode (tek kaynak)"}
İlk bakışta ağırlıklı en kısa yol gibi görünür ama değil. İki hile birleştirilir: (1) **Zincir-açma** — toplam tel $\le 100r$ olduğundan, ağırlık-$l$ kenarı $l$ tane ağırlık-1 kenardan oluşan bir zincire açılır → ağırlıksız çizge, BFS geçerli. (2) **Süpernode** — her router için her giriş noktasına ayrı ayrı BFS yapmak iç içe bir döngüdür; bunun yerine tüm giriş noktalarına bağlı *tek* sanal düğüm $s$ eklenir ve $s$'ten tek BFS tüm gecikmeleri bir dalgada verir.
:::
> *"he is a supernode, which is a term of art."* — Solomon, 40:18
**Çözüm.** Her router bir düğüm; her tel $l_i$ kenarlık zincire açılır (yardımcı "aux" düğümlerle), böylece $V = O(r)$ ve $E \le 100r = O(r)$. Tüm giriş noktalarına bağlı **tek bir süpernode** $s$ ekle. Üçgen eşitsizliğiyle, $s$'ten bir router'a en kısa yol önce $s$'ten en yakın giriş noktasına ($+1$ kenar) sonra oradan router'a gider — yani
$$\operatorname{gecikme}(i) = \operatorname{dist}(s, i) - 1.$$
Tek BFS (kaynak $s$) ile tüm $\operatorname{dist}(s, i)$ bulunur; cevap $\sum_i (\operatorname{dist}(s, i) - 1)$.
```python
def total_latency_supernode(n_nodes, wires, entries): # O(r)
adj = expand_weighted_edges(n_nodes, wires) # zincir-açma: ağırlıklı → ağırlıksız
s = ("super", 0) # tek sanal süpernode
adj[s] = []
for e in entries: # s → her giriş noktası (+1 kenar)
adj[s].append(e); adj[e].append(s)
delta, _ = bfs(adj, s) # TEK BFS (iç içe döngü YOK)
return sum(delta[i] - 1 for i in range(n_nodes)) # gecikme = dist(s,i) − 1
```
@fig-supernode üç panelde tüm hileyi motordan **gerçek** bir örnekle gösterir: 3 router, teller $(0\text{-}1,\ l{=}2)$ ve $(1\text{-}2,\ l{=}3)$, giriş noktası kümesi $\{0\}$. Zincir-açma $l{=}2$ teli için 1, $l{=}3$ teli için 2 aux düğüm üretir. Süpernode BFS'i $\operatorname{dist}(s, \cdot) = (1, 3, 6)$ verir → gecikmeler $0, 2, 5$ ve toplam $0 + 2 + 5 = 7$.
**Karmaşıklık.** Süpernode tek düğüm + (giriş sayısı kadar) kenar ekler (asimptotik değişmez). Tek BFS, $V + E = O(r)$ → **$O(r)$**.
```{python}
#| label: fig-supernode
#| fig-cap: "Süpernode hilesi — iç içe döngü YERİNE tek BFS dalgası — Problem 2 İMZA. Üç panel (motordan GERÇEK: 3 router, teller (0-1,ℓ=2),(1-2,ℓ=3), giriş {0}). ① AĞIRLIKLI HAT: router R0–R1–R2; kenar ağırlığı = tel uzunluğu ℓ; giriş noktası R0 amber çerçeve. ② ZİNCİR-AÇMA: her ağırlık-ℓ kenarı ℓ birim-kenara açılır, araya aux düğümler (ℓ=2→1 aux/2 kenar, ℓ=3→2 aux/3 kenar); tel ≤ 100r → E = O(r), ağırlıksız BFS geçerli. ③ SÜPERNODE s + TEK BFS: s büyük amber düğüm girişe +1 kenarla bağlanır; eş-merkezli BFS dalga yayları; her router gecikme rozeti dist(s,i) − 1 = (0, 2, 5); toplam kutusu Σ gecikme = 0 + 2 + 5 = 7 (Solomon 40:18)."
#| fig-width: 11.0
#| fig-height: 6.2
# fig-supernode — PS5 Problem 2 İMZA: zincir-açma + süpernode → tek BFS.
# Veri MOTORDAN: total_latency_supernode(3, [(0,1,2),(1,2,3)], [0]) == 7;
# dist(s,·) = (1,3,6) → gecikme (0,2,5). networkx KULLANILMAZ — elle koordinat.
# Setup globalleri: plt, Circle, FancyBboxPatch, FancyArrowPatch, Arc, COL_*,
# bfs, total_latency_supernode, expand_weighted_edges.
_WIRES = [(0, 1, 2), (1, 2, 3)]
_ENTRIES = [0]
_N_NODES = 3
_R_ROUTER = 0.30
_R_AUX = 0.115
def _router(ax, x, y, idx, *, is_entry=False, big=False):
r = _R_ROUTER * (1.18 if big else 1.0)
fc = COL_AMBER_100 if is_entry else COL_BG
ec = COL_ACCENT if is_entry else COL_PRIMARY
lw = 3.0 if is_entry else 2.0
ax.add_patch(Circle((x, y), r, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, y, f"R{idx}", ha="center", va="center",
fontsize=12.5, color=COL_TEXT, weight="bold", zorder=6)
def _aux(ax, x, y):
ax.add_patch(Circle((x, y), _R_AUX, facecolor=COL_WHITE,
edgecolor=COL_SLATE_400, linewidth=1.4, zorder=4))
# --- motor verisi + iç tutarlılık ---
total = total_latency_supernode(_N_NODES, _WIRES, _ENTRIES)
assert total == 7, total
_adj = expand_weighted_edges(_N_NODES, _WIRES)
_aux_nodes = [k for k in _adj if isinstance(k, tuple) and k[0] == "aux"]
assert len(_aux_nodes) == 3, len(_aux_nodes)
_s = ("super", 0)
_adj[_s] = []
for _e in _ENTRIES:
_adj[_s].append(_e)
_adj[_e].append(_s)
_delta, _ = bfs(_adj, _s)
dist_s = {i: _delta[i] for i in range(_N_NODES)}
assert dist_s == {0: 1, 1: 3, 2: 6}, dist_s
latency = {i: dist_s[i] - 1 for i in range(_N_NODES)}
assert latency == {0: 0, 1: 2, 2: 5}, latency
assert sum(latency.values()) == total
fig, ax = plt.subplots(figsize=(11.0, 6.2))
fig.patch.set_facecolor(COL_WHITE)
P0 = 0.0
P1 = 5.2
P2 = 10.6
yrow = 4.0
# ① SOL panel — orijinal AĞIRLIKLI hat
rx = [P0 + 0.0, P0 + 1.9, P0 + 3.8]
for i, x in enumerate(rx):
_router(ax, x, yrow, i, is_entry=(i in _ENTRIES))
for (u, v, l) in _WIRES:
x0, x1 = rx[u], rx[v]
ax.plot([x0 + _R_ROUTER, x1 - _R_ROUTER], [yrow, yrow],
color=COL_PRIMARY, linewidth=2.4, zorder=2, solid_capstyle="round")
ax.add_patch(FancyBboxPatch(
((x0 + x1) / 2 - 0.34, yrow + 0.20), 0.68, 0.40,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_BG, ec=COL_AMBER_700, linewidth=1.6, zorder=3))
ax.text((x0 + x1) / 2, yrow + 0.40, f"ℓ={l}", ha="center", va="center",
fontsize=10.5, color=COL_AMBER_700, weight="bold", zorder=4)
ax.text(rx[0], yrow - _R_ROUTER - 0.30, "giriş noktası", ha="center",
va="top", fontsize=9, color=COL_AMBER_700, weight="bold",
style="italic", zorder=6)
ax.text((rx[0] + rx[-1]) / 2, yrow + 1.55, "① ağırlıklı hat", ha="center",
va="center", fontsize=11.5, color=COL_TEXT, weight="bold", zorder=6)
ax.text((rx[0] + rx[-1]) / 2, yrow + 1.18, "kenar ağırlığı = tel uzunluğu ℓ",
ha="center", va="center", fontsize=8.8, color=COL_SLATE_500,
style="italic", zorder=6)
ax.add_patch(FancyArrowPatch(
(P0 + 4.25, yrow), (P1 - 0.55, yrow), arrowstyle="-|>",
mutation_scale=18, color=COL_AMBER_600, linewidth=2.2, zorder=3))
ax.text((P0 + 4.25 + P1 - 0.55) / 2, yrow + 0.28, "zincir-aç", ha="center",
va="bottom", fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=4)
# ② ORTA panel — ZİNCİR-AÇMA
seg = 0.62
mx = {0: P1 + 0.0}
x = mx[0]
_router(ax, x, yrow, 0, is_entry=True)
aux01 = x + seg
ax.plot([x + _R_ROUTER, aux01 - _R_AUX], [yrow, yrow],
color=COL_SLATE_400, linewidth=1.8, zorder=2, solid_capstyle="round")
_aux(ax, aux01, yrow)
x1_router = aux01 + seg
ax.plot([aux01 + _R_AUX, x1_router - _R_ROUTER], [yrow, yrow],
color=COL_SLATE_400, linewidth=1.8, zorder=2, solid_capstyle="round")
mx[1] = x1_router
_router(ax, x1_router, yrow, 1)
aux1 = x1_router + seg
ax.plot([x1_router + _R_ROUTER, aux1 - _R_AUX], [yrow, yrow],
color=COL_SLATE_400, linewidth=1.8, zorder=2, solid_capstyle="round")
_aux(ax, aux1, yrow)
aux2 = aux1 + seg
ax.plot([aux1 + _R_AUX, aux2 - _R_AUX], [yrow, yrow],
color=COL_SLATE_400, linewidth=1.8, zorder=2, solid_capstyle="round")
_aux(ax, aux2, yrow)
x2_router = aux2 + seg
ax.plot([aux2 + _R_AUX, x2_router - _R_ROUTER], [yrow, yrow],
color=COL_SLATE_400, linewidth=1.8, zorder=2, solid_capstyle="round")
mx[2] = x2_router
_router(ax, x2_router, yrow, 2)
ax.annotate("", xy=(aux01, yrow - 0.34), xytext=(aux01, yrow - 0.62),
arrowprops=dict(arrowstyle="-", color=COL_SLATE_400, lw=1.0),
zorder=3)
ax.text(aux01, yrow - 0.70, "1 aux\n(ℓ=2 → 2 kenar)", ha="center", va="top",
fontsize=7.6, color=COL_SLATE_500, zorder=4)
ax.text((aux1 + aux2) / 2, yrow - 0.70, "2 aux\n(ℓ=3 → 3 kenar)",
ha="center", va="top", fontsize=7.6, color=COL_SLATE_500, zorder=4)
ax.text((mx[0] + mx[2]) / 2, yrow + 1.55, "② zincir-açma (birim kenar)",
ha="center", va="center", fontsize=11.5, color=COL_TEXT,
weight="bold", zorder=6)
ax.text((mx[0] + mx[2]) / 2, yrow + 1.18,
"tel ≤ 100r → E = O(r), ağırlıksız BFS geçerli", ha="center",
va="center", fontsize=8.8, color=COL_SLATE_500, style="italic", zorder=6)
ax.add_patch(FancyArrowPatch(
(mx[2] + 0.45, yrow), (P2 - 0.55, yrow), arrowstyle="-|>",
mutation_scale=18, color=COL_AMBER_600, linewidth=2.2, zorder=3))
ax.text((mx[2] + 0.45 + P2 - 0.55) / 2, yrow + 0.28, "süpernode + BFS",
ha="center", va="bottom", fontsize=8.5, color=COL_AMBER_700,
weight="bold", zorder=4)
# ③ SAĞ panel — SÜPERNODE s + tek BFS dalgası + gecikme rozetleri
sx, sy = P2 + 0.0, yrow + 1.55
rrx = P2 + 2.55
rry = {0: yrow + 1.15, 1: yrow + 0.0, 2: yrow - 1.15}
for ring_r in (0.9, 1.7, 2.5, 3.3):
ax.add_patch(Arc((sx, sy), 2 * ring_r, 2 * ring_r, theta1=-72, theta2=8,
edgecolor=COL_AMBER_300, linewidth=1.3,
linestyle=(0, (3, 3)), alpha=0.7, zorder=0))
ax.plot([sx, rrx], [sy, rry[0]], color=COL_ACCENT, linewidth=2.0,
zorder=2, alpha=0.9)
ax.text((sx + rrx) / 2 - 0.05, (sy + rry[0]) / 2 + 0.18, "+1 kenar",
ha="center", va="bottom", fontsize=7.8, color=COL_AMBER_700,
weight="bold", rotation=0, zorder=4)
ax.plot([rrx, rrx], [rry[0], rry[2]], color=COL_SLATE_400,
linewidth=1.6, zorder=1, linestyle=(0, (4, 2)))
ax.add_patch(Circle((sx, sy), 0.34, facecolor=COL_ACCENT,
edgecolor=COL_AMBER_700, linewidth=2.6, zorder=6))
ax.text(sx, sy, "s", ha="center", va="center", fontsize=14,
color=COL_WHITE, weight="bold", zorder=7)
ax.text(sx, sy + 0.50, "süpernode", ha="center", va="bottom", fontsize=9,
color=COL_AMBER_700, weight="bold", style="italic", zorder=7)
for i in (0, 1, 2):
_router(ax, rrx, rry[i], i, is_entry=(i in _ENTRIES))
ax.add_patch(FancyBboxPatch(
(rrx + _R_ROUTER + 0.20, rry[i] - 0.22), 1.62, 0.44,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.8, zorder=5))
ax.text(rrx + _R_ROUTER + 0.30, rry[i],
f"dist={dist_s[i]} − 1 = {latency[i]}", ha="left", va="center",
fontsize=8.8, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(P2 + 1.6, yrow + 2.95, "③ süpernode s + TEK BFS", ha="center",
va="center", fontsize=11.5, color=COL_TEXT, weight="bold", zorder=6)
box_x, box_y = P2 + 0.0, yrow - 2.55
ax.add_patch(FancyBboxPatch(
(box_x, box_y), 4.5, 0.62, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.6, zorder=5))
ax.text(box_x + 2.25, box_y + 0.31,
f"Σ gecikme = {latency[0]} + {latency[1]} + {latency[2]} = {total}",
ha="center", va="center", fontsize=11.5, color=COL_AMBER_700,
weight="bold", zorder=6)
fig.suptitle("Süpernode hilesi: iç içe döngü YERİNE tek BFS dalgası — O(r)",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.975)
ax.text(0.5, 0.985,
"her giriş noktasından ayrı BFS (iç içe döngü) YERİNE: tek sanal düğüm s "
"→ tek enine arama · gecikme(i) = dist(s,i) − 1 · (Solomon 40:18)",
transform=ax.transAxes, ha="center", va="top", fontsize=8.6,
color=COL_SLATE_500, style="italic", zorder=6)
ax.set_xlim(P0 - 0.9, P2 + 4.9)
ax.set_ylim(yrow - 2.95, yrow + 2.75)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Problem 3: Potry Harter ve Büyülü Kapılar {#sec-problem-3-d17}
**İfade.** $n$ odalı bir labirent, her oda $\le 4$ kapı (yani düğüm derecesi $\le 4$). Kapılar kapalı; bazıları **büyülü (enchanted)** — açmak maliyetli, diğerleri bedava. Tüm odaları ziyaret etmek için **açılması gereken minimum büyülü kapı sayısını** $O(n)$'de bul.
::: {.callout-tip title="Yaklaşım — TSP tuzağı: aslında bedava-kapı bileşenlerini say"}
Tuzak: gezgin satıcı (TSP) gibi görünür ama **değil**. İki gözlem onu basitleştirir: (1) bir büyülü kapı açıldıktan sonra açık kalır — ileri-geri geçiş artık bedava; (2) en kısa yol *önemsizdir*, yalnız açılan kapı **sayısı** sorulur. Anahtar: bedava kapılarla birbirine bağlı odalar tek bir "kümedir" (bedava gezilebilen öbek). Geriye kalan, bu öbekleri birbirine bağlamak için kaç büyülü kapı gerektiğidir — bu da bir yayılma ağacı sayımıdır.
:::
> *"we're actually going to remove the enchanted doors."* — Solomon, 51:17
**Çözüm.** Çizge kur: düğüm = oda, kenar = **yalnız büyülü-olmayan (bedava) kapılar**. Bu çizgenin **bağlı bileşenlerini** (full BFS/DFS) hesapla — her bileşen, bedava gezilebilen bir oda öbeğidir. Cevap: **(bağlı bileşen sayısı) $-\,1$**.
Gerekçe: bileşenleri tek düğüm sayan bir meta-çizge düşün; hepsini birbirine bağlayan bir **yayılma ağacının** (spanning tree) kenar sayısı tam olarak (düğüm sayısı $-\,1$) = (bileşen sayısı $-\,1$)'dir, ve her böyle kenar bir büyülü kapıya karşılık gelir.
```python
def min_enchanted_doors(n_rooms, free_doors): # O(n)
adj = make_undirected(free_doors) if free_doors else {}
for r in range(n_rooms):
adj.setdefault(r, []) # izole oda = kendi bileşeni
return len(connected_components(adj)) - 1 # bileşen − 1 (yayılma ağacı)
```
> *"the number of edges in a spanning tree of my graph is exactly the number of vertices in my graph minus 1."* — Solomon, 58:08
**Karmaşıklık.** Derece $\le 4$ → $V = O(n)$ ve $E = O(n)$; bağlı bileşenler $O(V + E) = $ **$O(n)$**.
## Problem 4: Purity Atlantic ve Sabitten Yararlanma {#sec-problem-4-d17}
**İfade.** Bir havayolu; ev şehri + ziyaret edilecek **tam 3 şehir**; toplam **aktarma (connection)** sayısını en aza indiren rotayı bul. $c$ şehir, $f$ uçuş; hedef **$O(c + f)$**.
::: {.callout-tip title="Yaklaşım — verilen sabiti sömür: 3 şehir → O(1) permütasyon ve çift"}
"Tüm-çiftler en kısa yol" gibi görünür ama yalnızca **ilgilenilen 4 şehir** (ev + 3) önemlidir. Burada asıl numara verilen **sabiti** sömürmektir: ziyaret edilecek şehir sayısı tam 3 olduğundan, permütasyon sayısı $3! = 6$ (sabit), gerekli şehir-çifti sayısı $2 \cdot \binom{4}{2} = 12$ (sabit). Bu sabitler patlamadığı için problem doğrusal kalır.
:::
> *"this is one of these problems where you're really taking advantage of the constants that we gave you."* — Solomon, 1:09:06
**Çözüm.** Çizge: düğüm = şehir, kenar = uçuş. 4 ilgili şehrin her çifti (12 yönlü çift) için BFS ile en kısa yol uzunluğunu hesapla (aktarma sayısı = yol uzunluğu $-\,1$). Sonra 6 permütasyonu (ev → 1 → 2 → 3 → ev) gez, her birinin toplam maliyetini bul, minimumu döndür.
```python
def best_three_city_tour(adj, home, cities): # O(c + f)
pts = [home] + list(cities) # 4 ilgili şehir
dist = {}
for p in pts: # 4 BFS (sabit sayıda)
delta, _ = bfs(adj, p)
for q in pts:
dist[(p, q)] = delta.get(q)
best, order = None, None
for perm in permutations(cities): # 3! = 6 permütasyon
legs = [(home, perm[0]), (perm[0], perm[1]),
(perm[1], perm[2]), (perm[2], home)]
total = sum(dist[l] - 1 for l in legs) # aktarma = yol − 1
if best is None or total < best:
best, order = total, perm
return best, order
```
**Karmaşıklık.** $12 \times$ BFS $= 12 \cdot O(c + f) = O(c + f)$; $6$ permütasyon $= O(1)$. Toplam **$O(c + f)$**. (Eğer "$m$ şehir" deselerdi $m!$ patlardı — sabit olması kritik.)
## Problem 5: Cep Küpü — Durum Çizgesi ve Ortada Buluşma {#sec-problem-5-d17}
**İfade.** $2 \times 2$ Rubik küpü (pocket cube). Hamle = (yüz $f_j$, yön $s$). (a) Farklı konfigürasyon sayısının 12 milyondan az olduğunu göster. (b) Her düğümün derecesini bul. (c) Bir küpü en kısa hamle dizisiyle çözen hızlı algoritma.
::: {.callout-tip title="Yaklaşım — durum-uzayı çizgesi + ortada buluşma (çift-yönlü BFS)"}
Klasik **durum-uzayı çizgesi**: düğüm = küpün bir konfigürasyonu (renk durumu), kenar = bir hamle; çözüm = "düz" küpe en kısa yoldur. (a) ve (b) doğrudan sayımla çözülür. (c) için tek-yönlü BFS yavaştır (orta seviyelerde milyonlarca düğüm); **ortada buluşma (meet-in-the-middle)** ile kaynaktan *ve* hedeften *paralel* BFS yürütülür — iki dalga yarı-derinlikte buluşur.
:::
> *"think of every vertex of my graph as being the state of some system and every edge as being a transition."* — Solomon, 1:14:18
**Çözüm.**
**(a) Konfigürasyon üst sınırı.** Bir köşeyi sabitlersek geriye 7 köşe kalır; bunlar $\le 7!$ farklı düzende sıralanabilir ve her köşe 3 yönde dönebilir ($3^7$). Üst sınır:
$$3^7 \cdot 7! = 11\,022\,480 < 12 \text{ milyon}.$$
**(b) Derece.** 3 döndürülebilir yüz $\times$ 2 yön = **derece 6** (her düğümde sabit).
**(c) Ortada buluşma.** Tek-yönlü BFS, çözülebilir tüm konfigürasyonları gezer (~3 milyon; durum çizgesi 3 bağlı bileşenli, çap 14). Bunun yerine kaynaktan *ve* hedeften **paralel** BFS yap; seviye kümeleri ortada kesişir, hiçbir seviye yol uzunluğunun yarısından ($\lceil w/2 \rceil$) büyük olmaz.
```python
def bidirectional_bfs(adj, s, t): # ortada buluşma — Solomon 1:27:08
ds, dt = {s: 0}, {t: 0} # iki ayrı mesafe haritası
qs, qt = deque([s]), deque([t]) # iki ayrı kuyruk (paralel BFS)
while qs and qt:
# küçük cepheyi genişlet; komşu DİĞER taraftaysa → buluşma, dur
... # kesişim: ds[u] + 1 + dt[v]
```
> *"I'm going to run BFS sort of in parallel for two different vertices... The source and the target."* — Solomon, 1:27:08
@fig-meet-middle bu kazancı bir durum-uzayı maketi olan **tam ikili ağaç (127 düğüm)** üzerinde motordan **gerçek** çalıştırarak gösterir: iki uç yaprak $s = 63$ ve $t = 126$ arasındaki en kısa yol köke çıkıp inen 12 kenardır. Tek-yönlü BFS tüm ağacı tarar → **127 ziyaret**; çift-yönlü BFS iki küçük dalgayı yarı-derinlikte (6) buluşturup yalnız **36 ziyaret** eder.
::: {.callout-warning title="Dürüstlük notu — kazanç ÜSTEL dallanmadan gelir, çizgilerden değil"}
Notion'un "üstel büyüme yarıya iner" iddiası **yalnızca üstel dallanan** durum-uzaylarında doğrudur. Figürdeki yan panel bunu bir karşı-örnekle dürüstçe gösterir: dallanma çarpanı 1 olan bir **halka-20** çizgesinde ($s{=}0$, $t{=}10$) çift-yönlü BFS de tek-yönlü BFS de **20 düğüm** ziyaret eder — tasarruf YOKtur. Ortada buluşmanın gerçek kazancı, $N^w$ büyüyen bir uzayı $2 \cdot N^{\lceil w/2 \rceil}$'ye indirmesinden, yani üstel dallanmayı yarı-derinliğe çekmesinden gelir; cep küpü bu üstel rejimde olduğu için kazanç gerçektir.
:::
**Karmaşıklık.** Tek-yönlü BFS, çözülebilir tüm konfigürasyonları (~3 milyon) gezer. Ortada buluşma, gezilen düğüm sayısını ~$2 \cdot N^{\lceil w/2 \rceil}$'ye indirir ($N_i$ = $i$ hamlede erişilen konfigürasyon sayısı).
```{python}
#| label: fig-meet-middle
#| fig-cap: "Ortada buluşma — çift-yönlü BFS üstel büyümeyi yarıya iner — Problem 5 İMZA. Durum-uzayı maketi: tam ikili ağaç 127 düğüm (motordan GERÇEK). İki uç yaprak s=63 (sol-alt) ve t=126 (sağ-alt) amber işaretli; en kısa yol köke çıkıp inen 12 kenar. Tek-yönlü BFS: s'ten TÜM ağaca dev dalga → 127 ziyaret (soluk üçgen). Çift-yönlü: s ve t'den iki küçük amber kama; kökte (yarı-derinlik 6) buluşma yıldızı → 36 ziyaret. Karşılaştırma kutusu: 36 ≪ 127, hiçbir dalga yarı-derinlik 6'yı geçmez (Solomon 1:27:08). YAN panel DÜRÜSTLÜK: halka-20 (dallanma=1) — çift-yönlü 20 = tek-yönlü 20, TASARRUF YOK; kazanç üstel dallanmadan gelir. Alt şerit: pocket cube durum-uzayı 3⁷ × 7! = 11.022.480 < 12 milyon; düğüm derecesi = 3 yüz × 2 yön = 6."
#| fig-width: 11.0
#| fig-height: 7.0
# fig-meet-middle — PS5 Problem 5 İMZA: durum-uzayı + ortada buluşma.
# Veri MOTORDAN: bidirectional_bfs(btree,63,126)==(12,36),
# single_bfs_distance(btree,63,126)==(12,127); halka-20 ziyaret 20==20.
# networkx KULLANILMAZ — elle koordinat. Setup globalleri: plt, math, Circle,
# FancyBboxPatch, Polygon, Wedge, COL_*, make_undirected, bidirectional_bfs,
# single_bfs_distance.
_LEVELS = 7
_APEX = (0.0, 6.2)
_HALF = 3.7
_Y_TOP = 6.0
_Y_BOT = 0.0
def _level_y(k):
return _Y_TOP - k * (_Y_TOP - _Y_BOT) / (_LEVELS - 1)
def _level_halfwidth(k):
return _HALF * k / (_LEVELS - 1)
# --- motor verisi + iç tutarlılık ---
_tree_edges = ([(i, 2 * i + 1) for i in range(63)] +
[(i, 2 * i + 2) for i in range(63)])
btree = make_undirected(_tree_edges)
assert len(btree) == 127, len(btree)
bi_dist, bi_visit = bidirectional_bfs(btree, 63, 126)
sg_dist, sg_visit = single_bfs_distance(btree, 63, 126)
assert (bi_dist, bi_visit) == (12, 36), (bi_dist, bi_visit)
assert (sg_dist, sg_visit) == (12, 127), (sg_dist, sg_visit)
_ring = make_undirected([(i, (i + 1) % 20) for i in range(20)])
rbi_dist, rbi_visit = bidirectional_bfs(_ring, 0, 10)
rsg_dist, rsg_visit = single_bfs_distance(_ring, 0, 10)
assert rbi_visit == 20 and rsg_visit == 20, (rbi_visit, rsg_visit)
fig, ax = plt.subplots(figsize=(11.0, 7.0))
fig.patch.set_facecolor(COL_WHITE)
# (1) Tek-yönlü dalga: tüm üçgeni dolduran soluk taranmış alan
tri = Polygon([_APEX, (-_HALF, _Y_BOT), (_HALF, _Y_BOT)], closed=True,
facecolor=COL_AMBER_100, edgecolor="none", alpha=0.55, zorder=0)
ax.add_patch(tri)
# (2) Ağaç seviye şeritleri + birkaç düğüm noktası
for k in range(_LEVELS):
y = _level_y(k)
hw = _level_halfwidth(k)
if k > 0:
ax.plot([-hw, hw], [y, y], color=COL_SLATE_400,
linewidth=1.0, alpha=0.5, zorder=1)
n_nodes = 2 ** k
shown = min(n_nodes, 9)
xs = [0.0] if shown == 1 else [(-hw + 2 * hw * j / (shown - 1))
for j in range(shown)]
for x in xs:
ax.add_patch(Circle((x, y), 0.055, facecolor=COL_SLATE_500,
edgecolor="none", zorder=2, alpha=0.8))
ax.text(_HALF + 0.30, y, f"sv {k}", ha="left", va="center",
fontsize=8, color=COL_SLATE_500, zorder=2)
ax.plot([_APEX[0], -_HALF], [_APEX[1], _Y_BOT], color=COL_PRIMARY,
linewidth=1.6, zorder=2)
ax.plot([_APEX[0], _HALF], [_APEX[1], _Y_BOT], color=COL_PRIMARY,
linewidth=1.6, zorder=2)
ax.plot([-_HALF, _HALF], [_Y_BOT, _Y_BOT], color=COL_PRIMARY,
linewidth=1.6, zorder=2)
rx, ry = 0.0, _Y_TOP
ax.add_patch(Circle((rx, ry), 0.16, facecolor=COL_BG,
edgecolor=COL_PRIMARY, linewidth=2.0, zorder=5))
ax.text(rx, ry + 0.34, "kök = 0", ha="center", va="bottom",
fontsize=9, color=COL_TEXT, weight="bold", zorder=6)
# (3) Çift-yönlü iki küçük top (s ve t'den)
sx, sy = -_HALF, _Y_BOT
tx, ty = _HALF, _Y_BOT
for (lx, ly, ang0, ang1) in [(sx, sy, 30, 110), (tx, ty, 70, 150)]:
ax.add_patch(Wedge((lx, ly), 2.1, ang0, ang1, facecolor=COL_AMBER_300,
edgecolor=COL_AMBER_600, linewidth=1.4, alpha=0.75,
zorder=3))
ax.add_patch(Circle((sx, sy), 0.18, facecolor=COL_ACCENT,
edgecolor=COL_AMBER_700, linewidth=2.4, zorder=6))
ax.text(sx, sy - 0.42, "s = 63", ha="center", va="top",
fontsize=10, color=COL_AMBER_700, weight="bold", zorder=6)
ax.add_patch(Circle((tx, ty), 0.18, facecolor=COL_ACCENT,
edgecolor=COL_AMBER_700, linewidth=2.4, zorder=6))
ax.text(tx, ty - 0.42, "t = 126", ha="center", va="top",
fontsize=10, color=COL_AMBER_700, weight="bold", zorder=6)
ax.scatter([rx], [ry], marker="*", s=560, color=COL_ACCENT,
edgecolors=COL_AMBER_700, linewidths=1.4, zorder=7)
ax.text(rx, ry - 0.46, "buluşma", ha="center", va="top",
fontsize=8.5, color=COL_AMBER_700, weight="bold",
style="italic", zorder=7)
mid_s = (sx + (rx - sx) * 0.5, sy + (ry - sy) * 0.5)
mid_t = (tx + (rx - tx) * 0.5, ty + (ry - ty) * 0.5)
for (mxx, myy) in [mid_s, mid_t]:
ax.text(mxx, myy, "↑", ha="center", va="center", fontsize=13,
color=COL_AMBER_700, weight="bold", zorder=5)
# (4) Tek-yönlü "dev dalga" + çift-yönlü ziyaret etiketleri
ax.text(0.0, 1.55, "tek-yönlü BFS\ns'ten TÜM ağaca dalga", ha="center",
va="center", fontsize=9.5, color=COL_SLATE_500, style="italic", zorder=4)
ax.text(0.0, 0.78, f"{sg_visit} ziyaret", ha="center", va="center",
fontsize=11, color=COL_SLATE_500, weight="bold", zorder=4)
ax.text(0.0, 3.55, f"çift-yönlü: {bi_visit} ziyaret", ha="center",
va="center", fontsize=11, color=COL_AMBER_700, weight="bold", zorder=6,
bbox=dict(boxstyle="round,pad=0.3", fc=COL_WHITE, ec=COL_ACCENT,
linewidth=1.6))
# (5) Karşılaştırma kutusu (sağ üst)
box_x = 4.55
ax.add_patch(FancyBboxPatch(
(box_x, 3.55), 4.55, 2.55, boxstyle="round,pad=0.05,rounding_size=0.12",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.6, zorder=3))
ax.text(box_x + 0.28, 5.78, "ortada buluşma kazancı", ha="left", va="center",
fontsize=11, color=COL_TEXT, weight="bold", zorder=5)
ax.text(box_x + 0.28, 5.28, f"tek-yönlü: {sg_visit} düğüm (≈ 2¹² yol)",
ha="left", va="center", fontsize=10, color=COL_SLATE_500, zorder=5)
ax.text(box_x + 0.28, 4.82, f"çift-yönlü: {bi_visit} düğüm (2 × 2⁶ yarım)",
ha="left", va="center", fontsize=10, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text(box_x + 0.28, 4.28, f"{bi_visit} ≪ {sg_visit} — hiçbir dalga",
ha="left", va="center", fontsize=10.5, color=COL_ACCENT,
weight="bold", zorder=5)
ax.text(box_x + 0.28, 3.88, "yarı-derinlik 6'yı geçmez (Solomon 1:27:08)",
ha="left", va="center", fontsize=9.5, color=COL_SLATE_500,
style="italic", zorder=5)
# (6) YAN mini panel — halka-20 karşı-örneği (dürüstlük: tasarruf YOK)
ring_cx, ring_cy, ring_r = 7.0, 1.85, 1.05
ax.add_patch(FancyBboxPatch(
(4.55, 0.15), 4.55, 3.10, boxstyle="round,pad=0.05,rounding_size=0.12",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.4, zorder=3))
ax.text(4.83, 2.95, "dürüstlük: halka-20 (dallanma = 1)", ha="left",
va="center", fontsize=10, color=COL_TEXT, weight="bold", zorder=5)
for j in range(20):
ang = math.radians(90 - j * 360 / 20)
x = ring_cx + ring_r * math.cos(ang)
y = ring_cy + ring_r * math.sin(ang)
if j in (0, 10):
fc, ec = COL_ACCENT, COL_AMBER_700
else:
fc, ec = COL_BG, COL_SLATE_400
ax.add_patch(Circle((x, y), 0.085, facecolor=fc, edgecolor=ec,
linewidth=1.4, zorder=5))
ax.add_patch(Circle((ring_cx, ring_cy), ring_r, facecolor="none",
edgecolor=COL_SLATE_400, linewidth=1.2, zorder=4))
ax.text(ring_cx, ring_cy + ring_r + 0.22, "s=0", ha="center", va="bottom",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(ring_cx, ring_cy - ring_r - 0.22, "t=10", ha="center", va="top",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(ring_cx + ring_r + 0.45, ring_cy,
f"çift-yönlü {rbi_visit}\n= tek-yönlü {rsg_visit}\ntasarruf YOK",
ha="left", va="center", fontsize=9, color=COL_SLATE_500,
weight="bold", zorder=5)
# (7) Alt şerit — pocket cube durum sayımı + derece
upper = 3 ** 7 * 5040
assert upper == 11022480, upper
ax.text(0.0, -1.15,
"pocket cube durum-uzayı: 3⁷ × 7! = 11.022.480 < 12 milyon · "
"düğüm derecesi = 3 yüz × 2 yön = 6",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=5)
fig.suptitle("Ortada buluşma: çift-yönlü BFS üstel büyümeyi yarıya iner",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.975)
ax.text(0.0, 6.78,
"s ve t'den iki dalga; kökte (yarı-derinlik) buluşunca dur · "
"durum-uzayı = tam ikili ağaç (127 düğüm)",
ha="center", va="center", fontsize=9.5, color=COL_SLATE_500,
style="italic", zorder=6)
ax.set_xlim(-_HALF - 0.9, 9.4)
ax.set_ylim(-1.7, 7.1)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Ne Öğrendik? {#sec-ne-ogrendik-d17}
::: {.callout-important title="Yedi Taşınabilir Araç"}
Bu oturum, Ders 13-15'in BFS/DFS teorisini beş somut problemde uyguladı ve yedi taşınabilir araç kazandırdı:
1. **Süpernode:** birden çok "hedef"i tek düğüme bağlayıp tek BFS ile hepsine mesafeyi çöz (iç içe döngüden kurtul).
2. **Ağırlıklı → ağırlıksız:** küçük-toplamlı tamsayı ağırlıkları kenar zincirine açıp BFS'in doğrusallığını koru.
3. **Bağlı bileşenler:** "öbek" problemleri (büyülü kapılar) full BFS/DFS + (#bileşen $-\,1$) ile çözülür; yayılma ağacı argümanı.
4. **Sabitten yararlan:** "tam 3 şehir" gibi sabitler permütasyon/çift sayısını $O(1)$ yapar — $m$ olsaydı patlardı.
5. **Durum-uzayı çizgesi:** düğüm = sistem durumu, kenar = geçiş; bulmaca çözmek = en kısa yol (Rubik, satranç, AI arama).
6. **Ortada buluşma:** kaynak + hedeften paralel BFS, üstel arama uzayını yarı-derinliğe indirir (ama yalnız üstel dallanmada kazanç verir).
7. **Üçgen eşitsizliği + arg min/arg max:** yaklaşım sınırlarını ($2R$) ve süpernode mesafelerini kanıtlamanın aracı.
:::
## Sonraki {#sec-sonraki-d17}
::: {.callout-warning title="Ders 18 (L12) — Bellman-Ford"}
Sırada **Ders 18 (L12): Bellman-Ford** var — Jason Ku ile, DAG kısıtını kaldırıyoruz: *herhangi* bir ağırlıklı çizgede (çevrim, hatta negatif ağırlıklı çevrim dahil) tek-kaynak en kısa yol. DAG relaxation'ın "kenar gevşetme" tekniği aynı kalır ama topolojik sıra olmadığından kenarlar tekrar tekrar gevşetilir; negatif ağırlıklı çevrimler de tespit edilir.
:::
