Sommet (théorie des graphes)

En théorie des graphes, un sommet, aussi appelé nœud et plus rarement point, est l'unité fondamentale d'un graphe.

Pour les articles homonymes, voir Sommet et Nœud.

Ne doit pas être confondu avec Nœud (réseau).

Dans ce graphe, les sommets 4 et 5 sont voisins alors que les sommets 3 et 5 sont indépendants. Le degré du sommet 4 est égal à 3. Le sommet 6 est une feuille.

Deux sommets sont voisins s'ils sont reliés par une arête. Deux sommets sont indépendants s'ils ne sont pas voisins.

Types de sommet
Réseau de huit sommets (dont un isolé) et 10 arêtes.

Le degré d'un sommet v, noté 𝛿(v), est le nombre d'arêtes incidentes à ce sommet ou le nombre de voisins de v.

Un sommet isolé est un sommet dont le degré vaut zéro, c'est-à-dire un sommet qui n'est lié à aucun autre sommet. On appelle feuille un sommet dont le degré vaut un.

Dans un graphe orienté, on distingue le degré entrant, noté 𝛿−(v), du degré sortant, noté 𝛿 +(v). Un sommet source est un sommet dont le degré entrant vaut zéro tandis qu'un sommet flot est un sommet au degré sortant nul.

Liens internes
  • Portail de l'informatique théorique
  • Portail des mathématiques
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.