ArithmétiqueObjet mathématique · Glossaire
Graphe étiqueté
Un graphe étiqueté est un graphe dans lequel les sommets, les arêtes, ou les deux, sont munis d'étiquettes (des noms, des numéros ou d'autres informations). Lorsque les sommets sont étiquetés par des entiers distincts de 1 à n, on parle de graphe étiqueté sur n sommets. Le nombre de graphes étiquetés simples non orientés, sans boucles ni arêtes multiples, sur n sommets est 2^(n(n-1)/2). L'étiquetage est crucial pour compter des graphes et les distinguer des graphes non étiquetés qui sont considérés à isomorphisme près.
Sommaire
Ce que vous allez apprendre
- Identifier ce que les étiquettes ajoutent aux sommets ou aux arêtes.
- Dénombrer les 64 graphes simples étiquetés sur quatre sommets.
- Distinguer graphe étiqueté, graphe non étiqueté et graphe pondéré.
- Reconnaître les hypothèses nécessaires à la formule de comptage.
En clair
Imaginez quatre points reliés par quelques traits. Si les points portent les numéros 1, 2, 3 et 4, chacun possède une identité : échanger deux numéros peut changer le graphe étiqueté, même lorsque le dessin conserve la même forme. Une étiquette peut aussi être un nom ou une information, et elle peut être attachée aux traits plutôt qu'aux points.
Définition
Un graphe étiqueté est un graphe auquel une fonction d'étiquetage associe une information à chaque sommet, à chaque arête, ou aux deux. Les étiquettes peuvent être des noms, des nombres ou d'autres données. Elles font partie de la description de l'objet : un isomorphisme qui respecte les étiquettes doit conserver ces informations.
Dans le cas classique d'un graphe étiqueté sur n sommets, le nombre n désigne le nombre de sommets, et ceux-ci reçoivent une fois chacun les entiers de 1 à n. Si le graphe est simple, non orienté et sans boucle, chaque paire de sommets distincts peut porter ou non une arête. Il existe alors n(n − 1)/2 paires, donc le nombre de graphes possibles sur cet ensemble fixé d'étiquettes vaut :
Cette formule compte séparément deux graphes qui ont la même forme mais dont les étiquettes occupent des sommets différents. Un comptage de graphes non étiquetés les regroupe au contraire lorsqu'ils sont isomorphes.
De quoi c'est fait
Le support comprend des sommets, ici l'ensemble V = {1, 2, 3, 4}, et des arêtes, qui relient certaines paires de sommets. Une fonction d'étiquetage attache les numéros aux sommets ; une autre pourrait attacher des données aux arêtes. L'ensemble E des arêtes dépend des sommets disponibles, tandis que l'identité d'une extrémité dépend de son étiquette.
Dans l'exemple conducteur, E = {{1, 2}, {1, 3}, {3, 4}}. Les traits rouges matérialisent ces trois arêtes ; les traits noirs discontinus montrent les trois autres paires possibles. La position des points, leur couleur et la forme du dessin facilitent la lecture, mais ne définissent pas le graphe. Les ensembles V et E, avec l'étiquetage, suffisent à le reconstruire et à calculer son nombre d'arêtes.
Un exemple, pas à pas
On fixe quatre sommets étiquetés 1, 2, 3 et 4. Le graphe est simple et non orienté : il n'admet ni boucle ni arêtes multiples. Dans le graphe choisi, les arêtes sont {1, 2}, {1, 3} et {3, 4}.
1. Le sommet 1 peut être associé à 2, 3 ou 4 ; cela donne trois paires.
2. Parmi les sommets restants, 2 peut être associé à 3 ou 4, puis il reste la paire {3, 4}. On obtient donc 3 + 2 + 1 = 6 paires distinctes.
3. Chaque paire offre deux choix indépendants : arête présente ou absente. Le nombre total de graphes étiquetés simples est donc 26 = 64.
Le graphe représenté correspond à l'un de ces 64 choix et possède exactement trois arêtes. Pour contrôler le calcul, on énumère les six paires {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4} et {3, 4}, puis on vérifie que chacune a bien deux états possibles.
En pratique
Pour décrire un réseau concret, les étiquettes donnent un nom stable aux sommets ou aux arêtes. On les conserve lorsque l'identité des éléments compte ; on préfère un graphe non étiqueté lorsque seule la forme des connexions importe.
En combinatoire, numéroter les sommets fixe les objets que l'on compte. Pour quatre sommets, on examine les six paires possibles et l'on code chaque graphe par les arêtes présentes, ce qui évite de confondre une nouvelle attribution des numéros avec le même objet.
Dans un algorithme, les étiquettes servent aussi à retrouver sans ambiguïté les extrémités d'une arête. Si les nombres portés par les arêtes représentent plutôt un coût ou une distance, on emploie un graphe pondéré et l'on précise la signification de ces valeurs.
À ne pas confondre
Graphe non étiqueté. Deux dessins qui ne diffèrent que par le nom de sommets correspondants représentent le même graphe non étiqueté s'ils sont isomorphes. Ils peuvent compter comme deux graphes étiquetés lorsque l'isomorphisme ne conserve pas les étiquettes.
Graphe pondéré. Une pondération attribue aux arêtes ou aux sommets des valeurs destinées à un calcul, comme une longueur ou un coût. Une étiquette peut n'être qu'un identifiant : le numéro 3 distingue alors un sommet sans mesurer quoi que ce soit.
Graphe coloré. Une coloration impose souvent des contraintes, par exemple des couleurs différentes sur deux sommets adjacents. Un étiquetage ne comporte pas cette exigence : sa validité dépend uniquement de la règle d'étiquetage annoncée.
Limites et pièges
Portée des étiquettes. Dire seulement « graphe étiqueté » ne précise pas si les étiquettes portent sur les sommets, les arêtes ou les deux. Il faut annoncer ce support et la règle qui autorise ou interdit les répétitions.
Portée de la formule. Le nombre 2n(n − 1)/2 suppose un ensemble fixé de n sommets distinctement étiquetés et des graphes simples non orientés. Avec des boucles, une orientation, des arêtes multiples ou un autre jeu d'étiquettes, le choix élémentaire change et cette formule ne s'applique plus.
Petites valeurs. Pour n = 0 comme pour n = 1, aucune paire de sommets distincts n'existe. L'exposant vaut 0 et la formule donne 20 = 1 : le seul graphe simple possible n'a aucune arête.
Dessin trompeur. Déplacer les sommets ou courber une arête ne change pas le graphe. Pour décider si deux représentations étiquetées coïncident, il faut comparer les étiquettes et les paires reliées, non leur apparence géométrique.
Pour aller plus loin
Le glossaire Graphe simple précise les restrictions qui rendent possible le comptage par paires de sommets.
L'entrée analyse combinatoire situe les raisonnements de dénombrement dont le choix indépendant des arêtes est un exemple.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres