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

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

βασικοί ορισμοί

Τι είναι το γράφημα στην επιστήμη των υπολογιστών; Περιλαμβάνει ένα πλήθος αντικειμένων ονομάζονται κόμβοι ή κορυφές, μερικές ζεύγη των οποίων συνδέονται με m. N. πλευρών. Για παράδειγμα, η γραφική παράσταση στο σχήμα (α) αποτελείται από τέσσερις κόμβους, που συμβολίζεται Α, Β, C, και D, Β εκ των οποίων είναι συνδεδεμένο με κάθε μία από τις άλλες τρεις κορυφές νευρώσεις, και Γ και Δ συνδέονται επίσης. Δύο κόμβοι είναι γειτονικοί, εάν έχουν συνδεθεί από μια άκρη. Η εικόνα δείχνει ένα τυπικό τρόπο για το πώς να οικοδομήσουμε γραφήματα στην επιστήμη των υπολογιστών. Κύκλοι παριστούν τις κορυφές και τις γραμμές που συνδέει κάθε ζεύγος από αυτά, είναι οι νευρώσεις.

Τι μη-κατευθυνόμενο γράφημα ονομάζεται στην επιστήμη των υπολογιστών; Ο σχέσεων μεταξύ των δύο άκρων των πλευρών είναι συμμετρικές. Rib απλά να τους συνδέει μεταξύ τους. Σε πολλές περιπτώσεις, ωστόσο, είναι απαραίτητο να εκφραστεί η ασύμμετρη σχέση - για παράδειγμα, ότι ένα σημεία στο Β, αλλά όχι το αντίστροφο. Ο στόχος αυτός είναι ο ορισμός της γραφικής παράστασης στον υπολογιστή, ακόμα αποτελείται από ένα σύνολο κόμβων με μια σειρά από κατευθυνόμενες ακμές. Κάθε προσανατολισμένη ακμή είναι η σχέση μεταξύ των κορυφών των οποίων κατεύθυνση έχει σημασία. Κατευθυνόμενη γραφήματα απεικονίζουν, όπως φαίνεται στο Σχήμα (β), οι ακμές τους που αντιπροσωπεύεται από τα βέλη. Όταν θέλετε να τονίσω ότι η μη-κατευθυντικό γράφημα, αυτό ονομάζεται μη κατευθυνόμενη.

μοντέλα δικτύου

Γραφήματα στην επιστήμη των υπολογιστών είναι μαθηματικό μοντέλο των δομών του δικτύου. Το παρακάτω σχήμα δείχνει τη δομή του Διαδικτύου, τότε έφερε το όνομα του ARPANET, το Δεκέμβριο του 1970, όταν ήταν μόλις 13 πόντους. Οι κόμβοι είναι κέντρα επεξεργασίας και οι νευρώσεις συνδέουν τις δύο κορυφές feedforward μεταξύ αυτών. Αν δεν δώσουν προσοχή οι Ηνωμένες Πολιτείες επέβαλαν το χάρτη, το υπόλοιπο αυτής της εικόνας είναι ένα γράφημα 13-node παρόμοια με την προηγούμενη. Σε αυτή την περίπτωση, η πραγματική θέση της κορυφής δεν είναι απαραίτητη. Είναι σημαντικό στο οποίο οι κόμβοι συνδέονται μεταξύ τους.

Εφαρμογή των γραφημάτων στον υπολογιστή σας επιτρέπει να δείτε πώς είναι είτε φυσικά είτε λογικά συνδέονται μεταξύ τους σε μια δομή δικτύου πράγματα. 13-κόμβο ARPANET είναι ένα παράδειγμα του δικτύου επικοινωνίας στην οποία top υπολογιστές ή άλλες συσκευές που μπορεί να μεταδώσει μηνύματα, και οι ακμές αντιπροσωπεύουν άμεση σύνδεση στην οποία μπορεί να μεταδοθεί πληροφορία.

διαδρομές

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

Η ιδέα αυτή παρακινεί τον ορισμό της διαδρομής ως μια σειρά κόμβων που συνδέονται με ακμές. Μερικές φορές είναι απαραίτητο να εξεταστεί η διαδρομή που περιέχει όχι μόνο τα συστατικά, αλλά και την αλληλουχία των άκρων που συνδέει τους. Για παράδειγμα, η αλληλουχία των κορυφών ΜΙΤ, ΒΒΝ, RAND, UCLA είναι μια διαδρομή σε ARPANET γράφημα διαδίκτυο. Πέρασμα των κόμβων και των ακμών μπορεί να επαναληφθεί. Για παράδειγμα, SRI, STAN, UCLA, SRI, Utah, ΜΙΤ είναι επίσης μια διαδρομή. Ο τρόπος με τον οποίο οι νευρώσεις δεν επαναλαμβάνονται, που ονομάζεται αλυσίδα. Αν οι κόμβοι δεν επαναλαμβάνονται, αυτό ονομάζεται μια απλή αλυσίδα.

