Akademik Dersler - Tanıtım


Ders Kodu - Ders Adı	MAT647 - Algoritmik Çizge Kuramı
Ders Türü	Seçmeli Dersler
Ders Dili	Türkçe
Teori + Uygulama	3+0
AKTS	7.5
Öğretim Elemanları	PROFESÖR DOKTOR EMRAH AKYAR
Dersin Veriliş Biçimi	Bu ders yüz yüze ve/veya uzaktan öğretim şeklinde yürütülmektedir.
Dersin Önkoşulları	Yok
Önerilen Dersler	Çizge Kuramına Giriş
Zorunlu ya da Önerilen Kaynaklar	Gary Chartrand, Ortrud R. Oellermann, Applied and Algorithmic Graph Theory, McGraw-Hill, 1992.
Okuma Listesi	Gary Chartrand, Ortrud R. Oellermann, Applied and Algorithmic Graph Theory, McGraw-Hill, 1992.
Değerlendirme	Bir ara sınav ve bir dönem sonu sınavı.
Staj & Uygulama
Sürdürülebilir Kalkınma Amaçları

Haftalar	Konular
1. hafta	Çizgelere giriş, temel kavramlar, çizge türleri ve problemlerin çizgelerle modellenmesi.
2. hafta	Algoritma karmaşıklığına giriş, büyüme notasyonları ve algoritmaların verimliliğinin analizi.
3. hafta	Veri yapıları, komşuluk gösterimleri ve derin öncelikli arama (DFS) algoritması.
4. hafta	Genişlik öncelikli arama (BFS), en kısa yol kavramı ve DFS ile karşılaştırılması.
5. hafta	Kapsayan ağaç kavramı, kapsayan ağaçların özellikleri ve oluşturulması.
6. hafta	Minimum kapsayan ağaç problemleri ve Kruskal ile Prim algoritmaları.
7. hafta	Kapsayan ağaçların sayılması ve Kirchhoff’un matriks-ağaç teoremi.
8. hafta	Düzlemsel çizgeler, Euler formülü ve düzlemsellik kriterleri.
9. hafta	Çizgelerde eşleme, maksimum eşleme ve Hall teoremi.
10. hafta	Euler yolları ve turları, Euler kriterleri ve postacı problemleri.
11. hafta	Hamilton yolları ve döngüleri, varlık teoremleri ve gezgin satıcı problemi.
12. hafta	Çizge boyama, kromatik sayı, baskın kümeler, bağımsız kümeler ve hizipler.
13. hafta	Çizge problemleri ve karmaşıklık sınıfları, P ve NP kavramları ve indirgenebilirlik.
14. hafta	NP-tam çizge problemleri, bağımsız küme, hizip, Hamilton döngüsü, gezgin satıcı ve çizge boyama problemleri.

Değerlendirme Yöntemi ve Geçme Kriterleri
	Sayısı	Yüzde (%)
1.Ara Sınav	1	40
Dönem Sonu Sınavı	1	60
Toplam (%)		100