Graflara giriş ve graf izomorfizmi

Graf teorisi finalin son büyük bloğu. Bu hafta dili öğreniyorsun: köşe, kenar, derece, özel graflar ve iki grafın “aynı” olması (izomorfizm). Gelecek hafta bu dille yollar, Euler ve Hamilton soruları gelecek. Vizede yok, final konusu. Sınav soruları kısa ve hesaplıdır: “How many edges?”, “Is it bipartite?”, “Are these graphs isomorphic?”.

Altın kurallar:

1. El sıkışma teoremi: derecelerin toplamı kenar sayısının iki katıdır.
2. Bu yüzden tek dereceli köşelerin sayısı çifttir.
3. İki parçalı $\iff$ tek uzunlukta döngü yok $\iff$ 2 renkle boyanabilir.
4. İzomorf değil demek için tek bir değişmezin farklı olması yeter. İzomorf olduğunu göstermek için eşlemeyi yazmalısın.

Temel tanımlar

Bir graf (graph) $G = (V, E)$: köşeler (vertices) kümesi $V$ ve her biri bir ya da iki köşeyi bağlayan kenarlar (edges) kümesi $E$.

Aralarında kenar olan iki köşe komşudur (adjacent). Bir köşenin derecesi (degree) $\deg(v)$, ona değen kenar sayısıdır; döngü dereceye 2 katar. Derecesi 0 olan köşe isolated, 1 olan pendant.

Sezgi: köşeler takım arkadaşları, kenarlar “birbirine pas atmış olmak”. Derece, bir oyuncunun kaç farklı kişiyle pas alışverişi yaptığı.

El sıkışma teoremi

$2m = \sum_{v\in V} \deg(v), \qquad m = |E|.$

Her kenarın iki ucu var ve her uç bir köşenin derecesine 1 ekliyor. Yönlü graflarda giriş derecesi (in-degree) $\deg^-(v)$ ve çıkış derecesi (out-degree) $\deg^+(v)$ ayrılır: $\sum \deg^-(v) = \sum \deg^+(v) = m$.

Örnek. $V = \{a,b,c,d,e\}$, $E = \{ab, ac, bc, cd, de\}$:

deg(a) = 2  (b, c)
deg(b) = 2  (a, c)
deg(c) = 3  (a, b, d)
deg(d) = 2  (c, e)
deg(e) = 1  (d)      -> pendant
toplam = 10 = 2 * 5 kenar
tek dereceli köşeler: c, e  -> 2 tane (çift)

Tam yazılmış ispat

Theorem. An undirected graph has an even number of vertices of odd degree.

Proof. Let $V_1$ be the set of vertices of even degree and $V_2$ the set of vertices of odd degree in $G = (V,E)$ with $m$ edges. By the handshaking theorem, $2m = \sum_{v\in V_1}\deg(v) + \sum_{v\in V_2}\deg(v).$ The left side is even. The first sum on the right is even, since each of its terms is even. Hence the second sum is the difference of two even numbers, so it is even. Every term of the second sum is odd, and a sum of odd numbers is even only if the number of terms is even. Therefore $|V_2|$ is even. $\blacksquare$

Türkçesi: toplamı çift ve tek parçalarına böl, çift olanı çıkar, geriye kalan tek sayıların toplamı çift olmalı. Bu da ancak çift sayıda tek terimle olur. Sınavda “Is there a graph with degrees 3, 3, 2, 1, 1, 1?” gibi bir soruda bu teoremi kullanırsın: tek dereceli 5 köşe var, imkansız.

TUZAK · toplam çift diye graf var sanmak. $3,3,3,1$ dizisinin toplamı 10, çift. Ama 4 köşeli basit grafta derece 3 “herkese bağlı” demek, o zaman son köşenin derecesi de 3 olur. Toplamın çift olması gerekli koşul, yeterli değil.

Özel graflar

Tüm dereceleri eşit olan grafa regular denir: $K_n$, $C_n$, $Q_n$ regular; $W_n$ ($n \neq 3$) değil.

Kontrol: $K_5$‘te 10 kenar, $Q_3$‘te 12 kenar, $W_4$‘te 5 köşe ve 8 kenar.

