Graphe étoile

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

Cet article concerne le graphe en étoile. Pour les autres significations de « étoile », voir Étoile (homonymie).

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

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

Le graphe étoile S3 est le graphe griffe.

Voir aussi

  • Portail des mathématiques
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.