Magnet in a graph

Материал из WikiGrapp
Версия от 17:04, 31 мая 2011; Glk (обсуждение | вклад) (Новая страница: «'''Magnet in a graph''' --- магнит в графе. A '''magnet''' in a graph <math>G = (V,E)</math> is defined as a pair <math>(a,b)</math> of adjacent vertic…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Magnet in a graph --- магнит в графе.

A magnet in a graph [math]\displaystyle{ G = (V,E) }[/math] is defined as a pair [math]\displaystyle{ (a,b) }[/math] of adjacent vertices with the same weight and such that each vertex in [math]\displaystyle{ N_{G}(a) \setminus N_{G}(b) }[/math] is adjacent to each vertex in [math]\displaystyle{ N_{G}(b) \setminus N_{G}(a) }[/math]. In other words, the two endpoints of an edge induce a magnet in a graph [math]\displaystyle{ G }[/math] if and only if this edge is not the middle edge of any [math]\displaystyle{ P_{4} }[/math] in [math]\displaystyle{ G }[/math].