Εργασίες θεωρίας γραφημάτων στο Word. Θεωρία γραφημάτων

Δημοτικό δημοσιονομικό εκπαιδευτικό ίδρυμα

Γυμνάσιο Oktyabrskaya

Ερευνητική εργασία στα μαθηματικά

«Θεωρία γραφημάτων στην επίλυση διαφόρων

είδη εργασιών"

Ολοκληρώθηκε το:
Μαθητής της 7ης τάξης
Makshun Alexey

Επόπτης:

καθηγητής μαθηματικών

Moshkovo 2011

1. Εισαγωγή.

1. 1. Συνάφεια του επιλεγμένου θέματος.

Μια μέρα συνάντησα ένα πρόβλημα που περιγράφει ο Lewis Carroll. «Τρία άτομα ζούσαν σε τρία σπίτια, κοντά τους υπήρχαν τρία πηγάδια: το ένα με νερό, το άλλο με λάδι και το τρίτο με μαρμελάδα, και περπατούσαν κοντά τους στα μονοπάτια που φαίνονται στην εικόνα. Μια μέρα αυτοί οι άνθρωποι μάλωσαν και αποφάσισαν να χαράξουν μονοπάτια από τα σπίτια τους μέχρι τα πηγάδια για να μην διασταυρωθούν αυτά τα μονοπάτια».

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

Στόχος:

Δείξτε την εφαρμογή της θεωρίας γραφημάτων για την επίλυση διαφόρων τύπων προβλημάτων.

Καθήκοντα:

· Μελέτη στοιχείων θεωρίας γραφημάτων για επίλυση προβλημάτων που με ενδιαφέρουν.

· Αναλύστε λύσεις σε διάφορα είδη προβλημάτων.

· Βελτιώστε τη μαθηματική κουλτούρα.

1.2. Η ιστορία της εμφάνισης της θεωρίας γραφημάτων.

Η ημερομηνία γέννησης της θεωρίας γραφημάτων θεωρείται το 1736, όταν ο Leonhard Euler έλυσε το πρόβλημα των γεφυρών Königsberg. Οι κλάδοι του ποταμού Pregel, στις όχθες του οποίου βρίσκεται η πόλη Königsberg, σχημάτιζαν δύο νησιά. Σε αυτήν την εποχή, τα τέσσερα σχηματισμένα τμήματα γης (η δεξιά και η αριστερή όχθη και δύο νησιά) συνδέονταν με επτά γέφυρες όπως φαίνεται στο σχήμα. Οι κάτοικοι της πόλης, περπατώντας στην πόλη, προσπάθησαν να δημιουργήσουν μια διαδρομή ώστε να περνάει κάθε γέφυρα ακριβώς μια φορά. Δεν κατάφεραν να το κάνουν αυτό, αλλά ο Euler απέδειξε ότι αυτό ήταν θεμελιωδώς αδύνατο. Ο όρος «γραφική παράσταση» εισήχθη για πρώτη φορά το 1936 από τον Ούγγρο μαθηματικό Dénes König. Η θεωρία γραφημάτων έχει αναπτυχθεί ευρέως από τη δεκαετία του '50 του 20ου αιώνα σε σχέση με την εμφάνιση της κυβερνητικής και την ανάπτυξη της τεχνολογίας των υπολογιστών.

Η λέξη "γράφημα" στα μαθηματικά σημαίνει μια εικόνα με πολλά σημεία που σχεδιάζονται, μερικά από τα οποία συνδέονται με γραμμές. Συνδέονται με τον ευγενή τίτλο «count» με κοινή προέλευση από τη λατινική λέξη «graphio» - γράφω.

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

Σχέδιο του μετρό του Νοβοσιμπίρσκ.

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

Οικογενειακό δέντρο.

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

2. Κύριο μέρος.

2.1. Βασικές έννοιες της θεωρίας γραφημάτων. Η εφαρμογή του στην επίλυση λογικών προβλημάτων.

Στα μαθηματικά, ο ορισμός ενός γραφήματος δίνεται ως εξής:

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

Καλείται ένα γραφικό διάγραμμα που αποτελείται από «απομονωμένες» κορυφές μηδενικό γράφημα. (Εικ.2)

Τα γραφήματα στα οποία δεν έχουν κατασκευαστεί όλες οι πιθανές ακμές καλούνται ελλιπή γραφήματα. (Εικ.3)

Τα γραφήματα στα οποία κατασκευάζονται όλες οι πιθανές ακμές ονομάζονται πλήρη γραφήματα. (Εικ.4)

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

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

Το σχήμα 5 δείχνει ένα γράφημα με πέντε κορυφές. Ο βαθμός της κορυφής Α θα συμβολίζεται με το Art. Α. Στην εικόνα: Art. A = 1, St. B = 2, Art. B = 3, Art. G= 2, St. D= 0.

Εργασία Νο. 1.

Αρκάντι, Μπόρις. Ο Βλαντιμίρ, ο Γκριγκόρι και ο Ντμίτρι έδωσαν τα χέρια όταν συναντήθηκαν (ο καθένας έσφιξε τα χέρια μεταξύ τους μία φορά). Πόσες χειραψίες έγιναν;

Λύση:

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

