Collapsible graph

Collapsible graph — разборный граф, складной граф.

1. A cf-graph [math]\displaystyle{ \,G }[/math] is called a collapsible one if it can be transformed to a trivial one upon repeated application of transformations [math]\displaystyle{ \,T_{1} }[/math] and [math]\displaystyle{ \,T_{2} }[/math] desribed below.

Let [math]\displaystyle{ \,(n,n) }[/math] be an arc of [math]\displaystyle{ \,G }[/math]. The transformation [math]\displaystyle{ \,T_{1} }[/math] is removal of this edge.

Let [math]\displaystyle{ \,n_{2} }[/math] not be the initial node and have a single predecessor, [math]\displaystyle{ \,n_{1} }[/math]. The transformation [math]\displaystyle{ \,T_{2} }[/math] is the replacement of [math]\displaystyle{ \,n_{1} }[/math], [math]\displaystyle{ \,n_{2} }[/math] and [math]\displaystyle{ \,(n_{1},n_{2}) }[/math] by a single node [math]\displaystyle{ \,n }[/math]. The predecessors of [math]\displaystyle{ \,n_{1} }[/math] become the predecessors of [math]\displaystyle{ \,n }[/math]. The successors of [math]\displaystyle{ \,n_{1} }[/math] or [math]\displaystyle{ \,n_{2} }[/math] become the successors of [math]\displaystyle{ \,n }[/math]. There is an arc [math]\displaystyle{ \,(n,n) }[/math] if and only if there was formerly an edge [math]\displaystyle{ \,(n_{2},n_{1}) }[/math] or [math]\displaystyle{ \,(n_{1},n_{1}) }[/math].

2. A graph [math]\displaystyle{ \,H }[/math] is called collapsible if for every even subset [math]\displaystyle{ \,S \subseteq V(H) }[/math], there is a subgraph [math]\displaystyle{ \,T }[/math] of [math]\displaystyle{ \,H }[/math] such that [math]\displaystyle{ \,H - E(T) }[/math] is connected and the set of odd degree vertices of [math]\displaystyle{ \,T }[/math] is [math]\displaystyle{ \,S }[/math].

Литература

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