Graf Teorisi: Temel Kavramlar ve Uygulamalar
Graf Nedir?
Graf teorisi, düğümler (veya köşeler) ve bu düğümleri birbirine bağlayan kenarlar (veya yaylar) kümesinden oluşan matematiksel bir yapıdır. Graf, \(G = (V, E)\) şeklinde gösterilir, burada \(V\) düğüm kümesini ve \(E\) kenar kümesini temsil eder.
Temel Terimler
- Düğüm (Köşe): Grafın temel birimleridir. Genellikle noktalarla gösterilirler.
- Kenar (Yay): İki düğümü birbirine bağlayan çizgidir. Bir kenar, iki düğüm arasındaki ilişkiyi ifade eder.
- Derece: Bir düğüme bağlı olan kenarların sayısıdır. Bir \(v\) düğümünün derecesi \(d(v)\) ile gösterilir.
- Komşu Düğümler: Bir kenarla birbirine bağlı olan iki düğüme komşu düğümler denir.
- Basit Graf: Birden fazla kenarı olmayan ve kendi kendine döngüsü olmayan (bir düğümü kendisine bağlayan kenar) graflardır.
Graf Türleri
- Yönlü Graf (Yönlü Digraf): Kenarların bir yönü vardır. Bir kenar, \(u\) düğümünden \(v\) düğümüne doğru gider ve \((u, v)\) şeklinde gösterilir.
- Yönsüz Graf: Kenarların belirli bir yönü yoktur. Bir kenar, \(u\) ve \(v\) düğümleri arasındadır ve \(\{u, v\}\) şeklinde gösterilir.
- Ağırlıklı Graf: Her kenarın bir sayısal değeri (ağırlığı) vardır. Bu ağırlıklar maliyet, mesafe veya kapasite gibi anlamlar taşıyabilir.
Graf Teorisi'nin Önemi ve Uygulamaları
Graf teorisi, bilgisayar bilimleri, ağ analizi, lojistik, sosyal ağlar, biyoloji ve daha birçok alanda karmaşık ilişkileri modellemek ve analiz etmek için güçlü bir araçtır. 📌 Gerçek dünyadaki birçok problemi matematiksel olarak ifade etmemizi sağlar.
Graf teorisi, düğümler arasındaki bağlantıları inceleyerek verimliliği artırma, en kısa yolu bulma, ağ güvenliğini sağlama gibi konularda çözümler sunar. 💡
Önemli Özellikler ve Teoremler
- El Sıkışma Teoremi: Bir grafın tüm düğümlerinin derecelerinin toplamı, kenar sayısının iki katına eşittir. \(\sum_{v \in V} d(v) = 2|E|\). Bu, her kenarın iki düğümün derecesini bir artırdığı gerçeğinden kaynaklanır.
- Bağlı Graf: Bir grafın herhangi iki düğümü arasında bir yol varsa, o graf bağlıdır.
✍️ Çözümlü Örnek Sorular
Örnek 1: Dereceleri Hesaplama
Aşağıdaki yönsüz grafın düğümlerinin derecelerini bulunuz:
Düğümler: { \(A, B, C, D\) }
Kenarlar: { \((A, B), (A, C), (B, C), (C, D)\) }
Çözüm:- \(d(A) = 2\) (kenarlar \((A, B)\) ve \((A, C)\))
- \(d(B) = 2\) (kenarlar \((B, A)\) ve \((B, C)\))
- \(d(C) = 3\) (kenarlar \((C, A), (C, B)\) ve \((C, D)\))
- \(d(D) = 1\) (kenar \((D, C)\))
El Sıkışma Teoremi'ni kontrol edelim: \(2 + 2 + 3 + 1 = 8\). Kenar sayısı \(|E| = 4\). \(2|E| = 2 \times 4 = 8\). Teorem doğrulanmıştır. ✅
Örnek 2: Yönlü Graf ve Yollar
Aşağıdaki yönlü grafı göz önüne alalım:
Düğümler: { \(1, 2, 3\) }
Kenarlar: { \((1, 2), (2, 3), (3, 1), (1, 3)\) }
Düğüm \(1\) 'den Düğüm \(3\) 'e kaç farklı basit yol vardır?
Çözüm:Basit yol, tekrar eden düğüm içermeyen yoldur.
- Yol 1: \(1 \to 3\) (Doğrudan kenar)
- Yol 2: \(1 \to 2 \to 3\) (İki kenar kullanarak)
Düğüm \(1\) 'den Düğüm \(3\) 'e \(2\) farklı basit yol vardır. 🚀
Bir grafın 7 köşesi ve 11 kenarı bulunmaktadır. Bu grafın tüm köşelerinin dereceleri toplamı kaçtır?
A) \( 11 \)B) \( 14 \)
C) \( 18 \)
D) \( 22 \)
E) \( 25 \)
6 köşeli bir tam grafta (complete graph, \( K_6 \)) toplam kaç adet kenar bulunur?
B) \( 12 \)
C) \( 15 \)
D) \( 18 \)
E) \( 30 \)
Köşelerinin dereceleri \( 3, 4, 2, 5 \) ve \( x \) olan 5 köşeli bir grafın toplam 9 kenarı olduğu bilinmektedir. Buna göre \( x \) değeri kaçtır?
B) \( 3 \)
C) \( 4 \)
D) \( 5 \)
E) \( 6 \)
Aşağıda verilen derece dizilerinden hangisi 4 köşeli bir basit graf (simple graph) oluşturabilir?
B) \( (2, 2, 1, 1) \)
C) \( (3, 3, 3, 3) \)
D) \( (4, 2, 2, 2) \)
E) \( (3, 2, 1, 1) \)
Graf teorisinde, başladığı köşede biten ve hiçbir kenarı tekrar etmeyen kapalı yürüyüşe ne ad verilir?
B) Devre (Circuit)
C) Köşe dizisi
D) Alt graf
E) Komşuluk matrisi
Bir graftaki tüm köşelerin derecelerinin toplamı, o graftaki kenar sayısının iki katına eşittir. Bu kurala "El Sıkışma Teoremi" denir.
Buna göre, 8 köşesi ve 12 kenarı olan bir grafın tüm köşelerinin dereceleri toplamı kaçtır?
B) \( 16 \)
C) \( 20 \)
D) \( 24 \)
E) \( 32 \)
\( n \) adet köşesi olan tam bir grafta (her köşenin diğer tüm köşelere tam olarak bir kenarla bağlı olduğu basit graf) toplam kenar sayısı aşağıdaki formül ile hesaplanır:
\[\(\frac{n(n-1)}{2}\) \] Buna göre, 5 köşeli tam bir grafın (\( K_5 \)) toplam kenar sayısı kaçtır?
B) \( 10 \)
C) \( 15 \)
D) \( 20 \)
E) \( 25 \)
Bir grafın tüm kenarlarından tam olarak bir kez geçilerek çizilebilen yola "Euler Yolu" denir. Bir grafta Euler yolu bulunabilmesi için tek dereceli köşe sayısının 0 veya 2 olması gerekir.
Köşelerinin dereceleri aşağıda verilen graflardan hangisinde bir Euler yolu bulunabilir?
B) \( (2, 2, 3, 3) \)
C) \( (1, 1, 1, 1) \)
D) \( (1, 3, 3, 3) \)
E) \( (3, 3, 3, 5) \)
Basit bir grafta, herhangi iki köşe arasında en fazla bir kenar bulunabilir ve bir köşeden kendisine giden bir kenar (ilmek) bulunamaz.
Buna göre, 6 köşeli bir basit grafta, bir köşenin derecesi en fazla kaç olabilir?
B) \( 4 \)
C) \( 5 \)
D) \( 6 \)
E) \( 7 \)
Bir grafın komşuluk matrisi, köşeler arasındaki bağlantıları 1 ve 0 rakamlarıyla gösterir. 3 köşeli bir basit grafın komşuluk matrisi \( M \) aşağıda verilmiştir:
\[ M \(= \begin{pmatrix} 0\) & 1 & 1 \ 1 & 0 & 0 \ 1 & 0 & \(0 \end{pmatrix}\) \] Buna göre, bu grafta toplam kaç tane kenar vardır?
B) \( 2 \)
C) \( 3 \)
D) \( 4 \)
E) \( 6 \)
Bir graftaki tüm köşelerin derecelerinin toplamı, o graftaki kenar sayısının iki katına eşittir.
Buna göre, 6 köşesi olan ve her bir köşesinin derecesi 3 olan bir grafın toplam kenar sayısı kaçtır?
B) \( 9 \)
C) \( 12 \)
D) \( 15 \)
E) \( 18 \)
\( n \) köşeli bir tam grafta (her köşenin diğer tüm köşelere bir kenar ile bağlı olduğu graf), toplam kenar sayısı aşağıdaki formül ile hesaplanır:
\[\(\frac{n \cdot (n-1)}{2}\) \]
Buna göre, 5 köşeli bir tam grafın (\( K_5 \)) toplam kenar sayısı kaçtır?
B) \( 8 \)
C) \( 10 \)
D) \( 15 \)
E) \( 20 \)
Bir grafta bulunan tüm köşelerin derecelerinin toplamı 24 olarak verilmiştir.
Bu grafın kenar sayısı kaçtır?
B) \( 12 \)
C) \( 24 \)
D) \( 36 \)
E) \( 48 \)
Aşağıda verilen derecelerden hangisi, 4 köşeli basit bir grafa ait bir derece dizisi olabilir?
(Not: Basit bir grafta bir köşenin derecesi en fazla \( n-1 \) olabilir ve dereceler toplamı çift sayıdır.)
B) \( (1, 2, 2, 2) \)
C) \( (3, 3, 3, 2) \)
D) \( (4, 1, 1, 1) \)
E) \( (2, 2, 2, 5) \)
Döngü (çevrim) içermeyen bağlı bir grafa "ağaç" (tree) denir. \( n \) köşeli bir ağaç grafının kenar sayısı her zaman \( n-1 \) formülü ile bulunur.
Buna göre, 10 köşesi olan bir ağaç grafının kenar sayısı kaçtır?
B) \( 9 \)
C) \( 10 \)
D) \( 11 \)
E) \( 20 \)
Bir graftaki tüm köşelerin derecelerinin toplamı 24 olduğuna göre, bu grafta toplam kaç tane kenar bulunur?
\[\(\sum\) d(v) \(= 2 \cdot\) e \]
B) \( 12 \)
C) \( 18 \)
D) \( 24 \)
E) \( 48 \)
5 köşesi bulunan tam bir graftaki (\( K_5 \)) toplam kenar sayısı kaçtır?
\[\(\frac{n \cdot (n-1)}{2}\) \]
B) \( 8 \)
C) \( 10 \)
D) \( 15 \)
E) \( 20 \)
Köşelerinin dereceleri sırasıyla \( 3, 4, 2, 1 \) ve \( 2 \) olan bir grafta toplam kaç kenar vardır?
B) \( 7 \)
C) \( 8 \)
D) \( 9 \)
E) \( 12 \)
Bağlantılı bir grafın "Euler Yolu"na (her kenardan tam bir kez geçen yol) sahip olabilmesi için tek dereceli köşe sayısı en fazla kaç olabilir?
B) \( 1 \)
C) \( 2 \)
D) \( 3 \)
E) \( 4 \)
Her bir köşesinin derecesi 4 olan (4-regüler) ve 6 köşesi bulunan bir grafta toplam kenar sayısı kaçtır?
\[ e \(= \frac{n \cdot k}{2}\) \]
B) \( 10 \)
C) \( 12 \)
D) \( 18 \)
E) \( 24 \)
Bir grafın köşe derecelerinin toplamı, kenar sayısının iki katına eşittir. Köşe dereceleri \( 2, 3, 3, 4, 4 \) ve \( 2 \) olan bir grafın toplam kenar sayısı kaçtır?
A) \( 9 \)B) \( 10 \)
C) \( 12 \)
D) \( 18 \)
E) \( 20 \)
Bir gruptaki 6 arkadaşın her biri, gruptaki diğer tüm arkadaşlarıyla birer kez tokalaşmıştır. Bu durumu temsil eden tam grafın (complete graph, \( K_6 \)) toplam kenar sayısı kaçtır?
A) \( 6 \)B) \( 12 \)
C) \( 15 \)
D) \( 21 \)
E) \( 30 \)
Bir grafın "Euler devresine" (Eulerian circuit) sahip olabilmesi için grafın bağlı olması ve tüm köşelerinin derecelerinin çift sayı olması gerekir. Buna göre, aşağıdaki derece dizilerinden hangisine sahip olan bağlı bir grafın Euler devresi vardır?
A) \( 1, 2, 2, 1 \)B) \( 2, 3, 3, 2 \)
C) \( 2, 4, 4, 2 \)
D) \( 3, 3, 3, 3 \)
E) \( 2, 2, 1, 1 \)
8 köşeli basit bir grafın (simple graph) sahip olabileceği maksimum kenar sayısı kaçtır?
\[ E_{max} \(= \binom{n}{2}\) \]
B) \( 28 \)
C) \( 32 \)
D) \( 56 \)
E) \( 64 \)
Graf teorisinde "Derece Toplamı Teoremi"ne göre, bir graftaki tek dereceli köşelerin sayısı her zaman çift olmak zorundadır. Buna göre, aşağıdaki derece dizilerinden hangisi bir grafa ait olamaz?
A) \( 2, 2, 2, 2 \)B) \( 1, 1, 1, 1 \)
C) \( 3, 3, 2, 2 \)
D) \( 3, 3, 3, 1 \)
E) \( 3, 2, 2, 2 \)
Cevap Anahtarı ve Detaylı Çözümler İçin QR Kodu Okutun
https://yazili.eokultv.com/test/5936-9-sinif-graf-teorisi-test-coz-fkbh