Εργασία Νο. 2.

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

Τα βράδια, ο Αντρέι και ο τορντέρ παίζουν ντόμινο εναντίον του Σεργκέι και του ηλεκτρολόγου.

Καθορίστε το επάγγελμα του καθενός από τους φίλους σας.

Λύση.

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

V S N A

W S T E

Εργασία Νο. 3.

Πέντε φίλοι ζουν σε μια μικρή πόλη: ο Ivanov, ο Petrenko, ο Sidorchuk, ο Grishin και ο Kapustin. Τα επαγγέλματά τους είναι διαφορετικά: ο ένας είναι ζωγράφος, ο άλλος είναι μυλωνάς, ο τρίτος είναι ξυλουργός, ο τέταρτος είναι ταχυδρόμος και ο πέμπτος είναι κομμωτής.

Ο Petrenko και ο Grishin δεν κρατούσαν ποτέ πινέλο στα χέρια τους.

Ο Ιβάνοφ και ο Γκρίσιν πρόκειται να επισκεφτούν το μύλο όπου εργάζεται ο φίλος τους. Ο Petrenko και ο Kapustin μένουν στο ίδιο σπίτι με τον ταχυδρόμο.

Ο Sidorchuk ήταν πρόσφατα ένας από τους μάρτυρες στο ληξιαρχείο όταν ο Petrenko και η κόρη του κομμωτή παντρεύτηκαν νόμιμα. Ο Ιβάνοφ και ο Πετρένκο παίζουν μικρές πόλεις με έναν ξυλουργό και έναν ζωγράφο κάθε Κυριακή.

Ο Grishin και ο Kapustin συναντιούνται πάντα τα Σάββατα στο κομμωτήριο όπου εργάζεται ο φίλος τους. Ο ταχυδρόμος προτιμά να ξυρίζεται μόνος του. Ποιος είναι ποιος?

Λύση.

Ivanov Petrenko Sidorchuk Grishin Kapustin

ζωγράφος μυλωνάς ξυλουργός ταχυδρόμος κομμωτής

2.2. Μονοπάτια Euler. Κατασκευάζοντας μια φιγούρα με μια κίνηση.

Ας διατυπώσουμε κάποιες κανονικότητες που είναι εγγενείς σε ορισμένα γραφήματα.

Μοτίβο 1.

Οι μοίρες των κορυφών ενός πλήρους γραφήματος είναι ίδιες και καθεμία από αυτές είναι 1 μικρότερη από τον αριθμό των κορυφών αυτού του γραφήματος.

Απόδειξη:

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

Μοτίβο 2.

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

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

Απόδειξη:

Πράγματι, κάθε άκρη του γραφήματος συνδέει δύο κορυφές. Αυτό σημαίνει ότι αν προσθέσουμε τον αριθμό των μοιρών όλων των κορυφών του γραφήματος, θα έχουμε διπλάσιο αριθμό ακμών 2R (R είναι ο αριθμός των άκρων του γραφήματος), αφού κάθε ακμή μετρήθηκε δύο φορές, που ήταν αυτό που χρειαζόταν για να να αποδειχθεί.

Ο αριθμός των περιττών κορυφών σε οποιοδήποτε γράφημα είναι άρτιος. Απόδειξη:

Θεωρήστε ένα αυθαίρετο γράφημα G. Έστω ο αριθμός των κορυφών σε αυτό το γράφημα των οποίων ο βαθμός είναι 1 είναι ίσος με K1. Ο αριθμός των κορυφών των οποίων ο βαθμός είναι 2 είναι ίσος με K2. ...; ο αριθμός των κορυφών των οποίων ο βαθμός είναι n είναι ίσος με Kn. Τότε το άθροισμα των μοιρών των κορυφών αυτού του γραφήματος μπορεί να γραφτεί ως
K1 + 2K2 + ZK3 + ...+ nKn.
Από την άλλη πλευρά: αν ο αριθμός των ακμών του γραφήματος είναι R, τότε από τον νόμο 2 είναι γνωστό ότι το άθροισμα των μοιρών όλων των κορυφών του γραφήματος είναι ίσο με 2R. Τότε μπορούμε να γράψουμε την ισότητα
K1 + 2K2 + ZK3 + ... + nKn = 2R.
Ας επιλέξουμε στην αριστερή πλευρά της ισότητας ένα άθροισμα ίσο με τον αριθμό των περιττών κορυφών του γραφήματος (K1 + K3 + ...):
K1 + 2K2 + ZK3 + 4K4 + 5K5 + ... + nKn = 2R,
(K1 + K3 + K5 +...) + (2K2 + 2K3 +4K4 + 4K5 + ...)=2R
Η δεύτερη αγκύλη είναι ένας ζυγός αριθμός ως το άθροισμα των ζυγών αριθμών. Το άθροισμα (2R) που προκύπτει είναι ένας ζυγός αριθμός. Άρα (Κ1 + Κ3 + Κ5 +...) είναι ζυγός αριθμός.

Q.E.D.

Εργασία Νο. 4.

Είναι δυνατή η σύνδεση 25 συσκευών με καλώδια έτσι ώστε κάθε συσκευή να συνδέεται ακριβώς με άλλες πέντε;

Λύση.

