Bağlılık, Euler ve Hamilton yolları

Bu haftanın sorusu genelde iki parça: “Does this graph have an Euler circuit / Euler path?” ve “Does it have a Hamilton circuit?”. Euler tarafı tamamen derece saymaktır, Hamilton tarafı ise deneme ve birkaç teorem. Üstüne bağlılık (connectivity) tanımları ve kısa bir en kısa yol (Dijkstra) sorusu gelebilir. Vizede yok, final konusu.

Altın kurallar:

1. Euler = kenarlar, Hamilton = köşeler. Karıştırmak en pahalı hata.
2. Bağlı grafta Euler devresi $\iff$ her derece çift. Euler yolu (devre olmayan) $\iff$ tam iki tek dereceli köşe.
3. Hamilton için genel bir “ancak ve ancak” kriteri yok. Var demek için devreyi yaz ya da Dirac/Ore kullan; yok demek için bir engel göster.
4. Yol sayısı sorusu $\Rightarrow$ komşuluk matrisinin kuvveti.

Yollar ve devreler

Rosen’ın dilinde (bu dersin terimleri):

Sezgi: köşeler sahadaki istasyonlar, kenarlar koşu çizgileri. Bir antrenman parkuru bir yoldur; başladığın istasyona dönüyorsan devredir.

Matrisle yol sayma

$A$ komşuluk matrisi ise $v_i$‘den $v_j$‘ye uzunluğu $r$ olan yolların sayısı $(A^r)_{ij}$‘dir. Neden: $(A^2)_{ij} = \sum_k a_{ik}a_{kj}$, yani “$i$‘den $k$‘ye ve $k$‘den $j$‘ye kenar olan ara köşe $k$” sayısı.

Sorulardaki 4 köşeli graf için:

$A^2 = \begin{bmatrix} 2&1&2&1\\ 1&3&1&2\\ 2&1&2&1\\ 1&2&1&3 \end{bmatrix}$

Köşegen dereceleri veriyor: $v_i$‘den çıkıp geri dönen 2 uzunluklu yol = bir kenara gidip geri gelmek.

Bağlılık

Yönsüz bir graf, her iki köşesi arasında bir yol varsa bağlıdır (connected). Bağlı olmayan bir graf bileşenlere (connected components) ayrılır: maksimal bağlı alt graflar. Yalnız köşe tek başına bir bileşendir.

Kesme köşesi (cut vertex): silindiğinde (kenarlarıyla birlikte) bileşen sayısı artan köşe. Köprü (cut edge, bridge): silindiğinde bileşen sayısı artan kenar.

İPUCU · köprü testi. Bir kenar bir döngünün üzerindeyse köprü olamaz, çünkü döngünün geri kalanı iki ucu hala bağlar. Önce döngüleri işaretle, kalan kenarları kontrol et.

Ölçüler:

• Vertex connectivity $\kappa(G)$: grafı koparmak (ya da tek köşeye indirmek) için silinmesi gereken en az köşe sayısı.
• Edge connectivity $\lambda(G)$: koparmak için silinmesi gereken en az kenar sayısı.
• Her zaman $\kappa(G) \le \lambda(G) \le \min_v \deg(v)$.

Örnekler: $\kappa(K_n) = \lambda(K_n) = n-1$; $\kappa(K_{m,n}) = \min(m,n)$; bir köprü varsa $\lambda = 1$, kesme köşesi varsa $\kappa = 1$.

Yönlü graflarda: her $a, b$ için hem $a\to b$ hem $b\to a$ yönlü yol varsa strongly connected; yönleri yok sayınca bağlı oluyorsa weakly connected.

Euler devreleri ve yolları

Euler devresi (Euler circuit): her kenarı tam bir kez kullanan basit devre. Euler yolu (Euler path): her kenarı tam bir kez kullanan basit yol.

Hikaye: Königsberg’in 7 köprüsü. 4 kara parçası (köşe), 7 köprü (kenar), dereceler $5, 3, 3, 3$. Euler, her köprüden bir kez geçen tur olmadığını gösterdi.

Teorem. Bağlı ve en az iki köşeli bir multigraph’ta:

• Euler devresi vardır $\iff$ her köşenin derecesi çifttir.
• Euler yolu var ama devresi yok $\iff$ tam iki köşenin derecesi tektir. Yol bu iki köşede başlar ve biter.

Sezgi: bir köşeden geçen her tur bir kenarla girer, bir kenarla çıkar: dereceye 2 katar. Başlangıç ve bitiş noktası dışındaki her köşe bu yüzden çift dereceli olmalı.

Tam yazılmış ispat (gerek koşul)

