Core

Материал из WikiGrapp
Перейти к:навигация, поиск

Coreядро.

1. Given a graph \,G, a core of \,G is a subgraph \,C of \,G such that \,G is homomorphic to \,C, but \,C fails to be homomorphic to any proper subgraph of \,G. This notion of a core is due to Hell and Nešetřil (1992). A graph \,G is a core if \,G is a core for itself. It is known, that in general, the problem of deciding whether \,G is a core is NP-complete, but there exists a polinomial time algorithm to decide if \,G is a core for the particular case when \,G has the independence number \,\alpha(G) \leq 2. Finally, it is known that "almost all graphs" are cores.

2. Let \,\Omega(G) denote the family of all maximum stable sets. Then the core is defined as \,core(G) = \cap \{S: \; S \in\Omega(G)\}. Thus, the core is the set of vertices belonging to all maximum stable sets.

Литература

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