Αδύνατο. Ένα τέτοιο γράφημα θα είχε περιττό αριθμό κορυφών περιττού βαθμού.

Σημειώστε ότι εάν ένα πλήρες γράφημα έχει nκορυφές, τότε ο αριθμός των ακμών θα είναι ίσος με n(n-1)/2. Πράγματι, ο αριθμός των ακμών σε ένα πλήρες γράφημα με nκορυφές ορίζεται ως ο αριθμός των μη ταξινομημένων ζευγών που αποτελούνται από όλα nσημεία-άκρες του γραφήματος, δηλαδή ως ο αριθμός των συνδυασμών του nστοιχεία του 2:
Ένα γράφημα που δεν είναι πλήρες μπορεί να συμπληρωθεί για να συμπληρωθεί με τις ίδιες κορυφές προσθέτοντας τις ακμές που λείπουν. Για παράδειγμα, το σχήμα 3 δείχνει ένα ημιτελές γράφημα με πέντε κορυφές. Στο σχήμα 4, οι ακμές που μετατρέπουν το γράφημα σε πλήρες γράφημα απεικονίζονται με διαφορετικό χρώμα· η συλλογή των κορυφών του γραφήματος με αυτές τις ακμές ονομάζεται συμπλήρωμα του γραφήματος.

Εργασία Νο. 5.

Υπάρχουν 6 συμμετέχοντες στο πρωτάθλημα κατηγορίας επιτραπέζιας αντισφαίρισης: Andrey, Boris Victor, Galina, Dmitry και Elena. Το πρωτάθλημα διεξάγεται σε σύστημα round robin - κάθε συμμετέχων παίζει με κάθε έναν από τους άλλους μία φορά. Μέχρι σήμερα, μερικά παιχνίδια έχουν ήδη παιχτεί: Ο Αντρέι έπαιξε με τον Μπόρις, τη Γκαλίνα, την Έλενα. Μπόρις - με τον Αντρέι, Γκαλίνα. Βίκτωρ - με τη Γκαλίνα, τον Ντμίτρι, την Έλενα. Galina - με τον Andrey, τον Victor και τον Boris. Πόσα παιχνίδια έχουν παιχτεί μέχρι στιγμής και πόσα απομένουν;

Λύση:

Ας φτιάξουμε ένα γράφημα. Σημειώνουμε τα παιχνίδια που παίχτηκαν με μπλε γραμμές και προσθέτουμε κόκκινες γραμμές για να συμπληρώσουμε το γράφημα. Καταλαβαίνουμε ότι έχουν παιχτεί 7 παιχνίδια και έχουν απομείνει 8. Μπορείτε να ελέγξετε: στο γράφημα υπάρχουν 6 κορυφές, τότε υπάρχουν συνολικά 6*5/2=15 άκρες (7+8).

Γραφήματα Euler.

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

Ένα γράφημα που μπορεί να σχεδιαστεί χωρίς να σηκωθεί το μολύβι από το χαρτί ονομάζεται Ο Eulerian.(Εικ. 6) Αυτά τα γραφήματα ονομάζονται από τον επιστήμονα Leonhard Euler.

Εικ. 6 (γραφήματα Eulerian)

Κανονικότητα 3 (ακολουθεί το θεώρημα που εξετάσαμε).
Είναι αδύνατο να σχεδιάσετε ένα γράφημα με περιττό αριθμό περιττών κορυφών.
Μοτίβο 4.

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

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

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

Ένα σχήμα (γραφική παράσταση) που μπορεί να σχεδιαστεί χωρίς να σηκωθεί το μολύβι από το χαρτί ονομάζεται μονόδρομος.

Εργο № 6 για τις γέφυρες Königsberg.

Οι κλάδοι του ποταμού Pregel, στις όχθες του οποίου βρίσκεται η πόλη Königsberg, σχημάτιζαν δύο νησιά. Σε αυτήν την εποχή, τα τέσσερα σχηματισμένα τμήματα γης (η δεξιά και η αριστερή όχθη και δύο νησιά) συνδέονταν με επτά γέφυρες όπως φαίνεται στο σχήμα. Οι κάτοικοι της πόλης, περπατώντας στην πόλη, προσπάθησαν να δημιουργήσουν μια διαδρομή ώστε να περνάει κάθε γέφυρα ακριβώς μια φορά.

Λύση.

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

Εργασία Νο. 7.

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

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

Εργασία Νο. 8.

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

Λύση:

1) Είναι δυνατό, γιατί υπάρχουν μόνο 2 περιττές κορυφές.

2) Είναι αδύνατο, γιατί υπάρχουν 4 περιττές κορυφές.

Εργασία Νο. 9.

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

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

Εργασία Νο. 10.Πετάξτε σε ένα βάζο.

Μια μύγα μπήκε σε ένα βάζο ζάχαρης. Το βάζο έχει σχήμα κύβου. Μπορεί μια μύγα να γυρίσει διαδοχικά και τις 12 άκρες ενός κύβου χωρίς να περάσει από την ίδια άκρη δύο φορές; Δεν επιτρέπεται το άλμα και η πτήση από μέρος σε μέρος.

Λύση.

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

Εργασία Νο. 11.

