Component (graph theory) | EPFL Graph Search

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

Découvrez-en plus sur les applications Graph.

In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components. The number of components in a given graph is an important graph invariant, and is closely related to invariants of matroids, topological spaces, and matrices. In random graphs, a frequently occurring phenomenon is the incidence of a giant component, one component that is significantly larger than the others; and of a percolation threshold, an edge probability above which a giant component exists and below which it does not. The components of a graph can be constructed in linear time, and a special case of the problem, connected-component labeling, is a basic technique in . Dynamic connectivity algorithms maintain components as edges are inserted or deleted in a graph, in low time per change. In computational complexity theory, connected components have been used to study algorithms with limited space complexity, and sublinear time algorithms can accurately estimate the number of components. A component of a given undirected graph may be defined as a connected subgraph that is not part of any larger connected subgraph. For instance, the graph shown in the first illustration has three components. Every vertex of a graph belongs to one of the graph's components, which may be found as the induced subgraph of the set of vertices reachable from . Every graph is the disjoint union of its components. Additional examples include the following special cases: In an empty graph, each vertex forms a component with one vertex and zero edges. More generally, a component of this type is formed for every isolated vertex in any graph. In a connected graph, there is exactly one component: the whole graph. In a forest, every component is a tree.

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

Concepts associés (50)

Cours associés (23)

Séances de cours associées (224)

Lexique de la théorie des graphes

NOTOC Acyclique graphe ne contenant pas de cycle. Adjacence une liste d'adjacence est une structure de données constituée d'un tableau dont le -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque élément est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.

Component (graph theory)

Algorithme de Borůvka

Lalgorithme de Borůvka, est un algorithme de recherche de l'arbre couvrant de poids minimal dans un graphe pondéré. Il est aussi appelé algorithme de Sollin'. En théorie des graphes, étant donné un graphe non orienté connexe dont les arêtes sont pondérées, un arbre couvrant de poids minimal de ce graphe est un arbre couvrant (sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble) dont la somme des poids des arêtes est minimale.

Lattice models consist of (typically random) objects living on a periodic graph. We will study some models that are mathematically interesting and representative of physical phenomena seen in the real

Study of structures and concepts that do not require the notion of continuity. Graph theory, or study of general countable sets are some of the areas that are covered by discrete mathematics. Emphasis

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

Réseaux: Arbres MOOC: Optimization: principles and algorithms - Linear optimization

Explique le concept d'arbres dans la théorie des graphes et la définition d'un arbre couvrant.

Propagation de la croyance : méthodes clés et analyse PHYS-512: Statistical physics of computation

Couvre la propagation de la croyance, une méthode clé pour l'analyse et l'algorithme.

Théorie des graphiques de base MATH-261: Discrete optimization

Introduit des flux induits, des matrices de base et des solutions d'arbres dans la théorie des graphiques.