Séance de cours

Graphiques dirigés : Introduction et catégories

Graph Chat

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.

Description

Cette séance de cours introduit la notion fondamentale de composition des applications dans le contexte des graphiques dirigés, également appelés quivers. Il couvre la définition d'un graphique dirigé, composé de classes de sommets et de bords avec des fonctions de domaine et de codomaine. Des exemples de graphiques dirigés sont fournis, illustrant les relations sur des ensembles et leur représentation en tant que graphiques dirigés.

Source officielle

Proximité ontologique

Mathématiques

Mathématiques discrètes: Théorie des graphes

Concepts associés (32)

Graphe orienté

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.

Ensemble de définition

En mathématiques, l'ensemble de définition (également appelé domaine de définition ou parfois ensemble de départ, voir la discussion plus bas) d'une application ou d'une fonction désigne informellement l'ensemble des entrées acceptées par elle. La terminologie entre ensemble de définition et ensemble de départ diffère si l'on fait la distinction entre la notion de fonction et d'application ou non.

Fonction partielle

vignette|Exemple d'une fonction partielle En mathématiques, une fonction partielle (quelquefois appelée simplement fonction) sur un ensemble donné E est une application définie sur une partie de celui-ci, appelé ensemble de définition (ou domaine de définition) de la fonction partielle.

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 circuit. Un tel graphe peut être vu comme une hiérarchie. Un graphe orienté acyclique est un graphe orienté qui ne possède pas de circuit. On peut toujours trouver un sous-graphe couvrant d’un graphe orienté acyclique qui soit un arbre (resp. une forêt). Dans un graphe orienté acyclique, la relation d'accessibilité R(u, v) définie par « il existe un chemin de u à v » est une relation d'ordre partielle.

Graphe cycle

Les graphes cycles, ou n-cycles, forment une famille de graphes. Le graphe cycle est constitué d'un unique cycle élémentaire de longueur n (pour ). C'est un graphe connexe non-orienté d'ordre n à n arêtes. Il est 2-régulier, c'est-à-dire que chacun de ses sommets est de degré 2. Beaucoup de termes sont employés pour désigner le graphe cycle : n-cycle, polygone et n-gone. Le terme de graphe cyclique est parfois employé, mais il pose problème car il s'oppose normalement à graphe acyclique. Nombre chromatique.

Afficher plus

Séances de cours associées (64)

Théorie des graphiques et flux réseau

Introduit la théorie des graphiques, les flux de réseau et les lois de conservation des flux avec des exemples pratiques et des théorèmes.

Algorithmes graphiques : Modélisation et transversalité

Couvre les algorithmes graphiques, la modélisation des relations entre les objets et les techniques de traversée telles que BFS et DFS.

Introduction aux catégories

Introduit le concept de catégories essentielles pour comprendre la théorie des groupes.

Graphes et réseaux : bases et applications

Présente les bases des graphiques et des réseaux, couvrant les définitions, les chemins, les arbres, les flux, la circulation et les arbres couvrants.

Max Flav-Min Découpe dans les graphiques dirigés

Couvre le concept de réduction maximale du débit minimal dans les graphiques dirigés avec des contraintes de capacité.

Afficher plus

Concepts associés (32)

Graphe orienté

Ensemble de définition

Fonction partielle

Graphe orienté acyclique

Graphe cycle

Afficher plus