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

 
δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
κοινοποιήστε το τεκμήριο



Στοιχεία Γραφημάτων: Συνδεσιμότητα και Κύκλοι 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

Ελληνικό Ανοικτό Πανεπιστήμιο (EL)
Hellenic Open University (EN)

Ελληνική γλώσσα

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


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



*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.