Contraction of an even pair

Материал из WikiGrapp
Версия от 13:34, 15 марта 2011; Glk (обсуждение | вклад) (Новая страница: «'''Contraction of an even pair''' --- стягивание четной пары. The '''contraction of an even pair''' <math>(u,v)</math> is an operation that co…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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.