Core: различия между версиями

'''Core''' — ''[[ядро]].''

'''1.''' Given a [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math>, a '''core''' of <math>\,G</math> is a [[subgraph]] <math>\,C</math> of <math>\,G</math> such

that <math>\,G</math> is ''[[homomorphism of a graph|homomorphic]]'' to <math>\,C</math>, but <math>\,C</math> fails to be homomorphic to any proper subgraph of <math>\,G</math>. This notion of a core is due to Hell and

Nešetřil (1992). A graph <math>\,G</math> is a '''core''' if <math>\,G</math> is a core

for itself. It is known, that in general, the problem of deciding whether <math>\,G</math> is a core is NP-complete, but there exists a polinomial time algorithm to decide if <math>\,G</math> is a core for the particular case when <math>\,G</math> has the ''[[independence number]]'' <math>\,\alpha(G) \leq 2</math>. Finally, it is known that "almost all graphs" are cores.

'''2.''' Let <math>\,\Omega(G)</math> denote the family of all maximum stable sets. Then

the '''core''' is defined as <math>\,core(G) = \cap \{S: \; S \in\Omega(G)\}</math>. Thus, the core is the set of [[vertex|vertices]] belonging to all maximum stable sets.

 

 

* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.