Θεωρια Γραφηματων Ακαδημαϊκο Ετος 2008-- 2009

[Γενικες Πληροφοριες][Περιγραφη][Ανακοινωσεις][Ημερολογιο][Χρησιμο Υλικο]

Γενικες Πληροφοριες

Διδασκων:	Σπυρος Κοντογιαννης
Email -- URL -- Voice:	--  http://www.cs.uoi.gr/~kontog/  --  (26510) 98812
URL Μαθηματος:	http://www.cs.uoi.gr/~kontog/courses/GraphTheory/
Ωρες Διαλεξεων:	Καθε Τεταρτη 17:00--19:00 και Πεμπτη 17:00--19:00 (νεες ωρες)
Χωρος Διαλεξεων:	Αιθουσες Ι1 και Ι3 (Iσογειο Κτιριου)
Ωρες Επικοινωνιας:	Καθε Τριτη και Τεταρτη, 15:30-17:00

[Γενικες Πληροφοριες][Περιγραφη][Ανακοινωσεις][Ημερολογιο][Χρησιμο Υλικο]

Περιγραφη

Στις επιστημες των μαθηματικων και της θεωρητικης πληροφορικης, η θεωρια γραφηματων ειναι ενας σημαντικος κλαδος που μελετα θεμελιωδεις ιδιοτητες γραφηματων. Με απλα λογια, ενα γραφημα G περιγραφεται απο ενα ζευγος συνολων (V,E) τετοια ωστε:

• Το V ειναι ενα συνολο αντικειμενων που καλουνται κορυφες (Η κομβοι) του γραφηματος, οι οποιες κατα καποιο τροπο "συσχετιζονται" Η "δεν συσχετιζονται" μεταξυ τους ανα δυο.
• Το Ε ειναι το συνολο που περιγραφει ακριβως  αυτη τη συσχετιση με τη μορφη (διατεταγμενων ΚΑΙ/Η μη διατεταγμενων) ζευγων κορυφων που καλουνται ακμες του γραφηματος.

Καθε κορυφη του γραφηματος συνηθως αναπαρισταται απο ενα κομβο, ενω οποιαδηποτε ακμη του αναπαρισταται ως μια συνεχομενη (οχι απαραιτητα ευθυγραμμη) γραμμη που ενωνει τις δυο κορυφες οι οποιες συσχετιζονται απο αυτην.

Πολλα προβληματα με ιδιαιτερο πρακτικο ενδιαφερον μπορουν να αναπαρασταθουν απο γραφηματα. Για παραδειγμα, η ιστοδομη ενος δικτυακου τοπου ειναι ενα ειδος (κατευθυνομενου) γραφηματος, οπου κορυφες του ειναι οι σελιδες του δικτυακου τοπου και οι (κατευθυνομενες) ακμες αντιστοιχουν σε συνδεσεις μεταξυ σελιδων. Παρομοια, η αναθεση ραδιοσυχνοτητων σε σταθμους επικοινωνιας ενος ασυρματου τηλεπικοινωνιακου δικτυου, αναγεται σε προβληματα χρωματισμου κορυφων σε γραφηματα. Η αναπτυξη αλγοριθμων για την επιλυση συνδυαστικων προβληματων σε γραφηματα εχει λοιπον πολυ μεγαλη αξια για την επιστημη των υπολογιστων.

Πολλες φορες στις κορυφες και στις ακμες των γραφηματων αναθετουμε καποιες τιμες. Για παραδειγμα, αν το γραφημα μας αναπαριστα ενα οδικο δικτυο, τοτε καθε ακμη ενδεχομενως συνοδευεται και απο ενα θετικο αριθμο που αντιπροσωπευει το μηκος του αντιστοιχου δρομου, ενω καθε κορυφη αντιπροσωπευει μια συγκεκριμενη πολη. Θα μελετησουμε και προβληματα που αφορουν γραφηματα με βαρη στις ακμες ΚΑΙ/Η ετικετες στις κορυφες τους.

Στοχος του Μαθηματος

Στο μαθημα της Θεωριας Γραφηματων θα ασχοληθουμε με τις βασικες εννοιες και ιδιοτητες γραφηματων. Θα μελετησουμε ιδιαιτερα εννοιες οπως διαδρομες και αποστασεις, συνδεσιμοτητα, διαμερισεις, παραγοντοποιηση γραφηματων, κ.λπ. Θα δουμε ειδικες κατηγοριες γραφηματων (που ομως παρουσιαζουν ιδιαιτερο ενδιαφερον) πιο αναλυτικα, οπως για παραδειγμα  δενδρα / διμερη / πληρη / επιπεδα / κανονικα γραφηματα. Θα μελετησουμε την υπαρξη κυκλων Euler και Hamilton σε ενα γραφημα. Θα μελετησουμε ισομορφισμους γραφηματων. Θα ασχοληθουμε με προβληματα χρωματισμων κορυφων / ακμων γραφηματων. Θα μελετησουμε δικτυα, δηλαδη γραφηματα στα οποια υπαρχει απαιτηση μεταφορας ροων μεταξυ κορυφων τους. Θα ασχοληθουμε με κατευθυνομενα γραφηματα, και τελος θα δουμε μερικα δυσεπιλυτα προβληματα γραφηματων.

