Τι είναι η Θεωρία Γραφημάτων;

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

Ένα γράφημα ορίζεται ως $G=(V,E)$, όπου $V$ είναι το σύνολο των κόμβων (ή κορυφών) και $E$ το σύνολο των ακμών (ή συνδέσεων) που ενώνουν αυτούς τους κόμβους. Από την αρχή της ως θεωρητικό πεδίο, η Θεωρία Γραφημάτων έχει εξελιχθεί σε ένα ισχυρό εργαλείο για την ανάλυση σύνθετων δικτύων, από το διαδίκτυο μέχρι τη δομή του ανθρώπινου εγκεφάλου.

Το πρόβλημα του Sousselier

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

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

Παρά τις προσπάθειές του, δεν βρήκε λύση. 

Στην απόγνωσή του, στράφηκε σε έναν μαθηματικό. 

Τα Μαθηματικά στην καθημερινότητα | 10. Θεωρία Γραφημάτων (Graph Theory)

Καλώς ήρθατε στον εκπληκτικό και ποικιλόμορφο κόσμο των μαθηματικών! Σε αυτό το θέμα, θα εξετάσουμε $16$ διαφορετικούς τομείς των μαθηματικών και θα δούμε πώς παίζουν καθοριστικό ρόλο στην καθημερινή μας ζωή. 

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

10. Θεωρία Γραφημάτων (Graph Theory)

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

Applications of Graph Theory

Road coloring theorem

In graph theory the road coloring theorem, known previously as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destination from any other point within a network (which might be a representation of city streets or a maze). 

In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from. This theorem also has implications in symbolic dynamics.

The theorem was first conjectured by Roy Adler and Benjamin Weiss. It was proved by Avraham Trahtman.

Read more »

THEOREM OF THE DAY: 1 - 2 - 3 Conjecture

Ralph Keusch posted to the arxiv a solution to the 123 conjecture of graph theory last year. Following its publication in JCT-B I am excited to make this the 3rd theorem on my site to lose an "under construction" classification!

Click on image.

Finally, a Fast Algorithm for Shortest Paths on Negative Graphs

Decades ago, the Dutch computer scientist Edsger Dijkstra developed a greedy algorithm that finds shortest paths between points on a graph with positive weights. But if the weights are negative, the algorithm fumbles.

Read more »

Can you solve these two problems in graph theory?

The purpose of this article is to narrate you through solutions to the two math problems solved by the fictional character Will in the 1997 Academy Award-winning movie Good Will Hunting. 

The narration is based largely on the excellent paper Mathematics in Good Will Hunting II: Problems from the Students Perspective by Horváth, Korándi and Szabó (2010).

Read more »

Πέντε μυστηριώδεις αριθμοί

Ο Παναγιώτης έγραψε την ακόλουθη σειρά με πέντε μυστηριώδεις αριθμούς: 

@ ## ∗ ∗ ∗ &&&& %%%%%. 

Αποκάλυψε ότι οι χαρακτήρες @, #, ∗, &, % αντιπροσωπεύουν τα διαφορετικά ψηφία $1,2,3,4,5$ και ότι ο αριθμός που προκύπτει διαιρείται με το έντεκα. 

Ποιος είναι ο μικρότερος και ποιος ο μεγαλύτερος αριθμός που μπορεί να είναι το αποτέλεσμα του αριθμού του Παναγιώτη;

Μαθηματικοί διαγωνισμοί

Διοργανώνονται $22$ μαθηματικοί διαγωνισμοί και για κάθε διαγωνισμό δίνεται βραβείο σε διαγωνιζόμενους. 

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

Υπάρχει διαγωνιζόμενους που να έχει λάβει βραβείο σε όλους τους διαγωνισμούς;

Θεωρία γράφων

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

Η θεωρία γράφων έχει στενή σχέση με τη θεωρία ομάδων. Αυτός ο γράφος ενός κομμένου τετραέδρου έχει σχέση με την αντιμεταθετική ομάδα A4.

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

Οι Αριθμοί

Σ’ έναν υπολογιστή εισάγουμε έναν ακέραιο αριθμό «x» και ως αποτέλεσμα λαμβάνουμε έναν αριθμό «y» που ισούται με το άθροισμα των ψηφίων του αριθμού που χορηγήσαμε στον υπολογιστή αρχικά. Να βρείτε τα εξής: 

1.Εάν εμφανιστεί ως τελικό αποτέλεσμα ο αριθμός 10, τότε ποιος μπορεί να είναι ο αριθμός που χορηγήσαμε στον υπολογιστή, εάν γνωρίζουμε ότι πρόκειται για έναν αριθμό περιττό (μονό) από το 1 έως το 100;

2.Γράψτε τον μικρότερο αριθμό με 15 ψηφία, που εάν τον χορηγήσουμε στον υπολογιστή, θα μας δώσει ως αποτέλεσμα τον αριθμό 10. 

3.Υπάρχει αριθμός με 20 ψηφία, που να είναι πολλαπλάσιο του 3 και όταν τον χορηγήσουμε στον υπολογιστή να μας δώσει τον αριθμό 20; 

Πηγή:«Μικρός Ευκλείδης 2013» 

Οι Σχηματισμοί

α) Πόσους διαφορετικούς πενταψήφιους αριθμούς μπορούμε να σχηματίσουμε χρησιμοποιώντας τα ψηφία 3 ή 4;

β) Εάν επιλέξουμε στην τύχη έναν από αυτούς να υπολογίσετε την πιθανότητα να αρχίζει και να τελειώνει σε 4.

Οι Μαθητές ΙΙ

Σε έναν διαγωνισμό που η μέγιστη δυνατή βαθμολογία ήταν το 100, έλαβαν μέρος «x» μαθητές. Οκτώ μαθητές πήραν βαθμό 100, ενώ όλοι οι υπόλοιποι πήραν βαθμό μεγαλύτερο ή ίσο του 70. Αν ο μέσος όρος των βαθμών των μαθητών ήταν 78, να βρεθεί η ελάχιστη δυνατή τιμή του πλήθους των μαθητών.

Πηγή:

Οι Μαθητές

Το πλήθος των μαθητών σε ένα Γυμνάσιο είναι τουλάχιστον 170 και το πολύ 230. Εάν γνωρίζουμε ότι ακριβώς το 4% των μαθητών παίζουν βιολί και ότι το 1/3 από όσους παίζουν βιολί, παίζει και πιάνο. Να βρείτε το πλήθος των μαθητών του Γυμνασίου.

Πηγή:

Η Απόσταση

Ο Τοτός ήταν επιβάτης στο πλοίο «Σκυλοπνίχτης» με κατεύθυνση τα νησιά του Πάσχα. Κατά τη διάρκεια μιας φουρτούνας ο καπετάνιος του «Σκυλοπνίχτη» τα κατάφερε και ναυάγησε το πλοίο ανοικτά του νησιού Boole. Ο Τοτός –άριστος κολυμβητής- κατόρθωσε να φτάσει στην ακτή του νησιού Boole. Στο νησί αυτό οι κάτοικοι μιλούσαν ελληνικά έτσι συνάντησε τον Έλληνα πρόξενο αυτός του είπε ότι θα τον φιλοξενούσε στο νησί για δέκα μέρες περίπου μέχρι να περάσει το πλοίο που θα τον μετέφερε στην Ελλάδα.

Γραφογρίφος

Αυτή είναι η κάτοψη του πύργου του διάσημου μαθηματικού Von Dumkopf .

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