Ê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 Graph Search.
Concept
Biconnected graph
Résumé
In graph theory, a biconnected graph is a connected and "nonseparable" graph, meaning that if any one vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices.
The property of being 2-connected is equivalent to biconnectivity, except that the complete graph of two vertices is usually not regarded as 2-connected.
This property is especially useful in maintaining a graph with a two-fold redundancy, to prevent disconnection upon the removal of a single edge (or connection).
The use of biconnected graphs is very important in the field of networking (see Network flow), because of this property of redundancy.
A biconnected undirected graph is a connected graph that is not broken into disconnected pieces by deleting any single vertex (and its incident edges).
A biconnected directed graph is one such that for any two vertices v and w there are two directed paths from v to w which have no vertices in common other than v and w.
File:4 Node Biconnected.svg|A biconnected graph on four vertices and four edges
File:4 Node Not-Biconnected.svg|A graph that is not biconnected. The removal of vertex x would disconnect the graph.
File:5 Node Biconnected.svg|A biconnected graph on five vertices and six edges
File:5 Node Not-Biconnected.svg|A graph that is not biconnected. The removal of vertex x would disconnect the graph.
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.