Contraction of an even pair: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
(Новая страница: «'''Contraction of an even pair''' --- стягивание четной пары. The '''contraction of an even pair''' <math>(u,v)</math> is an operation that co…»)
 
Нет описания правки
 
Строка 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'''.

Навигация