C comme (graphe) complet
Ces billets visent à définir le plus clairement et le plus précisément possible des termes clés en analyse de réseau. Ils s’adressent à un public débutant et évitent autant que possible toute formalisation mathématique (pour cette dernière, voir les synthèses fmr sur Hal-Shs).
Un graphe est dit complet (complete graph) quand l’ensemble des liens possibles entre sommets sont présents. Si un graphe complet comprend n sommets, il est généralement noté Kn.
Que le graphe soit planaire (aucun lien ne peut en croiser un autre), biparti (liens entre deux ensembles distincts de sommets) ou simple (orienté ou non), lorsque le graphe est complet, la densité (nombre de liens présents divisé par le nombre de liens possibles) est égale à 1. Dans un graphe complet non biparti et non planaire, la distance, mesurée en nombre de liens, entre toute paire de sommets est également égale à 1. Dans ces graphes (non bipartis et non planaires), le degré des sommets est égal à n – 1.
Dans cette figure, le graphe de gauche est un graphe non planaire complet ; le graphe de droite un graphe planaire complet. Il n’est pas possible dans le graphe planaire d’ajouter un lien entre a et d sans provoquer un croisement entre les liens. Si la distance entre tous les sommets est de 1 à gauche, elle atteint 2 entre a et d dans le graphe planaire complet représenté ici. Dans le graphe de gauche comprenant 5 sommets, tous ont un degré égal à 4 (5 – 1).
Cette définition a servi de base en analyse de réseau pour la recherche des cliques, celles-ci sont en effet des sous graphes maximaux complets.
Billets liés : C comme clique/cluster/communautés, P comme (graphe) planaire.
OpenEdition vous propose de citer ce billet de la manière suivante :
Laurent Beauguitte (19 mars 2013). C comme (graphe) complet. groupe fmr (flux, matrices, réseaux). Consulté le 2 décembre 2024 à l’adresse https://doi.org/10.58079/p81v
