Дискретная математика

123 Объединением графов Gi=(Vj,Xi) и G2=(V2,X^ н^ыв а е т с я граф, множеством вершин которого является ~V=VjuV2, а множеством рёбер является X ^ X / u X j . Граф G^(V,X) называется двудольным, если существует разбиение множества его вершин на два непересекающихся подмножества У/ и F, так, что К=К/СУКги каждое ребро графа G соединяет вершины из разных множеств. Двудольный граф называется полньш двудольньш графом, если любая вершина из F/ соединена ребром с каждой вершшюй из К?, следовательно, каждая вершина из V2 соединена ребром с каждой вершиной из Vj. Если \Vi\'=m и '\V2\=n, то полный двудольный граф обозначается через На рис. 5-6, а) приведён пример полного двудольного графа S(VI)=={V2, V4}; S(V2) = {v,, V3, УЛ/ S(V4) = {V,, V2, Vj}. V] уз a) 6) Рис. 5.6 Многие фафы являются разреженными, т.е. число их ребер много меньше максималыю возможного числа рёбер. В этом случае .чучше задать граф с помощью списков смежностей вершин. При задании списков смежностей вершш1. для каждой вершины veV графа G=(V,X) выписывается множество S(v) (S(v)cV) вершин, смежных с v, см. рис. 5.6, б). Размер этого представления зависит от суммы длин списков. Каждое ребро вносит вершину в два списка, поэтому сумма длин списков содержит 21а'| элементов. Недостатком задания графов с помощью списков смежностей вершин является выяснение, соединены ли заданные вершины v и и ребром, ибо приходится просматривать весь список S(v) в поисках и. В случае, когда число ребер графа сравнимо с п' (п = I к | ) удобнее задавать граф матрицей смежности, которая будет введена в дальнейшем. Обобщением понятия графа является гиперграф H(VX), когда задается множество V вершин и множество X «ребер», которые являются некоторы\1и подмножествами множества К, эти подмножества могут содержать произвольное число элементов из V. Для графа ребра зада{отся двумя и только двумя вершинами, а в гиперграфе - произвольным числом элементов из V. Пусть, например, задано множество, состоящее из девяти вершин У=[^и V2,..., vp} И шести «ребер»: X = {xj,x j Хб}, где .х, = {vj. v^, .1-2 = {vj, V2, V.?, V,}, X3 = {V2, Vj}, X4 = {vc, vg), -Vj = {Vj. V7. V4-}, .xe = {vj}. В результате получили гиперграф H(V.X), изображенный на рис. 5.7, а;).