Séance de cours

Introduction aux 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 le concept de catégories en tant que graphiques dirigés avec des fonctions de composition satisfaisant des axiomes spécifiques, y compris l'existence d'identités et d'associativité, essentielle pour comprendre la théorie de groupe.

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.

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.

Axiome

Un axiome (en ἀξίωμα /axioma, « principe servant de base à une démonstration, principe évident en soi » – lui-même dérivé de άξιόω (axioô), « juger convenable, croire juste ») est une proposition non démontrée, utilisée comme fondement d’un raisonnement ou d’une théorie mathématique. Pour Euclide et certains philosophes grecs de l’Antiquité, un axiome était une affirmation qu'ils considéraient comme évidente et qui n'avait nul besoin de démonstration.

Line graph

En théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960. La même construction avait cependant déjà été utilisée par Whitney en 1932 et Krausz en 1943. Il est également appelé graphe adjoint. Un des premiers et des plus importants théorèmes sur les line graphs est énoncé par Hassler Whitney en 1932, qui prouve qu'en dehors d'un unique cas exceptionnel, la structure de G peut être entièrement retrouvée à partir de L(G) dans le cas des graphes connexes.

Afficher plus

Séances de cours associées (64)

Catégories et Functors

Explore les catégories de construction à partir de graphiques et l'encodage de l'information par les functeurs.

Introduction à la théorie des catégories

Couvre l'introduction aux catégories, y compris les définitions et les exemples.

Algorithme de Bellman-Ford : Estimation du chemin le plus court

Explique l'algorithme de Bellman-Ford pour trouver le chemin le plus court dans un graphe dirigé avec des poids de bord.

Théorie des groupes : définition et exemples

Couvre la définition d'un groupe, les propriétés des symétries et les opérations de groupe.

Les flux réseau rencontrent Simplex

Explore les flux réseau, la méthode simplex, la programmation linéaire, les solutions arborescentes et les solutions doubles dans les problèmes d'optimisation.

Afficher plus

Concepts associés (32)

Graphe orienté

Graphe orienté acyclique