This HTML5 document contains 54 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n11http://g.co/kg/m/
dbpedia-ruhttp://ru.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
category-frhttp://fr.dbpedia.org/resource/Catégorie:
n9http://fr.dbpedia.org/resource/Modèle:
wikipedia-frhttp://fr.wikipedia.org/wiki/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n4http://ma-graph.org/entity/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbpedia-fr:Orientation_forte
rdfs:label
Orientation forte
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.
owl:sameAs
n4:121047771 n11:03ym7qv dbr:Strong_orientation wikidata:Q7624577 dbpedia-ru:Сильная_ориентация_(теория_графов)
dbo:wikiPageID
14443072
dbo:wikiPageRevisionID
188551447
dbo:wikiPageWikiLink
dbpedia-fr:Cycle_(théorie_des_graphes) dbpedia-fr:Graphe_biparti dbpedia-fr:Densité_d'un_graphe dbpedia-fr:Analyse_de_la_complexité_des_algorithmes dbpedia-fr:Flip_graphique dbpedia-fr:Problème_NP-complet category-fr:Graphe_orienté dbpedia-fr:Graphe_eulérien dbpedia-fr:Graphe_dual dbpedia-fr:Arête_(théorie_des_graphes) dbpedia-fr:Composante_fortement_connexe dbpedia-fr:Sharp-P-complet dbpedia-fr:Crispin_Nash-Williams dbpedia-fr:Plan_hippodamien dbpedia-fr:Embouteillage_(route) dbpedia-fr:Isthme_(théorie_des_graphes) dbpedia-fr:Schéma_d'approximation_en_temps_polynomial dbpedia-fr:Graphe_(mathématiques_discrètes) dbpedia-fr:Graphe_orienté dbpedia-fr:Herbert_Robbins dbpedia-fr:Théorie_des_graphes dbpedia-fr:Degré_(théorie_des_graphes) dbpedia-fr:Algorithme_de_parcours_en_profondeur dbpedia-fr:Théorème_de_Robbins dbpedia-fr:Grille dbpedia-fr:Graphe_planaire dbpedia-fr:Largeur_arborescente dbpedia-fr:Graphe_arête-connexe category-fr:Théorie_des_graphes dbpedia-fr:Polynôme_de_Tutte dbpedia-fr:Cube_partiel dbpedia-fr:Théorème_de_Menger dbpedia-fr:Graphe_orienté_acyclique dbpedia-fr:Orientation_acyclique dbpedia-fr:Complexité_en_temps
dbo:wikiPageLength
15140
dct:subject
category-fr:Graphe_orienté category-fr:Théorie_des_graphes
prop-fr:wikiPageUsesTemplate
n9:Formule n9:Mvar n9:Portail n9:,
prov:wasDerivedFrom
wikipedia-fr:Orientation_forte?oldid=188551447&ns=0
foaf:isPrimaryTopicOf
wikipedia-fr:Orientation_forte
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 .