Séance de cours

Réseaux : coupures

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 coupes dans un graphe dirigé, qui sépare les nœuds en deux ensembles. En analysant les arcs qui traversent la coupe, semblables à des ponts dans une ville, on peut identifier le flux entre les deux ensembles.

Dans MOOC

Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Introduction au concept mathématique des réseaux et à deux importants problèmes d'optimisation sur les réseaux : le problème du transbordement et le problème du chemin le plus court. Brève introduction à la puissance de modélisation de l'optimisation discrète, avec référence à des problèmes classiques. Introduction à l'algorithme branch and bound et au concept de coupes.

Source officielle

Proximité ontologique

Mathématiques

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

Concepts associés (16)

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.

Cycle (théorie des graphes)

thumb|Dans ce graphe, le cycle rouge est élémentaire. Le cycle bleu ne l'est pas. La chaine verte n'est pas fermée et ne forme donc pas un cycle. Dans un graphe non orienté, un cycle est une suite d'arêtes consécutives distinctes (chaine simple) dont les deux sommets extrémités sont identiques. Dans les graphes orientés, la notion équivalente est celle de circuit, même si on parle parfois aussi de cycle (par exemple dans l'expression graphe acyclique orienté).

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)

Inférence causale & Graphiques dirigés

Explore l'inférence causale, les graphiques dirigés et l'équité dans les algorithmes, en mettant l'accent sur l'indépendance conditionnelle et les implications des GAD.

L'apprentissage actif dans la théorie des catégories

Explore des exemples de catégories, de morphismes, de groupoïdes et de functeurs dans la théorie des catégories.

Introduction à la théorie des catégories

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

Polynôme d'indépendance du graphique de dépendance

Couvre le polynôme d'indépendance d'un graphe de dépendance et des concepts connexes tels que la coloration du graphe et les propriétés du graphe dirigé.

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.

Afficher plus

Concepts associés (16)

Graphe orienté

Graphe orienté acyclique

Graphe cycle

Cycle (théorie des graphes)

Line graph

Afficher plus