Concept
Graphe sommet-connexe
Concepts associés (16)
Séparateur (théorie des graphes)
En théorie des graphes et en informatique théorique, un séparateur d'un graphe connexe est un sous-ensemble des sommets du graphe dont la suppression rend le graphe non-connexe. Cet objet est intéressant notamment pour décomposer un graphe en des graphes plus petits et plus simples. On appelle parfois séparateur un ensemble d'arêtes dont la suppression rend le graphe non-connexe, c'est-à-dire une coupe. Le théorème de Menger relie connectivité et séparateurs minimum. thumb|upright=1.2|Un separateur du graphe grille.
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.
Steinitz's theorem
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.
Biconnected component
In graph theory, a biconnected component (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or separating vertices or articulation points. Specifically, a cut vertex is any vertex whose removal increases the number of connected components.
Biconnected graph
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).
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.
Théorème de Menger
En théorie des graphes, le théorème de Menger est à l'origine du théorème flot-max/coupe-min qui le généralise. Il fut prouvé par Karl Menger en 1927. Le théorème de Menger s'énonce ainsi : Le théorème d'Erdős-Pósa est de même nature que celui de Menger, il relie la taille maximale d'une collection de cycles disjoints à la taille minimale d'un coupe-cycles de sommets (feedback vertex set). J. A. Bondy et U.S.R. Murty, Graph Theory with Applications, libre d'accès uniquement pour l'usage personnel Menger de
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é.
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.
Isthme (théorie des graphes)
In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges. This type of bridge should be distinguished from an unrelated meaning of "bridge" in graph theory, a subgraph separated from the rest of the graph by a specified subset of vertices; see bridge.