Les graphes complets
--------------------
En combinatoire, un
graphe est un ensemble de points (les
sommets) dont certains sont reliés entre eux par des lignes (les
arêtes). La forme géométrique des lignes n’a pas d’importance, seuls comptent les sommets qu’elles permettent de joindre (voir
les Graphes,
Bibliothèque Tangente 54, 2015).
Un graphe est dit complet lorsque chacun de ses sommets est relié à tous les autres. Le graphe complet à n sommets est noté Kn.
[/encadre]
Premières esquisses
-------------------
Le graphe complet à deux sommets, noté K2, ne présente aucune difficulté : il suffit de tracer un segment entre deux points. Le cas de K3 n’est pas plus difficile : on dessine simplement un triangle ; chacun choisira celui qui lui paraît le plus esthétique… Pour quatre sommets, la question des croisements commence à émerger. La représentation la plus habituelle est la suivante, qui fait apparaître un croisement.
En disposant les points autrement, ou en traçant des arêtes « moins rigides », on peut toutefois éviter les croisements. Le nombre minimum de croisements de K4 est donc, de fait, nul. On écrit : cr (K4) = 0.
Passons au cas du graphe complet à cinq sommets. Après quelques tentatives, il semble inévitable de croiser au moins une fois les arêtes… Mais en est-on certain ?
Il est possible de démontrer que cr (K5) = 1, c’est-à-dire que toute représentation de K5 dans le plan nécessite au moins un croisement. En fait, en utilisant astucieusement quelques résultats fondamentaux de théorie des graphes, on peut même aller plus loin. Plaçons-nous dans le cas général du graphe complet Kn. Chacun de ses sommets est relié aux n – 1 autres, et chaque arête relie deux sommets. Ce graphe compte donc 2n(n−1) arêtes.
Dessinons Kn avec son nombre minimum de croisements possible, et considérons chaque croisement comme un nouveau sommet. On obtient donc un nouveau graphe, noté Kn’, qui possède n + cr (Kn) sommets. Chaque croisement de notre graphe Kn originel ayant ajouté deux nouvelles arêtes exactement, le graphe Kn’ comporte, lui, précisément 2n(n−1)+2cr(Kn) arêtes.
le K5’ possède six sommets et douze arêtes (et aucun croisement).