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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Core''' --- ядро. '''1.''' Given a graph <math>G</math>, a '''core''' of <math>G</math> is a subgraph <math>C</math> of <math>G</math> such that <math>G</ma…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Core''' --- ядро.  
'''Core''' — ''[[ядро]].''


'''1.''' Given a graph <math>G</math>, a '''core''' of <math>G</math> is a subgraph <math>C</math> of <math>G</math> such
'''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 '' homomorphic'' to <math>C</math>, but <math>C</math> fails to be homomorphic
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
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
Ne\u{s}et\u{r}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.
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
'''2.''' Let <math>\,\Omega(G)</math> denote the family of all maximum stable sets. Then
the '''core''' is defined as <math>
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.
core(G) = \cap \{S: \; S \in
 
\Omega(G)\}</math>. Thus, the core is the set of vertices belonging to all
==Литература==
maximum stable sets.
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия от 12:25, 7 февраля 2017

Coreядро.

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

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

Литература

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