Γράφος: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
TjBot (συζήτηση | συνεισφορές) μ r2.5.4) (Ρομπότ: Προσθήκη: ta:கோட்டுரு (கணிதம்) |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 1:
Στα μαθηματικά, ένα γράφημα είναι μια αφηρημένη αναπαράσταση ενός συνόλου αντικειμένων, όπου μερικά ζευγάρια αντικειμένων συνδέονται μεταξύ τους με δεσμούς. Τα διασυνδεδεμένα αντικείμενα αναπαρηστούνται με μαθηματικές αφαιρέσεις οι οποίες ονομάζονται κορυφές ενώ οι δεσμοί που συνδέουν τα ζευγάρια των κορυφών ονομάζονται ακμές. Συνήθως, ένας γράφος απεικονίζεται σε διαγραμματική μορφή ως ένα σύνολο κουκκίδων για τις κορυφές, ενωμένα μεταξύ τους με γραμμές ή καμπύλες για τις ακμές. Τα γραφήματα είναι ένα από τα αντικείμενα μελέτης στα διακριτά μαθηματικά.
Οι ακμές μπορούν να είναι κατευθυνόμενες (ασύμμετρες) ή μη-κατευθυνόμενες (συμμετρικές). Για παράδειγμα, εάν οι κορυφές αντιπροσωπεύουν τα άτομα σε ένα πάρτι, και υπάρχει ακμή μεταξύ δύο ανθρώπων, αν δίνουν τα χέρια, τότε αυτό είναι ένα μη-κατευθυνόμενο γράφημα, γιατί αν το πρόσωπο Α έδωσε τα χέρια με το πρόσωπο Β, τότε και το πρόσωπο Β έδωσε τα χέρια και με πρόσωπο Α. Από την άλλη πλευρά, εάν οι κορυφές αντιπροσωπεύουν τα άτομα σε ένα πάρτι και υπάρχει μια άκρη από το πρόσωπο Α στο πρόσωπο Β όταν το πρόσωπο Α γνωρίζει το πρόσωπο Β, τότε η γραφική αυτή παράσταση είναι κατευθυνόμενη γιατί το να γνωρίζεις κάποιον δεν είναι απαραίτητα μια συμμετρική σχέση (δηλαδή, ένα άτομο που γνωρίζει ένα άλλο προσώπο δεν συνεπάγεται κατ 'ανάγκη το αντίθετο, για παράδειγμα, πολλοί άνθρωποι μπορεί να γνωρίζουν μια διάσημη προσωπικότητα αλλά η διάσημη προσωπικότητα είναι απίθανο να γνωρίζει όλους τους οπαδούς της). Το τελευταίο αυτό είδος γραφήματος ονομάζεται κατευθυνόμενος γράφος και οι ακμές του ονμάζονται κατευθυνόμενες ακμές ή τόξα.
Οι κορυφές καλούνται επίσης κόμβοι ή σημεία, και οι ακμές ονομάζονται επίσης γραμμές. Τα γραφήματα είναι το βασικό θέμα μελέτης από τη θεωρία γραφημάτων. Η λέξη «γράφημα» χρησιμοποιήθηκε για πρώτη φορά με αυτή την έννοια από τον James Joseph Sylvester|J.J. Sylvester το 1878.
== Ορισμοί ==
Οι ορισμοί στην θεωρία γραφημάτων διαφέρουν. Οι παρακάτω είναι μερικοί από τους πιο βασικούς τρόπους ορισμού των γράφων και των σχετικών μαθηματικών δομών.
=== Γράφος ===
Στην πιο κοινή έννοια του όρου, ένας γράφος είναι ένα διατεταγμένο ζεύγος G = (V, E) αποτελούμενο από ένα σύνολο V των κορυφών ή κόμβων μαζί με E σύνολο από ακμές ή γραμμές, οι οποίες είναι υποσύνολα δύο στοιχείων V (δηλαδή, μια ακμή σχετίζεται με δύο κορυφές και η σχέση απεικονίζεται ως μη ταξινομημένο ζεύγος των κορυφών σε σχέση με τη συγκεκριμένη ακμή). Για να αποφευχθούν οι αμφισημίες, αυτός ο τύπος γραφήματος μπορεί να περιγραφεί με ακρίβεια ως μη-κατευθυνόμενο και απλό.
Άλλες έννοιες του γραφήματος προέρχονται από διαφορετικές αντιλήψεις για το σύνολο των ακμών του. Σε μια πιο γενικευμένη έννοια, E είναι ένα σύνολο το οποίο σχετίζεται με τη σχέση της συχνότητας με την οποία συνδέονται δύο κορυφές με κάθε ακμή. Σε μια άλλη γενικευμένη έννοια, E είναι ένα πολυσύνολο απο μη ταξινομημένα ζεύγη κορυφών (όχι κατ 'ανάγκη διαφορετικά μεταξύ τους). Πολλοί συγγραφείς ονομάζουν αυτό το είδος αντικειμένων,ένα πολύγραφο ή ψευδογράφημα.
Οι κορυφές που ανήκουν σε μια ακμή ονομάζονται τελικά σημεία ή τελικές κορυφές της ακμής. Μια κορυφή μπορεί να υπάρχει σε ένα γράφο και να μην ανήκει σε ακμή.
V και Ε συνήθως λαμβάνονται υπόψην για ένα πεπερασμένο σύνολο, και πολλά από τα γνωστά αποτελέσματα δεν είναι αληθινά (ή είναι αρκετά διαφορετικά) για άπειρα γραφήματα, επειδή πολλά από τα επιχειρήματα αποτυγχάνουν σε άπειρες καταστάσεις. Η σειρά ενός γραφήματος είναι | V | (ο αριθμός των κορυφών). Το μέγεθος ενός γραφήματος είναι | Ε |, ο αριθμός των ακμών. Ο βαθμός ενός κόμβου είναι ο αριθμός των ακμών που συνδέονται με αυτόν, όπου μια ακμή η οποία συνδέεται με την κορυφή και στα δύο άκρα (ένας βρόχος) συνυπολογίζεται δύο φορές.
Για μια ακμή {u, v}, οι θεωρητικοί των γραφημάτων συνήθως χρησιμοποιούν την μικρότερη σημειογραφία uv.
=== Σχέση γειτνίασης ===
Οι ακμές Ε ενός μη-κατευθυνόμενου γραφήματος G περικλείουν μια συμμετρική δυαδική σχέση ~ με την V η οποία ονομάζεται σχέση γειτνίασης του G. Συγκεκριμένα, για κάθε ακμή {u, v}, οι κορυφές u και v λέγεται ότι είναι γειτονικές η μία στην άλλη, κάτι το οποίο συμβολίζεται ως u ~ 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 και Α όπως ορίζεται ανωτέρω. Τα κατευθυνόμενα και μη κατευθυνόμενα γραφήματα είναι ειδικές περιπτώσεις.
==== Πολύγραφος ====
Ένας βρόχος είναι μια ακμή (κατευθυνόμενη ή μη), η οποία αρχίζει και τελειώνει στην ίδια κορυφή. Αυτό μπορεί να επιτρέπεται ή να μην επιτρέπεται ανάλογα με την εφαρμογή. Στο πλαίσιο αυτό, μια ακμή με δύο διαφορετικές άκρες ονομάζεται μια σύνδεση.
Ο όρος "πολύγραφος» είναι γενικά αποδεκτό ότι εννοεί ότι επιτρέπονται πολλαπλές ακμές (και μερικές φορές βρόχοι). Σε περίπτωση που τα γραφήματα ορίζονται έτσι ώστε να επιτρέπουν loops και πολλαπλές ακμές, ένας πολύγραφος ορίζεται συχνά για να σημαίνει ένα γράφημα χωρίς βρόχους, ωστόσο, όπου τα γραφήματα ορίζονται έτσι ώστε να μην επιτρέπονται loops και πολλαπλές ακμές, ο όρος ορίζεται συχνά για να σημαίνει ένα «γράφημα», το οποίο μπορεί να έχει και πολλές ακμές και βρόχους, αν και πολλοί χρησιμοποιούν τον όρο "pseudograph" για αυτήν την έννοια.
==== Απλό γράφημα ====
Σε αντίθεση με το πολύγραφο, ένα απλό γράφημα είναι ένα μη-κατευθυνόμενο γράφημα που δεν έχει βρόχους και έχει όχι περισσότερες από μία ακμή ανάμεσα σε δύο διαφορετικές κορυφές. Σε ένα απλό γράφημα οι ακμές του γραφήματος αποτελούν ένα σύνολο (και όχι multiset) και κάθε ακμή είναι ένα ξεχωριστό ζευγάρι κορυφών. Σε ένα απλό γράφημα με 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.
== Ιδιότητες των γραφημάτων ==
Οι δύο άκρες ενός γραφήματος ονομάζονται γειτονικές (μερικές φορές συμπίπτουν) αν έχουν κοινή κορυφή. Δύο βέλη ενός κατευθυνόμενου γράφου ονομάζονται διαδοχικά εάν η αρχή του πρώτου είναι το τέλος του δεύτερου. Ομοίως, δύο κορυφές ονομάζονται γειτονικές αν μοιράζονται ένα κοινό άκρο (διαδοχικές και αν είναι στην αρχή και στο τέλος ενός βέλους), στην οποία περίπτωση η κοινή ακμή λέγεται ότι συνδέει τις δύο κορυφές. Μια ακμή και μια κορυφή σε εκείνη την ακμή ονομάζονται περιστατικό.
Το γράφημα με μία μόνο κορυφή και καθόλου ακμές ονομάζεται τετριμμένο γράφημα. Ένα γράφημα με μόνο κορυφές και καθόλου ακμές είναι γνωστό ως ένα γράφημα χωρίς άκρα. Το γράφημα χωρίς κορυφές και χωρίς ακμές μερικές φορές ονομάζεται μηδενικό ή κενό γράφημα αλλά η ορολογία δεν είναι συνεπής και όλοι οι μαθηματικοί δεν αποδέχονται αυτή τη θεώρηση.
Σε ένα σταθμισμένο γράφημα ή διγράφο κάθε άκρο συνδέεται με κάποια αξία, που ονομάζεται ποικιλοτρόπως ως κόστος, βάρος, μήκος ή με κάποιο άλλο όρο ανάλογα με την εφαρμογή. Τέτοιου είδους γραφήματα προκύπτουν σε πολλά πλαίσια, για παράδειγμα στο πρόβλημα βέλτιστης δρομολόγησης.
== Σημαντικά γραφήματα ==
Βασικά παραδείγματα είναι:
* Σε ένα πλήρες γράφημα, κάθε ζεύγος κορυφών είναι ενωμένα μεταξύ τους με μια ακμή. Δηλαδή, το γράφημα περιέχει όλες τις πιθανές ακμές.
* Σε ένα διμερές γράφημα, το σύνολο των κορυφών μπορεί να χωριστεί σε δύο ομάδες, W και X, έτσι ώστε να μην υπάρχουν δύο κορυφές στο W που να είναι γειτονικές και να μην υπάρχουν δύο κορυφές στο Χ που να είναι γειτονικές. Εναλλακτικά, αυτό είναι ένα γράφημα με χρωματικό αριθμό 2.
* Σε ένα πλήρες διμερές γράφημα, το σύνολο των κορυφών είναι η ένωση των δύο διακριτών συνόλων, W και X, έτσι ώστε κάθε κορυφή στο σύνολο W να είναι γειτονική με κάθε κορυφή στο σύνολο X αλλά να μην υπάρχουν ακμές ανάμεσα στο W ή X.
* Σε ένα γραμμικό γράφημα ή γράφημα με μονοπάτι μήκους n, οι κορυφές μπορούν να απαριθμούνται κατά σειρά, v0, v1, ..., vn, έτσι ώστε οι ακμές να είναι VI-1vi για κάθε i = 1, 2, ..., n . Αν ένα γραμμικό γράφημα εμφανίζεται ως υπογράφημα ενός άλλου γραφήματος, αυτό είναι ένα μονοπάτι στο γράφημα.
* Σε ένα κυκλικό γράφημα μήκους n ≥ 3, οι κορυφές μπορούν να ανομαστούν v1, ..., vn έτσι ώστε οι ακμές να είναι VI-1vi για κάθε i = 2,..., n εκτός από vnv1. Τα κυκλικά γραφήματα μπορούν να χαρακτηριστούν ως συνδεδεμένα 2-τακτικά γραφήματα. Εάν ένα κυκλίκό γράφημα εμφανίζεται ως υπογράφημα ενός άλλου γραφήματος τότε αυτό είναι ένας κύκλος ή κύκλωμα σε αυτό το γράφημα.
* Ένα επίπεδο γράφημα είναι ένα γράφημα του οποίου οι κορυφές και οι ακμές μπορούν να εξαχθούν σε ένα επίπεδο τέτοιο, ώστε να μην υπάρχουν δύο ακμές οι οποίες να τέμνονται.
* Ένα δέντρο είναι ένα συνεκτικό γράφημα χωρίς κύκλους.
* Ένα δάσος είναι ένα γράφημα χωρίς κύκλους (δηλ. η ένωση από ένα ή περισσότερα δέντρα).
Μερικά ποιο προχωρημένα είδη γραφημάτων είναι:
* Το γράφημα Petersen και γενικεύσεις του
* Τέλεια γραφήματα
* Cographs
* Chordal graphs
* Άλλα γραφήματα με μεγάλες ομάδες αυτομορφισμού
== Γενικεύσεις ==
Σε ένα υπεργράφημα, μια ακμή μπορεί να συμμετάσχει σε περισσότερες από δύο κορυφές.
Ένα μη-κατευθυνόμενο γράφημα μπορεί να θεωρηθεί ως ένα simplicial complex το οποίο αποτελείται από 1-simplices (τις ακμές) και 0-simplices (τις κορυφές). Ως εκ τούτου, τα complexes είναι γενικεύσεις των γραφημάτων, δεδομένου ότι αφήνουν περιθώρια για simplices μεγαλύτερων διαστάσεων.
Κάθε γράφημα δημιουργεί ένα matroid.
Στη Θεωρεία μοντέλων, ένα γράφημα είναι μόνο μια δομή. Στην περίπτωση όμως αυτή, δεν υπάρχει περιορισμός στον αριθμό των ακμών: μπορεί να είναι οποιοδήποτε απόλυτος αριθμός, βλ. Συνεχές γράφημα.
Στην υπολογιστική βιολογία,η ανάλυση των power graphs παρουσιάζει τα power graphs ως μια εναλλακτική αναπαράσταση των τυχαίων γραφημάτων.
Σε γεωγραφικά πληροφοριακά συστήματα, τα γεωμετρικά δίκτυα είναι στενά διαμορφωμένα με τη βοήθεια γραφημάτων και δανείζονται πολλές έννοιες από την θεωρία γράφων για την εκτέλεση χωρικής ανάλυσης των οδικών δικτύων ή δικτύων κοινής ωφελείας.
==Δείτε επίσης==
* [[Θεωρία γράφων]]
[[Κατηγορία:Θεωρία γράφων]]
| |||