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

Γράφος-μονοπάτι
Κορυφές	$n$
Ακμές	$n-1$
Ακτίνα	$\lfloor n/2\rceil$
Διάμετρος	$n-1$
Αυτομορφισμοί	2
Χρωματικός αριθμός	2
Χρωματικός δείκτης	2
Ιδιότητες	Διμερής γράφος Δέντρο (θεωρία γράφων)
Συμβολισμός	$P_{n}$
Πίνακας γράφων και των παραμέτρων τους

Στην θεωρία γράφων, γράφος-μονοπάτι είναι ο γράφος $G=(V,E)$ του οποίου οι κόμβοι μπορούν να παραταχθούν ως $v_{1},\ldots ,v_{n}$, ώστε το σύνολο των ακμών του είναι $E=\{\{v_{1},v_{2}\},\{v_{2},v_{3}\},\ldots ,\{v_{n-1},v_{n}\}\}$.

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

Παραδείγματα

• Για $n=3$, $P_{3}=(\{v_{1},v_{2},v_{3}\},\{(v_{1},v_{2}),(v_{2},v_{3})\})$.

Ο γράφος $P_{3}$.

• Για $n=4$, $P_{4}=(\{v_{1},v_{2},v_{3},v_{4}\},\{(v_{1},v_{2}),(v_{2},v_{3}),(v_{3},v_{4})\})$.

Ο γράφος $P_{4}$.

• Για $n=5$, $P_{5}=(\{v_{1},v_{2},v_{3}\},\{(v_{1},v_{2}),(v_{2},v_{3}),(v_{3},v_{4}),(v_{4},v_{5})\})$.

Ο γράφος $P_{5}$.

Ιδιότητες

• Ο πίνακας γειτνίασης του $P_{n}$ έχει την εξής μορφή

$A={\begin{bmatrix}0&1&0&0&\ldots &0&0\\1&0&1&0&\ldots &0&0\\0&1&0&1&\ldots &0&0\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&0&0&\ldots &0&1\\0&0&0&0&\ldots &1&0\end{bmatrix}}$,

ή αναλυτικά

$A_{ij}={\begin{cases}1&{\text{αν }}i=j+1{\text{ ή }}i=j-1,\\0&{\text{διαφορετικά}}.\end{cases}}$.

• Ο χρωματικός αριθμός του $P_{n}$ είναι $2$, καθώς μπορούμε να χρωματίσουμε τους κόμβους εναλλάξ.

Η διάμετρος για το $P_{n}$ για $n$ ζυγός αριθμός.

• Η διάμετρος του $P_{n}$ είναι $n-1$, καθώς η απόσταση μεταξύ των κόμβων $v_{1}$ και $v_{n}$ είναι $n-1$.

Η διάμετρος για το $P_{n}$.

• Η ακτίνα του $P_{n}$ είναι $\lfloor n/2\rfloor$, καθώς όταν $n=2k$ τότε οι κόμβοι $v_{k}$ και $v_{k+1}$ έχουν εκκεντρότητα $\epsilon (v_{k})=\epsilon (v_{k+1})=k$ και όταν $n=2k+1$, ΄τότε ο κόμβος $v_{k}$ έχει $\epsilon (v_{k})=k$.

Δείτε επίσης

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