Théorème de Menger

In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices. Proved by Karl Menger in 1927, it characterizes the connectivity of a graph. It is generalized by the max-flow min-cut theorem, which is a weighted, edge version, and which in turn is a special case of the strong duality theorem for linear programs. The edge-connectivity version of Menger's theorem is as follows: Let G be a finite undirected graph and x and y two distinct vertices. Then the size of the minimum edge cut for x and y (the minimum number of edges whose removal disconnects x and y) is equal to the maximum number of pairwise edge-independent paths from x to y. Extended to all pairs: a graph is k-edge-connected (it remains connected after removing fewer than k edges) if and only if every pair of vertices has k edge-disjoint paths in between. The vertex-connectivity statement of Menger's theorem is as follows: Let G be a finite undirected graph and x and y two nonadjacent vertices. Then the size of the minimum vertex cut for x and y (the minimum number of vertices, distinct from x and y, whose removal disconnects x and y) is equal to the maximum number of pairwise internally vertex-disjoint paths from x to y. Extended to all pairs: a graph is k-vertex-connected (it has more than k vertices and it remains connected after removing fewer than k vertices) if and only if every pair of vertices has at least k internally vertex-disjoint paths in between. All these statements (in both edge and vertex versions) remain true in directed graphs (when considering directed paths). Most direct proofs consider a more general statement to allow proving it by induction. It is also convenient to use definitions that include some degenerate cases. The following proof for undirected graphs works without change for directed graphs or multi-graphs, provided we take path to mean directed path.

À 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 (14)

Personnes associées (1)

Concepts associés (3)

Cours associés (3)

Séances de cours associées (10)

MATH-410: Riemann surfaces

This course is an introduction to the theory of Riemann surfaces. Riemann surfaces naturally appear is mathematics in many different ways: as a result of analytic continuation, as quotients of complex

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

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

Graphe arête-connexe

En théorie des graphes, un graphe k-arête-connexe est un graphe connexe qu'il est possible de déconnecter en supprimant k arêtes et tel que ce k soit minimal. Il existe donc un ou plusieurs ensembles de k arêtes dont la suppression rende le graphe déconnecté, mais la suppression de k-1 arêtes, quelles qu'elles soient, le fait demeurer connexe. Un graphe régulier de degré k est au plus k-arête-connexe et k-sommet-connexe. S'il est effectivement k-arête-connexe et k-sommet-connexe, il est qualifié de graphe optimalement connecté.

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.

Graphe sommet-connexe

En théorie des graphes, un graphe connexe . Un graphe autre qu'un graphe complet est de degré de sommet-connexité k s'il est k-sommet-connexe sans être k+1-sommet-connexe, donc si k est la taille du plus petit sous-ensemble de sommets dont la suppression déconnecte le graphe. Les graphes complets ne sont pas inclus dans cette version de la définition car ils ne peuvent pas être déconnectés en supprimant des sommets. Le graphe complet à n sommets est de degré de connexité n-1.

Topologie des surfaces de Riemann MATH-410: Riemann surfaces

Couvre la topologie des surfaces de Riemann et le concept de triangulation en utilisant un nombre fini de triangles.

Max-Flow Problème: Algorithme de Ford-Fulkerson MATH-261: Discrete optimization

Explore l'algorithme Ford-Fulkerson pour résoudre le problème Max-Flow et ses applications dans l'optimisation du flux réseau.

Paradigmes algorithmiques pour les problèmes de graphique dynamique

Couvre les paradigmes algorithmiques pour les problèmes de graphique dynamique, y compris la connectivité dynamique, la décomposition de l'expansion et le regroupement local, brisant les barrières dans les problèmes de connectivité k-vertex.

Molecular hypergraph neural networks

Philippe Schwaller, Junwu Chen

Graph neural networks (GNNs) have demonstrated promising performance across various chemistry-related tasks. However, conventional graphs only model the pairwise connectivity in molecules, failing to adequately represent higher order connections, such as m ...

Aip Publishing2024

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al.

Lukas Fritz Felix Vogl

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

Elsevier2024

Selective attention involves a feature-specific sequential release from inhibitory gating

David Pascucci, Gijs Plomp

Selective attention is a fundamental cognitive mechanism that allows our brain to preferentially process relevant sensory information, while filtering out distracting information. Attention is thought to flexibly gate the communication of irrelevant inform ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2022