Προσπαθήστε να φτιάξετε αυτές τις φιγούρες με μια κίνηση.

2.3. Επίπεδα γραφήματα.

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

Ο Euler απέδειξε ένα θεώρημα που δίνει αρνητική απάντηση στο ερώτημα αυτού του προβλήματος.

Θεώρημα Euler.

Αν ένα γράφημα με n κορυφές και m άκρες είναι επίπεδο, τότε είναι αληθής η ισότητα n-m+p=2, όπου p είναι ο αριθμός των ασυνεχών μερών (λέγονται όψεις) στα οποία η γραφική παράσταση διαιρεί το επίπεδο.

Απόδειξη.

Το γράφημα «τρία σπίτια και τρία πηγάδια» έχει έξι κορυφές και εννέα άκρες. Εάν είναι επίπεδο, ο αριθμός των άκρων p πρέπει να είναι ίσος με p = n – m + 2 = 9 - 6 + 2 = 5. Επειδή όμως δεν υπάρχουν δύο σπίτια ή δύο πηγάδια συνδεδεμένα μεταξύ τους, κάθε όψη έχει τουλάχιστον τέσσερα άκρα . Λαμβάνουμε την ανισότητα 2n ≥ 4p (κάθε ακμή μετράται δύο φορές), από την οποία προκύπτει η ψευδής ανισότητα 18 ≥ 20. Ομοίως, αποδεικνύεται ότι ένα πλήρες γράφημα πέντε κορυφών επίσης δεν μπορεί να είναι επίπεδο.

Θεώρημα Pontryagin–Kuratowski.

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

3. Συμπέρασμα.

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

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

4. Λογοτεχνία.

3. ευρηματικότητα Ignatiev. - Μ.: «Ωμέγα», 1994.

5. «Μαθηματικά» - συμπλήρωμα της εφημερίδας «Πρωτο Σεπτέμβρη» Νο. 7, 2005

6. Εγκυκλοπαιδικό Λεξικό Νεαρού Μαθηματικού / Σύνθ. Α.Π. Savin.- M.: Παιδαγωγική, 1989.

Χρησιμοποιήσαμε επίσης δεδομένα από τους ακόλουθους ιστότοπους:

Εγκυκλοπαιδικό Λεξικό Νέου Μαθηματικού / Σύνθ. Α.Π. Savin.- M.: Παιδαγωγική, 1989.

Παπούτσια στην τσέπη του καγκουρό. - M.: Bustard, 2010.

Http:infometronovosibirsk_metro_map. htm

http://www. /δείκτης. php; cnt=4

Φυσικομαθηματικό περιοδικό "Kvant", Νο. 6, 1994.

Προετοιμασία μαθητών για μαθηματικές ολυμπιάδες. 5-6 βαθμοί/σύνθ. – Μ.: «Σφαίρα», 2009.

Η εργασία της Makeeva στα μαθηματικά. – Σαράτοφ: «Λύκειο», 2002

«Μαθηματικά» - συμπλήρωμα της εφημερίδας «Πρωτο Σεπτέμβρη» Νο 7, 2005

Φυσικομαθηματικό περιοδικό "Kvant", Νο. 6, 1994.

Παπούτσια στην τσέπη του καγκουρό. - M.: Bustard, 2010.

Φυσικομαθηματικό περιοδικό "Kvant", Νο. 6, 1994.

Προετοιμασία μαθητών για μαθηματικές ολυμπιάδες. 5-6 βαθμοί/σύνθ. – Μ.: «Σφαίρα», 2009.

Φυσικομαθηματικό περιοδικό "Kvant", Νο. 6, 1994.

Παπούτσια στην τσέπη του καγκουρό. - M.: Bustard, 2010.

Η εργασία της Makeeva στα μαθηματικά. – Σαράτοφ: «Λύκειο», 2002

Η εργασία της Makeeva στα μαθηματικά. – Σαράτοφ: «Λύκειο», 2002

Η ευρηματικότητα του Ιγνάτιεφ. - Μ.: «Ωμέγα», 1994.

Η εργασία της Makeeva στα μαθηματικά. – Σαράτοφ: «Λύκειο», 2002

Προετοιμασία μαθητών για μαθηματικές ολυμπιάδες. 5-6 βαθμοί/σύνθ. – Μ.: «Σφαίρα», 2009.

Παπούτσια στην τσέπη του καγκουρό. - M.: Bustard, 2010.

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

Μερικά παραδείγματα θα δώσουν ένα μικρό σκίτσο του γραφήματος. Έτσι, ένα τυπικό γράφημα είναι ένας χάρτης του μετρό ή κάποια άλλη διαδρομή. Συγκεκριμένα, ο προγραμματιστής είναι εξοικειωμένος με ένα δίκτυο υπολογιστών, το οποίο είναι και ένα γράφημα. Το κοινό εδώ είναι η παρουσία σημείων που συνδέονται με γραμμές. Έτσι, σε ένα δίκτυο υπολογιστών, τα σημεία είναι μεμονωμένοι διακομιστές και οι γραμμές είναι διαφορετικοί τύποι ηλεκτρικών σημάτων. Στο μετρό, το πρώτο είναι οι σταθμοί, το δεύτερο είναι τα τούνελ που έχουν τοποθετηθεί ανάμεσά τους. Στη θεωρία γραφημάτων, τα σημεία ονομάζονται κορυφές (κόμβους), και οι γραμμές είναι παϊδάκια (τόξα). Ετσι, γραφική παράστασηείναι μια συλλογή κορυφών που συνδέονται με ακμές.

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

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

