В теории графов , то двудольный половина или половина-квадрат из двудольный граф G = ( U , V , E ) называется граф, множество вершин является одной из двух сторон двудольности ( без потери общности , U ) , и в которой существует ребро у я у J для каждых двух вершин у я и у J в U , которые находятся на расстоянии два друг от друга в G . [1] То есть в более компактных обозначениях двудольная половинаG 2 [ U ], где верхний индекс 2 обозначает квадрат графа, а квадратные скобки обозначают индуцированный подграф .
Примеры
Например, двудольная половина полного двудольного графа K n , n - это полный граф K n, а двудольная половина графа гиперкуба - это разрезанный пополам граф куба . Когда G - дистанционно регулярный граф , обе его двудольные половины дистанционно регулярны. [2] Например, разрезанный пополам граф Фостера является одним из конечного числа дистанционно регулярных локально линейных графов шестой степени . [3]
Представленность и твердость
Каждый график - двудольная половина другого графа, образованная разделением ребер графа. на двухсторонние пути. В более общем плане представлениекак двудольная половину можно найти, взяв любую клику край крышки оти заменяя каждую клику звездой . [4] Каждое представление возникает таким образом. Поскольку найти наименьшее покрытие ребер клики NP-сложно, так же и найти граф с наименьшим числом вершин, для которогоэто двудольная половина. [5]
Особые случаи
На карте графики , то есть пересечение графиков интерьера-непересекающихся односвязных областей в плоскости, в точности двухсторонние половинки двудольных плоских графов . [6]
Смотрите также
Рекомендации
- ^ Уилсон, Робин Дж. (2004), Разделы алгебраической теории графов , Энциклопедия математики и ее приложений, 102 , Cambridge University Press, стр. 188, ISBN 9780521801973.
- ^ Чихара, Лаура; Stanton, Dennis (1986), "схема ассоциации и квадратичные преобразования для ортогональных многочленов", Графы и комбинаторика , 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, 138 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. : 1-13: 15, DOI : 10,4230 / LIPIcs.MFCS.2019.13
- ^ Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , У. Х. Фриман , ISBN 0-7167-1045-5, Проблема GT59.
- ^ Чен, Чжи-Чжун; Гриньи, Микеланджело; Пападимитриу, Христос Х. (2002), «Графики карт», Журнал ACM , 49 (2): 127–138, arXiv : cs / 9910013 , doi : 10.1145 / 506147.506148 , MR 2147819 , S2CID 2657838.