(X,Y)-Графы пересечений: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''(<math>X,Y)</math>-Графы пересечений''' ((''<math>X,Y)</math>-Intersection graphs'') - Для пары <math>(X,Y)</ma...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''(<math>X,Y)</math>-Графы пересечений''' | '''(<math>X,Y)</math>-Графы пересечений''' (''[[(X,Y)-Intersection graphs|(<math>X,Y)</math>-Intersection graphs'']]) - Для пары <math>(X,Y)</math> заданных [[граф|графов]] <math>X</math> и <math>Y</math> под <math>(X,Y)</math>-графом [[пересечение графов|пересечений графа]] <math>G</math> понимается граф, [[вершина|вершины]] которого соответствуют различным индуцированным [[подграф|подграфам]] графа <math>G</math>, изоморфным <math>Y</math>, и где две [[смежные вершины|вершины смежны]], если пересечение соответствующих им подграфов содержит индуцированный подграф, изоморфный <math>X</math>. Это обобщает понятие ''[[реберный граф|реберного графа]]''. | ||
Для пары <math>(X,Y)</math> заданных графов <math>X</math> и <math>Y</math> под <math>(X,Y)</math>-графом | |||
пересечений графа <math>G</math> понимается граф, вершины которого соответствуют | |||
различным индуцированным подграфам графа <math>G</math>, изоморфным <math>Y</math>, и где | |||
две вершины смежны, если пересечение соответствующих им подграфов | |||
содержит индуцированный подграф, изоморфный <math>X</math>. Это обобщает понятие | |||
''реберного графа''. | |||
==Литература== | ==Литература== | ||
[J. Graph Theory] | [J. Graph Theory] | ||
Версия от 16:53, 13 октября 2009
([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]