Contraction of an even pair: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Contraction of an even pair''' --- стягивание четной пары. The '''contraction of an even pair''' <math>(u,v)</math> is an operation that co…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Contraction of an even pair''' | '''Contraction of an even pair''' — ''[[стягивание четной пары]].'' | ||
The '''contraction of an even pair''' <math>(u,v)</math> is an operation that consists in replacing | The '''contraction of an even pair''' <math>\,(u,v)</math> is an operation that consists in replacing the two [[vertex|vertices]] <math>\,u, v</math> by a unique vertex <math>\,t</math> whose ''[[neighbourhood of a vertex|neighborhood]]'' is <math>\,N_{G}(u) \cup N_{G}(v) - \{u,v\}</math>: the resulting [[graph, undirected graph, nonoriented graph|graph]] is denoted by <math>\,G_{uv}</math>. Contracting an even pair preserves the ''[[chromatic number]]'' and ''[[clique number]]''. Thus, successive contraction of even pairs could possibly be used to reduce a given graph <math>\,G</math> to a smaller, [[simple graph|simpler graph]] with the same parameters <math>\,\chi</math> and <math>\,\omega</math>. In the case where the final graph is a ''[[clique graph|clique]]'', <math>\,G</math> is called '''even contractile'''; whenever this reduction | ||
the two vertices <math>u, v</math> by a unique vertex <math>t</math> whose ''neighborhood'' is <math>N_{G}(u) \cup N_{G}(v) - \{u,v\}</math>: the resulting | can be performed not only for the graph <math>\,G</math> itself, but also for every one of its induced [[subgraph|subgraphs]], <math>\,G</math> is called '''[[perfectly contractile graph|perfectly contractile]]'''. | ||
graph is denoted by <math>G_{uv}</math>. Contracting an even pair preserves the ''chromatic number'' and ''clique number''. Thus, | |||
successive contraction of even pairs could possibly be used to reduce | ==Литература== | ||
a given graph <math>G</math> to a smaller, simpler graph with the same parameters | |||
<math>\chi</math> and <math>\omega</math>. In the case where the final graph is a ''clique'', <math>G</math> is called '''even contractile'''; whenever this reduction | * Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | ||
can be performed not only for the graph <math>G</math> itself, but also for every | |||
one of its induced subgraphs, <math>G</math> is called '''perfectly contractile'''. | |||
Текущая версия от 18:43, 2 февраля 2016
Contraction of an even pair — стягивание четной пары.
The contraction of an even pair [math]\displaystyle{ \,(u,v) }[/math] is an operation that consists in replacing the two vertices [math]\displaystyle{ \,u, v }[/math] by a unique vertex [math]\displaystyle{ \,t }[/math] whose neighborhood is [math]\displaystyle{ \,N_{G}(u) \cup N_{G}(v) - \{u,v\} }[/math]: the resulting graph is denoted by [math]\displaystyle{ \,G_{uv} }[/math]. Contracting an even pair preserves the chromatic number and clique number. Thus, successive contraction of even pairs could possibly be used to reduce a given graph [math]\displaystyle{ \,G }[/math] to a smaller, simpler graph with the same parameters [math]\displaystyle{ \,\chi }[/math] and [math]\displaystyle{ \,\omega }[/math]. In the case where the final graph is a clique, [math]\displaystyle{ \,G }[/math] is called even contractile; whenever this reduction can be performed not only for the graph [math]\displaystyle{ \,G }[/math] itself, but also for every one of its induced subgraphs, [math]\displaystyle{ \,G }[/math] is called perfectly contractile.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.