ΠΛΗ20 Μάθημα 4.5 – Κύκλος Hamilton


Στόχοι του Μαθήματος

Στο μάθημα αυτό:

  • Ορίζουμε τον κύκλο Hamilton (κύκλος του γραφήματος που περνάει από κάθε κορυφή ακριβώς μία φορά)
  • Μαθαίνουμε κάποιες ιδιότητες του κύκλου Hamilton και εντοπίζουμε την δυσκολία εύρεσης μεθοδολογίας για την ύπαρξη του κύκλου Hamilton (καθώς αυτό είναι NP-Complete)

Σύντομη Παρουσίαση

Με μια ματιά το μάθημα:

  • ΚΑΡΤΑ: Κύκλος Hamilton


Σχολιασμός (βίντεο)

Αναλυτική Παρουσίαση

ΠΕΡΙΕΧΟΜΕΝΑ ΜΑΘΗΜΑΤΟΣ:

1) Κύκλος Hamilton
1.1) Ορισμός Κύκλου Hamilton
1.2) Πως δείχνουμε ότι ένα γράφημα έχει κύκλο Hamilton (κατασκευαστικές, θεώρημα Dirac, θεώρημα Ore)
1.3) Πως δείχνουμε ότι ένα γράφημα δεν έχει κύκλο Hamilton (Απόδειξη εξαντλητικής περιπτωσιολογίας).
Ασκήσεις

Παρουσίαση τουΜαθήματος:


ΒΙΝΤΕΟ ΜΑΘΗΜΑΤΟΣ και ΣΧΟΛΙΑΣΜΟΣ

ΣΥΜΒΟΥΛΕΣ

 two-face.200  batman.200
ΚατηγορίαΧΔΣχόλιο
Θεωρία Ορισμός Κύκλου Hamilton και βασικές παρατηρήσεις.
Λύμενες 144Κύκλος Hamilton και πλήρη διμερή γραφήματα
Λύμενες 244Κύκλος Hamilton και κατευθυνόμενες(!) κλίκες.
Κατανόηση 152Ο ορισμός του κύκλου Hamilton στις γνωστές οικογένειες γραφημάτων
Κατανόηση 243Ορισμός του μονοπατιού Hamilton σε μία συλλογιστική απόδειξη
Κατανόηση 343Κύκλος Hamilton και σημείο άρθρωσης σε μία αποδειξη συλλογισμού
Κατανόηση 443Σπαζοκεφαλιές με τον κύκλο Hamilton
Ερωτήσεις 154Σημαντική Άσκηση που συνδυάζει τους κύκλους Euler και Hamilton
Ερωτήσεις 242Διατήρηση ιδιοτήτων γραφήματος κατά την πρόσθεση ή αφαίρεση ακμών.
Ερωτήσεις 343Άσκηση που συνδυάζει τον κύκλο Hamilton με τους ορισμούς των προηγούμενων μαθημάτων
Εφαρμογή 132Κατασκευές για τον συνδυασμό των ορισμών των κύκλων Euler και Hamilton
Εφαρμογή 253Πλήρη τριμερή γραφήματα και κύκλος Hamilton
Εφαρμογή 342Μία επαγωγή (για να μην ξεχνιόμαστε)
Εφαρμογή 424Άσκηση που αναλύουμε εξαντλητικά περιπτώσεις για την απόδειξη της μη ύπαρξης ενός κύκλου Hamilton

Περαιτέρω Εξάσκηση

(-)

Πηγές και Διαδίκτυο

Οι λυμένες ασκήσεις και οι ερωτήσεις είναι θέματα εξετάσεων-εργασιών του ΕΑΠ

Εκτυπώσιμη μορφή αρχείων PDF