Graphe série-parallèle

vignette|Opérations de composition en série et en parallèle pour les graphes 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 . 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. 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}. 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.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (1)

Concepts associés (4)

Séances de cours associées (1)

Outerplanar graph drawings with few slopes

Bartosz Maria Walczak

We consider straight-line outerplanar drawings of outerplanar graphs in which a small number of distinct edge slopes are used, that is, the segments representing edges are parallel to a small number of directions. We prove that Delta - 1 edge slopes suffic ...

Elsevier Science Bv2014

Forbidden graph characterization

In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor. A prototypical example of this phenomenon is Kuratowski's theorem, which states that a graph is planar (can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the complete graph K_5 and the complete bipartite graph K_3,3.

Ensemble dominant

En théorie des graphes, un ensemble dominant (ou dominating set en anglais) d'un graphe G = ( S, A ) est un sous-ensemble D de l'ensemble S des sommets tel que tout sommet qui n'appartient pas à D possède au moins une arête d'extrémité un sommet de D. Le problème de l'ensemble dominant est de déterminer, étant donné G et un entier naturel k, si G possède un ensemble dominant d'au plus k sommets. Ce problème est NP-complet.

Cographe

Un cographe est, en théorie des graphes, un graphe qui peut être généré par complémentation et union disjointe à partir du graphe à un nœud. La plupart des problèmes algorithmiques peuvent être résolus sur cette classe en temps polynomial, et même linaire, du fait de ses propriétés structurelles. Cette famille de graphe a été introduite par plusieurs auteurs indépendamment dans les années 1970 sous divers noms, notamment D*-graphes, hereditary Dacey graphs et 2-parity graphs.

Définition graphique : ensembles de niveaux et domaines

Couvre la définition graphique des fonctions, en se concentrant sur les ensembles de niveaux et les domaines.