Αξιολογηση του Μαθηματος

Η αξιολογηση του μαθηματος θα γινει ως εξης:

• Κατα τη διαρκεια του εξαμηνου θα δοθουν δυο Η τρεις Θεωρητικες Ασκησεις.
• Καθε εβδομαδα θα δινονται συνολα ασκησεων κατανοησης, για εξασκηση (προεραιτικες, ανα εβδομαδα).
• Στο τελος του εξαμηνου θα υπαρξει τελικη εξεταση του μαθηματος.

Οι φοιτητες που θα δηλωσουν το μαθημα, θα πρεπει να παραδωσουν υποχρεωτικα τις  θεωρητικες ασκησεις. Ο κανονας για τον υπολογισμο του τελικου βαθμου ειναι ο ακολουθος:

(Α) Για οποιον / οποια παραδωσει κανονικα ΚΑΙ ΤΙΣ ΤΡΕΙΣ αναθεσεις, ο τελικος βαθμος του μαθηματος προκυπτει ως εξης:

(Β) Οποιος φοιτητης / φοιτητρια δεν παραδωσει ΤΟ ΠΟΛΥ ΜΙΑ απο τις (υποχρεωτικες) αναθεσεις, θα εχει δικαιωμα συμμετοχης στην εξεταση του Φεβρουαριου, χωρις ομως να μετρησουν καθολου οι αλλες δυο αναθεσεις του, και εχοντας ως αριστα το 9. Δηλαδη:

(Γ) Οποιος δεν παραδωσει δυο Η περισσοτερες αναθεσεις, χανει το δικαιωμα συμμετοχης του στην εξεταση του Φεβρουαριου (και του Σεπτεμβριου).

[Γενικες Πληροφοριες][Περιγραφη][Ανακοινωσεις][Ημερολογιο][Χρησιμο Υλικο]

Ανακοινωσεις

• 6/03/2009: Η βαθμολογια της εξετασης Φεβρουαριου 2009 εχει αναρτηθει στον πινακα ανακοινωσεων του 3ου οροφου. Οσοι επιθυμουν να δουνε το γραπτο τους, μπορουν να ερθουν στο γραφειο του διδασκοντα μεχρι και την Δευτερα 9 Μαρτιου.
   
• [30/01/2009] ΕΠΕΙΓΟΝ Η εξεταση του μαθηματος μεταφερεται για την Τριτη 24 Φεβρουαριου 2009, στις 15:00--18:00, και στην αιθουσα Ι5 του κτιριου.
   
• [26/01/2009] Αναρτηθηκε η 2η αναθεση για το σπιτι. Ημερομηνια Παραδοσης: Δευτερα 9 Φεβρουαριου 2009 (στο γραφειο, Η στο γραμματοκιβωτιο του διδασκοντα).
   
• [14/11/2008] Αναρτηθηκε η 1η αναθεση για το σπιτι. Ημερομηνια Παραδοσης: Πεμπτη 4 Δεκεμβριου 2008 (στο μαθημα).
   
• [4/11/2008] Οι νεες ωρες διεξαγωγης του μαθηματος ειναι οι εξης: Καθε Τεταρτη 17:00--19:00 και καθε Πεμπτη 17:00-19:00. Ο χωρος διεξαγωγης ειναι καποια απο τις αιθουσες Ι1-Ι4 του κτιριου.
   
• [16/10/2008] Δειτε τη διευκρινιση στον τροπο υπολογισμου του τελικου βαθμου του μαθηματος.
   
• [16/10/2008] Παρακαλουνται οι φοιτητες και φοιτητριες του μαθηματος να (ξανα)παρουν τη διορθωμενη εκδοση των διαφανειων της 2ης εβδομαδας.

[Γενικες Πληροφοριες][Περιγραφη][Ανακοινωσεις][Ημερολογιο][Χρησιμο Υλικο]

Ημερολογιο Μαθηματος

Διδακτικη  Εβδομαδα	Ημερομηνιες Διδασκαλιας	Υλη Εβδομαδας	Συνοδευτικο Υλικο
			Σημειωσεις password protected	Διαφανειες password protected
