Graphe étoile

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

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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]