κύκλων

Ιδιαίτερα σημαντικά είδη στις γραφικές παραστάσεις υπολογιστή - είναι κύκλοι που αντιπροσωπεύουν μια δομή δακτυλίου, όπως μια ακολουθία κόμβων LINC, CASE, CARN, HARV, ΒΒΝ, ΜΙΤ, LINC. Διαδρομές με τουλάχιστον τρεις νευρώσεις, στην οποία το πρώτο και το τελευταίο κόμβο είναι τα ίδια, και τα υπόλοιπα είναι διαφορετικά, παριστούν μια κυκλική γραφήματα στην επιστήμη των υπολογιστών.

Παραδείγματα: SRI κύκλου, STAN, UCLA, SRI είναι η συντομότερη, και SRI, STAN, UCLA, RAND, ΒΒΝ, Γιούτα, SRI σημαντικά μεγαλύτερη.

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

Connected γράφημα: ευκρίνειας (επιστήμη των υπολογιστών)

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

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

εξαρτήματα

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

Συστατικά του γραφήματος αντιπροσωπεύουν ένα υποσύνολο των κόμβων, με τον οποίο:

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

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

Η μέγιστη συνιστώσα

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

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

Παγκόσμιο δίκτυο φίλων

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

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

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

Ατύχημα συγχώνευση συστατικό

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

American High School

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

Απόσταση και το πλάτος, αναζήτηση πρώτα

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

Για να γίνει αυτό, ορίζουν ένα μήκος διαδρομής ίσο με τον αριθμό των βημάτων που περιέχει από αρχή μέχρι το τέλος, δηλαδή. Ε Ο αριθμός των ακμών στην ακολουθία που είναι. Για παράδειγμα, ΜΙΤ, ΒΒΝ, RAND, UCLA διαδρομή έχει μήκος 3, και MIT, Utah - 1. Χρησιμοποιώντας το μήκος της διαδρομής, μπορούμε να πούμε ότι αν οι δύο κόμβοι διατάσσονται στη στήλη κοντά το ένα στο άλλο ή μακριά απόσταση μεταξύ των δύο κορυφών ορίζεται ως το μήκος της η συντομότερη διαδρομή μεταξύ τους. Για παράδειγμα, η απόσταση μεταξύ του LINC και SRI είναι 3, αν και, για να εξασφαλιστεί αυτό, είναι απαραίτητο να επαληθευθεί η απουσία των μήκος ίσο με 1 ή 2, μεταξύ τους.

Πλάτος-πρώτος αλγόριθμος αναζήτησης

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

Ο πιο φυσικός τρόπος για να γίνει αυτό και, ως εκ τούτου, η πιο αποτελεσματική είναι η εξής (για παράδειγμα, ένα παγκόσμιο δίκτυο φίλων):

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

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

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

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

Μικρές κόσμο

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

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

Η θεωρία των «έξι χειραψίες» για πρώτη φορά πειραματικά από Stanley Milgram και οι συνάδελφοί του στη δεκαετία του 1960. Χωρίς να έχουν οποιοδήποτε σύνολο δεδομένων κοινωνικών δικτύων, και με προϋπολογισμό $ 680 αποφάσισε να δείτε μια δημοφιλής ιδέα. Για το σκοπό αυτό, ζήτησε από 296 τυχαία επιλεγμένα εμπνευστές προσπαθήσει να στείλει μια επιστολή προς τον χρηματιστή, ο οποίος ζούσε σε ένα προάστιο της Βοστώνης. Εμπνευστές δόθηκαν κάποιες προσωπικές πληροφορίες για τους σκοπούς (συμπεριλαμβανομένης της διεύθυνσης και επάγγελμα), και έπρεπε να στείλει ένα γράμμα στο πρόσωπο που ήξεραν με το όνομα, με τις ίδιες οδηγίες, έτσι ώστε να επιτευχθεί ο στόχος όσο το δυνατόν γρηγορότερα. Κάθε γράμμα έχει περάσει από τα χέρια ενός αριθμού φίλων και σχημάτισε μια αλυσίδα κλείνει για χρηματιστές έξω της Βοστώνης.

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

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