Graf bilgi modeli: komşuluk matrisi ve yol sayısı

Bu derste öğreneceklerin

Bir grafın köşelerini, kenarlarını ve derecelerini tanımak; yönlü ve ağırlıklı grafları ayırt etmek.
Komşuluk matrisini graf çizimine ve çizimi matrise dönüştürmek, 1’leri saymak.
Tek yönlü yol şemasında yol sayısını «gelenleri topla» yöntemiyle bulmak (belirli bir köşeden geçerek veya ondan kaçınarak).
Ağırlık tablosuna göre bütün güzergâhları sıralayıp en kısasını seçmek.

Metro şeması, şehirler arasındaki yollar, sınıf arkadaşlarının arkadaşlıkları, web sayfaları ve aralarındaki bağlantılar — hepsinde nesneler ve onları birleştiren ilişkiler vardır. Böyle bir yapının modeli graftır. Azerbaycan’daki 2025–2026 giriş sınavlarında (I. grup, bilişim) her kitapçıkta bir graf sorusu vardı: matristeki 1’lerin sayısı, matrise veya yol şemasına göre yol sayısı. 2026’daki iki sınavda da bu soru kodlanmış soruydu: cevap seçenek olmadan, sayı olarak yazılmalıydı.

«Ağaç bilgi modeli» dersinde ağacın döngüsüz bir graf olduğunu gördük. Şimdi genel graflarla — döngüleri, yönleri ve ağırlıkları olan graflarla — çalışacağız.

Graf: köşeler ve kenarlar

Tanım

Graf

Köşelerden ve köşe çiftlerini birleştiren kenarlardan oluşan grafik bilgi modeli. Köşeler nesneleri, kenarlar aralarındaki ilişkileri gösterir.

Köşe (düğüm) — bir nesne (şehir, kişi, sayfa); kenar — iki köşeyi birleştiren çizgi. Bir kenarla bağlı köşeler komşudur.
Yönlü graf — kenarlar okla gösterilir, yalnızca ok yönünde gidilebilir (tek yönlü yollar).
Ağırlıklı graf — her kenarın üzerinde bir sayı (ağırlık) vardır: mesafe, fiyat, süre.
Köşenin derecesi — köşeden çıkan kenar sayısı. Yol, kenar kenar ilerleyen köşe dizisidir; başladığı köşeye dönen yola döngü denir.

deg(A₁) + deg(A₂) + … + deg(Aₙ) = 2 · m

burada:

deg(Aᵢ)i. köşenin derecesi
mkenar sayısı

«Tokalaşma» kuralı: her kenar iki köşeye aittir ve derecelerin toplamında iki kez sayılır. Demek ki derecelerin toplamı her zaman çifttir.

m = n · (n − 1) / 2m = n · (n − 1) / 2

burada:

nköşe sayısı
mtam grafta kenar sayısı

Tam graf: her iki köşe birbirine bağlıdır (örneğin her takım her takımla bir kez oynar).

Sorular 1–4: dereceler ve kenarlar

1) Aşağıdaki resimdeki grafta her köşenin derecesini ve kenar sayısını bul.
2) Bir grafın köşe dereceleri 4, 3, 3, 2, 2’dir. Kaç kenarı vardır?
3) 5 arkadaşın her biri, diğerlerinden tam 3 kişiyle arkadaş olabilir mi?
4) Bir turnuvada 6 takım var, her takım diğerleriyle bir kez oynuyor. Kaç maç olur?

Çözümü göster

1) A — 2, B — 3, C — 3, D — 2, E — 2. Toplam 12 = 2 · m → m = 6 (AB, AC, BC, BD, CE, DE).
2) m = (4 + 3 + 3 + 2 + 2) / 2 = 14 / 2 = 7.
3) Hayır: derecelerin toplamı 5 · 3 = 15 olurdu, bu tek sayıdır; oysa toplam her zaman 2 · m’ye, yani bir çift sayıya eşittir.
4) Tam graf: m = 6 · 5 / 2 = 15 maç.

Komşuluk matrisi

Tanım

Komşuluk matrisi

n köşeli bir grafın n × n tablosu: X satırı ile Y sütununun kesiştiği yere X ile Y bir kenarla bağlıysa 1, değilse 0 yazılır. Bu, «Tablo bilgi modeli: mantık problemlerinin tabloyla çözümü» dersindeki «nesne–nesne» tablosunun özel bir hâlidir.

Her kenar matriste iki tane 1 verir: AB kenarı hem A satırında hem B satırında görünür. Bir satırdaki 1’lerin sayısı köşenin derecesidir.

yönsüz graf: N₁ = 2 · m yönlü graf: N₁ = m

burada:

N₁komşuluk matrisindeki 1’lerin sayısı
mkenar (ok) sayısı

