O Leonhard Euler (1707-1783) θεωρείται “πατέρας” της θεωρίας γραφημάτων αφού έθεσε και έλυσε το περίφημο πρόβλημα της γέφυρας Köningsberg.To Köningsberg –πόλη της ανατολικής Πρωσίας που ονομάζεται Καλίνινγκραντ σήμερα- είναι χτισμένο στις όχθες ενός ποταμού σε σημείο όπου σχηματίζονται 2 νησίδες. Οι δύο όχθες και οι νησίδες συνδέονται με 7 γέφυρες.
http://[URL unfurl="true"]www.sciencenews.org/articles/20060923/f7720_1362.gif[/img[/URL]]
Το πρόβλημα ρωτά αν υπάρχει δυνατότητα κάποιος να κάνει μια βόλτα στην πόλη περνώντας όλες τις γέφυρες από μια μόνον φορά και τέλος να γυρίσει στο σημείο από όπου είχε ξεκίνησε.
Αυτό ισοδυναμεί με το να χαράξει κάποιος μία διαδρομή με μονοκονδυλιά χωρίς να χρειαστεί να σηκώσει το μολύβι του (ένα Οϊλεριανό μονοπάτι) πράγμα που όπως φαίνεται δεν είναι δυνατόν:
[img]http://mathforum.org/isaac/problems/images/networks/bridgesol1.gif
Ο Euler γενίκευσε το πρόβλημα αναπαριστώντας πρώτα κάθε μάζα ξηράς με ένα σημείο και κάθε γέφυρα με τόξο:
Αυτό είναι ένα γράφημα όπου το κάθε σημείο καλείται κορυφή και κάθε τόξο ακμή:
Ο αριθμός των ακμών που ξεκινούν (ή καταλήγουν) σε μία κορυφή θα είναι μονός ή ζυγός οπότε λέμε ότι η κορυφή έχει περιττό ή άρτιο βάρος. Στην συγκεκριμένη περίπτωση του Köningsberg έχουμε:
http://[URL unfurl="true"]www.jcu.edu/math/vignettes/v5im4.gif[/img[/URL]]
δηλαδή όλες οι κορυφές έχουν περιττό βάρος.
Ο Euler διατύπωσε την εξής πρόταση:
Αν σε ένα γράφημα υπάρχουν παραπάνω από 2 κορυφές με περιττό βάρος τότε στο γράφημα αυτό δεν υπάρχει κανένα Οϊλεριανό μονοπάτι (δηλαδή δεν υπάρχει διαδρομή που να περνάει από όλες τις κορυφές μόνον μία φοράς).
Πράγμα που είναι λογικό αν το σκεφτεί κανείς γιατί αν για παράδειγμα έχουμε μία κορυφή με βάρος 3 (δηλαδή συνδέεται με 3 ακμές) τότε αρχίζοντας από την κορυφή αυτή θα φύγουμε με την πρώτη ακμή, θα γυρίσουμε πίσω με την δεύτερη και θα πρέπει να ξαναφύγουμε με την τρίτη οπότε δεν μπορούμε να ξαναγυρίσουμε. Επομένως μία τέτοια κορυφή πρέπει να είναι η αρχική ή η τελική του γραφήματος. Άρα λοιπόν θα πρέπει να υπάρχουν 2 μόνον τέτοιες κορυφές, δηλαδή να αρχίζουμε από την μία και να τελειώνουμε στην άλλη.
Για προσπαθήστε να λύσετε το πρόβλημα τώρα.
