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 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

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]]'''.

 

 

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