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

Cтраница 3

Здесь мы сосредоточим внимание на трех классах графов - на классе полных графов, полных двудольных графов и кубов - и укажем для них известные значения названных выше инвариантов. [31]

К доказательству леммы 5. [32]

В условии леммы 5 специально выделено, что графы из Жр п р, симметрическая разность которых описывается как полный двудольный граф, не обязательно различны. [33]

Докажите, что сумма характеристических чисел простого графа равна нулю, и проиллюстрируйте это на примере полных графов и полных двудольных графов. [34]

Пусть Q - связный двудольный ( / п, / г) - грэф; / 0 t / t - полный двудольный граф. [35]

Доказать, что циклические матроиды М ( / С6) и М ( К3 3), где / С5 - полный граф на пяти вершинах, а / С3 з - полный двудольный граф ( рис. 6.1), являются графическими, но не кографическими. [36]

Если мы хотим сконструировать максимальный m - простой граф, то для графов типа I это сделать легко, так как при фиксированных п и m все такие графы изоморфны: из полного двудольного графа Кп п достаточно удалить п - т 1 ребер, инцидентных одной отмеченной вершине. [37]

Следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из Vi соединена с каждой вершиной из V2; если же это так и если при этом граф G простой, то он называется полным двудольным графом и обычно обозначается Кт п где тип - число вершин соответственно в Vi и К2 - Например, на рис. 3.8 изображен граф / С4 3, а на рис. 2.5 - два варианта графа Кз з - Заметим, что граф Кт п имеет ровно т - f n вершин и тп ребер. [38]

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

Разбиение ребер графа и совершенное паросочетание - понятия идентичные. Поэтому многогранник М есть выпуклая оболочка совершенных паросочетаний полного двудольного графа, причем характеристические векторы х таких паросочетаний записаны в форме матрицы, у которой строки отвечают вершинам одной доли графа / С л, а столбцы - второй. [40]

Обозначим через f ( n v) наибольшее из чисел &, для которых верно утверждение: если я-связный граф G имеет v вершин и 1 -фактор, то G имеет по крайней мере k ( различных) 1 -факторов. Пусть В - ( п, k) - граф, полученный из полного двудольного графа Кп, n 2k в результате добавления k попарно несмежных ребер, причем концевые вершины новых ребер лежат в множестве из п 2& вершин. Граф B ( n k) я-свя-зен и имеет п 1 -факторов. [41]

Двудольным называется граф, множество вершин которого можно разбить на два непустых подмножества ( на две доли) Vi и Т / 2 таким образом, что никакие две вершины из одной и той же доли не являются смежными. Если каждая вершина из Vi смежна с каждой вершиной из Vb, то двудольный граф называется полным двудольным графом. [42]

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

Задача, состоящая в выяснении того, какие графы имеют хроматический класс р, а какие р 1, не решена; однако в некоторых частных случаях соответствующие результаты находятся легко. Например, у е ( Сп) - 2 или 3 в зависимости от того, четно п или нечетно, а хе ( п) - п - 1 ( при п 4); как мы сейчас покажем, хроматические классы полных графов и полных двудольных графов вычисляются тоже довольно просто. [44]

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

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