Collapsible graph

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

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

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

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

Литература

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