BNN.grΔιάστημαΦυσικήΤεχνητή ΝοημοσύνηΒιολογίαΝευροεπιστήμεςΥγεία
Μαθηματικά

Θεωρία γραφημάτων

Ο γρίφος των γεφυρών

Το 1736 ο Leonhard Euler έλυσε το πρόβλημα των επτά γεφυρών του Königsberg: μπορεί κάποιος να διασχίσει κάθε γέφυρα ακριβώς μία φορά; Απέδειξε ότι όχι, αναπαριστώντας τις περιοχές ως κορυφές και τις γέφυρες ως ακμές. Έτσι γεννήθηκε η θεωρία γραφημάτων.

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

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

Το ήξερες; Το πρόβλημα των επτά γεφυρών θεωρείται η γέννηση της τοπολογίας και της θεωρίας γραφημάτων.
Δες το άρθρο στο διαδραστικό site →

Διάβασε και

Όλα τα άρθρα: Μαθηματικά