Graphe non orienté

Exemple de graphe non orienté à 5 sommets.

En théorie des graphes, un graphe non orienté G = ( V , E ) {\displaystyle G=(V,E)} est un couple formé de V {\displaystyle V} un ensemble de sommets et E {\displaystyle E} un ensemble d'arêtes, chaque arête étant une paire de sommets.

Cette définition ne s'applique qu'aux graphes simples et n'est pas valable pour les multigraphes.

Définitions

  • x 1 x 2 , x 2 x 3 , ⋯ , x n − 1 , x n {\displaystyle x_{1}x_{2},x_{2}x_{3},\cdots ,x_{n-1},x_{n}} est une chaîne si et seulement si ∀ p ∈ { 1 , 2 , ⋯ , n − 1 } , { x p , x p + 1 } {\displaystyle \forall p\in \{1,2,\cdots ,n-1\},\{x_{p},x_{p+1}\}} est une arête.
  • la chaîne x 1 x 2 , x 2 x 3 , ⋯ , x n − 1 , x n {\displaystyle x_{1}x_{2},x_{2}x_{3},\cdots ,x_{n-1},x_{n}} est un cycle si et seulement si { x n , x 1 } {\displaystyle \{x_{n},x_{1}\}} est une arête.

Voir aussi

Liens internes

Liens externes

Sur les autres projets Wikimedia :

  • Graphe non orienté, sur Wikimedia Commons
  • graphe non orienté, sur le Wiktionnaire
  • Graphe non orienté sur le site Euler, Académie de Versailles
  • icône décorative Portail de l'informatique théorique