Αστεροειδής γράφος

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

Αστροειδής γράφος
Ο αστεροειδής γράφος $S_{7}$.
Κορυφές	$n+1$
Ακμές	$n$
Ακτίνα	1
Διάμετρος	2
Περιφέρεια	$\infty$
Χρωματικός αριθμός	2
Ιδιότητες	Δέντρο Διμερής
Συμβολισμός	$S_{n}$ ή $K_{1,n}$
Πίνακας γράφων και των παραμέτρων τους

Ο αστεροειδής γράφος ταυτίζεται με τον πλήρη διμερή γράφο $K_{1,n}$ και με ένα δέντρο όπου η ρίζα έχει $n-1$ παιδιά.

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

Αστροειδείς γράφοι $S_{n}$ για $n=3,4,5,6$

$S_{3}$

$S_{4}$

$S_{5}$

$S_{6}$

Ιδιότητες

• Ο $S_{n}$ έχει ακτίνα $1$ και διάμετρο $2$, καθώς ο κεντρικός κόμβος έχει εκκεντρότητα $1$ και όλοι οι άλλοι έχουν εκκεντρότητα $2$ (όταν $n>2$).

Αστεροειδής γράφος $S_{5}$. Αριστερά οι αποστάσεις με κόκκινο από την κεντρική κορυφή και δεξιά οι αποστάσεις από μία μη-κεντρική κορυφή.

• Ο χρωματικός αριθμός του $S_{n}$ είναι $2$ και το χρωματικό πολυώνυμο του είναι

$P(G,x)=x\cdot (x-1)^{n-1}$.

Χρωματισμός αστροειδούς γράφου με δύο χρώματα.

Δείτε επίσης

• Πλήρης διμερής γράφος
• Δέντρο (θεωρία γράφων)