🕸️ 10.1: Graf (Graph) Nedir?

Düğümler ve Kenarlarla Modelleme - Detaylı Anlatım

📌 Bu Bölümde Öğrenecekleriniz

🕸️

Graf Nedir?

Temel kavramlar

🔀

Yönlü vs Yönsüz

Graf türleri

⚖️

Ağırlıklı Graflar

Kenar ağırlıkları

🌍

Kullanım Alanları

Gerçek dünya

🎯 Graf Nedir?

Graf (Graph), düğümler (vertices/nodes) ve bunları birbirine bağlayan kenarlardan (edges) oluşan bir veri yapısıdır. Matematiksel olarak G = (V, E) şeklinde gösterilir.

🌍 Günlük Hayattan Örnekler

  • Sosyal Ağlar: Kişiler = Düğümler, Arkadaşlıklar = Kenarlar (Facebook, Instagram)
  • Harita/Navigasyon: Şehirler = Düğümler, Yollar = Kenarlar (Google Maps)
  • İnternet: Web sayfaları = Düğümler, Linkler = Kenarlar (Google PageRank)
  • Uçuş Ağları: Havalimanları = Düğümler, Uçuş rotaları = Kenarlar

🎮 İnteraktif Graf Örneği

Düğümlere tıklayarak seçin, sürükleyerek konumlarını değiştirin

📚 Temel Terminoloji

📖 Graf Terminolojisi - Bunları İyi Öğrenin!

Düğüm (Vertex/Node): Grafın temel birimi. Bir varlığı temsil eder. Örneğin: Bir kişi, şehir, web sayfası, veya herhangi bir obje.
Kenar (Edge): İki düğüm arasındaki bağlantı. İlişkiyi temsil eder. Örneğin: Arkadaşlık, yol, hyperlink.
Komşu (Adjacent/Neighbor): Aralarında kenar bulunan iki düğüm birbirinin komşusudur. A — B varsa, A ve B komşudur.
Derece (Degree): Bir düğüme bağlı kenar sayısı.
  • In-degree: Yönlü graflarda, düğüme gelen kenar sayısı
  • Out-degree: Yönlü graflarda, düğümden çıkan kenar sayısı
Yol (Path): Bir düğümden diğerine giden kenar dizisi. A → B → C bir yoldur. Yol uzunluğu = kenar sayısı.
Döngü (Cycle): Başladığı düğüme geri dönen yol. A → B → C → A bir döngüdür.
Bağlantılı Graf (Connected Graph): Her düğüm çiftinin arasında en az bir yol var. Yönsüz graflarda kullanılır.
Bağlantılı Bileşen (Connected Component): Maksimal bağlantılı alt graf. Bir grafta birden fazla bileşen olabilir (adalar gibi düşünün).

🔀 Graf Türleri

↔️ Yönsüz Graf (Undirected)

Kenarların yönü yoktur. A—B demek hem A'dan B'ye hem B'den A'ya gidilebilir demektir.

Örnekler:
  • Facebook arkadaşlığı (karşılıklı)
  • Şehirler arası çift yönlü yollar
  • Telefon bağlantıları

➡️ Yönlü Graf (Directed/Digraph)

Kenarların yönü vardır. A→B demek sadece A'dan B'ye gidilebilir demektir, tersi ayrı kenar gerektirir.

Örnekler:
  • Twitter/Instagram takip etme
  • Web sayfaları ve linkler
  • Görev bağımlılıkları (prerequisite)

⚖️ Ağırlıklı Graf (Weighted)

Her kenarın bir ağırlık/maliyet değeri vardır. Mesafe, süre, maliyet gibi bilgileri taşır.

Örnekler:
  • Harita: Şehirler arası km
  • Ağ: Bağlantı gecikmesi (latency)
  • Uçuş: Bilet fiyatları

🔲 Ağırlıksız Graf (Unweighted)

Kenarlarda ağırlık yoktur (veya hepsi 1 kabul edilir). Sadece bağlantı var/yok bilgisi.

