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

Cтраница 1

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

Двудольный граф называется полным, если любая вершина х ( Xi смежна каждой вершине у е Х2, и наборот. [2]

Любой двудольный граф бихроматичен. [3]

Двудольный граф Cpq называется полным, если все р вершин связаны со всеми q вершинами. [4]

Двудольный граф G - это граф, множество вершин V которого можно разбить на два подмножества Va и Vb таким образом, что каждое ребро графа G соединяет вершины из разных множеств. Если при этом граф G содержит все ребра, соединяющие множества Vа и Fb, то этот граф называют полным двудольным. На рис. 2.3, а приведен пример полного двудольного графа, называемого графом Кенига. Если при этом граф G содержит все ребра, соединяющие подмножества Vt, Vj, i. [5]

Построим двудольный граф, соединяя г - и с-в том и только том случае, когда элемент m - j матрицы М отличен от нуля. [6]

Построим двудольный граф Н - ( V ( G) B) из графа G, добавляя по одной новой вершине на каждом ребре графа G. Новые вершины образуют множество В. Далее, продолжим функцию / на Я, положив / 1 для каждой из этих новых вершин. [7]

Образовать двудольный граф С ( X1 [ X, А), где X - множество вершин, каждая из которых соответствует некоторой области Ф, и А - множество дуг, такое, что дуга между областью-вершиной и вершиной XI существует тогда и только тогда, когда XI может быть достигнута из этой области. [8]

Начертить двудольный граф для отношения а А, где Л пробегает все подмноя ества множества V из 3 или 4 элементов. [9]

Начертить двудольный граф для отношения а - А, где А пробегает все подмножества множества V из 3 или 4 элементов. [10]

Образовать двудольный граф G ( X U X, А), где X - множество вершин, каждая из которых соответствует некоторой области Ф, и А - множество дуг, такое, что дуга между областью-вершиной и вершиной Xi существует тогда и только тогда, когда Xi может быть достигнута из этой области. [11]

Строим двудольный граф G ( V, V), где V есть множество вершин для G, a V - множество из k цветов. Для любого конечного множества F с: V определяется выбирающая функция при помощи такой раскраски вершин графа G ( F), что соединенные ребром вершины имеют различные цвета. [12]

Строим двудольный граф G ( V, V), где Уесть множество вершин для G, a V - множество из k цветов. Для любого конечного множества FcV определяется выбирающая функция при помощи такой раскраски вершин графа G ( F), что соединенные ребром вершины имеют различные цвета. [13]

Декомпозиция Далмеджа - Мендельсона двудольного графа. [14]

Рассмотрим теперь произвольный двудольный граф G. В силу теоремы 3.2.5 подграф G [ C U 6 2 ] имеет совершенное паросочетание и поэтому мы можем применить полученные нами результаты о разложении двудольных графов. [15]

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