Τι είναι ένα διασχίσιμο γράφημα στη θεωρία γραφημάτων;

Στο πλαίσιο της θεωρίας γραφημάτων, ένα διασχίσιμο γράφημα είναι ένα γράφημα στο οποίο είναι δυνατή η διέλευση όλων των κορυφών και των ακμών. Με άλλα λόγια, είναι ένα γράφημα που μας επιτρέπει να επισκεφτούμε κάθε κορυφή ακριβώς μία φορά και να επιστρέψουμε στην αρχική κορυφή.

Ένα διασχίσιμο γράφημα είναι επίσης γνωστό ως συνδεδεμένο γράφημα, επειδή είναι ένα γράφημα στο οποίο όλες οι κορυφές συνδέονται μεταξύ τους .

Για παράδειγμα, θεωρήστε ένα απλό γράφημα με τρεις κορυφές A, B και C, όπου υπάρχει μια ακμή μεταξύ A και B, μια ακμή μεταξύ B και C και μια ακμή μεταξύ A και C. Αυτό το γράφημα είναι διασχίσιμο επειδή μπορούμε ξεκινήστε από την κορυφή Α, ακολουθήστε τις άκρες προς το Β και μετά προς το Γ και επιστρέψτε στο A.

Από την άλλη πλευρά, ένα γράφημα με δύο αποσυνδεδεμένα στοιχεία, όπως δύο ξεχωριστά γραφήματα, δεν είναι διασχίσιμο επειδή δεν είναι δυνατή η επίσκεψη σε κάθε κορυφή ακριβώς μία φορά και επιστρέψτε στην αρχική κορυφή.