Örnekler:
  • Arkadaşlık ağı (bağlı mı değil mi)
  • Labirent (geçilebilir mi)
  • Ders bağımlılıkları

🌳 Özel Graf Türleri

🌲 Ağaç (Tree)

Döngüsüz, bağlantılı graf. N düğüm için tam olarak N-1 kenar vardır.

Önceki bölümlerde BST olarak gördük!

🔄 DAG (Directed Acyclic Graph)

Yönlü ve döngüsüz graf. Görev planlaması, derleyici optimizasyonu, Git commit geçmişi.

Topological Sort için gerekli!

🎨 İki Parçalı Graf (Bipartite)

Düğümler iki kümeye ayrılabilir ve kenarlar sadece farklı kümeler arasında.

Eşleştirme problemleri için kullanılır.

🔗 Tam Graf (Complete Graph)

Her düğüm çifti arasında kenar var. N düğümlü tam grafta N(N-1)/2 kenar vardır.

En yoğun graf türü.

📊 Seyrek vs Yoğun Graflar

Graf algoritmaları seçerken grafın yoğunluğu çok önemlidir:

Özellik Seyrek Graf (Sparse) Yoğun Graf (Dense)
Kenar Sayısı |E| ≈ O(|V|) |E| ≈ O(|V|²)
Temsil Yöntemi Adjacency List ✅ Adjacency Matrix ✅
Gerçek Dünya Sosyal ağlar, yol ağları Küçük ağlar, tam bağlı sistemler

💡 Pratikte Çoğu Graf Seyrektir!

Facebook'ta 2 milyar kullanıcı var ama herkes herkesle arkadaş değil. Ortalama arkadaş sayısı ~200. Bu da toplam kenar sayısının 2×10⁹ × 200 / 2 ≈ 2×10¹¹ olduğu anlamına gelir. Tam grafta ise 2×10¹⁸ kenar olurdu - 10 milyon kat daha fazla!

🌍 Gerçek Dünya Uygulamaları

🗺️

Navigasyon & Haritalar

Google Maps, Waze gibi uygulamalar grafları kullanarak en kısa yolu bulur. Dijkstra ve A* algoritmaları kullanılır.

👥

Sosyal Ağ Analizi

Facebook arkadaş önerileri, influence detection, topluluk tespiti. BFS ile "6 derece ayrımı" hesaplanır.

🔍

Arama Motorları

PageRank algoritması web sayfalarını bir graf olarak modeller. Önemli sayfalar daha çok link alır.

🎮

Oyun Geliştirme

NPC yol bulma (pathfinding), oyun haritaları, karar ağaçları. A* algoritması çok yaygın.

🧬

Biyoinformatik

Protein etkileşim ağları, gen düzenleme ağları, salgın yayılım modelleri.

📡

Ağ Tasarımı

İnternet yönlendirme, ağ topolojisi optimizasyonu, spanning tree protokolleri.

⚡ Graf Problemleri Özeti

🧭 Bu Bölümde Ele Alacağımız Konular

  • 📦 Graf Temsili: Adjacency Matrix vs Adjacency List
  • 🔍 BFS (Breadth-First Search): Seviye seviye arama, en kısa yol (ağırlıksız)
  • 🔎 DFS (Depth-First Search): Derinlemesine arama, döngü tespiti, bağlantılı bileşenler
  • 🎯 Dijkstra Algoritması: Ağırlıklı graflarda en kısa yol
  • 🐍 Python Implementasyonu: networkx, pratik örnekler
  • 🌍 Gerçek Dünya Örnekleri: Harita, sosyal ağ, web crawler
Problem Algoritma Zaman Karmaşıklığı
En kısa yol (ağırlıksız) BFS O(V + E)
En kısa yol (ağırlıklı, pozitif) Dijkstra O((V + E) log V)
Döngü tespiti DFS O(V + E)
Bağlantılı bileşenler BFS/DFS O(V + E)
Topological Sort DFS (Kahn's) O(V + E)