📚 Ayrık Yapılar (Diskrete Strukturen) - Ders Notları

Hafta 1-8 kapsamlı özet | Temel kavramlardan ileri seviye çizge teorisine

Bu belge, Ayrık Yapılar dersinin sistematik bir özetini sunmaktadır. Her bölümde temel Türkçe açıklamalar ve önemli Almanca terimler birlikte verilmiştir.

📑 İçindekiler

  1. Temel Yapılar
  2. İlişkiler
  3. Tümevarım İspatları
  4. Çizge Teorisi

1. Temel Yapılar

1.1 Kümeler (Mengen)

Kümeler, iyi tanımlanmış ve birbirinden farklı nesnelerin topluluğudur.

Temel Kavramlar:

  • Kardinalite (Mächtigkeit): |M| - Kümenin eleman sayısı
  • Kuvvet Kümesi (Potenzmenge): P(M) veya 2^M - Tüm alt kümelerin kümesi
    • n elemanlı bir kümenin kuvvet kümesi 2^n elemana sahiptir
  • Temel İşlemler:
    • Birleşim: A ∪ B - Her iki kümede de olan elemanlar
    • Kesişim: A ∩ B - Her iki kümede ortak olan elemanlar
    • Tümleyen: Ā - Evrensel kümede olup A’da olmayan elemanlar

Özel Kavram - Ayrışım (Partition):

Küme M'nin bir ayrışımı {M₁, M₂, ..., Mₙ} şu özelliklere sahiptir:
• Mᵢ ∩ Mⱼ = ∅ (i ≠ j için, ayrık kümeler)
• M₁ ∪ M₂ ∪ ... ∪ Mₙ = M (birleşim tüm kümeyi verir)

1.2 Demetler vs Kümeler (Tupel vs Mengen)

Kritik Fark: Demetlerde sıra önemlidir ve tekrar olabilir!

Özellik Küme Demet
Sıra Önemsiz Önemli
Tekrar Yok Olabilir
Örnek 1 {1, 2} = {2, 1} (1, 2) ≠ (2, 1)
Örnek 2 {1, 2, 1} = {1, 2} (1, 2, 1) ≠ (1, 2)

1.3 Kartezyen Çarpım (Kartesisches Produkt)

İki kümenin tüm olası sıralı çiftlerinin kümesi:

A × B = {(a, b) : a ∈ A, b ∈ B}

Örnek: A = {1, 2}, B = {x, y}
A × B = {(1,x), (1,y), (2,x), (2,y)}
|A × B| = |A| · |B| = 4

2. İlişkiler (Relationen)

İlişkiler, kümeler arası bağlantıları matematiksel olarak ifade eder.

2.1 Temel Tanım

İlişki: Kartezyen çarpımın bir alt kümesi

R ⊆ A × B
(a, b) ∈ R → "a ile b ilişkilidir"

İkili İlişki (Binäre Relation): R ⊆ A × A

  • Bir kümenin kendi üzerindeki ilişkisi
  • Yönlü çizge (Digraph) olarak görselleştirilebilir

2.2 İlişki Bileşkesi (Komposition)

İki ilişkiyi zincirleyerek yeni bir ilişki oluşturma:

R ⊆ A × B,  S ⊆ B × C  ⇒  S ∘ R ⊆ A × C

(a, c) ∈ S ∘ R  ⟺  ∃b: (a,b) ∈ R ∧ (b,c) ∈ S

Önemli: R² = R ∘ R çizgede uzunluk 2’lik tüm yolları temsil eder!

2.3 Kapantılar (Hüllen)

İlişkilere eksik bağlantıları ekleyerek genişletme:

Geçişli Kapantı (Transitive Hülle) - R⁺:

  • Tüm dolaylı bağlantıları ekler
  • A→B ve B→C varsa, A→C eklenir
  • Çizgede: Tüm yolları doğrudan bağlantı haline getirir

Yansımalı-Geçişli Kapantı - R:*

  • R⁺ + her düğümün kendine bağlantısı (a,a)
  • “Erişilebilirlik” ilişkisini temsil eder

2.4 İlişki Özellikleri

Bir ilişkinin yapısını karakterize eden özellikler:

