Γράφος-μονοπάτι

Στην θεωρία γράφων, γράφος-μονοπάτι είναι ο γράφος  του οποίου οι κόμβοι μπορούν να παραταχθούν ως , ώστε το σύνολο των ακμών του είναι .

Ο γράφος-μονοπάτι με  κόμβους συμβολίζεται ως .

 Παραδείγματα 
 Για , .
 Για , .
 Για , .

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

 Δείτε επίσης 
 Μονοπάτι (θεωρία γράφων)
 Κύκλος (θεωρία γράφων)

 Παραπομπές 

Κατηγορία:Θεωρία γράφων