Είναι ουσιαστικά ένα γράφημα. Οι πέντε υπολογιστές είναι οι κορυφές και οι συνδέσεις (διαδρομές σήματος) μεταξύ τους είναι οι ακμές. Αντικαθιστώντας τους υπολογιστές με κορυφές, παίρνουμε ένα μαθηματικό αντικείμενο - ένα γράφημα, το οποίο έχει 10 ακμές και 5 κορυφές. Οι κορυφές μπορούν να αριθμηθούν με οποιονδήποτε τρόπο, και όχι απαραίτητα όπως φαίνεται στο σχήμα. Αξίζει να σημειωθεί ότι αυτό το παράδειγμα δεν χρησιμοποιεί έναν μόνο βρόχο, δηλαδή μια άκρη που φεύγει από μια κορυφή και εισέρχεται αμέσως σε αυτήν, αλλά μπορεί να εμφανιστούν βρόχοι σε προβλήματα.

Ακολουθούν ορισμένες σημαντικές σημειώσεις που χρησιμοποιούνται στη θεωρία γραφημάτων:

• G=(V, E), εδώ G είναι το γράφημα, V είναι οι κορυφές του και E οι ακμές του.
• |V| – σειρά (αριθμός κορυφών).
• |Ε| – μέγεθος γραφήματος (αριθμός ακμών).

Στην περίπτωσή μας (Εικ. 1) |V|=5, |E|=10;

Όταν οποιαδήποτε άλλη κορυφή είναι προσβάσιμη από οποιαδήποτε κορυφή, τότε καλείται ένα τέτοιο γράφημα χωρίς προσανατολισμόσυνδεδεμένο γράφημα (Εικ. 1). Εάν το γράφημα είναι συνδεδεμένο, αλλά αυτή η συνθήκη δεν πληρούται, τότε καλείται ένα τέτοιο γράφημα προσανατολισμένηή διγράφημα (Εικ. 2).

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

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

Τα κατευθυνόμενα γραφήματα έχουν τον ακόλουθο συμβολισμό:

G=(V, A), όπου V είναι κορυφές, A είναι κατευθυνόμενες ακμές.

Ο τρίτος τύπος γραφημάτων είναι μικτόςγραφήματα (Εικ. 3). Έχουν τόσο κατευθυνόμενες όσο και μη κατευθυνόμενες άκρες. Τυπικά, ένα μικτό γράφημα γράφεται ως εξής: G=(V, E, A), όπου καθένα από τα γράμματα σε αγκύλες σημαίνει το ίδιο πράγμα που του είχε ανατεθεί νωρίτερα.

Στο γράφημα στο σχήμα 3, ορισμένα τόξα είναι κατευθυνόμενα [(e, a), (e, c), (a, b), (c, a), (d, b)], άλλα είναι μη κατευθυνόμενα [(e, δ), (ε, β), (δ, γ)…].

Με την πρώτη ματιά, δύο ή περισσότερα γραφήματα μπορεί να φαίνονται διαφορετικά στη δομή, κάτι που προκύπτει λόγω της διαφορετικής αναπαράστασής τους. Δεν είναι όμως πάντα έτσι. Ας πάρουμε δύο γραφήματα (Εικ. 4).

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

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

Σε οποιοδήποτε από τα γραφήματα που εξετάσαμε, είναι δυνατό να επιλέξετε μια διαδρομή και, επιπλέον, περισσότερα από ένα. Μονοπάτιείναι μια ακολουθία κορυφών, καθεμία από τις οποίες συνδέεται με την επόμενη μέσω μιας ακμής. Εάν η πρώτη και η τελευταία κορυφή συμπίπτουν, τότε μια τέτοια διαδρομή ονομάζεται κύκλος. Το μήκος μιας διαδρομής καθορίζεται από τον αριθμό των ακμών που την αποτελούν. Για παράδειγμα, στο σχήμα 4.a η διαδρομή είναι η ακολουθία [(e), (a), (b), (c)]. Αυτό το μονοπάτι είναι ένα υπογράφημα, αφού ο ορισμός του τελευταίου ισχύει για αυτό, δηλαδή: το γράφημα G'=(V', E') είναι υπογράφημα του γραφήματος G=(V, E) μόνο εάν V' και E' ανήκουν στους V, E .

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

Ας δούμε τη γραφική αναπαράσταση των γραφημάτων στον Πίνακα 1.

Πίνακας 1. Γραφική αναπαράσταση γραφημάτων

Πολλά αποτελέσματα που λαμβάνονται για απλά γραφήματα μπορούν εύκολα να μεταφερθούν σε πιο γενικά αντικείμενα στα οποία δύο κορυφές μπορούν να συνδεθούν με περισσότερες από μία ακμές. Επιπλέον, είναι συχνά βολικό να αφαιρείται ο περιορισμός ότι μια άκρη πρέπει να συνδέει δύο διαφορετικές κορυφές και να επιτρέπει την ύπαρξη βρόχων. Το αντικείμενο που προκύπτει, το οποίο μπορεί να έχει πολλαπλές ακμές και βρόχους, ονομάζεται γράφημα (ψευδογράφος). Ένας ψευδογράφος χωρίς βρόχους ονομάζεται πολύγραφος

