Γράφος: Διαφορά μεταξύ των αναθεωρήσεων

Στην πιο κοινή έννοια του όρου,<ref>Δες για παράδειγμα, Iyanaga and Kawada, '''69 J''', p. 234 or Biggs, p. 4.</ref> ένας γράφος είναι ένα διατεταγμένο ζεύγος ''G ''&nbsp;= &nbsp;(''V'', &nbsp;''E'') αποτελούμενο από ένα σύνολο ''V'' των κορυφών ή κόμβων μαζί με ''E'' σύνολο από ακμές ή γραμμές, οι οποίες είναι υποσύνολα δύο στοιχείων ''V'' (δηλαδή, μια ακμή σχετίζεται με δύο κορυφές και η σχέση απεικονίζεται ως μη ταξινομημένο ζεύγος των κορυφών σε σχέση με τη συγκεκριμένη ακμή). Για να αποφευχθούν οι αμφισημίες, αυτός ο τύπος γραφήματος μπορεί να περιγραφεί με ακρίβεια ως μη-κατευθυνόμενο και απλό.

Άλλες έννοιες του γραφήματος προέρχονται από διαφορετικές αντιλήψεις για το σύνολο των ακμών του. Σε μια πιο γενικευμένη έννοια,<ref>Δες για παράδειγμα, Graham et al., p. 5.</ref> ''E'' είναι ένα σύνολο το οποίο σχετίζεται με τη σχέση της συχνότητας με την οποία συνδέονται δύο κορυφές με κάθε ακμή. Σε μια άλλη γενικευμένη έννοια, ''E'' είναι ένα πολυσύνολο απο μη ταξινομημένα ζεύγη κορυφών (όχι κατ 'ανάγκη διαφορετικά μεταξύ τους). Πολλοί συγγραφείς ονομάζουν αυτό το είδος αντικειμένων,ένα πολύγραφο ή ψευδογράφημα.

''V'' και ''Ε'' συνήθως λαμβάνονται υπόψην για ένα πεπερασμένο σύνολο, και πολλά από τα γνωστά αποτελέσματα δεν είναι αληθινά (ή είναι αρκετά διαφορετικά) για άπειρα γραφήματα, επειδή πολλά από τα επιχειρήματα αποτυγχάνουν σε άπειρες καταστάσεις. Η σειρά ενός γραφήματος είναι <math>| V |</math> (ο αριθμός των κορυφών). Το μέγεθος ενός γραφήματος είναι <math>| Ε E|</math>, ο αριθμός των ακμών. Ο βαθμός ενός κόμβου είναι ο αριθμός των ακμών που συνδέονται με αυτόν, όπου μια ακμή η οποία συνδέεται με την κορυφή και στα δύο άκρα (ένας βρόχος) συνυπολογίζεται δύο φορές.

Για μια ακμή {''u'', &nbsp;''v''}, οι θεωρητικοί των γραφημάτων συνήθως χρησιμοποιούν την μικρότερη σημειογραφία ''uv''.

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

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

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

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

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

Μια παραλλαγή αυτού του ορισμού είναι το προσανατολισμένο γράφημα, στο οποίο δεν μπορούν να υπάρχουν παραπάνω από ένα από τα (''x'', &nbsp;''y'') και (''y'', &nbsp;''x'') τα οποία μπορούν να είναι τόξα.

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

Ο όρος "πολύγραφος» είναι γενικά αποδεκτό ότι εννοεί ότι επιτρέπονται πολλαπλές ακμές (και μερικές φορές βρόχοι). Σε περίπτωση που τα γραφήματα ορίζονται έτσι ώστε να επιτρέπουν loops και πολλαπλές ακμές, ένας πολύγραφος ορίζεται συχνά για να σημαίνει ένα γράφημα χωρίς βρόχους,<ref>Για παράδειγμα, δες Balakrishnan, p. 1, Gross (2003), p. 4, and Zwillinger, p. 220.</ref> ωστόσο, όπου τα γραφήματα ορίζονται έτσι ώστε να μην επιτρέπονται loops και πολλαπλές ακμές,<ref>Για παράδειγμα, δες Bollobás, p. 7 and Diestel, p. 25.</ref> ο όρος ορίζεται συχνά για να σημαίνει ένα «γράφημα», το οποίο μπορεί να έχει και πολλές ακμές και βρόχους, αν και πολλοί χρησιμοποιούν τον όρο "pseudograph" για αυτήν την έννοια.

Ένα πεπερασμένο γράφημα είναι ένα γράφημα ''G ''&nbsp;= &nbsp;(''V'', &nbsp;''E'') έτσι ώστε ''V'' και ''Ε'' να είναι πεπερασμένα σύνολα. Ένα άπειρο γράφημα είναι ένα γράφημα με ένα άπειρο σύνολο κορυφών ή ακμών ή και τα δύο.

* Σε ένα γραμμικό γράφημα ή γράφημα με μονοπάτι μήκους n, οι κορυφές μπορούν να απαριθμούνται κατά σειρά, v0''v''₀, v1''v''₁, ..., vn,''v''_n έτσι ώστε οι ακμές να είναι VI-1vi''v''_i&minus;1''v''_i για κάθε ''i'' = 1, 2, ..., ''n'' . Αν ένα γραμμικό γράφημα εμφανίζεται ως υπογράφημα ενός άλλου γραφήματος, αυτό είναι ένα μονοπάτι στο γράφημα.

* Σε ένα κυκλικό γράφημα μήκους ''n ≥ 3'', οι κορυφές μπορούν να ανομαστούν v1''v''₁, ..., vn''v''_n έτσι ώστε οι ακμές να είναι VI-1vi''v''_i&minus;1''v''_''i'' για κάθε ''i'' = 2,..., ''n'' εκτόςκαθώς απόκαι vnv1''v''_n''v''₁. Τα κυκλικά γραφήματα μπορούν να χαρακτηριστούν ως συνδεδεμένα 2-τακτικά γραφήματα. Εάν ένα κυκλίκό γράφημα εμφανίζεται ως υπογράφημα ενός άλλου γραφήματος τότε αυτό είναι ένας κύκλος ή κύκλωμα σε αυτό το γράφημα.