Représentation combinatoire dans laquelle des émetteurs, des liaisons ou des unités de transmission logiques sont des sommets et une arête (orientée ou non) entre deux sommets indique que leurs transmissions simultanées produisent une interférence mutuelle inacceptable selon les critères du modèle ; utilisée pour ramener l'allocation de spectre, la planification et le routage à des problèmes de théorie des graphes.

Principe

Éviter l'interférence dans le modèle revient à choisir des ensembles indépendants ou des colorations du graphe : tout ensemble de sommets actifs simultanément ne doit contenir aucune arête reliant deux d'entre eux selon la relation d'interférence du graphe.

Démonstration

Scénario illustratif : trois liaisons radio A, B et C produisent des interférences par paires formant un triangle. Reconnaissance : le graphe d'interférence est un 3-clique. Action : planifier les transmissions sur trois créneaux distincts ou attribuer trois canaux orthogonaux (trois couleurs). Conséquence : aucune paire de liaisons en interférence n'est active en même temps, respectant la contrainte du modèle.

Mauvaise application

Considérer le graphe d'interférence comme un modèle physique exact lorsque l'interférence s'additionne de façon continue (environnement SINR) — par exemple en supposant que l'absence d'arête garantit la coexistence sûre même si plusieurs interférences faibles cumulées dépassent le seuil du récepteur.

Conséquence

Lorsque le modèle s'applique, il permet d'utiliser des algorithmes combinatoires (coloration, approximation de l'ensemble indépendant maximal) pour obtenir des plannings et attributions de canaux pratiques ; en cas de mauvaise application, il peut produire des attributions qui ne satisfont pas les exigences physique du lien (SINR).

Inversion

Le modèle par graphe ne capture pas les interactions lorsque l'interférence est hautement cumulative, dépendante de la puissance, directionnelle ou variable dans le temps ; dans ces cas, un modèle SINR physique ou un traitement hybride graphe–SINR est requis.

Limite

Clairement inclus : scénarios de modèle de protocole où une arête signifie un conflit binaire empêchant la transmission simultanée. Cas limite : liaisons qui n'interfèrent qu'à certains niveaux de puissance ou avec des antennes directionnelles — l'existence d'une arête dépend des hypothèses de modélisation. Clairement exclu : modèles SINR continus qui calculent l'interférence agrégée comme une somme réelle plutôt que comme des arêtes binaires.

Tension sémantique

Simplicité et tractabilité algorithmique (graphes de conflit binaires) versus précision physique (modèles SINR et contrôle de puissance).

Synthèse

Le modèle de graphe transforme l'interférence en relation de compatibilité discrète pour permettre un raisonnement algorithmique ; son utilité dépend de l'adéquation de cette abstraction aux contraintes physiques essentielles du problème.