Metraipolis › archive › dc_de3d36dc1dd4

Component (graph theory) — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Component_(graph_theory)
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T14:34:05.768Z
SHA-256 of the archived text
4189eb792bbf4996253252c144491c029c9a454ec2ff13d178c8e91d084f5ffe
Stable URL of this page
https://metraipolis.com/documento/dc_de3d36dc1dd4

How to cite

Component (graph theory) — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Component_(graph_theory) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_de3d36dc1dd4 (Metraipolis archive dc_de3d36dc1dd4, sha256 4189eb792bbf4996253252c144491c029c9a454ec2ff13d178c8e91d084f5ffe)
BibTeX
@misc{dcde3d36dc1dd4,
  title = {Component (graph theory) — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Component_(graph_theory)},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_de3d36dc1dd4; sha256 4189eb792bbf4996253252c144491c029c9a454ec2ff13d178c8e91d084f5ffe},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Component_(graph_theory). Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 image analysis. 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.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Component (graph theory)» — https://en.wikipedia.org/wiki/Component_(graph_theory)
Wikidata Q2997928 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q2997928
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Component_(graph_theory)?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1375505358, consultata il 2026-10-15T13:56:59.558Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 0765641ad2d56f476622673284de57b2fbc6347f6062acdedf9d5aa7b4f85668