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

Externí odkazy

• Šablona:Commonscat