Graphe étoile

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur les redirections Cet article concerne le graphe en étoile. Pour les autres significations de « étoile », voir Étoile (homonymie).

En mathématiques, et plus particulièrement en théorie des graphes, une étoile Sk est le graphe biparti complet K1,k.

Définitions[modifier | modifier le code]

Les graphes en étoile S3, S4, S5 et S6.

On peut aussi le voir comme un arbre avec un nœud et k feuilles, du moins lorsque k > 1. Enfin, on peut le définir comme un graphe connexe dont tous les sommets sauf un sont de degré 1.

Certains auteurs définissent toutefois Sk comme l'arbre à k sommets de diamètre maximal 2. Attention, avec cette définition, une étoile n'a que k − 1 feuilles.

Propriétés[modifier | modifier le code]

Le graphe étoile S3 est le graphe griffe.

Voir aussi[modifier | modifier le code]