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. Une définition équivalente est qu'un graphe avec au moins deux sommets est k-sommet-connexe, pour chaque paire de ses sommets, il existe est k chaînes indépendantes reliant ces sommets ; c'est le théorème de Menger. Cette définition produit la même réponse n − 1, pour la connexité du graphe complet Kn. Un graphe 1-sommet-connexe est un appelé un graphe connexe ; un graphe 2-sommet-connexe et appelé un graphe biconnexe. Un graphe 3-connexe est aussi appelé triconnexe. Un graphe régulier de degré k est au plus k-sommet-connexe et k-arête-connexe. S'il est effectivement k-sommet-connexe et k-arête-connexe, il est dit optimalement connecté. Pour tout n, le graphe complet Kn (régulier de degré n – 1) est optimalement connecté. Pour tout k > 2 et tout j > 1, le graphe moulin Wd(k, j) est 1-sommet-connexe. Pour le séparer en j composantes connexes, il suffit de supprimer son sommet de plus haut degré : son centre. Le graphe cycle Cn est 2-sommet-connexe pour tout n > 3. Le 110-graphe de Iofinova-Ivanov est 3-sommet-connexe. Image:Biggs-Smith graph.svg|Le [[graphe de Biggs-Smith]] est 3-régulier, 3-sommet-connexe et 3-arête-connexe : il est optimalement connecté. Image:Windmill graph Wd(5,4).svg|Le [[graphe moulin]] Wd(5,4) n'est plus connexe si l'on supprime son sommet central: il est 1-sommet-connexe. Image:Complete graph K6.svg|Le [[graphe complet]] K6 est 5-sommet-connexe. Nombre de graphes simples -sommet-connexes à sommets pour de 1 à 9, avec la référence à OEIS : {| class="wikitable" |- ! \ !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8

À 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.

Personnes associées (4)

Unités associées (1)

Concepts associés (23)

Cours associés (4)

Séances de cours associées (41)

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

PHYS-435: Statistical physics III

This course introduces statistical field theory, and uses concepts related to phase transitions to discuss a variety of complex systems (random walks and polymers, disordered systems, combinatorial o

CS-450: Algorithms II

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper

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.

Théorie Lee-Yang MATH-486: Statistical mechanics and Gibbs measures

Explore la théorie de Lee-Yang, couvrant les graphes connectés, les chemins, les diagrammes de phase et la continuation analytique.

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.

Vectorworks Version éducative

Présente Vectorworks Version pédagogique pour les dessins architecturaux, les outils, les couches et les annotations.