Graf Teorisi — Düğümler, Kenarlar ve Temel Kavramlar

Graf teorisi, düğümler ve kenarlardan oluşan yapılar olan grafları inceler. Düğüm bir nesneyi, kenar ise iki nesne arasındaki ilişkiyi gösterir.

Graf teorisinin temellerini arıyorsanız, şu fikirle başlayın: graf, bağlantıları modellemenin düzenli bir yoludur. Sosyal ağdaki insanlar, yollarla bağlanan şehirler ve birbirine bağlantı veren web sayfaları graflarla gösterilebilir.

Matematikte Graf Ne Anlama Gelir?

Yönsüz bir grafta, bir kenar iki düğümün bağlı olduğunu söyler ve bu bağlantının yönü yoktur. Eğer $A$, $B$'ye bağlıysa, $B$ de $A$'ya bağlıdır.

Yönlü bir grafta ise kenarların yönü vardır; bu yüzden $A \to B$ ve $B \to A$ farklı ifadelerdir. Başlangıç düzeyindeki birçok örnekte basit yönsüz graflar kullanılır; yani döngü yoktur ve aynı iki düğüm arasında tekrarlanan kenarlar bulunmaz.

Bu koşul önemlidir çünkü tanımlar genellikle önce basit, yönsüz durumda verilir. Grafın türü değişirse, terimlerin anlamı da değişebilir.

Önce Bilmeniz Gereken Temel Graf Teorisi Terimleri

Düğümler ve kenarlar

Düğüm, takip etmek istediğiniz şeydir. Kenar ise takip etmek istediğiniz bağlantıdır.

Bir graf şehirleri ve yolları modelliyorsa, şehirler düğüm, yollar ise kenardır.

Derece

Yönsüz bir grafta bir düğümün derecesi, ona değen kenarların sayısıdır.

Bir şehrin başka üç şehre yolu varsa, derecesi $3$ olur.

Yol

Yol, ardışık her düğüm çifti bir kenarla bağlı olacak şekilde sıralanmış düğümler dizisidir.

Bir düğümden diğerine bir yol varsa, kenarları izleyerek birinden ötekine gidebilirsiniz.

Çevrim

Çevrim, başladığı düğümde biten bir yoldur. Temel tanımda, diğer hiçbir düğüm tekrar edilmez.

Bir çevrim, grafta kapalı bir döngü olduğunu gösterir.

Bağlı graf ve bağlı bileşenler

Yönsüz bir graf, her düğüme diğer her düğümden bir yol ile ulaşılabiliyorsa bağlıdır.

Bu sağlanmıyorsa, graf bağlı bileşenlere ayrılır. Her bileşen, grafın kendi içinde bağlı bir parçasıdır.

Çözümlü Örnek: Küçük Bir Graf

Bir grafın düğümlerinin $A$, $B$, $C$, $D$ ve $E$ olduğunu; kenarlarının ise

$$AB,\ AC,\ BC,\ CD$$

olduğunu varsayalım.

Bu, $A$, $B$ ve $C$ üzerinde bir üçgen, $C$'den $D$'ye bir ek kenar ve izole bir $E$ düğümü verir.

Artık temel fikirleri görmek kolaydır.

Dereceler şöyledir:

$$\deg(A)=2,\ \deg(B)=2,\ \deg(C)=3,\ \deg(D)=1,\ \deg(E)=0$$

$A$'dan $D$'ye bir yol vardır:

$$A-C-D$$

Bir çevrim de vardır:

$$A-B-C-A$$

Graf bağlı değildir çünkü $E$'ye diğer düğümlerden ulaşılamaz. Bu yüzden grafın iki bağlı bileşeni vardır: biri $A,B,C,D$'yi içerir, diğeri ise yalnızca $E$'yi.

Bu tek örnek; derece, yol, çevrim, izole düğümler ve bağlı bileşenlerin nasıl bir araya geldiğini gösterir.

Hızlı Bir Kontrol: Derecelerin Toplamı

Her sonlu yönsüz graf için,

$$\sum \deg(v) = 2|E|$$

olur.

Bunun nedeni, her kenarın tam olarak iki uca değmesidir; dolayısıyla her kenar iki derece sayımına $1$ ekler.

Yukarıdaki örnekte derece toplamı

$$2+2+3+1+0=8$$

olur.

Kenar sayısı $4$ olduğuna göre,

$$2|E| = 2 \cdot 4 = 8$$

elde edilir.

Bu, dereceleri elle sayarken kullanışlı bir kontroldür. Sayılar eşleşmiyorsa bir yerde hata vardır.

Graf Teorisinde Sık Yapılan Hatalar

Düğümlerle kenarları karıştırmak

Düğümler nesnelerdir. Kenarlar ise aralarındaki ilişkilerdir.

Elinizde hangi tür graf olduğunu unutmak

Basit yönsüz bir graf için doğru olan bir ifade, yönlü bir graf ya da döngülere izin veren bir graf için değiştirilmek zorunda olabilir.

Yolu çevrim gibi düşünmek

Bir yolun başladığı yere geri dönmesi gerekmez. Çevrimin ise gerekir.

İzole düğümleri göz ardı etmek

Derecesi $0$ olan bir düğüm hâlâ grafın parçasıdır. Grafın bağlı olup olmadığını değiştirebilir.

Graf Teorisinin Temelleri Nerelerde Kullanılır?

Bu fikirler bilgisayar ağlarında, rota planlamada, çizelgelemede, öneri sistemlerinde ve sosyal ağlarda karşımıza çıkar. Bağlam değişir, ama aynı sorular tekrar ortaya çıkar: ne bağlı, nereye ulaşılabilir ve döngüler nerede?

Bu yüzden graf teorisi hem ayrık matematikte hem de bilgisayar biliminde erken konular arasında yer alır.

Benzer Bir Graf Deneyin

$P$, $Q$, $R$ ve $S$ olmak üzere dört düğüm çizin. $PQ$, $QR$, $RS$ ve $SP$ kenarlarını ekleyin.

Sonra şu üç soruyu cevaplayın: her düğümün derecesi nedir, graf bağlı mıdır ve grafta bir çevrim var mıdır?