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

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

Текущая версия от 10:04, 31 мая 2011

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].