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

Перейти к навигации Перейти к поиску
нет описания правки
(Новая страница: «'''Collapsible graph''' --- разборный граф, складной граф. '''1.''' A ''cf-graph''<math>G</math> is called a '''collapsible''' one if it …»)
 
Нет описания правки
Строка 1: Строка 1:
'''Collapsible graph''' --- разборный  граф, складной граф.  
'''Collapsible graph''' — ''[[разборный  граф]], [[складной граф]]''.  


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


Let <math>(n,n)</math> be an arc of <math>G</math>.
Let <math>\,(n,n)</math> be an [[arc]] of <math>\,G</math>.
The transformation <math>T_{1}</math> is removal of this edge.
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,
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>
<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
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 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
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>.
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
'''2.''' A [[graph, undirected graph, nonoriented graph|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>
\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>.
is connected and the set of odd degree [[vertex|vertices]] of <math>\,T</math> is <math>\,S</math>.
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Навигация