Yönlü grafta X → Y oku yalnızca tek bir hücrede, X satırı ile Y sütununun kesiştiği yerde 1 verir; böyle bir matris genellikle simetrik değildir.

Sorular 5–6: matristeki 1’ler

5) Resimdeki grafın komşuluk matrisinde kaç tane 1 var? Her satırdaki 1’lerin sayısı neyi gösterir?
6) Yönsüz bir grafın komşuluk matrisinin satırlarında sırasıyla 4, 3, 3, 2, 2 tane 1 var. Grafın kaç kenarı var ve derecesi en büyük köşe hangi satırda?

Çözümü göster

5) N₁ = 2 · 6 = 12. Bir satırdaki 1’lerin sayısı köşenin derecesidir: A satırında 2, B’de 3, C’de 3, D’de 2, E’de 2.
6) 1’lerin toplamı 4 + 3 + 3 + 2 + 2 = 14 = 2 · m → m = 7. Derecesi en büyük (4) olan köşe birinci satırdadır.

Soru 7: grafı ikiye bölüyoruz

Resimdeki grafın komşuluk matrisinde x tane 1 var. Kesikli çizgiyle gösterilen kenarlar silinip graf iki grafa ayrıldıktan sonra onların komşuluk matrislerinde toplam y tane 1 olur. x − y farkını bulun.
A) 3 B) 12 C) 6 D) 18 E) 24

Çözümü göster

Kenarları sayıyoruz: solda 5, sağda 4, aralarında 3 — toplam 12. x = 2 · 12 = 24.
Silindikten sonra 5 + 4 = 9 kenar kalır: y = 2 · 9 = 18.
x − y = 24 − 18 = 6. Kısa yol: x − y = 2 · (silinen kenarlar) = 2 · 3 = 6.
Doğru cevap: C.

Yol sayısı: «gelenleri topla»

Tek yönlü yollar şeması yönlü bir graftır. Döngü yoksa (bir şehirden çıkıp ona geri dönülemiyorsa) A’dan her şehre kaç yolla gidilebileceğini saymak kolaydır. Bir şehre giden her yol, ona ok gönderen şehirlerden birinden geçer; bu yüzden o şehirlerin sayıları toplanır.

N(X) = N(Y₁) + N(Y₂) + … + N(Yₖ), N(A) = 1

burada:

N(X)A’dan X’e giden farklı yolların sayısı
Y₁, …, YₖX’e ok (doğrudan yol) gönderen bütün köşeler

Başlangıç köşesine 1 yazılır; her köşenin sayısı, ona gelen okların başladığı köşelerdeki sayıların toplamıdır.

1
Grafı çiz
Matris veya liste verildiyse önce çizimi yap: X satırı, Y sütununda 1 → X’ten Y’ye ok.
2
Başlangıç
Başlangıç köşesine 1 yaz.
3
Topla
Kendisine ok gönderen bütün köşeleri hesaplanmış bir köşe seç ve o sayıları topla. Bütün köşeler bitene kadar tekrarla.
4
Cevap
Son köşedeki sayı cevaptır. Yol az ise onları tek tek yazarak kontrol et.

	B	C	D	E	F
A	1	1	1	0	0
B	0	0	1	0	1
C	0	0	0	1	0
D	0	0	0	1	1
E	0	0	0	0	1
F	0	0	0	0	0

Yönlü bir grafın komşuluk matrisi (satır — nereden, sütun — nereye)

Soru 8: matrise göre yol sayısı

Komşuluk matrisine (yukarıdaki tablo) göre A köşesinden F köşesine kaç farklı yolla gidilebilir?

Çözümü göster

Oklar: A → B, A → C, A → D, B → D, B → F, C → E, D → E, D → F, E → F (9 tane 1 — 9 ok).
N(A) = 1; N(B) = N(A) = 1; N(C) = N(A) = 1; N(D) = N(A) + N(B) = 2; N(E) = N(C) + N(D) = 3; N(F) = N(B) + N(D) + N(E) = 1 + 2 + 3 = 6.
Kontrol: ABF, ABDF, ABDEF, ACEF, ADF, ADEF — 6 yol.
Cevap: 6.

Sayılar, A’dan o şehre giden yol sayısıdır; her sayı, ona ok gönderen şehirlerin sayılarının toplamıdır.

Soru 9: A’dan K’ye

Resimde şehirleri birleştiren yolların şeması verilmiştir; her yolda yalnızca ok yönünde gidilebilir. A şehrinden K şehrine kaç farklı yolla gidilebilir?

Çözümü göster

Sıra önemlidir: C’den önce B ve D, E’den önce C hesaplanmalıdır.
A = 1; B = A = 1; D = A = 1; C = A + B + D = 3; E = B + C = 4; F = C + D = 4; G = E = 4; H = E + F = 8; K = G + H + F = 4 + 8 + 4 = 16.
Cevap: 16.

