Просмотр кода страницы 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.