Ας δούμε μερικούς σημαντικούς τύπους γραφημάτων.

Ορισμός. Ένα γράφημα του οποίου οι πολλές ακμές είναι κενές ονομάζεται γράφημα εντελώς αποσυνδεδεμένο (ή κενό). Ένα εντελώς αποσυνδεδεμένο γράφημα συμβολίζεται με N

Σημειώστε ότι σε ένα εντελώς αποσυνδεδεμένο γράφημα όλες οι κορυφές είναι απομονωμένες

Ορισμός. Ένα απλό γράφημα στο οποίο οι δύο κορυφές είναι γειτονικές ονομάζεται πλήρες. Το πλήρες γράφημα συμβολίζεται με Κ

Σημειώστε ότι το πλήρες γράφημα ικανοποιεί την ισότητα

όπου m είναι ο αριθμός των ακμών, n ο αριθμός των κορυφών του γραφήματος.

Ορισμός. Ένα γράφημα στο οποίο όλες οι κορυφές έχουν τον ίδιο τοπικό βαθμό n ονομάζεται κανονικό (ή ομοιογενές) του βαθμού n.

Τα κανονικά γραφήματα του βαθμού 3 ονομάζονται κυβικά (ή τρισθενή).

Ένα διάσημο παράδειγμα κυβικού γραφήματος είναι το γράφημα Peterson

Μεταξύ των κανονικών γραφημάτων, τα λεγόμενα πλατωνικά γραφήματα είναι ιδιαίτερα ενδιαφέροντα - γραφήματα που σχηματίζονται από τις κορυφές και τις ακμές πέντε κανονικών πολύεδρων - Πλατωνικά στερεά: τετράεδρο, κύβος, οκτάεδρο, δωδεκάεδρο και εικοσάεδρο. Το σχήμα 6 δείχνει ένα γράφημα που αντιστοιχεί σε έναν κύβο.

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

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

Ορισμός. Εάν σε ένα διμερές γράφημα κάθε κορυφή από το V1 συνδέεται με κάθε κορυφή από το V2, τότε το γράφημα ονομάζεται πλήρης διμερής.

Σημειώστε ότι το γράφημα Km. Το n έχει ακριβώς m + n κορυφές και mn ακμές.

Ορισμός. Ένωση γραφημάτων

ονομάζεται γράφημα

Ορισμός. Με τομή γραφημάτων

ονομάζεται γράφημα

Ορισμός. Η σύνδεση των γραφημάτων G1 και G2 είναι ένα νέο γράφημα του οποίου

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

Ορισμός. Ένα γράφημα ονομάζεται συνδεδεμένο εάν δεν μπορεί να αναπαρασταθεί ως ένωση δύο γραφημάτων και αποσυνδέεται διαφορετικά.

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

Ορισμός. Ένα συνδεδεμένο κανονικό γράφημα βαθμού 2 ονομάζεται κυκλικό γράφημα. Συμβολίζεται με Cn.

Ορισμός. Η σύνδεση των γραφημάτων N1 και Cn-1 (n3) ονομάζεται τροχός με n κορυφές. Συμβολίζεται με Wn (Εικόνα 10)

Ορισμός. Το συμπλήρωμα ενός απλού γραφήματος G είναι ένα απλό γράφημα με ένα σύνολο κορυφών V(G) στο οποίο δύο κορυφές είναι γειτονικές εάν και μόνο εάν δεν είναι γειτονικές στο αρχικό γράφημα.

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

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

Τα γραφήματα είναι ένα διασκεδαστικό, ικανοποιητικό και τρομακτικό θέμα. Θεωρία Γραφημάτων - «Ο τρόμος του μαθητή». Οι αλγόριθμοι γραφημάτων είναι τα καταπληκτικά μυαλά των ανθρώπων που τους ανακάλυψαν.

Τι είναι ένα γράφημα; Για να απαντήσω σε αυτήν την ερώτηση για τους αναγνώστες μου, θα περιγράψω το θέμα λίγο διαφορετικά.
Ένα γράφημα είναι ένα σύνολο αντικειμένων.
Στα περισσότερα προβλήματα αυτά είναι αντικείμενα του ίδιου τύπου. (Πολλές πόλεις, ή πολλά σπίτια, ή πολλοί άνθρωποι, ή πολλά άλλα πράγματα του ίδιου τύπου)

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

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

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

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

