Graphe orienté


Graphe orienté

En théorie des graphes un graphe orienté G=(V,A) est défini par la donnée d'un ensemble de sommets V et d'un ensemble d'arcs A, chaque arête étant un couple de sommets (par exemple, si x et y sont des sommets, les couples (x,y) et (y,x) - notés respectivement xy et yx - peuvent être des arcs du graphe G).

Remarquons que dans un graphe non orienté G=(V,E), les arêtes remplacent les arcs et sont des paires de sommets (par exemple, si x et y sont des sommets, la paire {x, y}, notée xy, peut être une arête du graphe G).

Les graphes étudiés en théorie des graphes sont en général des graphes simples, sans arêtes/arcs multiples (par opposition aux multigraphes) et généralement sans boucles.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe orienté de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Graphe orienté — ● Graphe orienté quadruplet (X, C, o, e) où X est un ensemble d éléments appelés sommets, C une famille d éléments appelés arcs, o une application de C dans X (origine) et e une application de C dans X (extrémité) …   Encyclopédie Universelle

  • graphe orienté — orientuotasis grafas statusas T sritis automatika atitikmenys: angl. directed graph; oriented graph vok. gerichteter Graph, m; orientierter Graph, m rus. орграф, m; ориентированный граф, m pranc. graphe de fluence, m; graphe directe, m; graphe… …   Automatikos terminų žodynas

  • Graphe orienté acyclique — Un exemple de graphe orienté acyclique En théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG) est un graphe orienté qui ne possède pas de cycle. La notion est usuelle dans plusieurs domaines de… …   Wikipédia en Français

  • Graphe Eulérien — En théorie des graphes, on dit d un graphe non orienté qu il est « eulérien » en référence à Euler (la plupart des mathématiciens écrivent « Eulérien » à cause de l usage anglo saxon) s il a la propriété suivante : On… …   Wikipédia en Français

  • Graphe eulerien — Graphe eulérien En théorie des graphes, on dit d un graphe non orienté qu il est « eulérien » en référence à Euler (la plupart des mathématiciens écrivent « Eulérien » à cause de l usage anglo saxon) s il a la propriété… …   Wikipédia en Français

  • Graphe d'une chaîne de Markov — et classification des états Le graphe d une chaîne de Markov et la classification des états sont des notions de la théorie des graphes utilisées en calcul des probabilités. Sommaire 1 Graphe d une chaîne de Markov 2 Classification des états …   Wikipédia en Français

  • orienté — orienté, ée [ ɔrjɑ̃te ] adj. • 1485; de orienter 1 ♦ Disposé d une certaine manière par rapport aux points cardinaux. « les vastes chambres orientées à l est » (Colette). Appartement bien, mal orienté, orienté est ouest. 2 ♦ Math. Où l on a… …   Encyclopédie Universelle

  • graphe — [ graf ] n. m. • 1926; du gr. graphein « écrire » ♦ Math., log. Ensemble des couples d éléments vérifiant une relation donnée. Diagramme représentant le graphe d une relation. Théorie des graphes. Représentation graphique d une fonction. ● graphe …   Encyclopédie Universelle

  • Graphe Planaire — Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu aucune arête (ou arc pour un graphe orienté) n en croise une autre. Autrement dit, ces graphes sont précisément… …   Wikipédia en Français

  • Graphe Connexe — Définition En théorie des graphes, un graphe G = (S,A) est dit connexe si quels que soient les sommets u et v de S, il existe un chemin de u vers v. C est à dire, s il existe une suite d arêtes (ou d arcs correctement orientés dans le cas d un… …   Wikipédia en Français


We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.