N(A → K, D-dən keçməklə) = N(A → D) · N(D → K)

burada:

N(A → D)A’dan D’ye giden yol sayısı
N(D → K)D’den K’ye giden yol sayısı (D’ye 1 yazıp yeniden sayılır)

Belirli bir köşeden geçen yollar: ilk kısmın her seçeneği ikinci kısmın her seçeneğiyle birleşir, bu yüzden sayılar çarpılır.

Sorular 10–11: D’den geçerek ve C’den kaçınarak

Aynı şemaya göre: 10) A’dan K’ye D şehrinden geçen kaç yol var? 11) C şehrinden geçmeyen kaç yol var?

Çözümü göster

10) N(A → D) = 1 (yalnızca A → D). D’ye 1 yazıp D’den sayıyoruz: C = 1, E = C = 1, F = C + D = 2, G = E = 1, H = E + F = 3, K = G + H + F = 1 + 3 + 2 = 6 (D’den B’ye ulaşılamaz, sayısı 0). Cevap: 1 · 6 = 6.
11) C’yi siliyoruz (N(C) = 0) ve yeniden sayıyoruz: B = 1, D = 1, E = B = 1, F = D = 1, G = 1, H = E + F = 2, K = G + H + F = 1 + 2 + 1 = 4. Cevap: 4. Kontrol: C’den geçen yollar 16 − 4 = 12.

En kısa yol: ağırlıklı graf

Ağırlıklı graf çoğu zaman tablo olarak verilir: hücrede iki şehir arasındaki doğrudan yolun uzunluğu yazılıdır, boş hücre doğrudan yol olmadığını gösterir. En kısa güzergâhı bulmak için tabloya göre grafı çizer, şehirleri tekrarlamadan bütün güzergâhları sıralar ve uzunlukları toplarız. Dikkat: en kısa güzergâh, en az yollu güzergâh olmayabilir. Büyük graflar için Dijkstra algoritması vardır — «Graflar ve graf algoritmaları» dersine bak.

	P	Q	R	S	T
P		5	9	14
Q	5		3		11
R	9	3		4	8
S	14		4		2
T		11	8	2

P, Q, R, S, T şehirleri arasındaki doğrudan yolların uzunluğu, km (boş hücre — doğrudan yol yok)

Soru 12: en kısa güzergâh

Tabloya göre P şehrinden T şehrine en kısa güzergâh kaç kilometredir?
A) 16 B) 13 C) 15 D) 11 E) 14

Çözümü göster

Şehirleri tekrarlamayan bütün 9 güzergâh:
P–Q–T = 5 + 11 = 16; P–Q–R–T = 5 + 3 + 8 = 16; P–Q–R–S–T = 5 + 3 + 4 + 2 = 14;
P–R–T = 9 + 8 = 17; P–R–S–T = 9 + 4 + 2 = 15; P–R–Q–T = 9 + 3 + 11 = 23;
P–S–T = 14 + 2 = 16; P–S–R–T = 14 + 4 + 8 = 26; P–S–R–Q–T = 14 + 4 + 3 + 11 = 32.
En kısası P–Q–R–S–T = 14 km, dört yoldan oluşsa da.
Doğru cevap: E.

Etkileşimli

Simülasyon yükleniyor…

Dijkstra algoritması bütün güzergâhları sıralamadan en kısa uzaklıkları bulur: her adımda uzaklığı en küçük köşeyi «kapatır» ve komşularının uzaklıklarını günceller. A’dan başlarsan sonunda şunlar çıkar: C 2, B 3 (A → C → B; doğrudan A → B yolu 4’tür), I 6, D 8, H 9, E 10, F 12, G 13. Bir köşeye dokunarak ona giden yolu gör.

Önemli noktalar

Graf köşelerden ve kenarlardan oluşur; kenarlar yönlü (ok) ve ağırlıklı (sayı) olabilir.
Derecelerin toplamı = 2 · kenar; tam grafta n · (n − 1) / 2 kenar vardır.
Komşuluk matrisinde yönsüz grafın her kenarı iki, yönlü grafın her oku bir tane 1 verir; satırdaki 1’ler köşenin derecesidir.
Tek yönlü yollarda: N(başlangıç) = 1, her köşe = ona ok gönderenlerin toplamı.
«D’den geçerek» — N(A → D) · N(D → son); «X’ten kaçınarak» — X’e 0 yazıp yeniden saymak.
En kısa yol: bütün güzergâhları sırala ve topla; en kısa güzergâh en az yollu olmayabilir.

Kendini test et

12 soru. Her doğru cevap XP kazandırır.

1 / 12

Yönsüz bir grafın komşuluk matrisinde X satırı ile Y sütununun kesiştiği yerde 1 yazılı. Bu ne anlama gelir?