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

Στην θεωρία γράφων, γράφος-μονοπάτι είναι ο γράφος $G=(V,E)$ του οποίου οι κόμβοι μπορούν να παραταχθούν ως $v_1,\dots ,v_n$, ώστε το σύνολο των ακμών του είναι $E=\{\{v_1,v_2\},\{v_2,v_3\},\dots ,\{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)\})$.

Αρχείο:Path graph 5 with labels.svg

Ο γράφος $P_5$.

Ιδιότητες

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

$A=\left[\begin{array}{ccccccc}0& 1& 0& 0& \dots & 0& 0\\ 1& 0& 1& 0& \dots & 0& 0\\ 0& 1& 0& 1& \dots & 0& 0\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& 0& \dots & 0& 1\\ 0& 0& 0& 0& \dots & 1& 0\end{array}\right]$,

ή αναλυτικά

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

• Ο χρωματικός αριθμός του $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}$ έχουν εκκεντρότητα $ϵ(v_k)=ϵ(v_{k+1})=k$ και όταν $n=2k+1$, ΄τότε ο κόμβος $v_k$ έχει $ϵ(v_k)=k$.

Δείτε επίσης

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