(X,Y)-Графы пересечений

Материал из WikiGrapp
Версия от 17:01, 8 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''(<math>X,Y)</math>-Графы пересечений''' ((''<math>X,Y)</math>-Intersection graphs'') - Для пары <math>(X,Y)</ma...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

([math]\displaystyle{ X,Y) }[/math]-Графы пересечений (([math]\displaystyle{ X,Y) }[/math]-Intersection graphs) - Для пары [math]\displaystyle{ (X,Y) }[/math] заданных графов [math]\displaystyle{ X }[/math] и [math]\displaystyle{ Y }[/math] под [math]\displaystyle{ (X,Y) }[/math]-графом пересечений графа [math]\displaystyle{ G }[/math] понимается граф, вершины которого соответствуют различным индуцированным подграфам графа [math]\displaystyle{ G }[/math], изоморфным [math]\displaystyle{ Y }[/math], и где две вершины смежны, если пересечение соответствующих им подграфов содержит индуцированный подграф, изоморфный [math]\displaystyle{ X }[/math]. Это обобщает понятие реберного графа.

Литература

[J. Graph Theory]