Γράφος: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ →Σημαντικά γραφήματα: εσωτερικές συνδέσεις |
|||
Γραμμή 129:
Βασικά παραδείγματα είναι:
* Σε ένα πλήρες γράφημα, κάθε ζεύγος κορυφών είναι ενωμένα μεταξύ τους με μια ακμή. Δηλαδή, το γράφημα περιέχει όλες τις πιθανές ακμές.
* Σε ένα διμερές γράφημα, το σύνολο των κορυφών μπορεί να χωριστεί σε δύο ομάδες, W και X, έτσι ώστε να μην υπάρχουν δύο κορυφές στο W που να είναι γειτονικές και να μην υπάρχουν δύο κορυφές στο Χ που να είναι γειτονικές. Εναλλακτικά, αυτό είναι ένα γράφημα με [Χρωματισμός γραφήματος|χρωματικό αριθμό] 2.
* Σε ένα πλήρες διμερές γράφημα, το σύνολο των κορυφών είναι η ένωση των δύο διακριτών συνόλων, W και X, έτσι ώστε κάθε κορυφή στο σύνολο W να είναι γειτονική με κάθε κορυφή στο σύνολο X αλλά να μην υπάρχουν ακμές ανάμεσα στο W ή X.
* Σε ένα γραμμικό γράφημα ή γράφημα με μονοπάτι μήκους n, οι κορυφές μπορούν να απαριθμούνται κατά σειρά, ''v''<sub>0</sub>, ''v''<sub>1</sub>, ..., ''v''<sub>n</sub> έτσι ώστε οι ακμές να είναι ''v''<sub>i−1</sub>''v''<sub>i</sub> για κάθε ''i'' = 1, 2, ..., ''n'' . Αν ένα γραμμικό γράφημα εμφανίζεται ως υπογράφημα ενός άλλου γραφήματος, αυτό είναι ένα μονοπάτι στο γράφημα.
| |||