Интервальная размерность графа: различия между версиями

[отпатрулированная версия][отпатрулированная версия]
Содержимое удалено Содержимое добавлено
Нет описания правки
Строка 7:
На фигуре показан граф с шестью вершинами и представление этого графа в виде графа пересечений (обычных двумерных) прямоугольников. Этот граф нельзя представить в виде графа пересечений прямоугольников меньшей размерности (в данном случае – отрезков), так что интервальная размерность графа равна двум.
 
Робертс {{sfn|Roberts|1969}} показал, что граф с 2''n'' вершинами, образованный удалением [[Паросочетание|совершенного паросочетания]] из [[Полный граф|полного графа]] с 2''n'' вершинами, имеет интервальную размерность в точности ''n'' — любая пара несоединённых вершин должна быть представлена в виде гиперпрямоугольников, которые должны быть разделены в отличной от другой пары размерности. Представление этого графа в виде гиперпрямоугольников с размерностью в точности ''n'' можно найти путём утолщения каждой из 2''n'' граней ''n''-мерного [[гиперкуб]]а в гиперпрямоугольник. Вследствие этого результата такие графы начали называться ''графами Робертса'' <ref>Например, см. статьи Чандрана, Фрэнсиса и Сивадасана ({{harvtxt|Chandran|Francis|Sivadasan|2010}}), Чандрана и Сивадасана {{harvtxt|Chandran|Sivadasan|2007}}.</ref>, хотя они более известны как '''графы «вечеринки»''' и их можно трактовать также как [[Граф Турана|графы Турана]] ''T''(2''n'',''n'').
 
==Связь с другими классами графов ==