---
title: "Problem Oturumu 6"
subtitle: "Ders 16-19'un uygulaması: beş ağırlıklı en kısa yol problemi indirgemeyle Dijkstra/BFS'e iner — negatif kenarın kırdığı dondurma, Johnson ile ağırlıklı yarıçap, süpernode artı ikili arama, durum makinesi ile graf çoğaltma, darboğaz için modifiye gevşetme"
---
::: {.callout-note title="Oturum bilgisi"}
- **Solomon'un videosu:** [YouTube — Problem Session 6](https://www.youtube.com/watch?v=Md9QOXomxFs) (≈88 dk)
- **OCW sayfası:** [MIT 6.006 Problem Session 6](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_prob6/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 20 (Problem Oturumu 6)
- **Hoca:** Justin Solomon
- **Okuma süresi:** ≈24 dk
:::
## Bu Problem Oturumu Ne Hakkında? {#sec-hakkinda-d20}
Altıncı problem oturumu (Justin Solomon) **ağırlıklı en kısa yollar** üzerine beş problemi işler (@fig-concept-map): Dijkstra'yı elle çalıştırmak, tüm-çiftler en kısa yol (Johnson) ve birkaç "kılık değiştirmiş" en kısa yol problemi. Tema yine **indirgeme**: problem çoğu zaman doğrudan Dijkstra değil, ama **süpernode**, **graf çoğaltma**, **ikili arama** veya **modifiye gevşetme** ile Dijkstra/BFS'e iner.
> *"if there's an obvious algorithm staring us in the phase to solve a given algorithms problem, we should try that first before we try something more clever."* — Solomon, 15:01
Her problem "İfade → Yaklaşım → Çözüm → Karmaşıklık" akışıyla işlenir.
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Problem Oturumu 6'nın kavram haritası: kök (PS6) beş probleme dallanır ve ortadaki ortak tema düğümü beşini birden yönlendirir. Problem 1 Dijkstra'yı elle çalıştırır, sonra negatif bir kenarın dondurma varsayımını nasıl kırdığını gösterir; Problem 2 ağırlıklı yarıçabı Johnson algoritmasını kara kutu olarak çağırıp tanımı doğrudan koda dökerek çözer; Problem 3 sensör problemini bir süpernode artı cevap-üzerinde ikili aramaya indirir; Problem 4 küre kapasitesini durum makinesine çevirip çizgeyi kapasite katmanlarına çoğaltır; Problem 5 darboğaz yolunu toplama yerine min/maks ile gevşeten modifiye bir Dijkstra ile bulur. Ortak tema — zor görünen ağırlıklı problemi doğru indirgemeyle Dijkstra veya BFS'e çevir — Solomon'un her probleme aynı kapıdan girmesini sağlar."
flowchart TD
R["Problem Oturumu 6<br/>(Ders 16-19 uygulaması)"] --> P1["Problem 1<br/>Dijkstra elle + negatif kenar<br/>(dondurma varsayımı kırılır)"]
R --> P2["Problem 2<br/>Ağırlıklı yarıçap<br/>(Johnson + tanımı uygula)"]
R --> P3["Problem 3<br/>Sensörlerden uzak dur<br/>(süpernode + ikili arama)"]
R --> P4["Problem 4<br/>Küre kapasitesi<br/>(durum makinesi / çoğaltma)"]
R --> P5["Problem 5<br/>Nakliye darboğazı<br/>(modifiye gevşetme)"]
CORE["Ortak tema:<br/>zor görünen ağırlıklı problemi<br/>DOĞRU İNDİRGEMEYLE<br/>Dijkstra/BFS'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 20 (PS6) motoru (_engine_PS6.py) + D19/D18/D21/D13
# ağırlıklı SP altyapısı (_engine.py'den dijkstra, ChangeablePQ,
# bellman_ford_classic, johnson, bfs, INF, make_undirected,
# build_dijkstra_example + Johnson yardımcıları add_supernode/reweight) +
# 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ı
# (dijkstra_vs_bf, build_capacity_graph, shortest_no_sadness, widest_path,
# cheapest_at_capacity ...) + 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 ağırlıklı-SP altyapısı + 5 problem fonksiyonu burada
# self-contained INLINE → render dizininden bağımsız (kurs paritesi: PS5 emsali,
# düz INLINE).
# ============================================================================
import math
from collections import deque
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 BFS + D18/D19/D21 AĞIRLIKLI SP ALTYAPISI (_engine.py'den birebir; PS6
# motoru bunları import eder, burada INLINE). INF / bfs / make_undirected /
# ChangeablePQ / dijkstra / bellman_ford_classic / johnson (+ yardımcılar) +
# build_dijkstra_example.
# ===========================================================================
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 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 _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 / D18): 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 (δ_{V−1})
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üğü (cross-link). build O(n), delete_min / decrease_key
O(log n). Öğe = (key, id); id benzersiz."""
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 (cross-link ile konumu O(1) bul). O(log n)."""
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 / D19): 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
def build_dijkstra_example():
"""L13 §6 Notion çalışılan örneği (anlatı sayıları birebir):
s→a(10), s→c(3); c→a(4), c→b(8), c→d(2); d→b(5); a→b(2).
Çıkarılma sırası s(0), c(3), d(5), a(7), b(9); a 10→7, b 11→10→9."""
adj = {"s": ["a", "c"], "a": ["b"], "b": [], "c": ["a", "b", "d"],
"d": ["b"]}
weight = {("s", "a"): 10, ("s", "c"): 3, ("c", "a"): 4, ("c", "b"): 8,
("c", "d"): 2, ("d", "b"): 5, ("a", "b"): 2}
return adj, weight
def add_supernode(adj, weight):
"""Süpernode (L14 §8): s* → her düğüme 0-ağırlık; GELEN kenarı yok."""
s = ("super", "*")
adj2 = {s: list(adj.keys())}
for u in adj:
adj2[u] = list(adj[u])
w2 = dict(weight)
for v in adj:
w2[(s, v)] = 0
return adj2, w2, s
def reweight(adj, weight, h):
"""Potansiyel dönüşümü (L14 §6): w′(u,v) = w(u,v) + h(u) − h(v)."""
return {(u, v): weight[(u, v)] + h[u] - h[v] for u in adj for v in adj[u]}
def johnson(adj, weight):
"""Johnson APSP (L14 §9 / D21, kara kutu): süpernode + BF potansiyeli →
w′ ≥ 0 reweight → V × Dijkstra → geri çevir. Döndürür: {u:{v:δ}} ya da None."""
adj_s, w_s, s = add_supernode(adj, weight) # 1. süpernode
h = bellman_ford_classic(adj_s, w_s, s) # 2. h = δ(s,·)
if any(h[v] == -INF for v in adj):
return None # negatif çevrim
w_prime = reweight(adj, weight, h) # 3. w′ ≥ 0
delta = {}
for u in adj: # 4. V × Dijkstra
dp = dijkstra(adj, w_prime, u)
delta[u] = {v: (dp[v] - h[u] + h[v]) if dp[v] != INF else INF
for v in adj} # 5. geri çevir
return delta
# ===========================================================================
# _engine_PS6.py — PS6 problem motoru (ağırlıklı SP üstüne; INLINE).
# ===========================================================================
# --- Problem 1: Dijkstra dondurma ihlali (Solomon 4:49) ---
def dijkstra_vs_bf(adj, weight, s):
"""Negatif kenarlı çizgede Dijkstra'nın DONDURMA davranışını simüle et
(işlenmiş düğüme dokunmaz — 'frozen in time') ve BF ile karşılaştır.
Döndürür: (dijkstra_d, bf_d, fark_düğümleri, ihlaller)."""
d = {v: INF for v in adj}
d[s] = 0
Q = ChangeablePQ((v, d[v]) for v in adj)
done = set()
violations = []
while len(Q):
u, _ = Q.delete_min()
done.add(u) # DONDUR
for v in adj[u]:
if d[u] == INF:
continue
cand = d[u] + weight[(u, v)]
if v in done: # donmuş düğüme daha kısa yol!
if cand < d[v]:
violations.append((u, v, cand, d[v]))
continue # Dijkstra dokunMAZ (varsayım)
if cand < d[v]:
d[v] = cand
Q.decrease_key(v, d[v])
db = bellman_ford_classic(adj, weight, s)
diff = sorted(v for v in adj if d[v] != db[v])
return d, db, diff, violations
# --- Problem 2: Ağırlıklı yarıçap: Johnson + tanımı uygula (Solomon 15:49) ---
def weighted_radius(adj, weight):
"""ε(u) = maks_v δ(u,v); R = min_u ε(u). Johnson kara kutu. O(V³)."""
delta = johnson(adj, weight)
if delta is None:
return None, None
best, center = None, None
for u in adj:
ecc = max(delta[u][v] for v in adj) # erişilemeyen → INF → ecc INF
if best is None or ecc < best:
best, center = ecc, u
return best, center
# --- Problem 3: Sensörler: süpernode Dijkstra + cevap-üzerinde ikili arama ---
def nearest_sensor_dist(adj, weight, sensors):
"""Süpernode x → tüm sensörlere 0-ağırlık; x'ten Dijkstra → her kavşağın
en yakın sensör mesafesi (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}
def survives_threshold(adj, sensor_dist, s, t, k):
"""G_k = sensör-mesafesi > k olan kavşak alt-çizgesi; s→t BFS var mı?"""
if sensor_dist[s] <= k or sensor_dist[t] <= k:
return False
sub = {v: [u for u in adj[v] if sensor_dist[u] > k]
for v in adj if sensor_dist[v] > k}
delta, _ = bfs(sub, s)
return t in delta
def max_min_sensor_dist(adj, weight, sensors, s, t):
"""En büyük k*: 'her an sensörlerden ≥ k uzakta kalarak s→t' mümkün.
Kavşak mesafelerini SIRALA, dizi indeksinde İKİLİ ARAMA (Solomon 41:44)."""
sd = nearest_sensor_dist(adj, weight, sensors)
cands = sorted(set(sd.values()))
lo, hi, best = 0, len(cands) - 1, None
while lo <= hi:
mid = (lo + hi) // 2
k = cands[mid]
if survives_threshold(adj, sd, s, t, k - 1):
best = k
lo = mid + 1
else:
hi = mid - 1
return best
# --- Problem 4: Durum makinesi: k+1 kapasite katmanı (Solomon 56:42) ---
def build_capacity_graph(paths, stores, k):
"""Katmanlı çizge: düğüm (açıklık, boş-küre-sayısı). Kenar kuralı: kaynak
mağazalıysa çıkışta tam doldur (i' = k − c); değilse i' = i − c (i ≥ c şart)."""
adj, weight = {}, {}
nodes = set()
for a, b, l, c in paths:
nodes.add(a)
nodes.add(b)
for v in nodes:
for i in range(k + 1):
adj[(v, i)] = []
def add_dir(a, b, l, c):
for i in range(k + 1):
if a in stores:
j = k - c # tam kapasiteyle çık − patika critter'ı
if j >= 0:
adj[(a, i)].append((b, j))
weight[((a, i), (b, j))] = l
elif i >= c:
adj[(a, i)].append((b, i - c))
weight[((a, i), (b, i - c))] = l
for a, b, l, c in paths:
add_dir(a, b, l, c)
add_dir(b, a, l, c)
return adj, weight
def shortest_no_sadness(paths, stores, k, s, t):
"""(s, k)'dan Dijkstra; hedef herhangi (t, i) minimumu. ∞ = üzüntü
kaçınılmaz. O(nk log nk)."""
adj, weight = build_capacity_graph(paths, stores, k)
d = dijkstra(adj, weight, (s, k))
return min(d[(t, i)] for i in range(k + 1))
# --- Problem 5: Darboğaz: modifiye Dijkstra (min/maks gevşetme, 1:26:05) ---
def widest_path(adj, capacity, s):
"""Darboğaz-maks: toplama yerine min, küçültme yerine BÜYÜTME —
B(s,v) = maks_yol min-kenar. Max-PQ simülasyonu (anahtarları negatif tut)."""
B = {v: 0 for v in adj}
B[s] = INF # kaynağın darboğazı sonsuz
Q = ChangeablePQ((v, -B[v]) for v in adj)
done = set()
while len(Q):
u, negb = Q.delete_min()
done.add(u)
for v in adj[u]:
if v in done:
continue
cand = min(B[u], capacity[(u, v)]) # darboğaz-üçgeni
if cand > B[v]:
B[v] = cand
Q.decrease_key(v, -cand) # max-PQ: negatif küçült
return B
def cheapest_at_capacity(adj, capacity, cost, s, t, wstar):
"""(2) w* bilinince: yalnız capacity ≥ w* kenarlarını tut; maliyet-ağırlıklı
Dijkstra → en ucuz taşıma."""
sub = {v: [u for u in adj[v] if capacity[(v, u)] >= wstar] for v in adj}
wsub = {(u, v): cost[(u, v)] for u in sub for v in sub[u]}
return dijkstra(sub, wsub, s)[t]
```
::: {.callout-tip title="Yaklaşım — ortak strateji: önce bariz olanı dene, sonra indirgemeyi ara"}
Beş problemin tamamı aynı refleksle başlar: önce "asıl ne soruluyor" ve "hangi sabitler verildi" diye metni soy; eğer ortada bariz bir algoritma (doğrudan Dijkstra, tanımı uygula) varsa onu dene. Bariz değilse problemi **bildiğin bir araca** indirge: süpernode (çok hedef → tek kaynak), graf çoğaltma (konum + durum → katman), cevap-üzerinde ikili arama (log n bütçe → eşik ara) veya modifiye gevşetme (üçgen-eşitsizliği analoğu her güncelleme formülü Dijkstra iskeletine takılır). Bu oturum, ağırlıklı en kısa yol kasını bu beş indirgemeyle çalıştırır.
:::
## Problem 1: Dijkstra Elle ve Negatif Kenarın Kırdığı Varsayım {#sec-problem-1-d20}
**İfade.** (a) Verilen pozitif-ağırlıklı çizgede $s$'den Dijkstra'yı çalıştır (mesafeler + işlem sırası). (b) Bir kenarın ağırlığını **negatif** yap; Dijkstra çalıştırılırsa ne kırılır?
::: {.callout-tip title="Yaklaşım — dondurma varsayımı: işlenen düğüme bir daha dokunma"}
Dijkstra her adımda **en yakın işlenmemiş** düğümü çeker, komşularını üçgen eşitsizliğiyle günceller. Kilit özellik: bir düğüm işlenince (kesinleştirilince) **dondurulur** — bir daha dokunulmaz. Bu açgözlü doğruluk, ağırlıkların negatif-olmamasına dayanır: ileride keşfedilen hiçbir yol, çoktan kesinleşmiş bir düğümü kısaltamaz. Negatif bir kenar bu garantiyi yok eder; çözümü görmek için tek negatif kenarlı çizgeyi elle adım adım çalıştırmak yeterlidir.
:::
> *"once I visit a vertex, I never touch it again. It gets frozen in time."* — Solomon, 4:49
**Çözüm.**
**(a) Pozitif ağırlıklarla Dijkstra.** Kaynaktan başla, en yakın işlenmemiş düğümü çek, kenarlarını gevşet, dondur; sırayla tüm düğümler kesinleşir. Çıkarılma sırası mesafeye göre artar (Ders 19 Gözlem 1'in sonucu: ağırlık ≥ 0 → mesafe en kısa yol boyunca artar).
**(b) Negatif kenar dondurmayı kırar.** Çizgeye bir negatif kenar (örneğimizde $b \to c$ ağırlık $-8$) eklenince, $b$ işlendiğinde $b \to c$ üzerinden $9 + (-8) = 1 < 3$ bulunur — yani $c$'ye daha kısa bir yol keşfedilir, **ama $c$ çoktan dondurulmuştur**. Dijkstra'nın "işlenen düğüme bir daha dokunma" varsayımı kırılır; $c$'yi kuyruğa geri eklemek gerekir ama Dijkstra buna izin vermez. (Bu örnekte ek olarak $b \to c \to d \to b = -8 + 2 + 5 = -1$ negatif bir çevrim oluşur, bu yüzden çevrime erişilen her düğüm Bellman-Ford'da **eksi sonsuz** olur.)
```python
def dijkstra_vs_bf(adj, weight, s): # dondurma davranışını izle
d = {v: INF for v in adj}; d[s] = 0
Q = ChangeablePQ((v, d[v]) for v in adj)
done = set(); violations = []
while len(Q):
u, _ = Q.delete_min()
done.add(u) # DONDUR
for v in adj[u]:
cand = d[u] + weight[(u, v)]
if v in done: # donmuş düğüme daha kısa yol!
if cand < d[v]:
violations.append((u, v, cand, d[v]))
continue # Dijkstra DOKUNMAZ (varsayım)
if cand < d[v]:
d[v] = cand; Q.decrease_key(v, d[v])
return d, bellman_ford_classic(adj, weight, s), ..., violations
```
> *"that breaks our assumption, which is that as soon as I visit a vertex, I never have to touch it again."* — Solomon, 10:59
@fig-frozen-violation bu çöküşü motordan **gerçek** verilerle gösterir: örnek çizgeye $b \to c\,(-8)$ kenarı eklenir; donmuş davranışı taklit eden Dijkstra hâlâ $\{s{:}0,\,a{:}7,\,b{:}9,\,c{:}3,\,d{:}5\}$ (negatif kenarı yok sayan, **yanlış** sonuç) verirken, ihlal listesi tam olarak $[(b, c, 1, 3)]$'tür — $b$ işlenince $9 + (-8) = 1 < 3 = d[c]$ keşfedilir ama $c$ donmuştur. Bellman-Ford ise negatif çevrimi yakalar: $s$ hariç tüm düğümler eksi sonsuza düşer.
**Karmaşıklık.** (a) standart Dijkstra. (b) negatif kenar → Dijkstra geçersiz; **Bellman-Ford** gerekir (Ders 18).
```{python}
#| label: fig-frozen-violation
#| fig-cap: "Negatif kenar dondurmayı KIRAR — Problem 1 İMZA. Örnek çizgeye b→c(−8) eklenir (motordan GERÇEK). SOL: çizge (D19 yerleşimi); b→c kenarı kalın amber kesikli; Dijkstra işleme sıra rozetleri #1..#5; c düğümü 'd[c]=3'te DONDURULDU (#2)' kilit ikonu; b işlenince (#5) b→c üzerinden 9+(−8)=1 < 3 keşfi → ihlal okunda YASAK işareti (donmuş düğüme dokunulamaz, Solomon 4:49); negatif çevrim notu b→c→d→b = −1. SAĞ: düğüm / Dijkstra / Bellman-Ford tablosu (motor değerleri BİREBİR) — Dijkstra {s:0,a:7,b:9,c:3,d:5} (negatif kenarı ihmal etti, YANLIŞ), Bellman-Ford s hariç hepsi 'eksi sonsuz' (negatif çevrim yakalandı); fark hücreleri amber. Alt not: tek negatif kenar hem dondurma ihlali hem negatif çevrim doğurur; çözüm Bellman-Ford (Ders 18)."
#| fig-width: 11.0
#| fig-height: 6.8
# fig-frozen-violation — PS6 Problem 1 İMZA: negatif kenar Dijkstra dondurmasını kırar.
# Veri MOTORDAN: dijkstra_vs_bf(adj+b→c(−8)) → dd={s:0,a:7,b:9,c:3,d:5},
# db=hepsi −∞ (s hariç), viol=[('b','c',1,3)]. networkx KULLANILMAZ — elle koordinat.
# Setup globalleri: plt, Circle, FancyBboxPatch, FancyArrowPatch, COL_*,
# build_dijkstra_example, dijkstra_vs_bf, INF.
# Çizge yerleşimi (elle koordinat; networkx YOK) — brief sabit:
# s(0,1) c(1,0.4) a(1,1.6) d(2,0.4) b(2.6,1)
_POS = {
"s": (0.0, 1.0), "c": (1.0, 0.4), "a": (1.0, 1.6),
"d": (2.0, 0.4), "b": (2.6, 1.0),
}
_RAD = 0.22
_ORDER = ["s", "c", "d", "a", "b"] # Dijkstra çıkarılma sırası
def _build_neg_graph():
adj0, w0 = build_dijkstra_example()
adj = {k: list(v) for k, v in adj0.items()}
weight = dict(w0)
adj["b"].append("c") # negatif kenar ekle
weight[("b", "c")] = -8
return adj, weight
def _draw_lock(ax, x, y, s=0.10):
ax.add_patch(FancyBboxPatch(
(x - s, y - s), 2 * s, 1.7 * s,
boxstyle="round,pad=0.005,rounding_size=0.02",
fc=COL_AMBER_300, ec=COL_AMBER_700, linewidth=1.4, zorder=8))
ax.add_patch(FancyArrowPatch(
(x - s * 0.6, y + 0.7 * s), (x + s * 0.6, y + 0.7 * s),
connectionstyle="arc3,rad=-1.0", arrowstyle="-",
mutation_scale=1, color=COL_AMBER_700, linewidth=1.6, zorder=8))
ax.plot([x], [y + 0.35 * s], marker="o", markersize=2.2,
color=COL_AMBER_700, zorder=9)
def _draw_forbidden(ax, x, y, r=0.15):
ax.add_patch(Circle((x, y), r, facecolor="none", edgecolor=COL_AMBER_700,
linewidth=2.4, zorder=9))
d = r * 0.72
ax.plot([x - d, x + d], [y + d, y - d], color=COL_AMBER_700,
linewidth=2.4, zorder=9)
def _draw_graph(ax, ox, oy, adj, weight, order):
def P(v):
x, y = _POS[v]
return (ox + x, oy + y)
proc_idx = {v: i + 1 for i, v in enumerate(order)}
for u in adj:
for v in adj[u]:
wt = weight[(u, v)]
ux, uy = P(u)
vx, vy = P(v)
is_neg = (u, v) == ("b", "c")
cstyle = "arc3,rad=-0.30" if is_neg else "arc3,rad=0.0"
ecol = COL_ACCENT if is_neg else COL_PRIMARY
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=12,
color=ecol, linewidth=2.8 if is_neg else 1.6,
linestyle=(0, (4, 2)) if is_neg else "-",
shrinkA=_RAD * 70, shrinkB=_RAD * 70,
connectionstyle=cstyle, zorder=3 if is_neg else 2))
if is_neg:
mx, my = (ux + vx) * 0.5 - 0.30, (uy + vy) * 0.5 + 0.02
else:
mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5
tcol = COL_AMBER_700 if is_neg else COL_TEXT
ax.add_patch(FancyBboxPatch(
(mx - 0.145, my - 0.115), 0.29, 0.23,
boxstyle="round,pad=0.01,rounding_size=0.05",
fc=COL_AMBER_100 if is_neg else COL_WHITE,
ec=COL_ACCENT if is_neg else COL_SLATE_400,
linewidth=1.8 if is_neg else 1.0, zorder=6))
ax.text(mx, my, str(wt), ha="center", va="center",
fontsize=8.5 if is_neg else 8,
color=tcol, weight="bold", zorder=7)
for v, (x, y) in _POS.items():
is_src = (v == "s")
is_frozen = (v == "c")
px, py = P(v)
if is_src:
fc, ec, tc, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 2.6
elif is_frozen:
fc, ec, tc, lw = COL_BG, COL_ACCENT, COL_TEXT, 2.6
else:
fc, ec, tc, lw = COL_BG, COL_PRIMARY, COL_TEXT, 1.8
ax.add_patch(Circle((px, py), _RAD, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(px, py, v, ha="center", va="center", fontsize=11,
color=tc, weight="bold", zorder=6)
n = proc_idx[v]
bx, by = px - _RAD - 0.04, py + _RAD + 0.04
ax.add_patch(Circle((bx, by), 0.105, facecolor=COL_PRIMARY,
edgecolor=COL_WHITE, linewidth=1.2, zorder=7))
ax.text(bx, by, "#%d" % n, ha="center", va="center", fontsize=6.2,
color=COL_WHITE, weight="bold", zorder=8)
sx, sy = P("s")
ax.text(sx - _RAD - 0.14, sy, "kaynak", ha="right", va="center",
fontsize=7, color=COL_AMBER_700, weight="bold", zorder=6)
cx, cy = P("c")
_draw_lock(ax, cx + _RAD + 0.16, cy - 0.30)
ax.text(cx + _RAD + 0.36, cy - 0.30, "d[c]=3'te\nDONDURULDU (#2)",
ha="left", va="center", fontsize=7, color=COL_AMBER_700,
weight="bold", zorder=7)
_draw_forbidden(ax, cx, cy + _RAD + 0.06, r=0.135)
ax.text(ox - 0.30, cy + 0.18, "9 + (−8) = 1 < 3", ha="center", va="center",
fontsize=7.5, color=COL_AMBER_700, weight="bold",
family="monospace", zorder=8)
ax.text(ox - 0.30, cy - 0.04, "keşif ama c donmuş", ha="center",
va="center", fontsize=6.8, color=COL_AMBER_700, style="italic",
zorder=8)
ax.text(ox - 0.30, cy - 0.24, "→ dokunulamaz", ha="center", va="center",
fontsize=6.8, color=COL_AMBER_700, style="italic", zorder=8)
ax.add_patch(FancyArrowPatch(
(ox + 0.10, cy + 0.12), (cx - _RAD - 0.02, cy + 0.10), arrowstyle="-|>",
mutation_scale=9, color=COL_AMBER_700, linewidth=1.3,
linestyle=(0, (3, 2)), zorder=4))
ax.text(ox + 1.25, oy - 0.30,
"negatif çevrim b→c→d→b = −8+2+5 = −1", ha="center", va="center",
fontsize=7.2, color=COL_AMBER_700, style="italic", weight="bold",
zorder=6)
ax.text(ox + 1.25, oy + 2.34,
"Solomon PS6 4:49 — kesinleştirilen düğüm \"zamanda donar\"",
ha="center", va="center", fontsize=7, color=COL_SLATE_500,
style="italic", zorder=6)
def _draw_compare_table(ax, ox, oy, nodes, d_dij, d_bf, diff_nodes):
col_w = [0.95, 1.45, 1.85]
row_h = 0.52
x_edges = [ox]
for w in col_w:
x_edges.append(x_edges[-1] + w)
table_w = sum(col_w)
headers = ["düğüm", "Dijkstra", "Bellman-Ford"]
hy = oy
for c, htxt in enumerate(headers):
ax.add_patch(FancyBboxPatch(
(x_edges[c] + 0.02, hy - row_h), col_w[c] - 0.04, row_h,
boxstyle="square,pad=0.0", fc=COL_PRIMARY, ec=COL_PRIMARY,
linewidth=1.2, zorder=3))
ax.text(x_edges[c] + col_w[c] * 0.5, hy - row_h * 0.5, htxt,
ha="center", va="center", fontsize=9, color=COL_WHITE,
weight="bold", zorder=4)
def fmt(val):
if val == INF:
return "+sonsuz"
if val == -INF:
return "eksi sonsuz"
return str(val)
for r, v in enumerate(nodes):
ry = oy - (r + 2) * row_h
is_diff = v in diff_nodes
cells = [v, fmt(d_dij[v]), fmt(d_bf[v])]
for c, txt in enumerate(cells):
if c == 0:
fc, ec, tcol, lw = COL_BG, COL_SLATE_400, COL_TEXT, 1.0
elif is_diff:
fc, ec, tcol, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 1.8
else:
fc, ec, tcol, lw = COL_WHITE, COL_SLATE_400, COL_TEXT, 1.0
ax.add_patch(FancyBboxPatch(
(x_edges[c] + 0.02, ry), col_w[c] - 0.04, row_h - 0.02,
boxstyle="square,pad=0.0", fc=fc, ec=ec, linewidth=lw, zorder=3))
fsz = 8.0 if (c == 2 and txt == "eksi sonsuz") else 10
ax.text(x_edges[c] + col_w[c] * 0.5, ry + row_h * 0.5, txt,
ha="center", va="center", fontsize=fsz,
color=tcol,
weight="bold" if (c > 0 and is_diff) else
("bold" if c == 0 else "normal"),
family="monospace" if (c > 0 and txt != "eksi sonsuz")
else "sans-serif", zorder=4)
ax.text(ox + table_w * 0.5, oy + 0.30,
"Aynı çizge — iki algoritma, FARKLI yanıt", ha="center", va="center",
fontsize=9.5, color=COL_TEXT, weight="bold", zorder=4)
ly = oy - (len(nodes) + 1) * row_h - 0.20
ax.add_patch(FancyBboxPatch(
(ox + 0.05, ly - 0.10), 0.26, 0.20, boxstyle="square,pad=0.0",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.8, zorder=3))
ax.text(ox + 0.40, ly,
"= fark (Dijkstra yanlış) · s hariç tüm düğümler",
ha="left", va="center", fontsize=7.8, color=COL_AMBER_700,
style="italic", zorder=4)
return table_w
# --- motor verisi + iç tutarlılık (figür yalnız bunu çizer) ---
adj_n, weight_n = _build_neg_graph()
d_dij, d_bf, diff, viol = dijkstra_vs_bf(adj_n, weight_n, "s")
diff_nodes = set(diff)
assert d_dij == {"s": 0, "a": 7, "b": 9, "c": 3, "d": 5}, d_dij
assert d_bf == {"s": 0, "a": -INF, "b": -INF, "c": -INF, "d": -INF}, d_bf
assert diff == ["a", "b", "c", "d"], diff
assert viol == [("b", "c", 1, 3)], viol
_cyc = weight_n[("b", "c")] + weight_n[("c", "d")] + weight_n[("d", "b")]
assert _cyc == -1, _cyc
fig, ax = plt.subplots(figsize=(11.0, 6.8))
fig.patch.set_facecolor(COL_WHITE)
gx, gy = 0.0, 0.0
_draw_graph(ax, gx, gy, adj_n, weight_n, _ORDER)
tx, ty = 4.7, 2.55
_draw_compare_table(ax, tx, ty, ["s", "a", "b", "c", "d"], d_dij, d_bf, diff_nodes)
fig.suptitle(
"Negatif kenar dondurmayı KIRAR — \"kesinleştir, bir daha dokunma\" varsayımı çöker",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text(gx + 1.25, gy + 2.62,
"örnek çizgeye b→c(−8) eklendi · PS6 Problem 1 (Solomon) — ihlal "
"[('b','c',1,3)]",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=5)
note_y = gy - 0.95
ax.text(gx, note_y,
"Tek negatif kenar HEM dondurma ihlalini doğurur (b→c ile 9−8 = 1 < 3, "
"ama c donmuş → güncellenmez) HEM de (burada)",
ha="left", va="center", fontsize=8.6, color=COL_TEXT, weight="bold",
zorder=5)
ax.text(gx, note_y - 0.32,
"negatif çevrim yaratır (b→c→d→b = −1) → erişilen her düğüm BF'de "
"eksi sonsuz. Dijkstra'nın açgözlü varsayımı çöker.",
ha="left", va="center", fontsize=8.6, color=COL_SLATE_500, zorder=5)
ax.text(gx, note_y - 0.62,
"Çözüm: Bellman-Ford (Ders 18) — negatif kenarı + çevrimi işler. "
"PS6 Problem 1 bunu elle adım adım çalıştırır.",
ha="left", va="center", fontsize=8.6, color=COL_AMBER_700,
style="italic", weight="bold", zorder=5)
ax.set_xlim(-1.05, tx + 4.6)
ax.set_ylim(note_y - 0.95, gy + 2.95)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Problem 2: Ağırlıklı Yarıçap ve Johnson {#sec-problem-2-d20}
**İfade.** Ağırlıklı yönlü çizge (negatif ağırlık olabilir, negatif çevrim **yok**). **Ağırlıklı eksantriklik** $\varepsilon(u) = \max_v \delta(u, v)$; **ağırlıklı yarıçap** $= \min_u \varepsilon(u)$. Yarıçapı $O(V^3)$'te bul.
::: {.callout-tip title="Yaklaşım — akıllı olma, tanımı doğrudan algoritmaya çevir"}
Bu, Ders 17 (PS5)'teki yarıçap probleminin ağırlıklı versiyonudur. Burada hile aramaya gerek yok: tanımı doğrudan algoritmaya dök. Eksantriklik için tüm-çiftler mesafe gerekir; bunu **Johnson algoritması** verir (Ders 21'de açılacak; negatif çevrim olmadığından çalışır). Johnson'ı bir kara kutu olarak çağır, sonra iç içe döngüyle eksantriklikleri ve minimumlarını topla. Karmaşıklık bütçesi $O(V^3)$ bu naif yaklaşımı zaten rahatça karşılar.
:::
> *"that's called Johnson's algorithm."* — Solomon, 15:49
**Çözüm.** Üç adım, doğrudan tanımdan:
1. **Johnson** ile tüm $\delta(u, v)$ çiftlerini hesapla — $O(V \cdot E + V^2 \log V) \le O(V^3)$ (basit çizgede $E \le 2V^2$).
2. Her $u$ için iç içe döngüyle $\varepsilon(u) = \max_v \delta(u, v)$ — $O(V^2)$.
3. $\min_u \varepsilon(u)$ — $O(V)$.
İlk terim baskındır, dolayısıyla toplam $O(V^3)$ olur ve problem bütçesiyle uyumludur.
```python
def weighted_radius(adj, weight): # O(V³) — tanımı uygula
delta = johnson(adj, weight) # tüm-çiftler δ (kara kutu)
if delta is None:
return None, None # negatif çevrim → tanımsız
best, center = None, None
for u in adj: # her u: ε(u) = maks δ
ecc = max(delta[u][v] for v in adj)
if best is None or ecc < best: # R = min_u ε(u)
best, center = ecc, u
return best, center
```
Johnson burada **kara kutu**dur — içinde süpernode + Bellman-Ford potansiyeli ile kenarları negatif-olmayana yeniden ağırlıklandırıp $V$ kez Dijkstra çalıştırır, ama bu problem için önemli olan tek şey çıktısının tüm-çiftler mesafe tablosu olduğudur. Motor üzerinde bir doğrulama: rastgele üretilen 30 negatif-çevrimsiz çizgede `weighted_radius` (Johnson tabanlı) ile her düğümden Bellman-Ford koşan bağımsız bir $V \times \text{BF}$ tanığı **birebir** aynı yarıçapı verir — yani indirgemenin doğruluğu farklı bir mekanizmayla teyit edilir.
**Karmaşıklık.** $O(V^3)$ — yalnızca "tanımı uygula" ile, hiçbir akıllı numara olmadan.
## Problem 3: Atniss ve Sensörler — Süpernode ve İkili Arama {#sec-problem-3-d20}
**İfade.** $n$ kavşaklı boru ağı, her kavşak derecesi $\le 4$ (pozitif uzunluklu borular), bazı kavşaklarda **hareket sensörü**. Atniss, $s$'den $t$'ye giderken **herhangi sensöre olan minimum uzaklığı en büyük tutan** yolu ister; $O(n \log n)$'de.
::: {.callout-tip title="Yaklaşım — kılık değiştirmiş erişilebilirlik: iki katman + cevap-üzerinde ikili arama"}
Bu doğrudan en kısa yol *değil*; kılık değiştirmiş bir **erişilebilirlik** problemidir. İki katmana ayır: (i) her kavşağın en yakın sensöre uzaklığını bul, (ii) "en az $k$ uzakta kalarak $s \to t$ gidilir mi?" sorusunu $k$ üzerinde **ikili arama** ile çöz. İkinci katmanın ipucu sınıfta yalnız bir algoritmanın $\log n$ sürede koştuğudur: ikili arama. Yanıt monoton (büyük $k$ geçilebilir ise küçük $k$ de geçilir) olduğundan, eşiği sıralı bir dizi indeksinde aramak güvenlidir.
:::
> *"it's sort of a readability problem in disguise."* — Solomon, 24:16
**Çözüm.** Üç adımda:
1. **Süpernode** $x$ ekle, tüm sensörlere 0-ağırlıklı kenarla bağla; $x$'ten Dijkstra → her kavşağın en yakın sensör mesafesi ($O(n \log n)$).
> *"add a new vertex... and make that vertex distance 0 to every one of my sensors."* — Solomon, 31:10
2. $G_k$ = sensör-mesafesi $> k$ olan kavşakların alt-çizgesi; $G_k$'da BFS, "$k$ yarıçapı dışında $s \to t$ var mı?" sorusunu $O(n)$'de yanıtlar.
3. En büyük $k^\star$'yı bul: kavşakları sensör-mesafesine göre **sırala** ($O(n \log n)$), dizi **indeksi** üzerinde ikili arama ($\log n$ adım $\times\ O(n)$ BFS).
> *"we only have one algorithm that runs in log n time in this class, which is binary search."* — Solomon, 41:44
```python
def max_min_sensor_dist(adj, weight, sensors, s, t): # O(n log n)
sd = nearest_sensor_dist(adj, weight, sensors) # 1. süpernode Dijkstra
cands = sorted(set(sd.values())) # eşik adayları (sıralı)
lo, hi, best = 0, len(cands) - 1, None
while lo <= hi: # 3. indeks üzerinde ikili arama
mid = (lo + hi) // 2; k = cands[mid]
if survives_threshold(adj, sd, s, t, k - 1): # 2. G_k'da BFS
best = k; lo = mid + 1
else:
hi = mid - 1
return best
```
İndirgemenin doğruluğunu küçük bir çizgede bağımsız bir tanık teyit eder: tüm basit yolları DFS ile gezip her yolun minimum sensör-mesafesini alan, sonra bunların maksimumunu döndüren kaba-kuvvet, ikili aramanın bulduğu $k^\star$ ile **aynı** değeri verir.
**Karmaşıklık.** Dijkstra $O(n \log n)$ + ikili arama $\log n \times O(n)$ = $O(n \log n)$.
## Problem 4: Ashley ve Critter'lar — Graf Çoğaltma ve Durum Makinesi {#sec-problem-4-d20}
**İfade.** $n$ açıklık, her açıklık derecesi $\le 5$; her patika (uzunluk $l_t$, üzerinde $c_t$ critter). Yürüyen kişi her patikadaki tüm critter'ları toplamak **zorunda**; $k$ küre kapasitesi var, mağazalarda boşaltır. Küre yetmezse "üzülür". Üzülmeden en kısa yol; bütçe $O(nk \log nk)$.
::: {.callout-tip title="Yaklaşım — durum makinesi: konuma 'kalan kapasite' durumunu ekle, çizgeyi katmanla"}
Klasik **durum makinesi / graf çoğaltma**: konuma ek olarak "kalan kapasite" durumunu izle. Her fiziksel açıklığı $k+1$ kopyaya çoğalt — her kopya "kaç boş küre kaldı" bilgisini taşır. Bir critter patikası kapasiteyi tüketir; mağaza tam doldurur. Yeterli boş küre olmadan bir patikaya girilemez (o kenar yoktur), bu yüzden "üzülme" durumu otomatik olarak modelin dışında kalır. Bu çoğaltılmış çizgede Dijkstra, hem konumu hem kapasiteyi takip ederek doğru cevabı verir.
:::
> *"it's kind of like a state machine."* — Solomon, 56:42
**Çözüm.** Her açıklığın **$k+1$ kopyası**: $v_{c,i}$ = "açıklık $c$, $i$ boş küre". Kenarlar (her $(a, b)$ patikası, $c$ critter):
- **Mağaza yoksa:** $v_{a,i} \to v_{b,i-c}$ ($i \ge c$ gereği — yoksa üzülür);
- **Mağaza varsa:** $v_{a,i} \to v_{b,k-c}$ (önce boşalt, sonra topla).
Burada $V = O(kn)$ ve $E = O(kn)$. Dijkstra'yı $v_{s,k}$'dan çalıştır; hedef herhangi $v_{t,i}$. Sonuç $\infty$ ise "**üzüntü kaçınılmaz**". (Bu çizge DAG **değil** — iki mağaza arası ileri-geri bedava çevrim olabilir, bu yüzden DAG relaxation değil Dijkstra gerekir.)
```python
def shortest_no_sadness(paths, stores, k, s, t): # O(nk log nk)
adj, weight = build_capacity_graph(paths, stores, k) # k+1 kapasite katmanı
d = dijkstra(adj, weight, (s, k)) # tam küre ile başla
return min(d[(t, i)] for i in range(k + 1)) # herhangi (t,i) min; ∞ = üzüntü
```
@fig-state-machine bu çoğaltmayı motordan **gerçek** bir küçük örnekle gösterir: $s \xrightarrow{l=2,\,c=2} m \xrightarrow{l=3,\,c=1} t$, mağaza $m$, kapasite $k=2$. Katmanlı çizgede tek geçerli yol $(s, 2) \to (m, 0) \to (t, 1)$ ağırlık $2 + 3 = 5$'tir; $m$ mağazalı olduğu için çıkışta küre tam dolar ($k - c = 2 - 1 = 1$). Kapasite $k=1$'e düşürülünce $s \to m$ patikası $c = 2$ critter ister ama maksimum $i = 1 < 2$ olduğundan o kenar hiç oluşmaz → sonuç $\infty$ = **üzüntü kaçınılmaz**.
**Karmaşıklık.** Dijkstra, $O(kn)$ boyutlu çizgede → $O(nk \log nk)$.
```{python}
#| label: fig-state-machine
#| fig-cap: "Durum makinesi — konum + kalan küre = düğüm; çizgeyi k+1 katmana çoğalt — Problem 4 İMZA. Üç panel (motordan GERÇEK: paths=[(s,m,2,2),(m,t,3,1)], stores={m}). ① FİZİKSEL HAT: s –[ℓ=2, 2 critter]– m(MAĞAZA ikonu) –[ℓ=3, 1 critter]– t. ② KATMANLI ÇİZGE (k=2): 3 sütun (s/m/t) × 3 satır (boş küre i=2/1/0); aktif en kısa yol amber (s,2)→(m,0) w=2 (2 critter toplandı), m MAĞAZALI çıkışta boşalt (m,0)→(t,1) w=3; geçersiz örnek (s,1)→m YOK (i=1 < c=2 → uyulur); yol toplam (s,2)→(m,0)→(t,1) = 2+3 = 5 rozeti. ③ k=1 PANEL: hiçbir s→m kenarı yok (patika 2 critter ister, maks i=1) → δ(s→t)=+∞ üzüntü kaçınılmaz. Alt not: Solomon 56:42, V=O(nk), Dijkstra O(nk log nk)."
#| fig-width: 11.0
#| fig-height: 6.4
# fig-state-machine — PS6 Problem 4 İMZA: graf çoğaltma / durum makinesi.
# Veri MOTORDAN: shortest_no_sadness(...,2,...)==5, shortest_no_sadness(...,1,...)==INF;
# (s,2)->(m,0) w=2, (m,0)->(t,1) w=3. networkx KULLANILMAZ — elle koordinat.
# Setup globalleri: plt, Circle, FancyBboxPatch, FancyArrowPatch, Polygon, COL_*,
# build_capacity_graph, shortest_no_sadness, dijkstra, INF.
_PATHS = [("s", "m", 2, 2), ("m", "t", 3, 1)]
_STORES = {"m"}
_R_PHYS = 0.30
_R_LAYER = 0.21
def _draw_store_icon(ax, x, y, s=0.16):
ax.add_patch(FancyBboxPatch(
(x - s, y - s), 2 * s, 1.55 * s, boxstyle="square,pad=0.0",
fc=COL_AMBER_300, ec=COL_AMBER_700, linewidth=1.4, zorder=8))
ax.add_patch(Polygon(
[(x - s * 1.25, y + 0.55 * s), (x + s * 1.25, y + 0.55 * s),
(x, y + 1.45 * s)], closed=True, fc=COL_AMBER_600, ec=COL_AMBER_700,
linewidth=1.3, zorder=9))
ax.add_patch(FancyBboxPatch(
(x - s * 0.35, y - s), s * 0.7, 0.9 * s, boxstyle="square,pad=0.0",
fc=COL_AMBER_700, ec=COL_AMBER_700, linewidth=0.5, zorder=10))
def _draw_forbidden_sm(ax, x, y, r=0.16):
ax.add_patch(Circle((x, y), r, facecolor="none", edgecolor=COL_AMBER_700,
linewidth=2.4, zorder=9))
d = r * 0.72
ax.plot([x - d, x + d], [y + d, y - d], color=COL_AMBER_700,
linewidth=2.4, zorder=9)
def _draw_physical(ax, ox, oy):
pos = {"s": (ox + 0.0, oy), "m": (ox + 1.9, oy), "t": (ox + 3.8, oy)}
edges = [("s", "m", 2, 2), ("m", "t", 3, 1)]
for (u, v, l, c) in edges:
x0, y0 = pos[u]
x1, y1 = pos[v]
ax.plot([x0 + _R_PHYS, x1 - _R_PHYS], [y0, y1], color=COL_PRIMARY,
linewidth=2.4, zorder=2, solid_capstyle="round")
mxp = (x0 + x1) / 2
ax.add_patch(FancyBboxPatch(
(mxp - 0.46, y0 + 0.18), 0.92, 0.42,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_BG, ec=COL_AMBER_700, linewidth=1.6, zorder=3))
ax.text(mxp, y0 + 0.39, f"ℓ={l}", ha="center", va="center",
fontsize=10, color=COL_AMBER_700, weight="bold", zorder=4)
ax.text(mxp, y0 - 0.30, f"{c} critter", ha="center", va="center",
fontsize=8.2, color=COL_SLATE_500, style="italic", zorder=4)
for v, (x, y) in pos.items():
is_store = v in _STORES
fc = COL_AMBER_100 if is_store else COL_BG
ec = COL_ACCENT if is_store else COL_PRIMARY
lw = 2.8 if is_store else 2.0
ax.add_patch(Circle((x, y), _R_PHYS, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, y, v, ha="center", va="center", fontsize=13,
color=COL_TEXT, weight="bold", zorder=6)
mx, my = pos["m"]
_draw_store_icon(ax, mx, my + _R_PHYS + 0.30)
ax.text(mx, my + _R_PHYS + 0.66, "MAĞAZA", ha="center", va="bottom",
fontsize=7.6, color=COL_AMBER_700, weight="bold", zorder=8)
ax.text((pos["s"][0] + pos["t"][0]) / 2, oy + 1.42,
"① fiziksel critter hattı", ha="center", va="center",
fontsize=11.5, color=COL_TEXT, weight="bold", zorder=6)
ax.text((pos["s"][0] + pos["t"][0]) / 2, oy + 1.08,
"her patika belli sayıda critter ister — küreyi tüketir",
ha="center", va="center", fontsize=8.4, color=COL_SLATE_500,
style="italic", zorder=6)
ax.text((pos["s"][0] + pos["t"][0]) / 2, oy - 0.70,
"mağazada (m) küreyi TAM doldur: \"önce boşalt, sonra topla\"",
ha="center", va="center", fontsize=8.2, color=COL_AMBER_700,
weight="bold", zorder=6)
return pos
def _draw_layered(ax, ox, oy, adj, weight, path_dist):
cols = ["s", "m", "t"]
col_x = {"s": ox + 0.0, "m": ox + 1.85, "t": ox + 3.70}
row_y = {2: oy + 1.30, 1: oy + 0.0, 0: oy - 1.30}
def P(node):
v, i = node
return (col_x[v], row_y[i])
path_edges = {(("s", 2), ("m", 0)), (("m", 0), ("t", 1))}
for node in adj:
for nb in adj[node]:
if nb not in adj:
continue
if (node, nb) in path_edges:
continue
x0, y0 = P(node)
x1, y1 = P(nb)
ax.add_patch(FancyArrowPatch(
(x0, y0), (x1, y1), arrowstyle="-|>", mutation_scale=8,
color=COL_SLATE_400, linewidth=0.9, alpha=0.40,
shrinkA=_R_LAYER * 78, shrinkB=_R_LAYER * 78,
connectionstyle="arc3,rad=0.0", zorder=2))
for (u, v) in path_edges:
x0, y0 = P(u)
x1, y1 = P(v)
ax.add_patch(FancyArrowPatch(
(x0, y0), (x1, y1), arrowstyle="-|>", mutation_scale=13,
color=COL_ACCENT, linewidth=2.8,
shrinkA=_R_LAYER * 78, shrinkB=_R_LAYER * 78,
connectionstyle="arc3,rad=0.0", zorder=4))
wt = weight[(u, v)]
mxp = (x0 + x1) / 2
myp = (y0 + y1) / 2
ax.add_patch(FancyBboxPatch(
(mxp - 0.20, myp - 0.04), 0.40, 0.30,
boxstyle="round,pad=0.01,rounding_size=0.05",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.7, zorder=6))
ax.text(mxp, myp + 0.11, f"w={wt}", ha="center", va="center",
fontsize=8, color=COL_AMBER_700, weight="bold", zorder=7)
for v in cols:
for i in (2, 1, 0):
node = (v, i)
x, y = P(node)
on_path = node in {("s", 2), ("m", 0), ("t", 1)}
is_store = v in _STORES
if on_path:
fc, ec, lw = COL_AMBER_100, COL_ACCENT, 2.6
elif is_store:
fc, ec, lw = COL_BG, COL_AMBER_600, 1.6
else:
fc, ec, lw = COL_WHITE, COL_SLATE_400, 1.3
ax.add_patch(Circle((x, y), _R_LAYER, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, y, f"{v},{i}", ha="center", va="center", fontsize=8.2,
color=COL_TEXT, weight="bold", zorder=6)
for v in cols:
ax.text(col_x[v], row_y[2] + _R_LAYER + 0.26, v, ha="center",
va="bottom", fontsize=11, color=COL_PRIMARY, weight="bold",
zorder=6)
for i in (2, 1, 0):
ax.text(col_x["s"] - _R_LAYER - 0.30, row_y[i], f"i={i}", ha="right",
va="center", fontsize=8.4, color=COL_SLATE_500, style="italic",
zorder=6)
ax.text(col_x["s"] - _R_LAYER - 0.30, row_y[2] + 0.62, "boş küre",
ha="right", va="center", fontsize=7.6, color=COL_SLATE_500,
weight="bold", zorder=6)
_draw_store_icon(ax, col_x["m"], row_y[2] + _R_LAYER + 0.58)
sx1, sy1 = P(("s", 1))
_draw_forbidden_sm(ax, sx1 - _R_LAYER - 0.34, sy1 - 0.40, r=0.135)
ax.text(sx1 - _R_LAYER - 0.34, sy1 - 0.78, "(s,1)→m YOK\ni=1 < c=2 → UYULUR",
ha="center", va="top", fontsize=6.8, color=COL_AMBER_700,
weight="bold", zorder=8)
sx2, sy2 = P(("s", 2))
ax.text(sx2, sy2 + _R_LAYER + 0.16, "başla: 2 küre", ha="center",
va="bottom", fontsize=6.8, color=COL_SLATE_500, style="italic",
zorder=8)
ax.add_patch(FancyBboxPatch(
(col_x["s"] - 0.20, row_y[0] - 1.18), 3.95, 0.60,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=5))
ax.text(col_x["s"] + 1.78, row_y[0] - 0.88,
f"(s,2)→(m,0)→(t,1) = 2 + 3 = {path_dist}", ha="center",
va="center", fontsize=10, color=COL_AMBER_700, weight="bold",
zorder=6)
cmid = col_x["m"]
ax.text(cmid, row_y[2] + 1.30, "② katmanlı çizge (k = 2)", ha="center",
va="center", fontsize=11.5, color=COL_TEXT, weight="bold", zorder=6)
ax.text(cmid, row_y[2] + 0.98, "düğüm = (konum, kalan boş küre i)",
ha="center", va="center", fontsize=8.4, color=COL_SLATE_500,
style="italic", zorder=6)
def _draw_k1_panel(ax, ox, oy, k1_dist):
col_x = {"s": ox + 0.0, "m": ox + 1.55, "t": ox + 3.10}
row_y = {1: oy + 0.65, 0: oy - 0.65}
def P(node):
v, i = node
return (col_x[v], row_y[i])
for v in ("s", "m", "t"):
for i in (1, 0):
x, y = P((v, i))
is_store = v in _STORES
ec = COL_AMBER_600 if is_store else COL_SLATE_400
ax.add_patch(Circle((x, y), 0.185, facecolor=COL_WHITE,
edgecolor=ec, linewidth=1.3, zorder=5))
ax.text(x, y, f"{v},{i}", ha="center", va="center", fontsize=7.4,
color=COL_TEXT, weight="bold", zorder=6)
gx = (col_x["s"] + col_x["m"]) / 2
gy = (row_y[1] + row_y[0]) / 2
_draw_forbidden_sm(ax, gx, gy, r=0.20)
ax.text(gx, gy - 0.50, "s→m KENAR YOK", ha="center", va="center",
fontsize=7.6, color=COL_AMBER_700, weight="bold", zorder=8)
for v in ("s", "m", "t"):
ax.text(col_x[v], row_y[1] + 0.40, v, ha="center", va="bottom",
fontsize=9.5, color=COL_PRIMARY, weight="bold", zorder=6)
for i in (1, 0):
ax.text(col_x["s"] - 0.42, row_y[i], f"i={i}", ha="right", va="center",
fontsize=7.6, color=COL_SLATE_500, style="italic", zorder=6)
_draw_store_icon(ax, col_x["m"], row_y[1] + 0.70, s=0.11)
fmt = "+∞" if k1_dist == INF else str(k1_dist)
ax.add_patch(FancyBboxPatch(
(col_x["s"] - 0.30, row_y[0] - 1.30), 3.85, 0.58,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_BG, ec=COL_AMBER_700, linewidth=2.4, zorder=5))
ax.text(col_x["s"] + 1.62, row_y[0] - 1.01,
f"δ(s→t) = {fmt} üzüntü kaçınılmaz", ha="center", va="center",
fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(col_x["m"], row_y[1] + 1.30, "③ k = 1 (yetersiz küre)",
ha="center", va="center", fontsize=11.5, color=COL_TEXT,
weight="bold", zorder=6)
ax.text(col_x["m"], row_y[1] + 0.98, "patika 2 critter ister; maks i = 1 < 2",
ha="center", va="center", fontsize=8.0, color=COL_SLATE_500,
style="italic", zorder=6)
# --- motor verisi + iç tutarlılık ---
dist_k2 = shortest_no_sadness(_PATHS, _STORES, 2, "s", "t")
dist_k1 = shortest_no_sadness(_PATHS, _STORES, 1, "s", "t")
adj2, w2 = build_capacity_graph(_PATHS, _STORES, 2)
d2 = dijkstra(adj2, w2, ("s", 2))
assert dist_k2 == 5, dist_k2
assert dist_k1 == INF, dist_k1
assert w2[(("s", 2), ("m", 0))] == 2, w2[(("s", 2), ("m", 0))]
assert w2[(("m", 0), ("t", 1))] == 3, w2[(("m", 0), ("t", 1))]
assert d2[("t", 1)] == 5, d2[("t", 1)]
assert not any(nb[0] == "m" for nb in adj2[("s", 1)]), adj2[("s", 1)]
fig, ax = plt.subplots(figsize=(11.0, 6.4))
fig.patch.set_facecolor(COL_WHITE)
_draw_physical(ax, 0.0, 4.0)
ax.add_patch(FancyArrowPatch(
(4.35, 4.0), (5.05, 4.0), arrowstyle="-|>", mutation_scale=18,
color=COL_AMBER_600, linewidth=2.2, zorder=3))
ax.text(4.70, 4.30, "çoğalt", ha="center", va="bottom", fontsize=8.2,
color=COL_AMBER_700, weight="bold", zorder=4)
_draw_layered(ax, 5.55, 4.0, adj2, w2, dist_k2)
_draw_k1_panel(ax, 10.95, 4.30, dist_k1)
fig.suptitle(
"Durum makinesi: konum + kalan küre = düğüm → çizgeyi k+1 katmana çoğalt",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text(0.5, 0.018,
"Solomon PS6 56:42 — konum + durum (kalan boş küre) = graf çoğaltma "
"(Ders 18 katmanlı-çizge akrabası) · V = O(nk), Dijkstra O(nk log nk)",
transform=ax.transAxes, ha="center", va="bottom", fontsize=8.4,
color=COL_SLATE_500, style="italic", zorder=6)
ax.set_xlim(-1.1, 14.7)
ax.set_ylim(1.55, 6.55)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Problem 5: Nakliye ve Darboğaz — Modifiye Dijkstra {#sec-problem-5-d20}
**İfade.** $n$ kamyon rotası (kaynak, hedef, **maks ağırlık** $w_i$, maliyet $c_i$); yönlü. (1) Gönderilebilen **en ağır** server $w^\star$, (2) o ağırlığı **en az maliyetle** taşıma. ($\le 3\sqrt{n}$ şehir.)
::: {.callout-tip title="Yaklaşım — darboğaz dünyasının üçgen eşitsizliği: modifiye gevşetme + iki aşama"}
Bir yolun **darboğazı (bottleneck)** = yoldaki minimum kenar ağırlığıdır; $B(s, t)$ = tüm $\pi$ yolları üzerinde darboğazın maksimumu ($\max_\pi$). Anahtar gözlem bir eşitsizliktir: $B(s, t) \ge \min(B(s, v),\ w(v, t))$, bir $v^\star$ için eşitlikle — bu, **darboğaz dünyasının üçgen eşitsizliği**dir. Üçgen-eşitsizliği analoğu olan her güncelleme formülü Dijkstra iskeletine takılabilir: toplama yerine min, en küçüğü kesinleştirme yerine en büyüğü kesinleştirme. Sonra $w^\star$ bilinince problem ikinci aşamada sıradan bir maliyet-Dijkstra'ya iner.
:::
> *"the bottleneck of pi is going to be the minimum edge weight of any edge in pi."* — Solomon, 1:12:24
**Çözüm.**
**(1) En ağır $w^\star$.** Darboğaz eşitsizliği, Dijkstra'nın güncelleme formülünün analoğudur: toplama yerine min/maks ile gevşet — gelen komşular arasında en büyük darboğazı seç. **Modifiye Dijkstra** $w^\star$'ı verir.
> *"rather than updating by summing edge lengths, we update by using this formula."* — Solomon, 1:26:05
**(2) En az maliyet.** $w^\star$ bilinince, yalnız **$w^\star$ taşıyabilen** rotaları tut; kenar ağırlığı = maliyet olan bir çizgede Dijkstra → en az maliyet. $V = 3\sqrt{n}$ olduğundan array-PQ Dijkstra $O(V^2)$ = $O(n)$.
```python
def widest_path(adj, capacity, s): # (1) darboğaz-maks
B = {v: 0 for v in adj}; B[s] = INF # kaynağın darboğazı sonsuz
Q = ChangeablePQ((v, -B[v]) for v in adj) # max-PQ: anahtarları negatif tut
done = set()
while len(Q):
u, _ = Q.delete_min()
done.add(u)
for v in adj[u]:
if v in done:
continue
cand = min(B[u], capacity[(u, v)]) # TOPLA değil MIN (darboğaz-üçgeni)
if cand > B[v]: # KÜÇÜLT değil BÜYÜT
B[v] = cand; Q.decrease_key(v, -cand)
return B
```
@fig-bottleneck bu iki aşamayı motordan **gerçek** verilerle gösterir: $s \to t$ doğrudan (kapasite 10, maliyet 5) ile $s \to t_2 \to t$ alternatifi (kapasiteler $4, 4$; maliyetler $1, 1$). Aşama 1'de darboğaz gevşetmesi doğrudan rota için $\min(\infty, 10) = 10$, alternatif için $\min(4, 4) = 4$ bulur; $\max(10, 4) = 10$ → $w^\star = 10$. Aşama 2'de yalnız kapasitesi $\ge 10$ olan kenarlar kalır (alternatif rota $4 < 10$ ile elenir), kalan çizgede maliyet-Dijkstra en ucuz taşımayı 5 olarak verir.
**Karmaşıklık.** (1) modifiye Dijkstra; (2) array-PQ Dijkstra $O(V^2) = O((\sqrt{n})^2) = O(n)$.
```{python}
#| label: fig-bottleneck
#| fig-cap: "Darboğaz = modifiye Dijkstra: gevşetmeyi değiştir, iskeleti koru — Problem 5. İki aşama (motordan GERÇEK). SOL: iki rota s⟶t — doğrudan (kapasite 10, maliyet 5) vs t₂ üzerinden (kapasiteler 4,4; maliyetler 1,1). AŞAMA ①: darboğaz gevşetme formül kutusu B(v)=maks(min(B(u),kap)) — toplama→MIN, küçültme→BÜYÜTME (klasik d(v)=min(d(u)+w) ile kıyas); rota darboğazları doğrudan min(∞,10)=10 amber-kazanan vs alternatif min(4,4)=4; w*=maks(10,4)=10 rozeti. AŞAMA ②: w*≥10 süz → alternatif rota (kap 4 < 10) elenir soluk, doğrudan kazanır; kalan çizgede maliyet-Dijkstra → en ucuz=5. Alt not: üçgen-eşitsizliği-analogu her güncelleme formülü Dijkstra iskeletine takılır; V=3√n → array-PQ O(V²)=O(n) (Solomon 1:26:05)."
#| fig-width: 11.0
#| fig-height: 6.6
# fig-bottleneck — PS6 Problem 5 İMZA: darboğaz = modifiye Dijkstra (min/maks gevşetme).
# Veri MOTORDAN: widest_path(...)['t']==10, cheapest_at_capacity(...,10)==5,
# alternatif darboğaz min(4,4)==4 < 10. networkx KULLANILMAZ — elle koordinat.
# Setup globalleri: plt, Circle, FancyBboxPatch, FancyArrowPatch, COL_*,
# widest_path, cheapest_at_capacity, INF.
_ADJ = {"s": ["t", "t2"], "t": [], "t2": ["t"]}
_CAP = {("s", "t"): 10, ("s", "t2"): 4, ("t2", "t"): 4}
_COST = {("s", "t"): 5, ("s", "t2"): 1, ("t2", "t"): 1}
_R_BN = 0.30
def _node_bn(ax, x, y, label, *, role="plain"):
if role == "source":
fc, ec, tc, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 2.8
elif role == "sink":
fc, ec, tc, lw = COL_BG, COL_ACCENT, COL_TEXT, 2.6
else:
fc, ec, tc, lw = COL_BG, COL_PRIMARY, COL_TEXT, 1.8
ax.add_patch(Circle((x, y), _R_BN, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, y, label, ha="center", va="center", fontsize=12.5,
color=tc, weight="bold", zorder=6)
def _edge_bn(ax, p0, p1, *, color, lw, dashed=False, alpha=1.0, rad=0.0):
ax.add_patch(FancyArrowPatch(
p0, p1, arrowstyle="-|>", mutation_scale=14, color=color,
linewidth=lw, linestyle=(0, (5, 2)) if dashed else "-",
shrinkA=_R_BN * 73, shrinkB=_R_BN * 73, alpha=alpha,
connectionstyle=f"arc3,rad={rad}", zorder=3 if alpha > 0.5 else 2))
def _edge_badge(ax, mx, my, text, *, hot=False):
fc = COL_AMBER_100 if hot else COL_WHITE
ec = COL_ACCENT if hot else COL_SLATE_400
tc = COL_AMBER_700 if hot else COL_TEXT
ax.add_patch(FancyBboxPatch(
(mx - 0.50, my - 0.17), 1.0, 0.34,
boxstyle="round,pad=0.01,rounding_size=0.05",
fc=fc, ec=ec, linewidth=1.8 if hot else 1.0, zorder=6))
ax.text(mx, my, text, ha="center", va="center", fontsize=8.0,
color=tc, weight="bold", zorder=7, family="monospace")
def _draw_routes(ax, ox, oy, *, faded_alt=False, win_direct=False, show_cost=False):
P = {"s": (ox + 0.0, oy + 0.0), "t": (ox + 3.4, oy + 0.0),
"t2": (ox + 1.7, oy - 1.45)}
direct_col = COL_ACCENT if win_direct else COL_PRIMARY
direct_lw = 3.0 if win_direct else 2.2
alt_alpha = 0.28 if faded_alt else 1.0
alt_col = COL_SLATE_400 if faded_alt else COL_PRIMARY
alt_lw = 1.6 if faded_alt else 2.0
_edge_bn(ax, P["s"], P["t"], color=direct_col, lw=direct_lw)
_edge_bn(ax, P["s"], P["t2"], color=alt_col, lw=alt_lw, alpha=alt_alpha)
_edge_bn(ax, P["t2"], P["t"], color=alt_col, lw=alt_lw, alpha=alt_alpha)
if show_cost:
d_txt = f"maliyet {_COST[('s','t')]}"
a1_txt = f"maliyet {_COST[('s','t2')]}"
a2_txt = f"maliyet {_COST[('t2','t')]}"
else:
d_txt = f"kap. {_CAP[('s','t')]}"
a1_txt = f"kap. {_CAP[('s','t2')]}"
a2_txt = f"kap. {_CAP[('t2','t')]}"
md = ((P["s"][0] + P["t"][0]) * 0.5, P["s"][1] + 0.22)
_edge_badge(ax, md[0], md[1], d_txt, hot=win_direct)
ma1 = ((P["s"][0] + P["t2"][0]) * 0.5 - 0.30, (P["s"][1] + P["t2"][1]) * 0.5)
ma2 = ((P["t2"][0] + P["t"][0]) * 0.5 + 0.30, (P["t2"][1] + P["t"][1]) * 0.5)
if not faded_alt:
_edge_badge(ax, ma1[0], ma1[1], a1_txt)
_edge_badge(ax, ma2[0], ma2[1], a2_txt)
_node_bn(ax, P["s"][0], P["s"][1], "s", role="source")
_node_bn(ax, P["t"][0], P["t"][1], "t", role="sink")
_node_bn(ax, P["t2"][0], P["t2"][1], "t₂", role="mid")
return P
def _draw_formula_box(ax, x, y, w):
h = 1.85
ax.add_patch(FancyBboxPatch(
(x, y - h), w, h, boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=2.0, zorder=3))
cx = x + w * 0.5
ax.text(cx, y - 0.42, r"$B(v) = \max\,(\,\min(B(u),\ c(u,v))\,)$",
ha="center", va="center", fontsize=12.0, color=COL_AMBER_700,
weight="bold", zorder=4)
ax.text(cx, y - 0.88, "darboğaz gevşetmesi (modifiye Dijkstra)",
ha="center", va="center", fontsize=8.2, color=COL_AMBER_700,
style="italic", zorder=4)
ax.text(cx, y - 1.30, r"klasik: $d(v)=\min(\,d(u)+w(u,v)\,)$",
ha="center", va="center", fontsize=9.5, color=COL_SLATE_500, zorder=4)
ax.text(cx, y - 1.64, "toplama → MIN · küçültme → BÜYÜTME",
ha="center", va="center", fontsize=8.6, color=COL_TEXT,
weight="bold", zorder=4)
# --- MOTOR verisi + iç tutarlılık ---
B = widest_path(_ADJ, _CAP, "s")
wstar = B["t"]
cheapest = cheapest_at_capacity(_ADJ, _CAP, _COST, "s", "t", wstar)
direct_bn = _CAP[("s", "t")]
alt_bn = min(_CAP[("s", "t2")], _CAP[("t2", "t")])
assert wstar == 10, wstar
assert cheapest == 5, cheapest
assert direct_bn == 10 and alt_bn == 4, (direct_bn, alt_bn)
assert B["t2"] == 4 and B["s"] == INF, B
assert max(direct_bn, alt_bn) == wstar and alt_bn < wstar
fig, ax = plt.subplots(figsize=(11.0, 6.6))
fig.patch.set_facecolor(COL_WHITE)
rx, ry = 0.0, 4.55
_draw_routes(ax, rx, ry)
ax.text(rx + 1.7, ry + 1.30, "iki rota: s ⟶ t", ha="center", va="center",
fontsize=11.5, color=COL_TEXT, weight="bold", zorder=6)
ax.text(rx + 1.7, ry + 0.92, "doğrudan (kap. 10) vs t₂ üzerinden (kap. 4, 4)",
ha="center", va="center", fontsize=8.6, color=COL_SLATE_500,
style="italic", zorder=6)
s1x = 4.55
ax.text(s1x + 1.55, ry + 1.30, "① darboğaz gevşetmesi", ha="center",
va="center", fontsize=11.5, color=COL_TEXT, weight="bold", zorder=6)
_draw_formula_box(ax, s1x, ry + 0.70, 3.55)
bn_y = ry - 1.95
ax.add_patch(FancyBboxPatch(
(s1x, bn_y - 0.20), 1.65, 0.74, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=4))
ax.text(s1x + 0.825, bn_y + 0.30, "s → t doğrudan", ha="center", va="center",
fontsize=8.0, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(s1x + 0.825, bn_y - 0.02, f"min(∞, 10) = {direct_bn}", ha="center",
va="center", fontsize=9.0, color=COL_AMBER_700, weight="bold",
family="monospace", zorder=5)
ax.add_patch(FancyBboxPatch(
(s1x + 1.90, bn_y - 0.20), 1.65, 0.74,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.4, zorder=4))
ax.text(s1x + 1.90 + 0.825, bn_y + 0.30, "s → t₂ → t alternatif", ha="center",
va="center", fontsize=8.0, color=COL_SLATE_500, weight="bold", zorder=5)
ax.text(s1x + 1.90 + 0.825, bn_y - 0.02, f"min(4, 4) = {alt_bn}", ha="center",
va="center", fontsize=9.0, color=COL_TEXT, family="monospace", zorder=5)
wstar_y = bn_y - 1.05
ax.add_patch(FancyBboxPatch(
(s1x + 0.35, wstar_y - 0.16), 2.85, 0.62,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_ACCENT, ec=COL_AMBER_700, linewidth=2.6, zorder=5))
ax.text(s1x + 0.35 + 1.425, wstar_y + 0.15, f"w* = maks(10, 4) = {wstar}",
ha="center", va="center", fontsize=11.5, color=COL_WHITE,
weight="bold", family="monospace", zorder=6)
ax.add_patch(FancyArrowPatch(
(s1x + 0.825, bn_y - 0.22), (s1x + 1.05, wstar_y + 0.50), arrowstyle="-|>",
mutation_scale=11, color=COL_AMBER_700, linewidth=1.6,
connectionstyle="arc3,rad=-0.10", zorder=4))
ax.add_patch(FancyArrowPatch(
(s1x + 1.90 + 0.825, bn_y - 0.22), (s1x + 2.55, wstar_y + 0.50),
arrowstyle="-|>", mutation_scale=10, color=COL_SLATE_400, linewidth=1.3,
connectionstyle="arc3,rad=0.10", zorder=4))
sep_x = 8.45
ax.plot([sep_x, sep_x], [ry - 3.55, ry + 1.05], color=COL_SLATE_400,
linewidth=1.0, linestyle=(0, (3, 3)), zorder=1)
s2x = 8.85
ax.text(s2x + 1.55, ry + 1.30, "② w* ≥ 10 süz → maliyet-Dijkstra", ha="center",
va="center", fontsize=11.0, color=COL_TEXT, weight="bold", zorder=6)
_draw_routes(ax, s2x, ry - 0.35, faded_alt=True, win_direct=True, show_cost=True)
ax.text(s2x + 1.7, ry - 1.95, "kap. 4 < w* = 10 → elendi", ha="center",
va="center", fontsize=8.2, color=COL_SLATE_500, style="italic", zorder=6)
cy = ry - 2.85
ax.add_patch(FancyBboxPatch(
(s2x + 0.35, cy - 0.16), 2.85, 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(s2x + 0.35 + 1.425, cy + 0.15, f"en ucuz (kap.≥10) = {cheapest}",
ha="center", va="center", fontsize=11.0, color=COL_AMBER_700,
weight="bold", family="monospace", zorder=6)
fig.suptitle(
"Darboğaz = modifiye Dijkstra: gevşetmeyi değiştir, iskeleti koru (PS6 Problem 5)",
color=COL_TEXT, fontsize=13.0, weight="bold", y=0.975)
ax.text(0.5, 0.978,
"darboğaz gevşetmesi B(v)=maks(min(B(u),kap.)) — toplama→MIN, "
"küçültme→BÜYÜTME · (Solomon 1:26:05)",
transform=ax.transAxes, ha="center", va="top", fontsize=8.6,
color=COL_SLATE_500, style="italic", zorder=6)
note_y = ry - 3.95
ax.text(0.0, note_y,
"Üçgen-eşitsizliği-analogu HER güncelleme formülü Dijkstra iskeletine "
"takılabilir: önce w* (en geniş yol), sonra w* taşıyan",
ha="left", va="center", fontsize=8.6, color=COL_TEXT, weight="bold",
zorder=5)
ax.text(0.0, note_y - 0.34,
"alt-çizgede maliyet-Dijkstra → en ucuz taşıma. V = 3·√n düğümde "
"array-PQ → O(V²) = O(n). Motor: widest_path(...)['t'] = 10,",
ha="left", va="center", fontsize=8.6, color=COL_SLATE_500, zorder=5)
ax.text(0.0, note_y - 0.64, f"cheapest_at_capacity(..., w*=10) = {cheapest}.",
ha="left", va="center", fontsize=8.6, color=COL_AMBER_700,
style="italic", weight="bold", zorder=5)
ax.set_xlim(-0.9, s2x + 4.4)
ax.set_ylim(note_y - 0.95, ry + 1.75)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Ne Öğrendik? {#sec-ne-ogrendik-d20}
::: {.callout-important title="Altı Taşınabilir Araç"}
Bu oturum, Ders 16-19'un ağırlıklı en kısa yol teorisini beş somut problemde uyguladı ve altı taşınabilir araç kazandırdı:
1. **Dijkstra'nın dondurma varsayımı:** negatif kenar bu varsayımı kırar (düğüm geri eklenmeli) — bu yüzden Dijkstra yalnız negatif-olmayan ağırlıkta çalışır; negatif kenarda Bellman-Ford gerekir.
2. **"Önce bariz olanı dene":** yarıçap gibi problemler, akıllı numara yerine tanımı doğrudan kodlamayla (Johnson + iç içe döngü) $O(V^3)$'te çözülür.
3. **Süpernode:** birçok hedefe (sensör) tek 0-ağırlıklı kaynakla bağlanıp tek Dijkstra ile "en yakın hedef" mesafesini bul.
4. **Cevap-üzerinde ikili arama:** "$\log n$ bütçe" → ikili arama ipucu; monoton evet/hayır eşiğini ($k^\star$) sıralı dizi indeksinde ara.
5. **Graf çoğaltma / durum makinesi:** konum + durum (kalan kapasite) → $k+1$ katman; $O(kn)$ çizgede Dijkstra.
6. **Modifiye gevşetme:** üçgen-eşitsizliği analoğu olan her güncelleme formülü (darboğaz) Dijkstra iskeletine takılabilir — toplama yerine min/maks.
:::
## Sonraki {#sec-sonraki-d20}
::: {.callout-warning title="Ders 21 (L14) — Tüm-Çiftler En Kısa Yollar (APSP) ve Johnson"}
Sırada **Ders 21 (L14): Tüm-Çiftler En Kısa Yollar (APSP)** var — Jason Ku ile, bu oturumda kara kutu olarak kullandığımız **Johnson algoritmasını** açıyoruz: negatif ağırlıklı bir çizgede tüm düğüm çiftleri arası en kısa yol. Püf nokta, bir **potansiyel fonksiyonla** kenarları negatif-olmayana "yeniden ağırlıklandırıp" Dijkstra'yı $V$ kez çalıştırmaktır.
:::
