Problème de réalisation Digraph - Digraph realization problem

Le problème de réalisation du digraphe est un problème de décision en théorie des graphes . Étant donné les paires d' entiers non négatifs , le problème se demande s'il existe un graphe orienté simple étiqueté tel que chaque sommet ait un degré indegree et outdegree . ${\ displaystyle ((a_ {1}, b_ {1}), \ ldots, (a_ {n}, b_ {n}))}$ ${\ displaystyle v_ {i}}$ ${\ displaystyle a_ {i}}$ ${\ displaystyle b_ {i}}$

Solutions

Le problème appartient à la classe de complexité P . Deux algorithmes sont connus pour le prouver. La première approche est donnée par les algorithmes de Kleitman – Wang construisant une solution spéciale à l'aide d'un algorithme récursif . La seconde est une caractérisation par le théorème de Fulkerson – Chen – Anstee , c'est-à-dire qu'il faut valider l'exactitude des inégalités. ${\ displaystyle n}$

Autres notations

Le problème peut également être posé en termes de matrices zéro-un . La connexion peut être vue si l'on se rend compte que chaque graphe orienté a une matrice de contiguïté où les sommes de colonnes et de lignes correspondent à et . Notez que la diagonale de la matrice ne contient que des zéros. Le problème est alors souvent désigné par 0-1-matrices pour des sommes de lignes et de colonnes données . Dans la littérature classique, le problème était parfois posé dans le contexte des tableaux de contingence par des tableaux de contingence avec des marges données . ${\ displaystyle (a_ {1}, \ cdots, a_ {n})}$${\ displaystyle (b_ {1}, \ ldots, b_ {n})}$

Problèmes connexes

Des problèmes similaires décrivent les séquences degré de graphiques simples , graphiques simples dirigé de avec des boucles et des simples graphiques bipartites . Le premier problème est le soi-disant problème de réalisation de graphe . Le deuxième et le troisième sont équivalents et sont connus sous le nom de problème de réalisation bipartite . Chen (1966) a donné une caractérisation pour les multigraphes dirigées avec un nombre borné d'arcs et de boucles parallèles à une séquence de degrés donnée . La contrainte supplémentaire d'acycilicité du graphe orienté est connue sous le nom de réalisation de dag . Nichterlein & Hartung (2012) ont prouvé l' exhaustivité NP de ce problème. Berger & Müller-Hannemann (2011) ont montré que la classe de séquences opposées est en P . Le problème d' échantillonnage uniforme d'un graphe orienté à une séquence à degré fixe est de construire une solution pour le problème de réalisation du digraphe avec la contrainte supplémentaire qu'une telle solution a la même probabilité. Ce problème s'est avéré être dans FPTAS pour les séquences régulières par Catherine Greenhill  ( 2011 ) Le problème général n'est toujours pas résolu.

Les références

• Chen, Wai-Kai (1966), «Sur la réalisation d'un ( p , s ) -digraphe avec des degrés prescrits», Journal of the Franklin Institute , 103 : 406–422
• Nichterlein, André; Hartung, Sepp (2012), «NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs», Journal of the Franklin Institute , 7318 : 283-292
• Berger, Annabell; Müller-Hannemann, Matthias (2011), "Dag Realisations of Directed Degree Sequences", Actes de la 18e Conférence internationale sur les principes fondamentaux de la théorie du calcul : 264-275
• Greenhill, Catherine (2011), "Une borne polynomiale sur le temps de mélange d'une chaîne de Markov pour l'échantillonnage de graphes dirigés réguliers", Electronic Journal of Combinatorics , 18