1η	01--02/10/08	-- Εισαγωγη -- Βασικες Εννοιες Γραφηματων. -- Βαθμοι.	Κεφάλαιο 1	Διαφάνειες 1ης εβδομάδας
2η	08--09/10/08	-- Ακολουθίες Βαθμών -- Υπογραφηματα. -- Διαδρομες σε Γραφηματα. -- Μορφισμοί Γραφημάτων.		Διαφάνειες 2ης εβδομάδας
3η	15--16/10/08	-- Αναπαραση Γραφηματων -- Αποστασεις σε Γραφηματα	Κεφάλαιο 2	Διαφάνειες 3ης εβδομάδας
4η	22--23/10/08	-- Αποστασεις σε Γραφηματα -- Αλγοριθμοι ευρεσης μονοπατιων ελαχιστου μηκους	Κεφάλαιο 3	Διαφάνειες 4ης εβδομάδας
5η	29--30/10/08	-- Κυκλωματα και Μονοκονδυλιες Euler	Κεφάλαιο 4	Διαφάνειες 5ης εβδομάδας
6η	05--06/11/08	-- Το Προβλημα του Κινεζου Ταχυδρομου -- Κυκλοι και Μονοπατια Hamilton	Κεφάλαιο 5	Διαφάνειες 6ης--7ης εβδομάδας
7η	12--13/11/08	-- Ικανες / Αναγκαιες Συνθηκες Υπαρξης Κυκλων / Μονοπατιων Hamilton -- Το Προβλημα του Περιοδευοντος Πωλητη
	19--20/11/08	ΑΝΑΒΟΛΗ ΔΙΑΛΕΞΕΩΝ ΛΟΓΩ ΑΠΟΥΣΙΑΣ ΔΙΔΑΣΚΟΝΤΑ (Το μαθημα θα αναπληρωθει με συμπληρωματικες ωρες διδασκαλιας)
8η	26--27/11/08	-- Εισαγωγη στα Δενδρα	Κεφάλαιο 6	Διαφάνειες 8ης--9ης εβδομάδας
9η	03--04/12/08	-- Απαριθμηση Δενδρων
	10--11/12/08	ΑΝΑΒΟΛΗ ΔΙΑΛΕΞΕΩΝ ΛΟΓΩ ΚΑΤΑΛΗΨΗΣ
	17--18/12/08	ΑΝΑΒΟΛΗ ΔΙΑΛΕΞΕΩΝ ΛΟΓΩ ΚΑΤΑΛΗΨΗΣ
	07--8/01/09	ΑΝΑΒΟΛΗ ΔΙΑΛΕΞΕΩΝ ΛΟΓΩ ΚΑΤΑΛΗΨΗΣ
	14--15/01/09	ΑΝΑΒΟΛΗ ΔΙΑΛΕΞΕΩΝ ΛΟΓΩ ΚΑΤΑΛΗΨΗΣ
10η	21--22/01/09	-- Αλγοριθμοι για Δενδρα	Κεφάλαιο 7	Διαφάνειες 10ης εβδομάδας
11η	27--28/01/09	-- Αλγοριθμοι για Δενδρα| -- Πολυσυνδεσιμοτητα Γραφηματων	Κεφάλαιο 8	Διαφάνειες 11ης εβδομάδας
12η	04--05/02/09	-- Επιπεδοτητα Γραφηματων	Κεφάλαιο 9
	24/02/09	ΕΞΕΤΑΣΗ ΜΑΘΗΜΑΤΟΣ:   -- Ωρα: 15:00--18:00   -- Αιθουσα: Ι5 (στο ισογειο του κτιριου)   -- Σημειώσεις ΑΝΟΙΚΤΕΣ

[Γενικες Πληροφοριες][Περιγραφη][Ανακοινωσεις][Ημερολογιο][Χρησιμο Υλικο]

Χρησιμο Υλικο

Βιβλιογραφια Μαθηματος

Τα βασικα εγχειριδια του μαθηματος ειναι:

• Γιαννης Μανωλοπουλος, Μαθηματα Θεωριας Γραφων: Θεμελιωσεις - Αλγοριθμοι - Εφαρμογες.
  Εκδοσεις Νεων Τεχνολογιων, ISBN 960-7235-87-8, Εκδοση 2η (2000).
   
• Σημειωσεις/διαφανειες του διδασκοντος (θα δινονται περιοδικα απο το Ημερολογιο του μαθηματος).

Τα ακολουθα βιβλια ειναι επισης πολυ χρησιμες αναφορες για το μαθημα:

• Reinhard Diestel, Graph Theory (3rd edition).  Springer 2005 (διατιθεται  ηλεκτρονικα).
   
• Frank Harary, Graph Theory.
  Addison-Wesley Series in Mathematics, ISBN 0-201-02787-9, 1972.
   
• J.A. Bondy, U.S.R. Murty. Graph Theory with Applications (διατιθεται και ηλεκτρονικα).
   
• Kurt Mehlhorn. Algorithms on Graphs. Chapter 4 of the book Data Structures and Algorithms (διαθεσιμο ηλεκτρονικα).
   
• Λ. Κυρουσης, Χ. Μπουρας, Π. Σπυρακης, Γ. Σταματιου. Εισαγωγη στους Γραφους.
  CTI Press, ISBN 960-01-0815-3, 1999.

[Γενικες Πληροφοριες][Περιγραφη][Ανακοινωσεις][Ημερολογιο][Χρησιμο Υλικο]

Δημιουργια και συντηρηση σελιδας μαθηματος: Σπυρος Κοντογιαννης. Ημερομηνια τελευταιας αλλαγης: 06/03/2009.