Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Réseaux, Flux

Description

Cette séance de cours couvre la définition du flux dans un réseau, le calcul du flux à travers une coupe, et le concept de flux de chemin simple, fournissant des exemples et un résumé à la fin.

Dans MOOC

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

Source officielle

Proximité ontologique

Mathématiques

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

Concepts associés (22)

Théorie des graphes

vignette|Un tracé de graphe. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non symétriques (les graphes sont alors dits orientés) et sont alors appelées des flèches ou des arcs.

Lexique de la théorie des graphes

NOTOC Acyclique graphe ne contenant pas de cycle. Adjacence une liste d'adjacence est une structure de données constituée d'un tableau dont le -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque élément est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.

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.

Chaîne (théorie des graphes)

Dans un graphe non orienté, une chaîne reliant à , notée , est définie par une suite finie d'arêtes consécutives, reliant à . La notion correspondante dans les graphes orientés est celle de chemin. Une chaîne élémentaire est une chaîne ne passant pas deux fois par un même sommet, c'est-à-dire dont tous les sommets sont distincts. Une chaîne simple est une chaîne ne passant pas deux fois par une même arête, c'est-à-dire dont toutes les arêtes sont distinctes. Un cycle est une chaîne simple dont les deux extrémités sont identiques.

Sommet (théorie des graphes)

vignette|Dans ce graphe, les sommets 4 et 5 sont voisins alors que les sommets 3 et 5 sont indépendants. Le degré du sommet 4 est égal à 3. Le sommet 6 est une feuille. En théorie des graphes, un sommet, aussi appelé nœud et plus rarement point, est l'unité fondamentale d'un graphe. Deux sommets sont voisins s'ils sont reliés par une arête. Deux sommets sont indépendants s'ils ne sont pas voisins. alt=A small example network with 8 vertices and 10 edges.|vignette|Réseau de huit sommets (dont un isolé) et 10 arêtes.

Afficher plus

Séances de cours associées (32)

Graph Models et Brain Connectomics

Explore la théorie des graphes dans la connectomique cérébrale, les applications d'IRM, la pertinence de l'analyse de réseau et les empreintes digitales individuelles.

Topologie dans les réseaux complexes : Perspectives de l'analyse des données topologiques

Explore le rôle des propriétés topologiques d'ordre supérieur dans les réseaux complexes en utilisant l'analyse topologique des données pour la détection des ruptures structurelles et des anomalies de prix.

Régression non paramétrique pour les réseaux

Explore la régression non paramétrique pour les réseaux, couvrant l'analyse des données d'objets, les graphiques de réseaux, les distances extrinsèques et les projections pratiques.

Introduction aux réseaux et aux réseaux du cerveau

Introduit les fondamentaux de la science des réseaux, en se concentrant sur les réseaux du cerveau et leurs percées historiques.

Manipulation des réseaux : théorie des graphes

Couvre les bases de la manipulation des réseaux et des mesures de centralité dans la théorie des graphes.

Afficher plus

Concepts associés (22)

Théorie des graphes

Lexique de la théorie des graphes

Connectivity (graph theory)

Chaîne (théorie des graphes)

Sommet (théorie des graphes)

Afficher plus