independent set in a graph

独立集

Combinatorics · Undergraduate · Mathematics Resources editorial compilation (AI-assisted)

Other names / variants: stable set

Translation evidence: Literature usage

Meaning in context

An independent set in a simple graph is a vertex subset containing no adjacent pair of distinct vertices.

简单图的独立集是一个顶点子集，其中任意两个不同顶点均不相邻。

Example

In the path a−b−c−da-b-c-d, {a,c}\{a,c\} is an independent set.

Usage and distinctions

An independent set consists of vertices; a matching consists of edges with no common endpoints. Independence asserts no maximality.

Recommended reading in this subject · Preparation & skip guidance

Definition sources

  1. Keller and Trotter — Applied Combinatorics (2016)Section 14.2, opening description of the two independent vertex parts · Checked 2026-10-14

Translation sources

  1. 新疆大学 — 本科课程教学大纲汇编，图论（050762）PDF p.95 / printed p.94，图论课程四、第三部分，第七章「独立集和团」 · Checked 2026-10-14
Edit source / propose a PRReport a correction

Original encyclopedia and terminology content: CC BY-SA 4.0. Contribute or report a correction.