Çizge Kavramı

Ağaçlar iki kısıt taşıyordu: döngü yoktu ve her düğümün tek bir üstü vardı. Bu kısıtlar kaldırıldığında elde edilen yapı, ilişkileri modellemenin en genel biçimidir.

Çizge (graph), düğümler ve onları birleştiren kenarlardan oluşur. Bu kadar basit bir tanımın bu kadar geniş bir uygulama alanı olması, ilişkinin kendisinin temel bir kavram olmasındandır: yollar arasındaki bağlantılar, kişiler arasındaki tanışıklık, görevler arasındaki bağımlılık, sayfalar arasındaki bağlantılar — hepsi aynı yapıdır.

Temel Terimler

Bir çizge $G = (V, E)$ olarak yazılır: $V$ düğüm kümesi, $E$ kenar kümesidir.

Terim	Anlamı
Düğüm (vertex)	Yapının birimi; modellenen varlık
Kenar (edge)	İki düğüm arasındaki ilişki
Komşu	Aralarında kenar bulunan düğümler
Derece	Bir düğüme bağlı kenar sayısı
Yol	Kenarlar üzerinden ilerleyen düğüm dizisi
Döngü	Başladığı düğüme dönen yol
Bağlı bileşen	Kendi içinde birbirine ulaşabilen düğüm kümesi

Bir düğümden diğerine ulaşılabiliyorsa aralarında bir yol vardır. Tüm düğüm çiftlerinin birbirine ulaşabildiği çizgeye bağlı denir; ulaşamayanlar varsa çizge birden çok bileşene ayrılmıştır.

Yönlü ve Yönsüz

Yönsüz çizgede kenar iki yönlüdür: a ile b arasında kenar varsa, a’dan b’ye ve b’den a’ya gidilebilir. Karşılıklı ilişkileri modeller — iki şehir arasındaki yol, iki kişi arasındaki arkadaşlık.

Yönlü çizgede kenarın bir yönü vardır. Tek yönlü ilişkileri modeller — bir sayfadan diğerine verilen bağlantı, bir görevin diğerine bağımlılığı, tek yönlü bir sokak.

Yönlü çizgede derece ikiye ayrılır: giriş derecesi (düğüme gelen kenar sayısı) ve çıkış derecesi (düğümden çıkan). Bu ayrım, topolojik sıralama dersinde belirleyici olacaktır.

Yönlü çizgelerde döngü kavramı da özelleşir. Yönlü çevrimsiz çizge, hiçbir yönlü döngü içermeyen çizgedir ve bağımlılık ilişkilerinin doğal modelidir: bir görev kendisine dolaylı olarak da bağımlı olamaz.

Ağırlık

Kenarlara sayısal bir değer — ağırlık — atanabilir. Ağırlık, ilişkinin maliyetini veya gücünü taşır: iki şehir arasındaki uzaklık, bir bağlantının gecikmesi, bir işlemin süresi.

Ağırlıksız çizgede “en kısa yol”, en az kenar kullanan yoldur. Ağırlıklı çizgede ise ağırlık toplamı en küçük olan yoldur ve bu iki yol farklı olabilir: az sayıda uzun kenar mı, çok sayıda kısa kenar mı sorusu, ancak ağırlıklara bakılarak yanıtlanır.

Ağaçlar Çizgelerin Özel Hâlidir

Önceki konunun tanımı burada yerine oturur: ağaç, döngüsüz ve bağlı bir yönsüz çizgedir. $n$ düğümlü ağacın $n-1$ kenarı olması, bu tanımın doğrudan sonucuydu.

İlişki üç adımda kurulur:

• Çizgeden döngüler çıkarılırsa orman elde edilir.
• Orman bağlıysa ağaç olur.
• Ağaçta bir düğüm kök seçilirse köklü ağaç olur.

Bu, önceki konudaki tüm yapıların çizgelerin özel hâli olduğu anlamına gelir. Tersi doğru değildir: çizgeler ağaçların yapamadığı şeyleri modeller — döngüler, çoklu yollar, birden çok ebeveyn.

Ayrık kümeler dersindeki “bağlı bileşen” sorusu da buraya bağlanır: kenarlar eklendikçe hangi düğümlerin aynı bileşende olduğu, orada birleştir–bul ile izleniyordu.

Özel Çizge Aileleri

Aile	Tanım	Örnek kullanım
Yönlü çevrimsiz çizge	Yönlü, döngüsüz	Görev bağımlılıkları, derleme sırası
İki parçalı çizge	Düğümler iki gruba ayrılır, kenarlar yalnız gruplar arası	Eşleştirme problemleri
Tam çizge	Her düğüm çifti arasında kenar var	En kötü durum çözümlemeleri
Seyrek / yoğun çizge	Kenar sayısı düğüm sayısına yakın / karesine yakın	Gösterim seçimini belirler