Σίγουρα έχετε διαβάσει σχολικά βιβλία και έχετε δει αυτόν τον συμβολισμό G(V,E) ή κάτι παρόμοιο. Άρα, το V είναι ένα αντικείμενο από όλο το σύνολο των αντικειμένων. Στην περίπτωσή μας, το σύνολο των αντικειμένων είναι πόλεις, επομένως, το V είναι μια συγκεκριμένη πόλη. Δεδομένου ότι τα αντικείμενα δεν είναι απαραίτητα πόλεις και η λέξη αντικείμενο μπορεί να προκαλέσει σύγχυση, ένα τέτοιο αντικείμενο από το σύνολο μπορεί να ονομαστεί σημείο, σημείο ή κάτι άλλο, αλλά τις περισσότερες φορές ονομάζεται κορυφή του γραφήματος και συμβολίζεται με το γράμμα V.
Στον προγραμματισμό, αυτό είναι συνήθως είτε μια στήλη είτε μια γραμμή ενός δισδιάστατου πίνακα, όπου ο πίνακας ονομάζεται είτε πίνακας γειτνίασης είτε πίνακας πρόσπτωσης.

Στη λογοτεχνία, στο Διαδίκτυο και γενικά όπου γράφεται κάτι για γραφήματα, θα συναντήσετε έννοιες όπως τόξα και ακμές. Αυτό το σχήμα δείχνει τις άκρες του γραφήματος. Εκείνοι. αυτές είναι τρεις ακμές Ε1, Ε2 και Ε3.

Ένα τόξο και μια ακμή διαφέρουν στο ότι μια άκρη είναι μια αμφίδρομη σύνδεση. Το ήθελε, πήγε στον γείτονά του, το ήθελε, γύρισε από τον γείτονά του. Αν δεν είναι πολύ ξεκάθαρο, τότε μπορείτε να φανταστείτε ένα σπίτι, ένα αεροδρόμιο, ένα ιπτάμενο αεροπλάνο και έναν αλεξιπτωτιστή. Ένας αλεξιπτωτιστής μπορεί να πάει από το σπίτι του στο αεροδρόμιο, αλλά όταν φτάνει στο αεροδρόμιο, θυμάται ότι ξέχασε το τυχερό του αλεξίπτωτο στο σπίτι, μετά επιστρέφει σπίτι του και παίρνει το αλεξίπτωτο. — Ένας δρόμος στον οποίο μπορείτε να περπατήσετε πέρα ​​δώθε ονομάζεται άκρη.
Εάν ένας αλεξιπτωτιστής είναι σε ένα αεροπλάνο και πηδά από το αεροπλάνο, αλλά ο αλεξιπτωτιστής ξέχασε να φορέσει το τυχερό του αλεξίπτωτο στο αεροπλάνο, θα μπορέσει ο αλεξιπτωτιστής να πάρει αυτό που ξέχασε; Ένα μονοπάτι που πηγαίνει μόνο προς μία κατεύθυνση ονομάζεται τόξο. Συνήθως λέμε ότι μια άκρη συνδέει δύο κορυφές και ένα τόξο πηγαίνει από τη μια κορυφή στην άλλη.

Σε αυτό το σχήμα, το γράφημα έχει μόνο τόξα. Τα τόξα στο γράφημα υποδεικνύονται με βέλη, επειδή η προσβάσιμη κατεύθυνση είναι τόσο σαφής. Εάν ένα γράφημα αποτελείται μόνο από τέτοια τόξα, τότε ένα τέτοιο γράφημα ονομάζεται κατευθυνόμενο.

Θα συναντήσετε συχνά τις έννοιες της γειτνίασης και της επίπτωσης. Στο σχήμα, δύο άκρες που πηγαίνουν σε ένα σημείο σημειώνονται με κόκκινο χρώμα. Τέτοιες ακμές, όπως οι κορυφές που περιγράφηκαν παραπάνω, ονομάζονται επίσης γειτονικές.

Πολλά δεν περιγράφονται, αλλά αυτή η πληροφορία μπορεί να βοηθήσει κάποιον.

«Ένας άλλος συναρπαστικός τρόπος επίλυσης προβλημάτων» (μέθοδος γραφήματος) Συγγραφέας: Maria Pyrkova, μαθήτρια 7ης τάξης στο οικοτροφείο Νο. 9 των Ρωσικών Σιδηροδρόμων, Kinel, Περιφέρεια Σαμάρας Επόπτης: Olga Alekseevna Stepanova, καθηγήτρια μαθηματικών ανώτερης κατηγορίας. Kinel, 2015

Συνάφεια του καθοριστικού ρόλου των προβλημάτων στη διδασκαλία των μαθηματικών. Εισαγωγή στο σχολικό μάθημα των ενοτήτων «Συνδυαστική», «Λογική», «Πιθανότητες»· βρίσκοντας τρόπους επίλυσης μη τυπικών προβλημάτων.

Σκοπός της μελέτης: η μελέτη της έννοιας του «γραφήματος» και των στοιχείων του. εφαρμόζονται κατά την επίλυση διαφόρων τύπων προβλημάτων.

Αντικείμενο μελέτης: γράφημα ΘΕΜΑ ΕΡΕΥΝΑΣ ιστορία μαθηματικών, είδη προβλημάτων, μέθοδοι επίλυσης προβλημάτων.

Κύριες μέθοδοι έρευνας: έρευνα; χρήση στην πράξη. επεξεργασία δεδομένων υπολογιστή? ταξινόμηση και ανάλυση του συλλεγόμενου υλικού. μαθηματική επιλογή.

