Graphe série-parallèle

Dans ce contexte, le terme graphe signifie multigraphe. Il existe plusieurs façons équivalentes de définir des graphes série-parallèle.

La définition suivante suit essentiellement celle utilisée par David Eppstein^[1].

• Un graphe à deux sommets terminaux (TTG) est un graphe avec deux sommets distincts s et t appelés respectivement source et puits.
• La composition parallèle de deux TTG X et Y est le TTG Z formé à partir de l'union disjointe des graphes X et Y en fusionnant les sources de X et Y pour créer la source de Z et en fusionnant les puits de X et Y pour créer le puits de Z.
• La composition en série de deux TTG X et Y est le TTG Z créé à partir de l'union disjointe des graphes X et Y en fusionnant le puits de X avec la source de Y. La source de X devient la source de Z et le puits de Y devient le puits de Z .

Définition 1. Un graphe série-parallèle (SP-graphe) est un graphe qui peut être construit par une suite de compositions en séries et parallèles à partir d'un ensemble de copies d'un graphe à deux sommet reliés par une arête.

De la même manière, on peut définir des graphes orientés série-parallèle, construits à partir de copies de graphes à un seul arc, avec des arcs dirigés de la source vers le puits.

Courcelle et Engelfriet^[2] donnent la définition sous forme de grammaire de graphes :

S= (S//S)∪(S•S)∪{e}.

La définition suivante décrit la même classe de graphes^[3] :

Définition 2. Un graphe est un SP-graphe, s'il peut être transformé en K₂, le graphe complet à 2 sommets, par une séquence d'opérations suivantes :

• remplacement d'une paire d'arêtes parallèles par une seule arête qui relie leurs extrémités communes ;
• remplacement d'une paire d'arêtes incidentes à un sommet de degré 2 autre que s ou t par une seule arête.

La même définition, formulée de façon constructive, s'énonce comme suit^[4] : on part du graphe à deux sommets reliés par une arête, et on itère les opérations suivantes :

• une arête (x,y) est remplacée par deux arêtes (x,z) et (z,y), où z est un nouveau sommet (opération de sérialisation) ;
• une arête (x,y) est dupliquée^[5] (opération de parallélisation).

Tout graphe série-parallèle a une largeur arborescente au plus 2 et une largeur de branche au plus 2^[6]. En effet, un graphe a une largeur arborescente au plus 2 si et seulement s'il a une largeur de branche au plus 2, si et seulement si chaque composante biconnexe est un graphe série-parallèle^[7],[8]. Les graphes série-parallèle maximaux, graphes auxquels aucune arête supplémentaire ne peut être ajoutée sans détruire leur structure série-parallèle, sont exactement les 2-arbres.

Les graphes série-parallèle 2-connexes sont caractérisés par la propriété qu'aucun sous-graphe n'est homéomorphe à K₄^[6]

Les graphes série-parallèle peuvent également être caractérisés par leurs décompositions auriculaires (en)^[1].

Les SP-graphes peuvent être reconnus en temps linéaire^[9] et leur décomposition série-parallèle peut également être construite en temps linéaire.

En plus d'être un modèle de certains types de réseaux électriques, ces graphes sont intéressants en théorie de la complexité de calcul, car un certain nombre de problèmes usuels sur les graphes se résolvent en temps linéaire pour les SP-graphes^[10]  ; ces problèmes comprennent la recherche d'un couplage maximum, d'un ensemble indépendant maximal, d'un ensemble dominant minimal et la complétion hamiltonienne (en). Certains de ces problèmes sont NP-complets pour les graphes généraux. La solution tire profit du fait que si la réponse à l'un de ces problèmes est connue pour deux SP-graphes, alors on peut trouver rapidement la réponse pour leurs compositions en série et parallèle.