Graphe série-parallèle
# Graphe série-parallèle

En théorie des graphes, les graphes série-parallèle sont des graphes avec deux sommets distingués, la source et le puits, et formés récursivement par deux opérations qui sont la composition en série et la composition parallèle. Ces graphes peuvent servir pour modéliser des circuits électriques en série et en parallèle .

## Définition et terminologie

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

### Une première définition

La définition suivante suit essentiellement celle utilisée par David Eppstein.

* 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 donnent la définition sous forme de grammaire de graphes :

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

### Une autre définition

La définition suivante décrit la même classe de graphes :

Définition 2. Un graphe est un SP-graphe, s'il peut être transformé en $K_2,$ 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 : 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 (opération de parallélisation).

## Propriétés

Tout graphe série-parallèle a une largeur arborescente au plus 2 et une largeur de branche au plus 2. 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^,.$ 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_4$

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

## Complexité algorithmique

Les SP-graphes peuvent être reconnus en temps linéaire 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 ; 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.

## Généralisations

Les graphes série-parallèle généralisés (GSP) sont une extension des SP-graphes avec la même complexité algorithmique pour les problèmes énumérés plus haut. La classe des GSP-graphes comprend les SP-graphes et les graphes planaires extérieurs.

Les GSP-graphes peuvent être définis à partir de la définition 2 augmentée d'une troisième opération qui est la suppression d'un sommet pendant (sommet de degré 1). De manière équivalente, la définition 1 peut être complétée avec l'opération de fusion suivante : la fusion à la source S = M (X, Y) de deux TTG X et Y est un TTG créé à partir de l'union disjointe des graphes X et Y en fusionnant la source de X avec la source de Y. Autrement dit, la source et le puits de X deviennent respectivement la source et le puits de S.

Un arbre SPQR est une structure arborescente qui peut être définie pour un graphe sommet-connexe arbitraire ; à chaque sommet est associé un graphe ou multigraphe. Il a des nœuds source S, qui sont analogues aux opérations de composition en série dans les graphes série-parallèle, des nœuds puits P, qui sont analogues aux opérations de composition parallèle dans les graphes série-parallèle, et des nœuds R, qui ne correspondent pas aux compositions série-parallèle. Un graphe biconnexe est série-parallèle si et seulement s'il n'y a pas de nœuds R dans son arbre SPQR.

