Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Graphe orienté
Résumé
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).
Source officielle
À 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 (1)
Concepts associés (74)
Densité d'un graphe
En mathématiques, et plus particulièrement en théorie des graphes, on peut associer à tout graphe un entier appelé densité du graphe. Ce paramètre mesure si le graphe a beaucoup d'arêtes ou peu. Un graphe dense (dense graph) est un graphe dans lequel le nombre d'arêtes (ou d'arcs) est proche du nombre maximal, par exemple un nombre quadratique par rapport au nombre de sommets. Un graphe creux (sparse graph) a au contraire peu d'arêtes, par exemple un nombre linéaire. La distinction entre graphe creux et dense est plutôt vague et dépend du contexte.
Graphe (mathématiques discrètes)
Dans le domaine des mathématiques discrètes, la théorie des graphes définit le graphe, une structure composée d'objets et de relations entre deux de ces objets. Abstraitement, lesdits objets sont appelés sommets (ou nœuds ou points), et les relations entre eux sont nommées arêtes (ou liens ou lignes). On distingue les graphes non orientés, où les arêtes relient deux sommets de manière symétrique, et les graphes orientés, où les arêtes, alors appelées arcs (ou flèches), relient deux sommets de manière asymétrique.
Carquois (théorie des catégories)
Un carquois est une collection d'arcs joignant des couples de points. En ce sens, il s'agit d'un graphe orienté, mais la notion intervient en physique théorique ainsi qu'en théorie des représentations, des groupes et des catégories de manière naturelle. En effet, une catégorie est un carquois doté d'une structure supplémentaire : nommément la présence d'identités et de compositions. On parle donc de carquois lorsque l'on souhaite évoquer ce contexte catégorique (ou de représentation), plutôt que de (multi-di-)graphe orienté.
Cours associés (92)
ME-427: Networked control systems
This course offers an introduction to control systems using communication networks for interfacing sensors, actuators, controllers, and processes. Challenges due to network non-idealities and opportun
PHYS-512: Statistical physics of computation
This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and
MATH-467: Probabilistic methods in combinatorics
We develop a sophisticated framework for solving problems in discrete mathematics through the use of randomness (i.e., coin flipping). This includes constructing mathematical structures with unexpecte
MOOCs associés (11)
Analyse I
Le contenu de ce cours correspond à celui du cours d'Analyse I, comme il est enseigné pour les étudiantes et les étudiants de l'EPFL pendant leur premier semestre. Chaque chapitre du cours correspond
Analyse I (partie 1) : Prélude, notions de base, les nombres réels
Concepts de base de l'analyse réelle et introduction aux nombres réels.
Analyse I (partie 2) : Introduction aux nombres complexes
Introduction aux nombres complexes