Полный двудольный граф

Cтраница 2

Граф Томсена является примером полного двудольного графа. Более того, каждая вершина из и соединена с каждой вершиной из V единственным звеном. [16]

Обозначим через Km, n полный двудольный граф на множествах из га и п вершин, т.е. граф с ребрами, соединяющими всевозможные пары вершин, из которых одна принадлежит одному множеству, а вторая - другому. Через Dmtn обозначим изображение графа Km, n, т.е. его отображение на плоскость, при котором вершинам сопоставляются точки плоскости a, bj ( l i n, 1 / га), называемые узлами, а ребрам - жордановы кривые конечной длины ( дуги), ограниченные соответствующими узлами. Изображение будем называть хорошим, если никакие две дуги не имеют более одной общей точки и эта общая точка есть либо узел, ограничивающий каждую из этих дуг, либо скрещивание. Будем говорить, что две дуги at-bj, akbt ( i Ф k, j Ф l) скрещиваются, если дугу aibj можно замкнуть кривой, соединяющей и с bj, не пересекающейся с a bi и такой, что дуга a bi имеет точки как внутри, так и вне этой замкнутой кривой. [17]

Пример двудольного графа с совершенным паросочетанием. Можно предложить и более точный алгоритм поиска совершенного паросочетания, лишенный недостатков первого алгоритма. Второй алгоритм найдет совершенное паросочетание в графе, составленном из двух полных двудольных графов, как описано выше. Второй алгоритм находит такие наборы их k вершин в каждой из долей, которые имеют ребра в совокупности точно с k вершинами другой доли. Поиск таких наборов начинается с kl. Если вершина первой степени ( висячая существует в двудольном графе, то она вместе с соединенной с ней вершиной ( не обязательно первой степени составят пару для совершенного паросочетания и будут удалены из графа вместе со всеми своими ребрами. После удаления всех висячих вершин, если они есть, наличие такого набора при k2 будет означать, что существует две вершины второй степени, соединенных с двумя вершинами другой доли. [18]

Цепочка соединит вершины третьей степени полных двудольных графов. Получим двудольный граф, в каждой доле которого по восемь вершин. Совершенное паросочетание в этом графе существует - это два крайних ребра соединительной цепочки и по три ребра из каждого из полных двудольных графов. [19]

Барьер X, строго содержащийся в множестве A ( G. [20]

Клешня есть индуцированный подграф, изоморфный полному двудольному графу KI - He содержащие клешней графы будут изучаться в связи с вершинной упаковкой в разд. [21]

Например, графом, дополнительным к полному двудольному графу Kp q, будет граф Кр Kq - граф, состоящий из двух полных подграфов на двух непересекающихся подмножествах по р и q вершин, соответственно. [22]

Латинский квадрат также может быть представлен как полный двудольный граф G, в котором каждое множество вершин имеет п элементов, а каждая вершина из У соединена ребрами со всеми вершинами из V, и наоборот. [23]

Лемма 2 дает возможность определить толщину некоторых полных двудольных графов. [24]

Двудольным турниром называется орграф, полученный из полного двудольного графа приписыванием направления каждому ребру. [25]

Но частичная геометрия ( п, 2 1) есть полный двудольный граф, и значит, двойственная ей ( 2, л, 1) с необходимостью есть п X я-квадратная решетка. [26]

В этом разделе описываются реберные графы деревьев, полных графов и полных двудольных графов. [27]

Следующая теорема устанавливает связь между базисами транспортного многогранника и остовными деревьями соответствующего полного двудольного графа. [28]

Заметим, что при фиксированном р полный граф Сп - можно разложить на полный двудольный граф Ср, п р, в котором остальные ребра исключены. [29]

Если С - двудольный граф, то iya0p0, а равенство достигается только для полных двудольных графов. [30]

Страницы: 1 2 3 4