İki parçalı graflar

$V$ iki ayrık kümeye $V_1, V_2$ bölünebiliyor ve her kenar bir $V_1$ köşesini bir $V_2$ köşesine bağlıyorsa graf iki parçalıdır (bipartite). Eşdeğer tanım: köşeleri iki renkle, komşular farklı renkte olacak şekilde boyayabilirsin.

Teorem: Bir graf iki parçalı ancak ve ancak tek uzunlukta bir döngü içermez.

Pratik test: bir köşeyi kırmızı yap, komşularını mavi, onların komşularını kırmızı… Aynı renkte iki komşu çıkarsa iki parçalı değil.

C6:  1R 2M 3R 4M 5R 6M, 6-1 kenarı M-R   -> bipartite
C5:  1R 2M 3R 4M 5R, 5-1 kenarı R-R      -> bipartite DEĞİL
K3:  üçgen = uzunluk 3 döngü             -> bipartite DEĞİL

Grafı temsil etmek

Komşuluk listesi (adjacency list): her köşenin komşuları. Seyrek graflarda verimli.

Komşuluk matrisi (adjacency matrix) $A$: $a_{ij} = 1$ eğer $v_i v_j$ kenarı varsa, değilse 0. Yukarıdaki örnek graf ($a,b,c,d,e$ sırasıyla):

$A = \begin{bmatrix} 0&1&1&0&0\\ 1&0&1&0&0\\ 1&1&0&1&0\\ 0&0&1&0&1\\ 0&0&0&1&0 \end{bmatrix}$

Yönsüz grafta $A$ simetrik; basit grafta köşegen 0 ve satır toplamı dereceyi verir. Multigraph’ta $a_{ij}$ paralel kenar sayısıdır. Incidence matrix ise köşe × kenar tablosudur: $m_{ij} = 1$ eğer $e_j$ kenarı $v_i$‘ye değiyorsa.

Alt graf (subgraph): $V$ ve $E$‘nin alt kümelerinden oluşan graf. Tümleyen (complement) $\overline{G}$: aynı köşeler, $G$‘de olmayan tüm kenarlar. $m(G) + m(\overline{G}) = \frac{n(n-1)}{2}$.

Graf izomorfizmi

$G_1 = (V_1,E_1)$ ve $G_2 = (V_2,E_2)$ izomorftur (isomorphic) eğer bir birebir ve örten $f: V_1\to V_2$ varsa öyle ki

$uv \in E_1 \iff f(u)f(v)\in E_2.$

Sezgi: aynı graf, köşeler farklı isimlendirilmiş ve kağıda farklı çizilmiş.

İzomorf değil göstermek: değişmezler

Graph invariant: izomorfizmle korunan özellik. Biri farklıysa graflar izomorf olamaz.

Örnek. $C_6$ ile iki ayrık üçgen ($2K_3$). İkisi de 6 köşe, 6 kenar, tüm dereceler 2. Ama $C_6$ bağlı ve üçgen içermiyor; $2K_3$ iki bileşenli ve üçgen içeriyor. İzomorf değil.

İzomorf olduğunu göstermek

Değişmezlerin hepsinin aynı olması ispat değildir. Eşlemeyi yazıp her kenarı kontrol etmelisin. Yöntem:

1. Derece sırası aynı mı bak.
2. Benzersiz dereceli köşelerden başla (derece 3 → derece 3).
3. Komşulukları koru: $u$‘nun komşuları $f(u)$‘nun komşularına gitmeli.
4. Son adım: bütün kenarları tek tek çevirip $E_2$‘de olduklarını yaz. İstersen matrisle: köşeleri $f$ sırasıyla dizdiğinde iki komşuluk matrisi aynı olmalı.

Sorulardaki $G$ ve $H$ örneği tam bu yöntemle çözülüyor.

İPUCU · tümleyen hilesi. Kenarı çok olan iki grafı karşılaştırmak zorsa tümleyenlerine bak. $G_1 \cong G_2 \iff \overline{G_1}\cong\overline{G_2}$ ve tümleyenler daha seyrek olur.

Sık yapılan hatalar