Двусторонняя половина
В теории графов двудольная половина или полуквадрат двудольного графа G = ( U , V , E ) — это граф которого , множество вершин является одной из двух сторон двудольного деления ( без ограничения общности , U ) и в котором существует ребро u i u j для каждой пары вершин u i , u j в U , которые находятся на расстоянии двух друг от друга в G . [1] То есть в более компактных обозначениях двудольная половина — это G 2 [ U ] , где верхний индекс 2 обозначает квадрат графа , а квадратные скобки обозначают индуцированный подграф .
Примеры
[ редактировать ]Например, двудольная половина полного двудольного графа Kn , , n — это полный граф Kn половинный а двудольная половина графа гиперкуба — это граф куба .Когда G — дистанционно регулярный граф , две его двудольные половины являются дистанционно регулярными. [2] Например, половинный граф Фостера является одним из конечного числа дистанционно регулярных локально линейных графов степени 6 . [3]
Представление и твердость
[ редактировать ]Каждый граф G является двудольной половиной другого графа, образованной разделением ребер G на пути с двумя ребрами. В более общем смысле представление G взяв любое покрытие ребер клики G как двудольной половины можно найти , и заменив каждую клику звездочкой . [4] Таким образом возникает всякое представление. Поскольку найти наименьшее покрытие ребер клики NP-сложно, то же самое относится и к поиску графа с наименьшим количеством вершин, для которого G является двудольной половиной. [5]
Особые случаи
[ редактировать ]Графы карт , то есть графы пересечений внутренне непересекающихся односвязных областей на плоскости, представляют собой в точности двудольные половины двудольных плоских графов . [6]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Уилсон, Робин Дж. (2004), Темы алгебраической теории графов , Энциклопедия математики и ее приложений, том. 102, Издательство Кембриджского университета, стр. 102. 188, ISBN 9780521801973 .
- ^ Чихара, Лаура; Стэнтон, Деннис (1986), «Схемы ассоциаций и квадратичные преобразования для ортогональных полиномов», Graphs and Combinatorics , 2 (2): 101–112, doi : 10.1007/BF01788084 , MR 0932118 , S2CID 28803214 .
- ^ Хираки, Акира; Номура, Казумаса; Судзуки, Хироши (2000), «Дистанционно-регулярные графы валентности 6 и ", Журнал алгебраической комбинаторики , 11 (2): 101–134, doi : 10.1023/A:1008776031839 , MR 1761910
- ^ Ле, Хоанг-Оан; Ле, Ван Банг (2019), «Ограниченные представления графов карт и полуквадратов», Россманит, Питер; Хеггернес, Пинар; Катоен, Йост-Питер (ред.), 44-й Международный симпозиум по математическим основам информатики, MFCS 2019, 26–30 августа 2019 г., Ахен, Германия , LIPIcs, vol. 138, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 13: 1–13: 15, doi : 10.4230/LIPIcs.MFCS.2019.13 , ISBN 9783959771177
- ^ Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455 . МР 0519066 . OCLC 247570676 . , Задача GT59.
- ^ Чен, Чжи-Чжун; Гриньи, Микеланджело; Пападимитриу, Христос Х. (2002), «Карта графиков», Журнал ACM , 49 (2): 127–138, arXiv : cs/9910013 , doi : 10.1145/506147.506148 , MR 2147819 , S2CID 2657838 .
