ART

 

.

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

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

Οι κορυφές καλούνται επίσης κόμβοι ή σημεία, και οι ακμές ονομάζονται επίσης γραμμές. Τα γραφήματα είναι το βασικό θέμα μελέτης από τη θεωρία γραφημάτων. Η λέξη «γράφημα» χρησιμοποιήθηκε για πρώτη φορά με αυτή την έννοια από τον James Joseph Sylvester το 1878.

Ορισμοί

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


Γράφημα

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

Άλλες έννοιες του γραφήματος προέρχονται από διαφορετικές αντιλήψεις για το σύνολο των ακμών του. Σε μια πιο γενικευμένη έννοια,[2] E είναι ένα σύνολο το οποίο σχετίζεται με τη σχέση της συχνότητας με την οποία συνδέονται δύο κορυφές με κάθε ακμή. Σε μια άλλη γενικευμένη έννοια, E είναι ένα πολυσύνολο από μη ταξινομημένα ζεύγη κορυφών (όχι κατ 'ανάγκη διαφορετικά μεταξύ τους). Πολλοί συγγραφείς ονομάζουν αυτό το είδος αντικειμένων πολύγραφο ή ψευδογράφημα.

Οι κορυφές που ανήκουν σε μια ακμή ονομάζονται τελικά σημεία ή τελικές κορυφές της ακμής. Μια κορυφή μπορεί να υπάρχει σε ένα γράφημα και να μην ανήκει σε ακμή. V και Ε συνήθως λαμβάνονται υπόψιν για ένα πεπερασμένο σύνολο, και πολλά από τα γνωστά αποτελέσματα δεν είναι αληθινά (ή είναι αρκετά διαφορετικά) για άπειρα γραφήματα, επειδή πολλά από τα επιχειρήματα αποτυγχάνουν σε άπειρες καταστάσεις. Η σειρά ενός γραφήματος είναι |V| (ο αριθμός των κορυφών). Το μέγεθος ενός γραφήματος είναι |E|, ο αριθμός των ακμών. Ο βαθμός ενός κόμβου είναι ο αριθμός των ακμών που συνδέονται με αυτόν, όπου μια ακμή η οποία συνδέεται με την κορυφή και στα δύο άκρα (ένας βρόχος) συνυπολογίζεται δύο φορές. Για μια ακμή {u, v}, οι θεωρητικοί των γραφημάτων συνήθως χρησιμοποιούν την μικρότερη σημειογραφία uv.


Σχέση γειτνίασης

Οι ακμές Ε ενός μη-κατευθυνόμενου γραφήματος G περικλείουν μια συμμετρική δυαδική σχέση ~ με την V η οποία ονομάζεται σχέση γειτνίασης του G. Συγκεκριμένα, για κάθε ακμή {u, v}, οι κορυφές u και v λέγεται ότι είναι γειτονικές η μία στην άλλη, κάτι το οποίο συμβολίζεται ως u ~ v.


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

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

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


Μονοπάτια και είδη

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

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


Τύποι γραφημάτων
Διάκριση όσον αφορά τον κύριο ορισμό

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


Μη κατευθυνόμενο γράφημα

Ένα μη-κατευθυνόμενο γράφημα είναι εκείνο στο οποίο οι ακμές δεν έχουν προσανατολισμό. Η ακμή (α, β) είναι ταυτόσημη με την άκρη (β, α), δηλαδή, δεν υπάρχουν διατεταγμένα ζεύγη, αλλά σύνολα {u, v} (ή 2-multisets) των κορυφών.


Ένα κατευθυνόμενο γράφημα

Κύριο λήμμα: Κατευθυνόμενο Γράφημα

Ένα κατευθυνόμενο γράφημα ή διγράφημα είναι ένα διατεταγμένο ζεύγος D = (V, A) όπου V, είναι ένα σύνολο του οποίου τα στοιχεία λέγονται κορυφές ή κόμβοι και Α, είναι μια σειρά από διατεταγμένα ζεύγη κορυφών, τα οποία ονομάζονται τόξα, διατεταγμένες ακμές ή βέλη. Ένα τόξο a = (x, y) θεωρείται ότι κατευθύνεται από το x στο y; y ονομάζεται η αρχή και x to τέλος του τόξου; y λέγεται ότι είναι άμεσος διάδοχος του x, και το x λέγεται ότι είναι ο άμεσος προκάτοχός του y. Αν ένα μονοπάτι οδηγεί από το x στο y, τότε το y λέγεται ότι είναι διάδοχος του x και προσβάσιμο από το x, και το x λέγεται ότι είναι ο προκάτοχος του y. Το τόξο (y, x) ονομάζεται το τόξο (x, y) ανεστραμμένο.

Ένας κατευθυνόμενο γράφημα D λέγεται συμμετρικός αν για κάθε τόξο στο D, το αντίστοιχο αντεστραμμένο τόξο ανήκει και αυτό στο D. Ένα συμμετρικό χωρίς επαναλήψεις κατευθυνόμενο γράφημα D = (V, A) είναι ισοδύναμο με ένα απλό μη-κατευθυνόμενο γράφημα G = (V, E) , όπου τα ζευγάρια του αντιστρόφου τόξου στο Α αντιστοιχούν 1-προς-1 με τις ακμές στο E; έτσι ο αριθμός |E| = |A|/2, ή το μισό του αριθμού των τόξων στο D. Μια παραλλαγή αυτού του ορισμού είναι το προσανατολισμένο γράφημα, στο οποίο δεν μπορούν να υπάρχουν παραπάνω από ένα από τα (x, y) και (y, x) τα οποία μπορούν να είναι τόξα.


Μικτό γράφημα

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


Πολύγραφος

Ένας βρόχος είναι μια ακμή (κατευθυνόμενη ή μη), η οποία αρχίζει και τελειώνει στην ίδια κορυφή. Αυτό μπορεί να επιτρέπεται ή να μην επιτρέπεται ανάλογα με την εφαρμογή. Στο πλαίσιο αυτό, μια ακμή με δύο διαφορετικές άκρες ονομάζεται μια σύνδεση. Ο όρος "πολύγραφος» είναι γενικά αποδεκτό ότι εννοεί ότι επιτρέπονται πολλαπλές ακμές (και μερικές φορές βρόχοι). Σε περίπτωση που τα γραφήματα ορίζονται έτσι ώστε να επιτρέπουν loops και πολλαπλές ακμές, ένας πολύγραφος ορίζεται συχνά για να σημαίνει ένα γράφημα χωρίς βρόχους,[3] ωστόσο, όπου τα γραφήματα ορίζονται έτσι ώστε να μην επιτρέπονται loops και πολλαπλές ακμές,[4] ο όρος ορίζεται συχνά για να σημαίνει ένα «γράφημα», το οποίο μπορεί να έχει και πολλές ακμές και βρόχους, αν και πολλοί χρησιμοποιούν τον όρο "pseudograph" για αυτήν την έννοια.


Απλό γράφημα

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


Σταθμισμένο γράφημα

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


Half-edges, loose edges

Σε εξαιρετικές περιπτώσεις είναι απαραίτητο να υπάρχουν ακμές με μόνο το ένα άκρο, οι οποίες ονομάζονται half-edges, ή καθόλου άκρα (loose edges).
Σημαντικές κατηγορίες γραφημάτων


Τυπικό γράφημα

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


Πλήρες γράφημα

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

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


Κλάσεις γραφημάτων από πλευράς συνδεσιμότητας

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

Ένα γράφημα λέγεται k-vertex-connected ή k-edge-connected αν δεν υπάρχει σύνολο από k-1 κορυφές (αντίστοιχα, ακμές) που όταν αφαιρεθούν να αποσυνδέεται το γράφημα. Ένα k-vertex-connected γράφημα καλείται συχνά απλά ως k-connected. Ένα κατευθυνόμενο γράφημα λέγεται ασθενώς συνδεδεμένο εάν αντικαθιστώντας όλες τις κατευθυνόμενες ακμές του με μη-κατευθυνόμενες ακμές παράγεται ένα συνδεδεμένο (μη-κατευθυνόμενο) γράφημα. Είναι άρρηκτα συνδεδεμένο ή ισχυρό αν περιέχει ένα κατευθυνόμενο μονοπάτι από τον u στον v και ένα κατευθυνόμενο μονοπάτι από τον v με u για κάθε ζεύγος κορυφών u, v.
Ιδιότητες των γραφημάτων

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

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

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


Σημαντικά γραφήματα

Βασικά παραδείγματα είναι:

Μερικά πιο προχωρημένα είδη γραφημάτων είναι:

Γενικεύσεις

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

Ένα μη-κατευθυνόμενο γράφημα μπορεί να θεωρηθεί ως ένα simplicial complex το οποίο αποτελείται από 1-simplices (τις ακμές) και 0-simplices (τις κορυφές). Ως εκ τούτου, τα complexes είναι γενικεύσεις των γραφημάτων, δεδομένου ότι αφήνουν περιθώρια για simplices μεγαλύτερων διαστάσεων.

Κάθε γράφημα δημιουργεί ένα matroid.

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

Στην υπολογιστική βιολογία,η ανάλυση των power graphs παρουσιάζει τα power graphs ως μια εναλλακτική αναπαράσταση των τυχαίων γραφημάτων.

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

Δες για παράδειγμα, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
Δες για παράδειγμα, Graham et al., p. 5.
Για παράδειγμα, δες Balakrishnan, p. 1, Gross (2003), p. 4, and Zwillinger, p. 220.

Για παράδειγμα, δες Bollobás, p. 7 and Diestel, p. 25.

Δείτε επίσης

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

Γράφος Γυρίνος

Γράφος με ετικέτες

Γράφος του Πάππου

Γράφος χαρταετού Krackhardt

Γράφος Barbell

Γράφος Brinkmann

Γράφος Cameron

Γράφος Chvatal

Γράφος Coxeter

Γράφος Dyck

Γράφος Errera

Γράφος Foster

Γράφος Franklin

Γράφος Golomb

Γράφος Gosset

Γράφος Grötzsch

Γράφος Hall–Janko

Γράφος Harries

Γράφος Heawood

Γράφος Herschel

Γράφος Horton

Γράφος Kittell

Γράφος Livingstone

Γράφος Markström

Γράφος McGee

Γράφος Meredith

Γράφος Nauru

Γράφος Perkel

Γράφος Petersen *

Γράφος Poussin

Γράφος Robertson

Γράφος Thomsen *

Γράφος Tietze

Γράφος Wagner

Γράφος Wells

Γράφος Wiener–Araya

Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Graph (mathematics) της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).

Εγκυκλοπαίδεια Μαθηματικών

Κόσμος

Αλφαβητικός κατάλογος

Hellenica World - Scientific Library

Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License