Project Links Logo Artwork
Graph Theory: Industrial Drilling
Home > Graph Theory: Industrial Drilling > Solving the Drilling Problem > Independent Sets, Cliques, etc.
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

Independent Sets, Cliques, etc.

  1. A set of vertices is called independent if no two vertices in the set are adjacent.
  2. A set of vertices is called a clique if every pair of vertices in the set is adjacent.
  3. An independent set (resp. a clique) is called maximal if no other independent set (resp. clique) contains it.
  4. An independent set (resp. a clique) is called maximum if its cardinality is maximal among all independent sets (resp. clique) in the graph.
  5. (resp. ) denotes the maximum size of an independent set (resp. a clique) in a graph .
  6. A set of edges in a graph is called a matching if no two of them are incident to the same vertex. denotes the maximum size of a matching in a graph .
 
 
go backgo forward
go backgo forward