Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Στην θεωρία γράφων, γράφος-μονοπάτι είναι ο γράφος
του οποίου οι κόμβοι μπορούν να παραταχθούν ως
, ώστε το σύνολο των ακμών του είναι
.[1][2]
Ο γράφος-μονοπάτι με
κόμβους συμβολίζεται ως
.
- Για
,
.
Ο γράφος
.
- Για
,
.
Ο γράφος
.
- Για
,
.
Ο γράφος
.
,
- ή αναλυτικά
.
- Ο χρωματικός αριθμός του
είναι
, καθώς μπορούμε να χρωματίσουμε τους κόμβους εναλλάξ.
Η διάμετρος για το
για
ζυγός αριθμός.
- Η διάμετρος του
είναι
, καθώς η απόσταση μεταξύ των κόμβων
και
είναι
.
Η διάμετρος για το
.
- Η ακτίνα του
είναι
, καθώς όταν
τότε οι κόμβοι
και
έχουν εκκεντρότητα
και όταν
, ΄τότε ο κόμβος
έχει
.