Ders Kodu | Ders Adı | Sınıf | Kredisi | Ders Saati | Haftalık Ders Saati(Teorik) | Haftalık Ders Saati(Uygulama) | Haftalık Ders Saati(Laboratuvar) |
---|---|---|---|---|---|---|---|
GT 3201 | Grafik Teorisi | Üçüncü Sınıf | 5 | 150 | 1 | 2 | 2 |
Öğrencileri grafik teorisinin temel kavramlarıyla tanıştırmak ve onları kullanılabilecekleri bir duruma getirmek; grafik teorisinde problemleri ve bunları çözme yöntemlerini belirleme konusunda ustalaşmak; temel grafik teorisi algoritmalarına hakim olmak; grafik teorisi açısından çeşitli alanlardaki uygulamalı problemleri incelemek.
---
Ayrık Matematik.
Anlatım, fikir alışverişi, tartışma, problem çözme yöntemleri.
1 | Graf teorisinin temel kavramlarını, graf türlerini ve temsil yöntemlerini bilir. |
2 | Grafiklerde en kısa yolları arama ve ağdaki maksimum akışı bulma algoritmalarını anlar. |
3 | Ağaç kavramını ve ağaç özelliklerini bilir. |
4 | Euler ve Hamilton döngülerinin kavramlarını ve bunların varoluş koşullarını bilir. |
5 | Düzlemsel ve düzlemsel grafik kavramlarını, bir grafiğin düzlemsel olması için gerekli ve yeterli koşulları, bir grafiğin kromatik sayısını tahmin etme yöntemlerini bilir. |
6 | Grafik sağlama yöntemlerini kullanır. |
7 | Grafiklerdeki en kısa yolları bulma problemlerini çözmek için klasik algoritmaları kullanır ve değişikliklerini yapar. |
8 | En küçük ağırlıktaki ahşap çerçeveyi oluşturabilme. |
9 | Euler ve Hamilton döngülerini grafiklerde bulabilir. |
10 | Düzlemsel bir grafiği bir düzlemle ilişkilendirebilir, grafiğin düzlemsel olup olmadığını belirleyebilir, grafiğin en uygun rengini bulabilir. |
Haftalık Konu | Değerlendirme Yöntemi | |
---|---|---|
1 | Grafik teorisinin tarihi. Suç ortaklığı. Grafikler ve benzeri nesneler. Grafiklerin izomorfizmi. Değerlik. | |
2 | Grafikleri aktarmanın yolları. Grafikler üzerinde işlemler. | |
3 | Grafik sayısı. Dahili grafikler. Grafik türleri. | |
4 | Güzergah numaralarının belirlenmesi. Rotaların ve döngülerin varlığının belirlenmesi. | |
5 | Bir grafiğin metrik özellikleri. Grafiğin geçişi. | |
6 | İletişim bileşenleri. Grafiklerde ve digraflarda bağlantı. Yoğuşma oluşturma algoritması. Baz ve antibazı tanımlayın. | |
7 | Çevrimiçi akışlar. Ford-Falkerson teoremi. Maksimum akışı bulmak için algoritma. | |
8 | Ağırlıklı grafiklerde en kısa yollar. En kısa yolları bulmanın hesaplanması. Dijkstra'nın algoritması. Ford-Bellman algoritması. | |
9 | Ağaçlar ve özellikleri. Ağaçların merkez noktası. Prufer kodu | |
10 | Ağaçlardaki sorunlar. Boğumlu ağaçların zincirlenmesi. Budaklı ağaçları saymak. | |
11 | Minimum nedir? Kraskal'ın algoritması. Prim'in algoritması. Yönlendirilmiş, sıralı ve ikili ağaçlar. | |
12 | Temel döngüler ve temel bölüm sistemleri. Bir dizi bağımsız döngü. Temel döngülerin oluşturulması için algoritma. Bir dizi bağımsız bölüm. Temel bölümlerin oluşturulması için algoritma. | |
13 | Euler çevrimleri (zincirler). Euler çevrimlerinin varlığı için gerekli ve yeterli koşullar. Euler döngülerini bulma algoritması. Hamilton çevrimleri. Hamilton çevriminin varlığı için yeterli koşullar. Hamilton döngülerini bulmak için algoritma (cebirsel yöntem). | |
14 | Bağımsız (iç kararlılık) köşe kümesi kavramı. Maksimum bağımsız kümeleri aramak için algoritma. Baskın (dış stabilite) zirveler kümesi kavramı. Minimal baskın kümeleri aramak için algoritma. | |
15 | Düzlemsel grafikler. Düzlemsel grafikler. Bir grafiği bir düzleme eşlemek için algoritma. Bir grafiğin kromatik sayısı. Grafik renklendirme algoritmaları. |
PÇ1 | PÇ2 | PÇ3 | PÇ4 | PÇ5 | PÇ6 | PÇ7 | PÇ8 | PÇ9 | PÇ10 | PÇ11 | PÇ12 |
---|
Ders Kitabı / Malzemesi / Önerilen Kaynaklar | ||
---|---|---|
1 | Ә.С.Төлеп, Б.И.Ескараева. Графтар теориясы. Оқу құралы. -Түркістан, 2019. -115 б. | |
2 | Ә.С. Төлеп, Б.И. Ескараева. Дискретті математика. Теория және практикум. -Шымкент, 2020. -132 б. | |
3 | Абильдаева Г.Б. Дискретті математика: Электрондық оқулық. - Қарағанды: ҚарМТУ, 2017 |