| dbo:abstract
|
- 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 , 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 . (fr)
- 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 , 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 . (fr)
|
| rdfs:comment
|
- 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. (fr)
- 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. (fr)
|