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

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

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

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