---
title: 'Çizge Kavramı'
source: 'https://academia.sh/tr/kurslar/veri-yapilari/cizge-kavrami'
course: 'Veri Yapıları'
language: tr
updated: '2026-08-17T18:07:53+00:00'
license: 'CC BY-SA 4.0'
---

# Çizge Kavramı

Düğüm ve kenar tanımı, yönlü ve yönsüz çizgeler, ağırlık, derece, yol ve döngü kavramları.

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.

```python
# 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.