Όλα τα γραφήματα Hamiltonian είναι διπλά συνδεδεμένα, αλλά ένα διπλοσυνδεδεμένο γράφημα δεν χρειάζεται να είναι Hamiltonian (δείτε, για παράδειγμα, το γράφημα Petersen). Ένα γράφημα Euler G (ένα συνδεδεμένο γράφημα στο οποίο κάθε κορυφή έχει άρτια μοίρα) έχει απαραίτητα μια περιήγηση Euler, μια κλειστή διαδρομή που περνά από κάθε άκρη του G ακριβώς μία φορά.
Μπορεί ένα γράφημα να είναι Hamiltonian αλλά όχι Eulerian;
Ένα συνδεδεμένο γράφημα G είναι Χαμιλτονιανό εάν υπάρχει ένας κύκλος που περιλαμβάνει κάθε κορυφή του G. ένας τέτοιος κύκλος ονομάζεται κύκλος Hamiltonian. … Αυτό το γράφημα είναι ΤΟΣΟ Eulerian και Hamiltonian. Αυτό το γράφημα είναι Eulerian, αλλά ΟΧΙ Χαμιλτονιανό. Αυτό το γράφημα είναι Hamiltionian, αλλά ΟΧΙ Eulerian.
Είναι κάθε γράφημα Hamiltonian είναι Eulerian;
Όχι. Ένα μονοπάτι Hamiltonian επισκέπτεται κάθε κορυφή ακριβώς μία φορά, αλλά μπορεί να επαναλαμβάνει τις ακμές. Ένα κύκλωμα Eulerian διασχίζει κάθε ακμή σε ένα γράφημα ακριβώς μία φορά, αλλά μπορεί να επαναλαμβάνει τις κορυφές.
Τι είναι ο Eulerian όχι ο Χαμιλτονιανός;
Το πλήρες διμερές γράφημα K2, 4 έχει κύκλωμα Eulerian, αλλά δεν είναι Χαμιλτονιανό (στην πραγματικότητα, δεν περιέχει καν Χαμιλτονιανή διαδρομή). Οποιοδήποτε μονοπάτι Hamiltonian θα εναλλάσσει χρώματα (και δεν υπάρχουν αρκετές μπλε κορυφές).
Είναι όλα τα πλήρη γραφήματα Eulerian;
Ένα γράφημα είναι Eulerian αν και μόνο αν ο βαθμός κάθε κορυφής είναι άρτιος. Επομένως, το Kn είναι Eulerian αν το n είναι περιττό. (ii) Το μόνο ημι-Eulerian πλήρες γράφημα είναι το K2. … Το γράφημα είναι συνδεδεμένο, και υπάρχουν ακριβώςδύο κορυφές περιττού βαθμού.
