Graphe étoile

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

Les graphes en étoile S₃, S₄, S₅ et S₆.

Définitions

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 S_k 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

Le graphe étoile S₃ est le graphe griffe.

Voir aussi

• Graphe roue
• Réseau en étoile

• Portail des mathématiques
• Portail de l'informatique théorique