Worldlex Wiki En mathématiques , et plus précisément en théorie des graphes , un multigraphe est un graphe qui peut avoir plusieurs arêtes (également appelées arêtes parallèles ), c'est-à-dire des arêtes qui ont les mêmes extrémités . Ainsi, deux sommets peuvent être reliés par plusieurs arêtes.
Il existe deux notions distinctes d'arêtes multiples :
- Arêtes sans identité propre : L’identité d’une arête est définie uniquement par les deux nœuds qu’elle relie. Dans ce cas, l’expression « arêtes multiples » signifie qu’une même arête peut apparaître plusieurs fois entre ces deux nœuds.
- Arêtes à identité propre : les arêtes sont des entités primitives, tout comme les nœuds. Lorsque plusieurs arêtes relient deux nœuds, il s’agit d’arêtes distinctes.
Un multigraphe est différent d'un hypergraphe , qui est un graphe dans lequel une arête peut connecter un nombre quelconque de nœuds, et non seulement deux.
Pour certains auteurs, les termes pseudographe et multigraphe sont synonymes. Pour d'autres, un pseudographe est un multigraphe pouvant contenir des boucles .
paire ordonnée G := ( V , E ) avec- V un ensemble de sommets ou de nœuds ,
- E un multiensemble de paires non ordonnées de sommets, appelées arêtes ou lignes .
Multigraphe non orienté (arêtes ayant leur propre identité)
Un multigraphe G est un triplet ordonné G := ( V , E , r ) avec
- V un ensemble de sommets ou de nœuds ,
- E un ensemble d' arêtes ou de lignes ,
- r : E → { { x , y } : x , y ∈ V }, en attribuant à chaque arête une paire non ordonnée de nœuds d'extrémité.
Certains auteurs autorisent les multigraphes à avoir des boucles , c'est-à-dire une arête qui relie un sommet à lui-même, tandis que d'autres les appellent des pseudographes , réservant le terme multigraphe au cas sans boucles.
Multigraphe orienté (arêtes sans identité propre)
Un multidigraphe est un graphe orienté pouvant comporter plusieurs arcs, c'est-à-dire des arcs ayant les mêmes nœuds source et cible. Un multidigraphe G est une paire ordonnée G := ( V , A ) avec
- V un ensemble de sommets ou de nœuds ,
- Un multiensemble de paires ordonnées de sommets appelés arêtes orientées , arcs ou flèches .
Un multigraphe mixte G := ( V , E , A ) peut être défini de la même manière qu'un graphe mixte .
Multigraphe orienté (arêtes ayant leur propre identité)
Un multidigraphe ou carquois G est un quadruplet ordonné G := ( V , A , s , t ) avec
Cette notion pourrait servir à modéliser les correspondances aériennes possibles proposées par une compagnie aérienne. Dans ce cas, le multigraphe serait un graphe orienté dont les paires d'arêtes parallèles orientées relient les villes, indiquant ainsi la possibilité de se rendre dans les deux sens vers ces destinations .
En théorie des catégories, une petite catégorie peut être définie comme un multidigraphe (dont les arêtes possèdent leur propre identité) muni d'une loi de composition associative et d'une boucle particulière sur elle-même à chaque sommet, servant d'identité à gauche et à droite pour la composition. C'est pourquoi, en théorie des catégories, le terme « graphe » est généralement compris comme « multidigraphe », et le multidigraphe sous-jacent d'une catégorie est appelé son digraphe sous-jacent .
Étiquetage
Les multigraphes et les multidigraphes prennent également en charge la notion d' étiquetage de graphes , de manière similaire. Cependant, la terminologie employée dans ce cas n'est pas unifiée.
Les définitions des multigraphes étiquetés et des multidigraphes étiquetés sont similaires, et nous ne définissons ici que ces derniers.
Définition 1 : Un multidigraphe étiqueté est un graphe étiqueté avec des arcs étiquetés .
Formellement : Un multigraphe étiqueté G est un multigraphe dont les sommets et les arcs sont étiquetés . Formellement, c'est un 8-uplet où
Définition 2 : Un multidigraphe étiqueté est un graphe étiqueté avec plusieurs arcs étiquetés , c'est-à-dire des arcs avec les mêmes sommets d'extrémité et la même étiquette d'arc (notez que cette notion de graphe étiqueté est différente de la notion donnée par l'article étiquetage de graphes ).