Graphe non orienté

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

Exemple de graphe non orienté à 5 sommets.

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

Définitions

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

Voir aussi

Liens internes

• Graphe orienté
• Lexique de la théorie des graphes

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

• Portail de l'informatique théorique