Claim. If a connected multigraph $G$ has an Euler circuit, then every vertex of $G$ has even degree.

Proof. Let the Euler circuit start and end at $a$, and follow it. The first edge contributes 1 to $\deg(a)$. Each time the circuit passes through a vertex $v$ (including returns to $a$ before the end), it enters $v$ along one edge and leaves along another, contributing 2 to $\deg(v)$. The last edge enters $a$ and contributes 1 more to $\deg(a)$. Since the circuit uses every edge exactly once, these contributions count every edge end exactly once. Hence $\deg(a) = 1 + 2t + 1$ for some integer $t \ge 0$, which is even, and every other vertex has degree equal to a sum of 2’s, which is even. $\blacksquare$

Türkçesi: devreyi takip et, her “geçiş” bir köşeye 2 ekler; başlangıç köşesi ilk ve son kenarlardan 1 + 1 alır. Ters yön (her derece çiftse devre vardır) yapıcı ispattır: bir devre kur, kalan kenarlardan yeni devreler bulup birleştir (Hierholzer). Finalde genelde gerek koşul ya da sadece teoremin uygulanması istenir.

Uygulama örneği. “Kelebek” graf: $ab, bc, ca, cd, de, ec$ (ortak köşesi $c$ olan iki üçgen).

dereceler: a 2, b 2, c 4, d 2, e 2   -> hepsi çift, bağlı
Euler devresi: a, b, c, d, e, c, a
Hamilton devresi? c bir kesme köşesi (silince {a,b} ve {d,e} kopar)
  -> c'den iki kez geçmek gerekir -> Hamilton devresi YOK

Aynı graf Euler açısından mükemmel, Hamilton açısından imkansız. İki kavramın bağımsız olduğunu gösteren en iyi örnek.

Hamilton yolları ve devreleri

Hamilton yolu (Hamilton path): her köşeden tam bir kez geçen basit yol. Hamilton devresi (Hamilton circuit): başladığı köşeye dönen ve diğer her köşeden tam bir kez geçen devre.

Euler’in aksine, Hamilton devresi için bilinen basit bir “ancak ve ancak” koşulu yok (problem NP-complete). Elinde iki tür araç var.

Var olduğunu göstermek (yeterli koşullar):

Bu koşullar yeterli ama gerekli değil: $C_{10}$‘da dereceler 2, koşullar sağlanmaz ama $C_{10}$ kendisi bir Hamilton devresidir.

Olmadığını göstermek (engeller):

1. Derecesi 1 olan köşe varsa Hamilton devresi yok (o köşeye girip çıkmak için 2 kenar lazım).
2. Derecesi 2 olan köşenin iki kenarı da devrede zorunlu. Zorunlu kenarlar bir köşede 3 tane olursa ya da tam olmayan küçük bir devre kapatırsa çelişki.
3. Kesme köşesi varsa Hamilton devresi yok.
4. İki parçalı grafta taraflar eşit büyüklükte değilse Hamilton devresi yok.

Özel graflar: $K_n$ ($n\ge 3$) her zaman Hamilton devreli, farklı devre sayısı $\frac{(n-1)!}{2}$. $Q_n$ ($n \ge 2$) Hamilton devreli: Gray kodu (ardışık kodlar tek bit farklı) tam olarak $Q_n$‘de bir Hamilton devresidir.

TUZAK · Euler koşulunu Hamilton için kullanmak. “Bütün dereceler çift, o halde Hamilton devresi var” yanlış. Kelebek grafında bütün dereceler çift ama Hamilton devresi yok. Tersine $K_4$‘te dereceler 3 (tek) ama Hamilton devresi var.

En kısa yol: Dijkstra (kısaca)

Ağırlıklı (weighted) grafta iki köşe arası en kısa yol uzunluğu. Dijkstra algoritması (negatif ağırlık yokken):

1. Başlangıca 0, diğerlerine $\infty$ etiketi ver.
2. Kesinleşmemiş köşelerden etiketi en küçük olanı seç, kesinleştir.
3. Onun komşularının etiketini güncelle: $L(v) = \min\big(L(v),\ L(u) + w(u,v)\big)$.
4. Hedef kesinleşene kadar tekrarla.

Sorudaki graf için kesinleşme sırası:

a:0  ->  c:2  ->  b:3  ->  d:8  ->  e:10  ->  z:13
yol (geri izle): z <- e <- d <- b <- c <- a   uzunluk 13

Dikkat: $b$‘nin ilk etiketi 4 ($ab$ kenarı), ama $c$ üzerinden 3. Bir köşe kesinleşmeden önce etiketi düşebilir; kesinleştikten sonra değişmez. Karmaşıklık $O(n^2)$.

Sık yapılan hatalar