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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''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.

Версия от 10:46, 24 октября 2018

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.