Collapsible graph

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

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.