Özellik Tanım Çizge Anlamı Örnek
Yansımalı(reflexiv) ∀a: (a,a) ∈ R Her düğümün kendine oku ≤
Simetrik(symmetrisch) (a,b) ∈ R ⇒ (b,a) ∈ R Oklar çift yönlü =
Antisimetrik(antisymmetrisch) (a,b) ∈ R ∧ (b,a) ∈ R ⇒ a=b Tek yönlü oklar ≤
Asimetrik(asymmetrisch) (a,b) ∈ R ⇒ (b,a) ∉ R Hiç çift yönlü ok yok <
Geçişli(transitiv) (a,b), (b,c) ∈ R ⇒ (a,c) ∈ R Zincirleme bağlantılar <

2.5 Özel İlişki Türleri

Denklik İlişkisi (Äquivalenzrelation):

  • Özellikler: Yansımalı + Simetrik + Geçişli
  • Kümeyi “eşdeğer” sınıflara böler
  • Örnekler: Eşitlik (=), Modulo ilişkisi (≡)

Kısmi Sıralama (Partielle Ordnung - PO):

  • Özellikler: Yansımalı + Antisimetrik + Geçişli
  • Elemanlar arası “büyüklük” ilişkisi
  • Örnekler: ≤, ⊆ (alt küme)

Katı Kısmi Sıralama (Strikte PO):

  • Özellikler: Yansımasız + Antisimetrik + Geçişli
  • Örnekler: <, ⊂ (öz alt küme)

3. Tümevarım İspatları (Induktion)

Ayrık yapıların en güçlü ispat tekniği - domino taşı prensibi!

3.1 Klasik Tümevarım

Üç Adımlı Yöntem:

1. TEMEL DURUM (Basisfall)
   P(1)'in doğru olduğunu göster
   
2. TÜMEVARIM ADIMI (Induktionsschritt)
   Varsay: P(k) doğru (Tümevarım Varsayımı)
   Kanıtla: P(k) ⇒ P(k+1)
   
3. SONUÇ (Schlussfolgerung)
   P(1) doğru ve P(k) ⇒ P(k+1) doğru
   ∴ ∀n ∈ ℕ: P(n) doğru

3.2 Klasik Örnek: Gauss Formülü

İddia: 1 + 2 + 3 + ... + n = n(n+1)/2

İspat:

  • Temel: n=1 için: 1 = 1(2)/2 = 1 ✓

  • Adım: P(k) doğru olsun, yani 1+2+...+k = k(k+1)/2

    P(k+1) için:

    1+2+...+k+(k+1) = k(k+1)/2 + (k+1)
                 = (k+1)(k/2 + 1)
                 = (k+1)(k+2)/2  ✓

  • Sonuç: Tüm n için doğru

3.3 Hanoi Kuleleri Örneği

Problem: n diski A çubuğundan C’ye taşı (B yardımcı)

İddia: Minimum adım sayısı = 2^n - 1

İspat Stratejisi:

n+1 disk için:
├─ Üstteki n diski B'ye taşı     → 2^n - 1 adım (varsayım)
├─ En büyük diski C'ye taşı      → 1 adım
└─ n diski B'den C'ye taşı       → 2^n - 1 adım (varsayım)

Toplam: (2^n - 1) + 1 + (2^n - 1) = 2^(n+1) - 1 ✓

3.4 Güçlü Tümevarım (Starke Induktion)

Fark: Sadece P(k) değil, P(1), P(2), …, P(k)’nin HEPSİNİ varsayabilirsiniz!

Ne Zaman Kullanılır: Çizge ispatlarında, özellikle yapıyı parçalara böldüğümüzde

4. Çizge Teorisi (Graphentheorie)

Ders notlarının en kapsamlı konusu. Düğümler (Knoten) ve kenarlardan (Kanten) oluşan yapılar.

4.1 Temel Kavramlar

Çizge Tanımı: G = (V, E)

  • V: Düğümler kümesi (Vertices/Knoten)
  • E: Kenarlar kümesi (Edges/Kanten)

Bağlantılılık (Zusammenhang):

Tür Tanım Geçerlilik
Bağlantılı Her düğüm çiftine yol var Yönsüz çizgeler
Kuvvetli Bağlantılı Her düğüm çiftine yönlü yol var Yönlü çizgeler

