Hvězda (graf)

Hvězda^[1] 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 ${\displaystyle n}$ listech bývá značena buď jako bipartitní graf ${\displaystyle K_{1,n}}$, nebo je pro ni používána zvláštní značka ${\displaystyle 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 ${\displaystyle S_{n}}$ je úplný graf ${\displaystyle 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