Στοιχεία Γραφημάτων: Συνδεσιμότητα και Κύκλοι Hamilton(Κοντογιάννης-ΗΤ-ΠΛΗ20)

 
This item is provided by the institution :

Repository :
Institutional Repository of the Hellenic Open University
see the original item page
in the repository's web site and access all digital files if the item*
share




2008 (EN)

Στοιχεία Γραφημάτων: Συνδεσιμότητα και Κύκλοι Hamilton(Κοντογιάννης-ΗΤ-ΠΛΗ20)

ΚΟΝΤΟΓΙΑΝΝΗΣ, ΣΠΥΡΟΣ

ΚΑΒΒΑΔΙΑΣ, ΔΗΜΗΤΡΗΣ
ΣΚΟΔΡΑΣ, ΑΘΑΝΑΣΙΟΣ

Σκοπός του παρόντος υλικού είναι η εξοικείωση των φοιτητών της Θ.Ε. ΠΛΗ20, με τις βασικές έννοιες που σχετίζονται με τη Συνδεσιμότητα και τη Χαμιλτονικότητα Γραφημάτων. Θα καλυφθούν έννοιες όπως: διαδρομές / ίχνη / μονοπάτια, κυκλώματα / κύκλοι, συνδεσιμότητα και συνεκτικές συνιστώσες, πολυσυνδεσιμότητα γραφημάτων, κομβικά σημεία και διαχωριστές, γέφυρες και σύνολα (ακμών) κοπής, τεμάχια γραφημάτων και το θεώρημα του Menger. Επίσης θα μελετηθούν οι έννοιες των κύκλων και μονοπατιών Hamilton, καθώς και ορισμένες ικανές ή αναγκαίες συνθήκες για την ύπαρξη κύκλων / μονοπατιών Hamilton (χαμιλτονικότητα γραφήματος).
H συγκεκριμένη ενότητα ΕΔΥ της ΠΛΗ20 εισάγει τις βασικές έννοιες για τη συνδεσιμότητα γραφημάτων, και παρουσιάζει μερικές θεμελειώδεις ιδιότητες της συνδεσιμότητας. Επίσης εισάγει τις βασικές έννοιες για τη Χαμιλτονικότητα των γραφημάτων και παρουσιάζει ικανές ή αναγκαίες συνθήκες ύπαρξης κύκλων και μονοπατιών Hamilton σε ένα γράφημα.

Συνεκτικές συνιστώσες, Πολυσυνδεσιμότητα γραφημάτων,Κομβικά σημεία και Διαχωριστές,Γέφυρες και Σύνολα (ακμών) κοπής,Θεώρημα του Menger,Κύκλοι και μονοπάτια Hamilton,Ικανές / Αναγκαίες συνθήκες χαμιλτονικοτητας
Walks / Trails / Paths / Circuits / Cycles,Connected Components, (multi)connectivity of graphs,Bridges and (Edge) Cut sets, Articulation points and Separators,Menger Theorem,Hamiltonian Cycles and Hamiltonian Paths,Sufficient / Necessary conditions for hamiltonicity


Greek

2013-12-13T09:50:11Z
2008-12-15T11:19:39Z


Η μελέτη του ΕΔΥ-ΓΡΑΦΗΜΑΤΑ θα πρέπει να γίνει παράλληλα με τις ενότητες που σχετίζονται με την συνδεσιμότητα και τη χαμιλτονικότητα γραφημάτων. Η ύλη που περιλαμβάνεται στο παρόν υλικό δεν είναι καινούργια, αλλά συμπληρωματική αυτής που παρέχεται στις [ενότητα 4.3, Τόμος 1] και [ενότητα 1.2.2, Τόμος 2] της ύλης της ΠΛΗ20. Ο χρόνος που θα αφιερωθεί για όλες αυτές τις ενότητες, συμπεριλαμβανομένου του ΕΔΥ-ΓΡΑΦΗΜΑΤΑ, πρέπει να είναι η 20η και η 24η εβδομάδα μελέτης, όπως αναφέρεται στο χρονοδιάγραμμα μελέτης της ΠΛΗ20.




*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)