Collapsible graph: различия между версиями

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

'''1.''' A ''cf-graph''<math>G</math> is called a '''collapsible''' one if

it can be transformed to a trivial one upon repeated application of

transformations <math>T_{1}</math> and <math>T_{2}</math>  desribed below.

Let <math>(n,n)</math> be an arc of <math>G</math>.

The transformation <math>T_{1}</math> is removal of this edge.

Let <math>n_{2}</math> not be the initial node and have a single predecessor,

<math>n_{1}</math>. The transformation <math>T_{2}</math> is the replacement of <math>n_{1}</math>, <math>n_{2}</math>

and <math>(n_{1},n_{2})</math> by a single node <math>n</math>. The predecessors of <math>n_{1}</math> become

the predecessors of <math>n</math>. The successors of <math>n_{1}</math> or <math>n_{2}</math> become

the successors of <math>n</math>. There is an arc <math>(n,n)</math> if and only if there was

formerly an edge <math>(n_{2},n_{1})</math> or <math>(n_{1},n_{1})</math>.

'''2.''' A graph <math>H</math> is called '''collapsible''' if for every even subset <math>S

\subseteq V(H)</math>, there is a subgraph <math>T</math> of <math>H</math> such that <math>H - E(T)</math>

is connected and the set of odd degree vertices of <math>T</math> is <math>S</math>.