Accueil du site > MOCA > Définitions sur les graphes
Définitions sur les graphes

Graphes non-orientés

Définition d’un graphe non-orienté

Un graphe non-orienté G est défini par le doublet où :

  • X est l’ensemble des sommes du graphe
  • U est l’ensemble des arêtes

PNG - 9.7 ko
Graphe non-orienté

X = \left\lbrace1, 2, 3, 4, 5\right\rbrace
U = \left\lbrace u_{1}, u_{2}, u_{3}, u_{4}, u_{5}, u_{6}, u_{7}, u_{8}, u_{9}\right\rbrace

Définition d’une chaine

Une chaîne est une séquence d’arêtes consécutives.

Voir la figure Graphe non-orienté

P_{8} = \left\lbrace 1, 2, 3\right\rbrace
P_{8} = \left\lbrace u_{1}, u_{3}\right\rbrace

Définition d’un cycle

Un cycle est une chaîne fermée.

Voir la figure Graphe non-orienté

P_{9} = \left\lbrace1, 2, 3, 5, 1\right\rbrace
P_{9} = \left\lbrace u_{1}, u_{3}, u_{6}, u_{5}\right\rbrace

Définition d’un graphe complet

Un graphe est dit complet si chaque sommet possède une [1] arête vers tout autre sommet y compris lui-même.

PNG - 6.6 ko
Graphe complet

N sommets \Rightarrow \frac{N*(N + 1)}{2} arêtes

Démonstration de la formule ci-dessus :

S = N + (N + 1) + ... + 1
\underline{S = 1 + 2 + ... + (N-1) + N}
2S = (N+1) + ... + (N+1)\qquad \leftarrow N fois
2S = N*(N+1)
S = \frac{N*(N+1)}{2}

  • Sommet 1 : 4 arêtes
  • Sommet 2 : 3 arêtes
  • Sommet 3 : 2 arêtes
  • Sommet 4 : 1 arête

De façon plus générale, on peut dire :

  • Sommet 1 : N arêtes
  • Sommet 2 : N-1 arêtes
  • Sommet ... : ... arêtes
  • Sommet N : 1 arête

Définition d’un graphe simple

Un graphe est dit simple si [2] il ne comporte pas de boucle et s’il n’y à pas plus d’une arête entre deux sommets quelconques.

PNG - 4.6 ko
Graphe simple
pages : << 1 2 3 4 5 6 7 8 >>

[1] et une seule
[2] et seulement si

Poster un message