thumb|Un graphe orienté .(Figure 1) Dans la théorie des graphes, un graphe orienté est un couple formé de un ensemble, appelé ensemble de nœuds et un ensemble appelé ensemble d'arêtes. Les arêtes sont alors nommées arcs, chaque arête étant un couple de noeuds, représenté par une flèche. Étant donné un arc , on dit que est l'origine (ou la source ou le départ ou le début) de et que est la cible (ou l'arrivée ou la fin) de . Le demi-degré extérieur (degré sortant) d'un nœud, noté , est le nombre d'arcs ayant ce nœud pour origine. Le demi-degré intérieur (degré entrant) d'un nœud, noté , est le nombre d'arcs ayant ce nœud pour cible. Chaque arc ayant une seule origine et une seule cible, le graphe comporte autant de degrés sortants que de degrés entrants : . est un chemin si et seulement si est un arc ; on dit que le chemin est élémentaire si tous les sont distincts. le chemin est un circuit si et seulement si est un arc. Ce qui est équivalent à dire que le nœud de début du chemin est également sa fin. le graphe est un sous-graphe du graphe orienté si et seulement si contient . Plus précisément, si et seulement si et . Le graphe transposé d'un graphe orienté est obtenu en conservant tous les nœuds de et en inversant tous les arcs de . Autrement dit, avec . On parle aussi de graphe inverse. Une chaîne est une séquence de noeuds telle que . thumb|, un sous-graphe du graphe .(Figure 2) le graphe dessiné dans la figure 1 est défini par et par. le degré sortant . Deux arcs ont pour origine le nœud . le degré entrant . Aucun arc n'a pour cible le nœud . est un chemin du graphe (puisque et appartiennent à ) . est un circuit du graphe (et c'est le seul circuit élémentaire si on l'identifie au circuit ), car les arcs et appartiennent à . est une chaîne de . est un sous-graphe de . est le transposé de . Les graphes orientés sont des modèles pour diverses situations. Les systèmes routiers possédant des sens uniques, les systèmes de transport dissymétriques... Les graphes d'état mêlant transitions réversibles et irréversibles (exemple : les automates à états finis).

À 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.
Cours associés (32)
MATH-448: Statistical analysis of network data
A first course in statistical network analysis and applications.
MGT-416: Causal inference
Students will learn the core concepts and techniques of network analysis with emphasis on causal inference. Theory and application will be balanced, with students working directly with network data th
CS-455: Topics in theoretical computer science
The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced techniques, and develops an understanding of f
Afficher plus
Publications associées (32)
Concepts associés (32)
Arborescence (graph theory)
In graph theory, an arborescence is a directed graph in which, for a vertex u (called the root) and any other vertex v, there is exactly one directed path from u to v. An arborescence is thus the directed-graph form of a rooted tree, understood here as an undirected graph. Equivalently, an arborescence is a directed, rooted tree in which all edges point away from the root; a number of other equivalent characterizations exist. Every arborescence is a directed acyclic graph (DAG), but not every DAG is an arborescence.
Boucle (théorie des graphes)
In graph theory, a loop (also called a self-loop or a buckle) is an edge that connects a vertex to itself. A simple graph contains no loops. Depending on the context, a graph or a multigraph may be defined so as to either allow or disallow the presence of loops (often in concert with allowing or disallowing multiple edges between the same vertices): Where graphs are defined so as to allow loops and multiple edges, a graph without loops or multiple edges is often distinguished from other graphs by calling it a simple graph.
Connectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.