| Ders Adı | Kodu | Yerel Kredi | AKTS | Ders (saat/hafta) | Uygulama (saat/hafta) | Laboratuar (saat/hafta) |
|---|---|---|---|---|---|---|
| Graf Teoriye Giriş | MAT4550 | 3 | 5 | 3 | 0 | 0 |
| Önkoşullar | Yok |
|---|
| Yarıyıl | Güz, Bahar |
|---|
| Dersin Dili | İngilizce, Türkçe |
|---|---|
| Dersin Seviyesi | Lisans |
| Dersin Türü | Seçmeli @ Matematik Lisans Programı |
| Ders Kategorisi | Temel Meslek Dersleri |
| Dersin Veriliş Şekli | Yüz yüze |
| Dersi Sunan Akademik Birim | Matematik Bölümü |
|---|---|
| Dersin Koordinatörü | Mehmet Emin Köroğlu |
| Dersi Veren(ler) | Mehmet Emin Köroğlu |
| Asistan(lar)ı |
| Dersin Amacı | Bu dersin amacı, öğrencilere çizge kuramının temel kavramlarını, yapılarını ve algoritmalarını tanıtmaktır. Ders sonunda öğrencilerin, çizgeleri matematiksel bir dil kullanarak modelleyebilmesi, temel çizge parametreleri olan bağlılık, çap, çevre gibi kavramları analiz edebilmesi, ağaç yapılarını ve özelliklerini kavraması ve en kısa yol, minimum geren ağaç gibi temel algoritmik problemleri çözme yeteneği kazanması hedeflenmektedir. Ayrıca, Euler ve Hamilton döngüleri ile çizge renklendirme gibi klasik problemler hakkında teorik bir altyapı oluşturmak dersin temel amaçlarındandır. |
|---|---|
| Dersin İçeriği | Graf teorisinin temel kavramları (köşe, kenar, derece), graf türleri, altgraflar ve geren altgraflar, bağlılık, yürüyüşler, yollar ve çevrimler; graf metrikleri (çap, yarıçap, çevre); iki parçalı, bağlantılı, tam graflar ve karakterizasyonları; graf izomorfizması ve matris temsilleri; ağaçlar ve özellikleri, geren ağaçlar, Kruskal ve Prim algoritmaları; en kısa yol problemi ve Dijkstra algoritması; Euler turları ve Hamilton çevrimleri; graf renklendirme ve kromatik sayı. |
| Ders Kitabı / Malzemesi / Önerilen Kaynaklar |
|
| Opsiyonel Program Bileşenleri | Yok |
Ders Öğrenim Çıktıları
- Çizge kuramının köşe, kenar, derece, yol, döngü gibi temel kavramlarını tanımlayarak ve bu kavramları kullanarak bir çizgenin temel yapısal özelliklerini analiz edebileceklerdir.
- Bir çizgenin altçizgelerini, geren altçizgelerini ve bağlı bileşenlerini belirleyebileceklerdir.
- Bipartite çizgeleri tanıyarak; bir çizgenin bipartite olup olmadığını döngü yapısına göre kanıtlayabileceklerdir.
- İki çizgenin izomorfik olup olmadığını analiz edip; çizgeleri komşuluk ve kesişim matrisleri ile temsil edebileceklerdir.
- Ağaçların temel özelliklerini anlayıp, ispatlayarak, bir çizge içindeki minimum geren ağacı Kruskal veya Prim algoritmalarını kullanarak bulabileceklerdir.
- Ağırlıklı bir çizgede verilen iki köşe arasındaki en kısa yolu Dijkstra algoritmasını kullanarak hesaplayabileceklerdir.
- Bir çizgenin Euler turuna veya Hamilton döngüsüne sahip olup olmadığını belirlemek için gerekli teoremleri uygulayabileceklerdir.
- Çizge renklendirme problemini anlayarak, basit çizgeler için kromatik sayıyı hesaplayabileceklerdir.
Ders Öğrenim Çıktısı & Program Çıktısı Matrisi
| DÖÇ-1 | DÖÇ-2 | DÖÇ-3 | DÖÇ-4 | DÖÇ-5 | DÖÇ-6 | DÖÇ-7 | DÖÇ-8 |
Haftalık Konular ve İlgili Ön Hazırlık Çalışmaları
| Hafta | Konular | Ön Hazırlık |
|---|---|---|
| 1 | Konu Anlatımı: Giriş, temel tanımlar: köşe, kenar (ayrıt), komşuluk, derece; graf türleri (basit, yönlü, ağırlıklı); derece-toplam formülü (El Sıkışma Teoremi) Sınıf-içi Uygulama (5 dk.): Königsberg köprü problemi ile motivasyonun verilmesi Sınıf-içi Tartışma (5 dk.): Grafların öneminin ve uygulama alanlarının tartışılması | 1. Kümeler ve fonksiyonlar konularının hatırlanması. Kaynak: [2], 115-138. 2. Temel graf tanımları bölümünün okunması. Kaynak: Ders Kitabı, 1-13. |
| 2 | Konu Anlatımı: Altgraflar (subgraphs), indüklenmiş altgraflar (induced), geren altgraflar (spanning); yürüyüş (walk), yol/patika (path), çevrim/döngü (cycle); bağlı (connected) graflar ve bileşenler Sınıf-içi Uygulama (10 dk.): Her kavrama küçük, anlamayı kolaylaştıran örneklerin verilmesi Sınıf-içi Tartışma (5 dk.): Temel kavramların irdelenmesi hakkında bir tartışma yapılması | 1. Temel ispat yöntemlerinin (doğrudan, çelişkiyle) hatırlanması. Kaynak: [2], 81-103. 2. Yollar ve çevrimler bölümünün okunması. Kaynak: Ders Kitabı, 20-25. |
| 3 | Konu Anlatımı: Euler turları: Königsberg köprü problemi. bir grafta Euler turu/patikası bulunması için gerek ve yeter koşullar ve ispatı; Hamilton çevrimleri: tanım ve problem zorluğu; Hamilton çevriminin varlığı için yeterlilik koşulları (Dirac ve Ore Teoremleri) Sınıf-içi Uygulama (10 dk): Anlamayı kolaylaştıran örneklerin verilmesi Sınıf-içi Tartışma (5 dk.): Bir grafta Hamilton çevriminin varlığının araştırılması üzerine bir tartışma yapılması | 1. Temel sayma prensipleri konusunun hatırlanması. "ancak ve ancak" ispat yapısının hatırlanması. NP-Tamlık (NP-Completeness) kavramının okunması. Kaynaklar: [2], 82. [2], 385-404. [1], 1048-106. 2. Euler turları bölümünün okunması. Hamilton çevrimleri bölümünün okunması. Kaynaklar: Ders Kitabı, 259-266; 273-280. |
| 4 | Konu Anlatımı: Özel graf türleri: tam graf (Kₙ), iki parçalı graf, tam iki parçalı graf (Kₘ,ₙ), düzenli graf; graf metrikleri: uzaklık, çap (diameter), kuşak (girth) Sınıf-içi Uygulama (10 dk): Küçük mertebeden özel grafların çizilmesi. Sınıf-içi Tartışma (5 dk.): Graf metriklerinin aralarındaki ilişkinin tartışılması | 1. Çelişkiyle ispat yönteminin pekiştirilmesi. Kaynak: [2], 86-87. 2. İki parçalı graflar bölümünün okunması. Kaynak: Ders Kitabı, 27-29. |
| 5 | Konu Anlatımı: Graf izomorfizması; grafların matris temsilleri: komşuluk matrisi, kesişim, bağlantı matrisi ve özellikleri Sınıf-içi Uygulama (10 dk): Verilen bazı grafların bağlantı matrislerinin bulunması Sınıf-içi Tartışma (5 dk.): Verilen iki grafın izomorf olup olmadığının tartışılması | 1. Matrisler konusunun hatırlanması. Kaynak: [2], 171-178. 2. İzomorfizma ve matrisler bölümlerinin okunması. Kaynak: Ders Kitabı, 10-13; 44-46. |
| 6 | Konu Anlatımı: Ağaçlar (trees): tanımı ve eşdeğer tanımları (bağlı ve çevrimsiz, n köşe n-1 kenar vb.); yapraklar (leaves); ormanlar (forests) Sınıf-içi Uygulama (10 dk.): Anlamayı kolaylaştıran örneklerin verilmesi Sınıf-içi Tartışma (5 dk.): Ağaçların uygulamadaki öneminin tartışılması | 1. Tümevarım ve ispat konusunun hatırlanması. Kaynak: [2], 311-333. 2. Ağaçların özellikleri bölümünün okunması. Kaynak: Ders Kitabı, 67-73. |
| 7 | Konu Anlatımı: Geren ağaçlar (spanning trees); minimum geren ağaç (mst) problemi Sınıf-içi Uygulama (10 dk.): Anlamayı kolaylaştıran örneklerin verilmesi Sınıf-içi Tartışma (5 dk.): Minimum geren ağaç probleminin irdelenmesi üzerine bir tartışma yapılması | 1. Açgözlü (greedy) algoritmalar fikrinin hatırlanması. Kaynak: [1], 414-419. 2. Kruskal algoritması bölümünün okunması. Kaynak: Ders Kitabı, 84-85. |
| 8 | Ara Sınav 1 | |
| 9 | Konu Anlatımı: Prim ve Kruskul algoritması ve örnek uygulamaları; algoritmaların karşılaştırılması Sınıf-içi Uygulama (40 dk.): Verilen ağırlıklı bir grafta iki algoritmayı da kullanarak minimum germe ağacının bulunması. Sınıf-içi Tartışma (5 dk.): Prim ve Kruskal algoritmalarının karşılaştırılması üzerine bir tartışma yapılması | 1. Öncelik kuyrukları (priority queues) ve yığın (heap) veri yapılarının hatırlanması. Kaynak: [1], 151-169. 2. Prim algoritması bölümünün okunması. Kaynak: Ders Kitabı, 86-87. |
| 10 | Konu Anlatımı: En kısa yol problemi; Dijkstra algoritması ve uygulamaları. Sınıf-içi Uygulama (40 dk.): Verilen ağırlıklı bir grafta algoritmayı kullanarak en kısa yolun bulunması. Sınıf-içi Tartışma (5 dk.): Dijkstra algoritmasının avantajlarının tartışılması | 1. Algoritma karmaşıklığı (asimptotik notasyon) konusunun hatırlanması. Kaynak: [1], 43-61. 2. Dijkstra algoritması bölümünün okunması. Kaynak: Ders Kitabı, 87-90. |
| 11 | Konu Anlatımı: Graf renklendirme: köşe renklendirme; kromatik sayı (χ(G)); basit graflar için kromatik sayıya dair üst sınırlar Sınıf-içi Uygulama (15 dk.): Verilen grafların kromatik sayısının bulunması Sınıf-içi Tartışma (5 dk.): Kromatik sayının sınırlarıyla ilgili teoremlerin irdelenmesi hakkında bir tartışma yapılması | 1. Kuvvetli tümevarım (strong induction) konusunun hatırlanması. Kaynak: [2], 327-333. 2. Köşe renklendirme bölümünün okunması. Kaynak: Ders Kitabı, 187-194. |
| 12 | Konu Anlatımı: Öğrenci sunumları Sınıf-içi Tartışma (15 dk.): Sunumda anlatılan konuların bir tartışma ortamı içinde irdelenmesi Kısa Sınav (30 dk.): Ders sonunda, derste işlenen konuları içeren bir kısa sınavın yapılması | 1. Sınav haftasına kadar işlenen konuların tümünün tekrar edilmesi 2. Bazı özel konuların okunması. Kaynak: Ders Kitabı, 319-452. |
| 13 | Konu Anlatımı: Öğrenci sunumları Sınıf-içi Tartışma (15 dk.): Sunumda anlatılan konuların bir tartışma ortamı içinde irdelenmesi | 1. Bazı özel konuların okunması. Kaynak: Ders Kitabı, 319-452. |
| 14 | Konu Anlatımı: Öğrenci sunumları Sınıf-içi Tartışma (15 dk.): Sunumda anlatılan konuların bir tartışma ortamı içinde irdelenmesi | 1. Bazı özel konuların okunması. Kaynak: Ders Kitabı, 319-452. |
| 15 | Konu Anlatımı: Genel tekrar Sınıf-içi Uygulama (30 dk): İşlenen tüm konular ile ilgili çeşitli örneklerin çözülmesi Sınıf-içi Tartışma (10 dk): Dersin genel kazanımlarının değerlendirilmesi ve tartışılması | 1. İşlenen tüm kavramların hatırlanması ve önceki haftalardaki kısımların okumalarının yapılması. |
| 16 | Final |
Değerlendirme Sistemi
| Etkinlikler | Sayı | Katkı Payı |
|---|---|---|
| Devam/Katılım | 14 | 5 |
| Laboratuar | ||
| Uygulama | ||
| Arazi Çalışması | ||
| Derse Özgü Staj | ||
| Küçük Sınavlar/Stüdyo Kritiği | 1 | 5 |
| Ödev | 1 | 10 |
| Sunum/Jüri | 1 | 10 |
| Projeler | ||
| Seminer/Workshop | ||
| Ara Sınavlar | 1 | 30 |
| Final | 1 | 40 |
| Dönem İçi Çalışmaların Başarı Notuna Katkısı | ||
| Final Sınavının Başarı Notuna Katkısı | ||
| TOPLAM | 100 | |
AKTS İşyükü Tablosu
| Etkinlikler | Sayı | Süresi (Saat) | Toplam İşyükü |
|---|---|---|---|
| Ders Saati | 14 | 3 | |
| Laboratuar | |||
| Uygulama | |||
| Arazi Çalışması | |||
| Sınıf Dışı Ders Çalışması | 14 | 2 | |
| Derse Özgü Staj | |||
| Ödev | 1 | 20 | |
| Küçük Sınavlar/Stüdyo Kritiği | 1 | 5 | |
| Projeler | |||
| Sunum / Seminer | 1 | 10 | |
| Ara Sınavlar (Sınav Süresi + Sınav Hazırlık Süresi) | 1 | 15 | |
| Final (Sınav Süresi + Sınav Hazırlık Süresi) | 1 | 30 | |
| Toplam İşyükü : | |||
| Toplam İşyükü / 30(s) : | |||
| AKTS Kredisi : | |||
| Diğer Notlar | Yok |
|---|
