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 K2, 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 à K4

Les graphes série-parallèle peuvent également être caractérisés par leurs .

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 . 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.

Voir aussi 

 Graphe de seuil
 Cographe
 Polytope de Hanner
 Ordre partiel série-parallèle

Références 

Graphe planaire
Opération sur les graphes
Famille de graphes