CENG715 Graph Theory

6 AKTS - 3-0 Süre (T+U)- . Yarıyıl- 3 Yerel Kredi

Genel Bilgi

Kod CENG715
Ad Graph Theory
Dönem 2023-2024 Eğitim-Öğretim Yılı
Yarıyıl . Yarıyıl
Süre (T+U) 3-0 (T-U) (17 Hafta)
AKTS 6 AKTS
Yerel Kredi 3 Yerel Kredi
Eğitim Dil İngilizce
Seviye Doktora Dersi
Tür Normal
Öğretim Şekli Yüz Yüze Öğretim
Bilgi Paketi Koordinatörü Prof. Dr. UMUT ORHAN


Dersin Amacı / Hedefi

Amaç, çizgelerin teorik arka planını anlamak ve grafik algoritmalarını en bilinen problemlere uygulamaktır.

Dersin İçeriği

Connected graphs, paths, distance, cut-vertices, cut-edges, weighted graphs, shortest path, Spanning trees, Bipartite graphs, Eulerian graphs, Hamilton graphs, Independent-covering-mathcing graphs, Vertex colorings, Edge colorings, Planar graphs, Directed graph

Dersin Ön Koşulu

yok

Kaynaklar

D. B. West, Introduction to Graph Theory,Prentice-Hall of India/Pearson, 2009.

Notlar

J. A. Bondy and U. S. R. Murty, Graph Theory and Applications, 2008.


Dersin Öğrenme Çıktıları

Sıra Dersin Öğrenme Çıktıları
ÖÇ01 Grafların temsilini bilir, problemlere uygular
ÖÇ02 Bağlı grafları bilir
ÖÇ03 Kapsayan ağaçları bilir
ÖÇ04 İki-parçalı grafları bilir
ÖÇ05 Hamilton ve Euler yollarını bilir
ÖÇ06 Köşe ve kenar renklemeyi bilir
ÖÇ07 Düzlem grafları bilir


Program Öğrenme Çıktıları ile İlişkisi

Sıra Tür Program Öğrenme Çıktıları Duzey
PÖÇ01 Bilgi - Kuramsal, Olgusal Lisans düzeyinde kazanılan yetkinlikler temelinde Bilgisayar Mühendisliği temel alanında özgün çalışmalar için gerekli temeli sağlayan ileri düzeyde bilgi ve kavrayışa sahiptir. 4
PÖÇ02 Bilgi - Kuramsal, Olgusal Mühendislik alanında bilimsel araştırma yaparak bilgiye genişlemesine ve derinlemesine ulaşır, bilgiyi değerlendirir, yorumlar ve uygular. 4
PÖÇ03 Yetkinlikler - Öğrenme Yetkinliği Mesleğinin yeni ve gelişmekte olan uygulamalarının farkında olup, gerektiğinde bunları inceler ve öğrenir. 3
PÖÇ04 Yetkinlikler - Öğrenme Yetkinliği Mühendislik problemlerini kurgular, çözmek için yöntem geliştirir ve çözümlerde yenilikçi yöntemler uygular. 3
PÖÇ05 Yetkinlikler - Öğrenme Yetkinliği Analitik, modelleme ve deneysel esaslı araştırmaları tasarlar ve uygular, bu süreçte karşılaşılan karmaşık durumları çözümler ve yorumlar. 4
PÖÇ06 Yetkinlikler - Öğrenme Yetkinliği Yeni ve/veya özgün fikir ve yöntemler geliştirir, sistem, parça veya süreç tasarımlarında yenilikçi çözümler geliştirir.
PÖÇ07 Beceriler - Bilişsel, Uygulamalı Öğrenme becerilerine sahip olur. 3
PÖÇ08 Beceriler - Bilişsel, Uygulamalı Bilgisayar Mühendisliğinin yeni ve gelişmekte olan uygulamalarının farkında olup gerektiğinde bunları inceler ve öğrenir. 2
PÖÇ09 Beceriler - Bilişsel, Uygulamalı Çalışmalarının süreç ve sonuçlarını Bilgisayar Mühendisliği alanındaki veya alan dışındaki ulusal ve uluslararası ortamlarda açık bir şekilde yazılı veya sözlü olarak aktarır. 2
PÖÇ10 Beceriler - Bilişsel, Uygulamalı Bilgisayar Mühendisliğinde uygulanan güncel teknik ve yöntemler ile bunların kısıtları hakkında kapsamlı bilgiye sahip olur. 3
PÖÇ11 Beceriler - Bilişsel, Uygulamalı Bilgisayar Mühendisliğinin gerektirdiği düzeyde bilgisayar yazılımı ile birlikte bilişim ve iletişim teknolojilerini ileri düzeyde etkileşimli olarak kullanır. 2
PÖÇ12 Bilgi - Kuramsal, Olgusal Mesleki tüm etkinliklerde toplumsal, bilimsel ve etik değerleri gözetir.


Haftalık Akış

Hafta Konu Ön Hazırlık Yöntemler
1 Introduction to Graphs, isomorphism, subgraphs, matrix representations, degree Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
2 Connected graphs, paths, distance, cut-vertices, cut-edges, weighted graphs, shortest path Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
3 Kapsayan ağaçlar Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
4 Bipartite graflar, line graflar, chordal graflar Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
5 Eulerian grafları, Fleury algoritması, chinese-postman problemi Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
6 Hamilton grafları Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
7 Arasınav için tekrar Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
8 Ara Sınav Ders notları ve uygulamalara hazırlanmak Ölçme Yöntemleri:
Proje / Tasarım
9 Independent-covering-mathcing graflar, mükemmel eşleme Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
10 Düğüm renkleme, kromatik sayı ve klikler, açgözlü renkleme, Brook teoremi Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
11 Kenar renkleme, Gupta-Vizing teoremi, class-1 ve class-2 grafları Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
12 Düzlem graflar, 4 ve 5 renkleme Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
13 Directed graph, underlying graph, outdegree, in-degree, connectivity, orientation, Eulerian directed graphs, Hamilton directed graphs, tournaments Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
14 Öğrenci sunumları Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
15 Final için tekrar Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
16 Yarıyıl Sonu Sınavları Ders notları ve uygulamalara hazırlanmak Ölçme Yöntemleri:
Yazılı Sınav
17 Yarıyıl Sonu Sınavları Ders notları ve uygulamalara hazırlanmak Ölçme Yöntemleri:
Yazılı Sınav


Öğrenci İş Yükü - AKTS

Çalışmalar Sayısı Süresi (Saat) İş Yükü (Saat)
Ders ile İlgili Çalışmalar
Ders (Sınav haftaları dahil değildir) 14 3 42
Sınıf Dışı Ders Çalışma (Ön çalışma, pekiştirme) 14 5 70
Değerlendirmeler ile İlgili Çalışmalar
Ödev, Proje, Diğer 0 0 0
Ara Sınavlar (Yazılı, Sözlü, vs.) 1 15 15
Yarıyıl/Yıl Sonu/Final Sınavı 1 30 30
Toplam İş Yükü (Saat) 157
Toplam İş Yükü / 25 (s) 6,28
AKTS 6 AKTS

Güncelleme Zamanı: 16.05.2023 01:44