Bu dersin sonunda öğrenciler; 1) Çizge kuramının temel kavramlarını ve tekniklerini öğrenirler. 2) Bilgisayar bilimlerinde, mühendislikte ve yöneylem araştırmasında karşıya çıkan problemlerin çözümü için çizge kuramının uygun modellerini ve algoritmalarını seçerler. 3) Euler devrelerini ve ilgili uygulama problemlerini öğrenir, algoritma kullanarak çözerler. 4) Hamilton devreleri üzerine mevcut teorik bilgilere sahip olurlar. Gezgin satıcı probleminin çözümünde karşıya çıkan zorlukları anlarlar. 5) En kısa yol probleminin çözümü için kullanılan algoritmaları öğrenirler ve hesaplama karmaşıklığı açısından kıyaslarlar. 6) En fazla akış problemini çözebilecekler. Eşleme ve atama algoritmalarını uygularlar. 7) Ağaç algoritmalarını uygulayarak ilgili problemleri çözerler.
DERSİN VERİLİŞ BİÇİMİ
Yüz Yüze
DERSİN ÖNKOŞULLARI
Yok
ÖNERİLEN DERSLER
Yok
DERS TANIMI
Çizge ve çizge modelleri, bağlı çizgeler. Çoklu çizge ve çift çizgeler. İzomorfik çizgeler. Ağaçlar, minimum kapsayan ağaç problemi. Bağlanabilirlik. Euler çizgeleri. Hamilton çizgeleri. Eşleme ve çarpanlara ayırma. Düzlemsellik ve düzlemsel çizgeler. Çizge renklendirme, dört renk problemi. Tepe noktası renklendirme, kenar renklendirme. Matrisler ve çizge algoritmaları. Akışlar ve kesikler, en büyük akış çizimi.
DERS İÇERİĞİ
HAFTA
KONULAR
1. Hafta
Çizge ve çizge modelleri, bağlı çizgeler.
2. Hafta
Çoklu çizge ve yönlü çizgeler.
3. Hafta
İzomorfik çizgeler.
4. Hafta
Ağaçlar, minimum kapsayan ağaç problemi.
5. Hafta
Bağlanabilirlik, Euler çizgeleri.
6. Hafta
Hamilton çizgeleri.
7. Hafta
Ara-sınav
8. Hafta
Eşleme ve atama problemleri.
9. Hafta
Düzlemsellik ve düzlemsel çizgeler.
10. Hafta
Çizge renklendirme, dört renk problemi.
11. Hafta
Tepe noktası renklendirme, kenar renklendirme.
12. Hafta
Matrisler ve çizge algoritmaları.
13. Hafta
Akışlar ve kesikler, en büyük akış bulma.
14. Hafta
Akışlar ve kesikler, en büyük akış bulma.
ZORUNLU YA DA ÖNERİLEN KAYNAKLAR
1. Buckley F., Lewinter M., Friendly introduction to Graph Theory, Prentice Hall, 2003 2. Grimaldi R.P., Discrete and Combinatorial Mathematics, 5/E, Addison Wesley, 2003 3. Rosen K.H., Discrete Mathematics and Its Applications, 6/E, McGraw-Hill, 2007
