Hvězda (graf)

Hvězda se sedmi listy (tj. hvězda na osmi vrcholech)

Hvězdy $S_{3},S_{4},S_{5},S_{6}$.

Hvězda je v teorii grafů označení takových grafů, které mají jednoduchou podobu jediného centrálního vrcholu a na něj napojených listů. Jedná se tedy zároveň o strom a zároveň o úplný bipartitní graf. Hvězda o $n$ listech bývá značena buď jako bipartitní graf $K_{1,n}$, nebo je pro ni používána zvláštní značka $S_{n}$.

V rámci síťové topologie odpovídá hvězda hvězdicové topologii.

Vlastnosti

• Hvězda je stromem, tedy souvislým acyklickým grafem bez násobných hran. Kořenem hvězdy se obvykle automaticky rozumí její centrální uzel.
• Hvězda je úplným bipartitním grafem, kde je jedna množina vrcholů tvořena listy a druhá pouze centrálním vrcholem.
• Hranovým grafem hvězdy $S_{n}$ je úplný graf $K_{n}$.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Sterngraph na německé Wikipedii.

Externí odkazy

• Obrázky, zvuky či videa k tématu hvězda na Wikimedia Commons