Orientation forte

Une orientation forte est, en théorie des graphes, l'attribution d'un sens à chaque arête d'un graphe non orienté (une orientation) qui en fait un graphe fortement connexe. Par exemple, on peut attribuer une orientation forte à un réseau routier s'il est possible de faire de chaque rue un sens unique sans rendre aucune intersection inaccessible. Le théorème de Robbins caractérise les graphes fortement orientables, qui sont exactement les graphes connexes sans pont. Les orientations eulériennes et les orientations bien équilibrées sont des cas particuliers d'orientations fortes. Pour les graphes non connexes, la notion d'orientation forte se généralise par les orientations totalement cycliques. L'ensemble des orientations fortes d'un graphe forme un cube partiel, dont les orientations adjacentes diffèrent par l'orientation d'une seule arête. Étant donné un graphe, il est possible de lui trouver une orientation forte en temps linéaire. En revanche, compter le nombre d'orientations fortes d'un graphe donné est un problème #P-complet. Herbert Robbins présenta dans un article de 1939 la recherche d'une orientation forte par le problème d'une ville fictive dont les rues et les intersections sont représentés par un graphe G donné. Pendant la semaine, les routes sont à double sens, mais la ville aimerait savoir si elle peut couper la circulation sur n'importe quelle section de rue pour y faire des travaux, tout en évitant qu'un quartier de la ville ne se retrouve inaccessible, c'est-à-dire qu'il doit toujours exister un itinéraire entre deux points de la ville, même si une section de rue est bloquée. Le week-end, il n'y a pas de travaux et toutes les rues sont ouvertes à la circulation, mais pour réduire les embouteillages, la ville souhaiterait rendre toutes les rues à sens unique, toujours sans isoler un point de la ville du reste du réseau routier. En termes de théorie des graphes, le critère des travaux en semaine peut être satisfait si G est un graphe sans pont (il est 2-arête-connexe) et celui des sens uniques du week-end est résolu s'il existe une orientation forte pour G.

À 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 (8)

Personnes associées (1)

Unités associées (1)

Concepts associés (6)

Séances de cours associées (6)

Orientation (graph theory)

In graph theory, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph. A directed graph is called an oriented graph if none of its pairs of vertices is linked by two symmetric edges. Among directed graphs, the oriented graphs are the ones that have no 2-cycles (that is at most one of (x, y) and (y, x) may be arrows of the graph). A tournament is an orientation of a complete graph. A polytree is an orientation of an undirected tree.

Graphe arête-connexe

En théorie des graphes, un graphe k-arête-connexe est un graphe connexe qu'il est possible de déconnecter en supprimant k arêtes et tel que ce k soit minimal. Il existe donc un ou plusieurs ensembles de k arêtes dont la suppression rende le graphe déconnecté, mais la suppression de k-1 arêtes, quelles qu'elles soient, le fait demeurer connexe. Un graphe régulier de degré k est au plus k-arête-connexe et k-sommet-connexe. S'il est effectivement k-arête-connexe et k-sommet-connexe, il est qualifié de graphe optimalement connecté.

Graphe dual

En théorie des graphes, le graphe dual d'un graphe plongé dans une surface est défini à l'aide des composantes de son complémentaire, lesquelles sont reliées entre elles par les arêtes du graphe de départ. Cette notion généralise celle de dualité dans les polyèdres. Il faut noter qu'un même graphe abstrait peut avoir des graphes duaux non isomorphes en fonction du plongement choisi, même dans le cas de plongements dans le plan. Un graphe (plongé) isomorphe à son dual est dit autodual.

A monotone cylindrical graph is a topological graph drawn on an open cylinder with an infinite vertical axis satisfying the condition that every vertical line intersects every edge at most once. It is called simple if any pair of its edges have at most one ...

Elsevier Science Bv2017

This thesis is devoted to the understanding of topological graphs. We consider the following four problems: 1. A \emph{simple topological graph} is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any t ...

EPFL2016

Many complex networks erase parts of their geometry as they develop, so that their evolution is difficult to quantify and trace. Here we introduce entropy measures for quantifying the complexity of street orientations and length variations within planar ne ...

2013

Inférence causale : Structures de graphes d'apprentissage MGT-416: Causal inference

Explore l'inférence causale à travers des structures de graphes d'apprentissage pour le raisonnement causal à partir de données d'observation.

Modèle d' Ising: Expansion 2D à haute température PHYS-316: Statistical physics II

Explore l'expansion à haute température du modèle Ising en treillis carré 2D.

Élimination des bords et orientation dans les graphiques MGT-416: Causal inference

Couvre l'élimination des bords et l'orientation dans les graphiques, y compris les tests de premier ordre et l'orientation logique.