2-Switch

Материал из WEGA
Перейти к навигации Перейти к поиску

2-Switch --- 2-переключение.

A 2-switch in a simple graph [math]\displaystyle{ G }[/math] is the replacement of a pair of edges [math]\displaystyle{ xy }[/math] and [math]\displaystyle{ zw }[/math] in [math]\displaystyle{ G }[/math] by the edges [math]\displaystyle{ yz }[/math] and [math]\displaystyle{ wx }[/math], given that [math]\displaystyle{ ez }[/math] and [math]\displaystyle{ wx }[/math] were not present in [math]\displaystyle{ G }[/math] originally.

The switch operation is addition or deletion of an edge whose endpoints have the same degree. Graphs [math]\displaystyle{ H }[/math] and [math]\displaystyle{ H' }[/math] are switch equivalent, if there is a sequence of switches transforming [math]\displaystyle{ H }[/math] to [math]\displaystyle{ H' }[/math].