GRAPH THEORY

CSE475

Ders Kodu: CSE475
Yarıyıl: -
Teori+Uygulama: 3 + 0
AKTS: 5

Dersin Türü

Seçmeli

Dersin Düzeyi

Lisans

Dersin Yılı

Dersin Yarıyılı

AKTS

Öğretim Eleman(lar)ı

Öğretim Görevlisi Nazlıcan Çakmak

Öğrenme Kazanımları

Bu dersin sonunda öğrenciler;

Çizge kuramının temel kavramlarını ve tekniklerini öğrenirler.
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.
Euler devrelerini ve ilgili uygulama problemlerini öğrenir, algoritma kullanarak çözerler.
Hamilton devreleri üzerine mevcut teorik bilgilere sahip olurlar. Gezgin satıcı probleminin çözümünde karşıya çıkan zorlukları anlarlar.
En kısa yol probleminin çözümü için kullanılan algoritmaları öğrenirler ve hesaplama karmaşıklığı açısından kıyaslarlar.
En fazla akış problemini çözebilecekler. Eşleme ve atama algoritmalarını uygularlar.
Ağaç algoritmalarını uygulayarak ilgili problemleri çözerler.

Veriliş Biçimi

Yüz Yüze

Önkoşullar

Yok

Önerilen Dersler

Yok

Ders Tanımı

Ç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 İçeriği

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.
15. Hafta	Genel Tekrar

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

Öğretim Yöntemleri

Soru-Cevap
Diğer
Sunum
Rapor Hazırlama
Proje
Sorun/Problem Çözme
Eğitim-Uygulama
Deney

Değerlendirme

	Sayısı	Toplam Katkısı (%)
Ara Sınav	3	30
Ödev	7	15
Proje	1	15
Toplam(%)		60
Yıl İçinin Başarıya Oranı(%)		60
Finalin Başarıya Oranı(%)		40
Toplam(%)		100

Dil

İngilizce

Staj / Uygulama

Yok

Program Yeterlilikleri / Öğrenme Kazanımları

	Ö1	Ö2	Ö3	Ö4	Ö5	Ö6	Ö7
P1	X	X	X	X	X	X	X
P2		X	X	X	X	X	X
P3
P4
P5
P6
P7
P8
P9
P10
P11