Son satır, sonraki dersin konusudur: kenar sayısının düğüm sayısına oranı, hangi gösterimin uygun olduğunu doğrudan belirler.

Kenar sayısı için sınırlar da bu ayrımdan çıkar. Yönsüz ve basit bir çizgede en fazla kenar sayısı:

$$\lvert E \rvert \leq \frac{\lvert V \rvert (\lvert V \rvert - 1)}{2}$$

Yani kenar sayısı, düğüm sayısının karesiyle sınırlıdır. Gerçek çizgelerin çoğu bu sınırın çok altındadır — bir yol ağında her şehir yalnızca birkaç komşuya bağlıdır. Bu gözlem, gösterim seçiminin pratikte neden seyrek çizgelere göre yapıldığını açıklar.

Modelleme Örneği

Ölçüm istasyonları arasındaki bağlantılar bir çizgeyle modellensin: istasyonlar düğüm, aralarındaki iletişim hatları kenar, hattın gecikmesi ağırlık olsun.

# Yönsüz, ağırlıklı çizge: her kenar bir kez yazılır.
kenarlar = [
    ("kuzey", "merkez", 4),
    ("guney", "merkez", 2),
    ("dogu",  "merkez", 7),
    ("bati",  "kuzey",  3),
    ("bati",  "guney",  5),
]

dugumler = {d for kenar in kenarlar for d in kenar[:2]}
print(sorted(dugumler))        # ['bati', 'dogu', 'guney', 'kuzey', 'merkez']
print(len(dugumler), len(kenarlar))     # 5 5

derece: dict[str, int] = {d: 0 for d in dugumler}
for a, b, _ in kenarlar:
    derece[a] += 1
    derece[b] += 1

print(sorted(derece.items()))
# [('bati', 2), ('dogu', 1), ('guney', 2), ('kuzey', 2), ('merkez', 3)]
print(sum(derece.values()), 2 * len(kenarlar))    # 10 10

Son satır, çizge kuramının en temel özdeşliğini gösterir: derecelerin toplamı, kenar sayısının iki katıdır. Her kenar iki düğümün derecesine birer katkı yaptığı için bu her yönsüz çizgede geçerlidir. Doğrudan bir sonucu, tek dereceli düğüm sayısının her zaman çift olmasıdır.

Çoklu kenar ve ilmek — aynı düğüm çifti arasında birden çok kenar, ya da bir düğümden kendisine giden kenar — bazı modellerde anlamlıdır. Bunlara izin veren çizgelere çoklu çizge denir; bu kurstaki tanım, izin vermeyen basit çizgedir.

Çizgelerle Sorulan Sorular

Yapının kendisi kadar, üzerinde sorulan sorular da standarttır:

• Ulaşılabilirlik: İki düğüm arasında yol var mı?
• En kısa yol: Varsa en ucuzu hangisi?
• Bağlı bileşenler: Çizge kaç parçaya ayrılmış?
• Döngü tespiti: Yapıda döngü var mı?
• Sıralama: Bağımlılıklara uygun bir yürütme sırası var mı?
• Kapsama: Tüm düğümlere en az maliyetle ulaşan kenar kümesi hangisi?

Soruların çoğu, çizgenin yönlü olup olmadığına ve ağırlık taşıyıp taşımadığına göre farklı algoritmalar gerektirir. Bu kursun kalan üç dersi ilk dördünü yanıtlayan gezinme yöntemlerini kurar; en kısa yol ve kapsama problemleri, ağırlıkların devreye girdiği algoritmalarla birlikte Algoritmalar kursunda ele alınır.

Özet

• Çizge, düğümler ve kenarlardan oluşan en genel ilişki modelidir.
• Yönsüz kenar karşılıklı, yönlü kenar tek yönlü ilişkiyi gösterir; yönlü çizgede giriş ve çıkış dereceleri ayrılır.
• Ağırlık, ilişkinin maliyetini taşır ve “en kısa yol” tanımını değiştirir.
• Ağaç, döngüsüz ve bağlı bir çizgedir; ormanlar ve köklü ağaçlar bu tanımın özelleşmiş hâlleridir.
• Yönlü çevrimsiz çizgeler bağımlılık ilişkilerinin doğal modelidir.
• Derecelerin toplamı kenar sayısının iki katıdır; kenar sayısı düğüm sayısının karesiyle sınırlıdır.

Sonraki Adım

Çizge kavramı tanımlandı, ancak bellekte nasıl tutulacağı belirtilmedi. Seçim önemsiz değildir: aynı algoritma, gösterime göre farklı maliyetlerle çalışır. Sonraki ders iki temel gösterimi ve seçimi belirleyen ölçütü ele alacak.