Metraipolis › archive › dc_aed8103f8d65
Independent set (graph theory) — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Independent_set_(graph_theory)
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-06T12:51:44.331Z
- SHA-256 of the archived text
2bce0d1544c0048e4e46e33270fa9134b4fd41e25da7d9fd1f67339e8282ac19- Stable URL of this page
https://metraipolis.com/documento/dc_aed8103f8d65
How to cite
Independent set (graph theory) — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Independent_set_(graph_theory) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_aed8103f8d65 (Metraipolis archive dc_aed8103f8d65, sha256 2bce0d1544c0048e4e46e33270fa9134b4fd41e25da7d9fd1f67339e8282ac19)
BibTeX
@misc{dcaed8103f8d65,
title = {Independent set (graph theory) — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Independent_set_(graph_theory)},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_aed8103f8d65; sha256 2bce0d1544c0048e4e46e33270fa9134b4fd41e25da7d9fd1f67339e8282ac19},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Independent_set_(graph_theory). Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S {\displaystyle S} of vertices such that for every two vertices in S {\displaystyle S} , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in S {\displaystyle S} . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening. A maximal independent set is an independent set that is not a proper subset of any other independent set. A maximum independent set is an independent set of largest possible size for a given graph G {\displaystyle G} . This size is called the independence number of G {\displaystyle G} and is usually denoted by α ( G ) {\displaystyle \alpha (G)} . The optimization problem of finding such a set is called the maximum independent set problem. It is a strongly NP-hard problem. As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph. Every maximum independent set also is maximal, but the converse implication does not necessarily hold.
Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Independent set (graph theory)» — https://en.wikipedia.org/wiki/Independent_set_(graph_theory)
Wikidata Q1060343: «tipo di insieme in teoria dei grafi» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1060343
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Independent_set_(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 1374722467, consultata il 2026-10-06T11:07:58.652Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: fdd8b3c8fffe19791347878859d951a9dcfe5455aba91916cdcc40c61d583c5f