Arête (théorie des graphes)
partie d'un graphe / De Wikipedia, l'encyclopédie encyclopedia
Cher Wikiwand IA, Faisons court en répondant simplement à ces questions clés :
Pouvez-vous énumérer les principaux faits et statistiques sur Arête (théorie des graphes)?
Résumez cet article pour un enfant de 10 ans
Pour les articles homonymes, voir Arête.
En théorie des graphes, une arête, aussi appelée lien ou ligne, est une liaison entre deux sommets d'un graphe. Ces deux sommets sont les extrémités de l'arête. Une arête ayant une orientation (arête orientée) est plus souvent appelée arc ou flèche. En théorie des automates, les arcs sont appelés transitions.
Un graphe dont toutes les arêtes sont non orientées est lui-même dit non orienté, et un graphe dont toutes les arêtes sont orientées est dit orienté ; si seulement certaines arêtes sont orientées, le graphe est dit mixte.
L'ensemble des arêtes d'un graphe est couramment appelé E. Un ensemble d'arcs est parfois plutôt appelé A. L'ensemble des sommets étant appelé V :
- un graphe non orienté est un couple G = (V, E) ;
- un graphe orienté est un couple G = (V, A) ;
- un graphe mixte est un triplet G = (V, E, A).
Une arête est souvent désignée par les deux sommets u et v qu'elle relie, sous la forme d'une paire {u, v} (ou un singleton {u} dans le cas d'une boucle) si elle est non orientée, ou bien un couple (u, v) si elle est orientée. Ainsi l'arête {1, 2} relie les sommets 1 et 2, et l'arc (7, 9) mène du sommet 7 au sommet 9.