Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Graphe arête-connexe
Résumé
In graph theory, a connected graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.
The edge-connectivity of a graph is the largest k for which the graph is k-edge-connected.
Edge connectivity and the enumeration of k-edge-connected graphs was studied by Camille Jordan in 1869.
Let be an arbitrary graph.
If the subgraph is connected for all where , then G is said to be k-edge-connected.
The edge connectivity of is the maximum value k such that G is k-edge-connected. The smallest set X whose removal disconnects G is a minimum cut in G.
The edge connectivity version of Menger's theorem provides an alternative and equivalent characterization, in terms of edge-disjoint paths in the graph. If and only if every two vertices of G form the endpoints of k paths, no two of which share an edge with each other, then G is k-edge-connected. In one direction this is easy: if a system of paths like this exists, then every set X of fewer than k edges is disjoint from at least one of the paths, and the pair of vertices remains connected to each other even after X is deleted. In the other direction, the existence of a system of paths for each pair of vertices in a graph that cannot be disconnected by the removal of few edges can be proven using the max-flow min-cut theorem from the theory of network flows.
Minimum vertex degree gives a trivial upper bound on edge-connectivity. That is, if a graph is k-edge-connected then it is necessary that k ≤ δ(G), where δ(G) is the minimum degree of any vertex v ∈ V. Obviously, deleting all edges incident to a vertex, v, would then disconnect v from the graph.
Edge connectivity is the dual concept to girth, the length of the shortest cycle in a graph, in the sense that the girth of a planar graph is the edge connectivity of its dual graph, and vice versa. These concepts are unified in matroid theory by the girth of a matroid, the size of the smallest dependent set in the matroid. For a graphic matroid, the matroid girth equals the girth of the underlying graph, while for a co-graphic matroid it equals the edge connectivity.
Source officielle
À 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.