Γράφος

Ορισμοί

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

Γράφημα

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

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

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

Συνεκτικότητα και συνιστώσες

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

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

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

Διάκριση όσον αφορά τον κύριο ορισμό

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

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

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

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

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

Πολύγραφος

Ένας βρόχος είναι μια ακμή (κατευθυνόμενη ή μη), η οποία αρχίζει και τελειώνει στην ίδια κορυφή. Αυτό μπορεί να επιτρέπεται ή να μην επιτρέπεται ανάλογα με την εφαρμογή. Στο πλαίσιο αυτό, μια ακμή με δύο διαφορετικές άκρες ονομάζεται μια σύνδεση.
Ο όρος "πολύγραφος» είναι γενικά αποδεκτό ότι εννοεί ότι επιτρέπονται  πολλαπλές ακμές (και μερικές φορές βρόχοι). Σε περίπτωση που τα γραφήματα ορίζονται έτσι ώστε να επιτρέπουν loops και πολλαπλές ακμές, ένας πολύγραφος ορίζεται συχνά για να σημαίνει ένα γράφημα χωρίς βρόχους, ωστόσο, όπου τα γραφήματα ορίζονται έτσι ώστε να μην επιτρέπονται loops και πολλαπλές ακμές, ο όρος ορίζεται συχνά για να σημαίνει ένα «γράφημα», το οποίο μπορεί να έχει και πολλές ακμές και βρόχους, αν και πολλοί χρησιμοποιούν τον όρο "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 ως μια εναλλακτική αναπαράσταση των  τυχαίων γραφημάτων.
Σε γεωγραφικά πληροφοριακά συστήματα, τα γεωμετρικά δίκτυα είναι στενά διαμορφωμένα με τη βοήθεια γραφημάτων και  δανείζονται πολλές έννοιες από την θεωρία γράφων για την εκτέλεση χωρικής ανάλυσης των οδικών δικτύων ή δικτύων κοινής ωφελείας.