Η μαθηματική έννοια του «γραφήματος». Στα μαθηματικά, ένα γράφημα είναι ένα πεπερασμένο σύνολο σημείων, μερικά από τα οποία συνδέονται με γραμμές. Τα σημεία ονομάζονται κορυφές του γραφήματος και οι συνδετικές γραμμές ονομάζονται ακμές. ένα γράφημα μηδέν είναι ένα ημιτελές γράφημα. πλήρες γράφημα.

Πεδίο εφαρμογής των γραφημάτων

Πρακτικό μέρος

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

«Πόσα κεφάλια βοοειδή έχεις στο κοπάδι σου;» Στην ερώτηση του ταξιδιώτη: ο βοσκός απάντησε: «Αν πρόσθεσα μια αγελάδα στο κοπάδι μου, τότε το ένα τρίτο ολόκληρου του κοπαδιού θα αποτελείται από πρόβατα και κατσίκες. Αν προσθέταμε ένα πρόβατο στα υπάρχοντα αιγοπρόβατα, τότε το έβδομο μέρος τους θα ήταν κατσίκες, εκ των οποίων το τρίτο είναι μόνο ένα μικρό κατσίκι». Πόσα κεφάλια βοοειδών υπήρχαν στο κοπάδι; Λύση: Ας δημιουργήσουμε ένα γράφημα με βάση τις συνθήκες του προβλήματος. Ας αποφασίσουμε πίσω. Απάντηση: υπάρχουν 59 βοοειδή στο κοπάδι.

Εργασίες κίνησης. Το αυτοκίνητο κάλυψε το πρώτο τμήμα της διαδρομής σε 3 ώρες και το δεύτερο τμήμα σε 2 ώρες. Το μήκος και των δύο τμημάτων μαζί είναι 267 χλμ. Με τι ταχύτητα πήγαινε το αυτοκίνητο σε κάθε τμήμα, αν η ταχύτητα στο δεύτερο τμήμα ήταν 8,5 km/h μεγαλύτερη από ό,τι στο πρώτο; Ας φτιάξουμε ένα γράφημα δικτύου. Έστω V 1 = x km/h, μετά V 2 = x+ 8,5 km/h, S 1 = 3x km, S 2 = 2(x+8,5) km Ας δημιουργήσουμε την εξίσωση: 3x + 2(x+8,5 ) = 267 Απάντηση: 50 km/h

Συνδυαστικά προβλήματα. Η εργασία "Ποιο είναι υψηλότερο;" Στο χώρο του σχολείου φυτρώνουν 8 δέντρα: μηλιά, λεύκα, σημύδα, σορβιά, βελανιδιά, σφενδάμι, πεύκη και πεύκο. Το Rowan είναι υψηλότερο από την λάρικα, η μηλιά είναι ψηλότερα από το σφενδάμι, η βελανιδιά είναι χαμηλότερη από τη σημύδα, αλλά ψηλότερα από το πεύκο, το πεύκο είναι υψηλότερο από τη σορβιά, η σημύδα είναι χαμηλότερη από τη λεύκα και η πεύκη είναι υψηλότερη από τη μηλιά. Τακτοποιήστε τα δέντρα από το πιο κοντό στο ψηλότερο. Απάντηση: ο σφένδαμος είναι το πιο κοντό δέντρο.

Έρευνα συμμαθητών

Συμπέρασμα «Αργά ή γρήγορα, κάθε σωστή μαθηματική ιδέα βρίσκει εφαρμογή στο ένα ή στο άλλο πράγμα». (A.N. Krylov) Τα γραφήματα είναι υπέροχα μαθηματικά αντικείμενα με τα οποία μπορείτε να λύσετε μαθηματικά, οικονομικά και λογικά προβλήματα. Τα γραφήματα σάς επιτρέπουν να αναπαραστήσετε οπτικά τις συνθήκες ενός προβλήματος, να διατηρήσετε πολλά γεγονότα στη μνήμη και επομένως να απλοποιήσετε σημαντικά τη λύση του. Δημιουργεί ενδιαφέρον για την εκμάθηση μαθηματικών και την επίτευξη καλών αποτελεσμάτων.

Αναφορές Εγκυκλοπαιδικό Λεξικό ενός Νεαρού Μαθηματικού. \Συνθ. A.P.Savin. - M.: Pedagogy, 1989 Quantum No. 6 1994 M. Gardner “Mathematical leisure” M.: Mir, 1972 Berge K. Graph theory and its application. Ι.Λ., 1962. Μαθηματικά, εγχειρίδιο Ε' Δημοτικού. / N.Ya.Vilenkin, V.I.Zhokhov και άλλοι - M: Εκπαίδευση, 2011 Μαθηματικά, εγχειρίδιο για την 6η τάξη. / N.Ya.Vilenkin, V.I.Zhokhov και άλλοι - M: Εκπαίδευση, 2011 Άλγεβρα: εγχειρίδιο για την 7η τάξη. / Yu.N. Makarychev et al., επιμέλεια S.A. Telyakovsky.-M.: Εκπαίδευση, 2011 Μαθήματα επιλογής "Επίλυση προβλημάτων χρησιμοποιώντας γραφήματα" / συγγραφέας - L.N. Kharlamov. - Βόλγκογκραντ: Δάσκαλος, 2007.

Σας ευχαριστώ για την προσοχή σας!