Core: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''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…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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 | ||
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.