Bağlantılı Bileşen (ZHK): Maksimal bağlantılı alt çizge

4.2 Önemli Çizge Kavramları

Eşyapısallık (Isomorphie) - G₁ ≅ G₂:

İki çizge yapısal olarak aynıdır ⟺
Düğümler arası birebir eşleme (Bijektion) var ve
bu eşleme kenar ilişkilerini korur

Çevre (Zyklus/Kreis): Bir düğümden başlayıp aynı düğüme dönen yol

DAG (Directed Acyclic Graph): Çevre içermeyen yönlü çizge

  • Topolojik sıralama yapılabilir (örn: görev bağımlılıkları)

Zincir (Chain): Karşılaştırılabilir düğümler (birbirine erişilebilen)

Antizincir (Antichain): Karşılaştırılamaz düğümler (birbirine erişilemeyen)

4.3 Çizgelerde Tümevarım

DOĞRU YÖNTEM ✓:

1. P(1), ..., P(k) doğru olsun (güçlü tümevarım)
2. n=k+1 düğümlü RASTGELE bir G çizgesi al
3. Bir düğüm/kenar ÇıKAR → k durumuna in
4. Varsayımı uygula
5. Çıkardığını geri koy ve sonucu kanıtla

YANLIŞ YÖNTEM ✗:

  • k durumuna eleman EKLEYEREK k+1 oluşturmak
  • Neden yanlış? Tüm k+1 durumlarını kapsamaz!

Klasik Teorem:

Basit, bağlantılı n düğümlü çizgenin en az n-1 kenarı vardır

İspat İdeası:

  • Bir düğüm u’yu çıkar → Çizge d bileşene ayrılabilir
  • Her bileşene güçlü tümevarım uygula
  • u’nun en az d kenarı olmalı (her bileşene bağlanmak için)
  • Sonuç: m ≥ (n-d) + d = n - 1 + d ≥ n - 1

4.4 Özel Çizge Türleri ve Algoritmalar

Minimum Kapsayan Ağaç (MST - Minimaler Spannbaum):

  • Tüm düğümleri bağlayan minimum toplam ağırlıklı ağaç
  • Algoritmalar: Kruskal, Prim

Euler Turu (Euler Kreis):

  • Her kenardan tam bir kez geçen kapalı yol
  • Koşul: Çizge bağlantılı + her düğümün derecesi çift
  • Örnek: Bir kağıdı tek çizgide çizmek

Hamilton Turu (Hamilton Kreis):

  • Her düğümden tam bir kez geçen kapalı yol
  • Genel koşul yok (NP-tam problem!)
  • Örnek: Gezgin satıcı problemi

4.5 Çizge Boyama (Knotenfärbung)

Problem: Komşu düğümlere farklı renk ver

Kromatik Sayı χ(G): Gereken minimum renk sayısı

Özel Durumlar:

  • İkili çizge: χ(G) = 2
  • Tam çizge Kₙ: χ(G) = n
  • Çevre Cₙ: χ(G) = 2 (n çift), 3 (n tek)

Açgözlü (Greedy) Algoritma:

1. Düğümleri dereceye göre AZALAN sırala
2. İlk düğüme Renk 1
3. Listede ilerle, Renk 1'li komşusu olmayan herkese Renk 1
4. İlk boyanmamış düğüme Renk 2
5. Tekrarla (3-4) tüm düğümler boyanana kadar

Not: Greedy optimum garanti etmez ama iyi bir üst sınır verir!

🎯 Özet ve Bağlantılar

Kümeler → İlişkiler → Çizgeler
   ↓          ↓          ↓
Temel     Yapısal    Algoritmik
Yapılar   Özellikler  Problemler
   ↓          ↓          ↓
   └──── Tümevarım ────┘
      (Tümünü Kanıtlar)

Önemli Dersler:

  1. Terimler önemli: Almanca terimleri öğrenin (sınavlarda gerekir)
  2. Tümevarımı ustalaşın: En çok kullanılan ispat tekniği
  3. Çizge düşünün: Soyut problemleri çizge olarak görselleştirin
  4. Örnekler çözün: Teori anlaşılır ama pratik önemli!

Kapsam: Diskrete Strukturen Tam Özet