Graf kuramı: adım adım çözümlü alıştırma soruları

1Köşeler, kenarlar ve dereceler

Bir graf köşelerden (noktalar) ve kenarlardan (iki köşe arasındaki çizgiler) oluşur. Basit bir grafta döngü kenarı (kendine bağlanan kenar) ve çift kenar yoktur.

Bir köşenin derecesi ona değen kenar sayısıdır. Her kenarın iki ucu vardır; bu yüzden her iki ucun derecesine de 1 ekler. Buradan el sıkışma lemması çıkar:

İki sonuç: derecelerin toplamı her zaman çifttir ve derecesi tek olan köşelerin sayısı da çifttir.

• K_n tam grafı her çifti birleştirir: n(n − 1)/2 kenar.
• K_m,n tam iki parçalı grafı bir taraftaki her köşeyi öbür taraftaki her köşeye bağlar: m·n kenar.
• n köşeli k-düzgün bir grafın n·k/2 kenarı vardır.

Komşuluk matrisi, i ve j birleşikse (i, j) konumunda 1 taşır. Yönsüz bir graf için simetriktir, bir satır toplamı bir derecedir ve Mᴸ’nin (i, j) girdisi i’den j’ye L uzunluğundaki gezintilerin sayısını verir.

2Euler ve Hamilton

Bir Euler devresi her kenarı tam bir kez kullanır ve başladığı yere döner. Bir Euler yolu her kenarı bir kez kullanır ama başka yerde bitebilir. Bağlantılı bir graf için:

• tüm dereceler çift: bir Euler devresi vardır;
• tam olarak iki derece tek: bir Euler yolu vardır, tek dereceli bir köşeden ötekine;
• ikiden fazla tek derece: hiçbiri yoktur.

Bir Hamilton devresi her köşeyi tam bir kez ziyaret eder. Bunun için basit bir derece sınaması yoktur. K_n içinde (n − 1)!/2 farklı Hamilton devresi vardır: başlangıcı sabitleyin, öbür n − 1 köşeyi sıralayın ve iki yön için 2’ye bölün.

3Ağaçlar

Ağaç, döngüsüz bağlantılı bir graftır. n köşeli her ağacın tam olarak n − 1 kenarı vardır. Herhangi bir kenar eklemek bir döngü oluşturur; herhangi bir kenarı kaldırmak bağlantıyı koparır.

n köşede c ağaçtan oluşan bir ormanın n − c kenarı vardır. m kenarlı bağlantılı bir graf, m − n + 1 kenar kaldırıldıktan sonra bir kapsayan ağaç bırakır.

El sıkışma lemması yaprakları sayar: Σ deg = 2(n − 1). Kısa biçimi L = 2 + Σ (d − 2)’dir; toplam, derecesi d ≥ 3 olan köşeler üzerindendir. Derecesi 3 olan iki köşesi olup geri kalanı yaprak olan bir ağacın 2 + 1 + 1 = 4 yaprağı vardır.

4Dijkstra ve en küçük kapsayan ağaçlar

Dijkstra algoritması, negatif olmayan ağırlıklı bir grafta bir başlangıç köşesinden en kısa uzaklıkları bulur.

1. Başlangıca 0, diğer her köşeye ∞ uzaklığı verin.
2. Kesinleşmemiş köşelerden en küçük uzaklıklı olanı kesinleştirin; uzaklığı artık kesindir.
3. Her komşu v için d(v) = min(d(v), d(u) + w(u, v)) değerini güncelleyin.
4. Hedef kesinleşene kadar tekrarlayın.

En küçük kapsayan ağaç tüm köşeleri en küçük toplam ağırlıkla bağlar. Kruskal kenarları hafiften ağıra sıralar ve bir döngü kapatmadıkça her birini alır. Prim bir başlangıç köşesinden tek bir ağaç büyütür ve her seferinde ağaçtan çıkan en hafif kenarı ekler. İkisi de n − 1 kenardan sonra durur.

5Sık yapılan hatalar

• Kenar sayısını bulmak için derece toplamını 2’ye bölmeyi unutmak.
• Grafın bağlantılı olduğunu denetlemeden Euler devresi sınamak.
• Dijkstra’da bir köşeyi, geçici uzaklığı en küçük olmadan kesinleştirmek.
• Döngü olup olmadığına bakmadan en hafif n − 1 kenarı almak.
• K_n içindeki Hamilton devrelerini (n − 1)!/2 yerine n! olarak saymak.

6Sınav soruları nasıl görünür

• Kolay: dereceler ve kenarlar. El sıkışma lemmasını kullanır, K_n, K_m,n, düzgün graflar ve ağaçların kenarlarını sayar, bir komşuluk matrisini okur ya da verilen derecedeki köşeye tıklarsınız.
• Orta: Euler yolları ve ağaçlar. Bir grafın Euler devresi ya da yolu olup olmadığına karar verir, bir ağacın yapraklarını sayar, kapsayan ağaç için çıkarılacak kenarları sayar ya da K_n içindeki Hamilton devrelerini sayarsınız.
• Zor: en kısa yollar ve kapsayan ağaçlar. Dijkstra algoritmasını çalıştırır, verilen turda kesinleşen köşeyi bulur, en küçük kapsayan ağacın ağırlığını bulur, Kruskal ya da Prim’in sıradaki ekleyeceği kenara tıklar ya da komşuluk matrisiyle gezintileri sayarsınız.