Графовая модель при описании конкретных объектов, процессов или явлений может быть расширена следующим образом.
1. Взвешивание дуг (ребер). Каждому ребру графа приписывается число - вес дуги (ребра). В частном случае ограничиваются случаем, когда вес дуги является неотрицательным числом. Вес может обозначать, например, расстояние между городами, если вершинам приписаны имена городов а ребрам - дороги между ними. Для описания взвешенного графа используется матрица смежности, в которой в ячейках записаны веса. Если особо не оговорено, то под взвешенным графом будем понимать такой граф.
2. Взвешивание вершин. Аналогично дугам веса приписываются вершинам. Например, вершинам составлены магазины и склады, тогда веса могут обозначать, например, количество некоторого товара на складе или в магазине.
3. Взвешивание дуг и/или вершин векторами. Взвешивание производится не числом, а набором чисел. Например, кроме расстояния для дороги могут быть указаны стоимость проезда, время в пути и т.д.
1. В графе допускается несколько “параллельных” дуг в одном и том же направлении между двумя вершинами. В этом случае говорят о кратных дугах, а такие графы называют мультиграфами. Для описания мультиграфов используются такие же таблицы, как и для простых графов, но в клетках записаны не 0 и 1, а кратность дуги.
2.В графе используется не бинарное, а r-арное отношение, где r больше 2. Такие графы называются гиперграфами. Для представления этих графов на плоскости вершины, которые относятся к одному ребру, объединяются замкнутыми линиями как на рис. 3. Здесь граф имеет три ребра:
(1, 2, 3), (1, 2, 4), (4, 5, 6). К таким графам приходят при описании логических сетей, когда элементы находятся в отношении, если они имеют полюса, связанные общей цепью.
Для графаG=<A,U> графH=<A,U’>называетсячастичнымграфом графаG,если в немU’ Í U.ГрафP=<A’,U’’>называютподграфомграфаG,еслиA’ Í AиU’’подмножество всех дуг изU,связанных с вершинами изА’.И, наконец, графQ=<A’,U*> ,гдеU*ÍU’’,называют частичным подграфомграфа G.
16 Двудольные графы.
Граф G=(V,X) называется двудольным, если существует разбиение V=V1UV2(V1пересечениеV2=непустое множество), такое, что никакие две вершины из Vi (i = 1, 2) не являются смежными. Обозначение: G = (V1UV2, X). Заметим, что двудольный Граф может быть несвязным.
Звездой называется полный двудольный графK1,n
Из определений видно, что граф Km,,n содержит тп ребер.
Теор. Граф является двудольным тогда и только тогда, когда все его простые циклы имеют четную длину.
Доказательство. Необходимость. Пусть G=(V,X) двудольный граф, тогда существует разбиение V=V1UV2 вершин графа, такое, что любое ребро графа инцидентноодной вершине из V1и одной вершине из V2. Пусть v1, v2, .... ,v1— последовательноcnm. вершин графа, соответствующая простому циклу. . Если v1 из V1, то вcе вершины этой последовательности с нечетными номерами принадлежат V1, а все вершины с четными номерами принадлежат Vг-Следовательно, число ребер в рассматриваемом простом цикле четно.
Достаточность. Заметим, что если в графе все простые циклы имеют четную длину, то и все замкнутые маршруты имеют четную длину (из произвольного замкнутого маршрута можно получить простой цикл, убирая из него последовательно простые циклы между соседними одинаковыми вершинами заданного маршрута, т.е., убирая четное число ребер). Предположим, что G - связный граф (для доказательства достаточно рассмотреть компоненту связности). Зафиксируем вершину v1 из V. Обозначим через V1 множество, состоящее из вершины v1 и всех вершин из V, находящихся на четном расстоянии от v1. Обозначим V2= VV1. Покажем, что каждое ребро графа G соединяет, вершину из V1, с вершиной из V2. Если ребро соединяет v с uи v,u из V1ьто найдутся цепи четной длины, соединяющие v1 c v и v1c u. Объединение этих цепей с ребром, соединяющим v с u, является замкнутым маршрутом нечетной длины.Противоречие. Ecли v,u еV2, то, в силу связности графа, существуют цепи, соединяющие v1 c v и v1 cи. Поскольку v,u не из V1, то эти цепи имеют нечетную дину. Объединениеэтих цепей с ребром, соединяющим v с u, является замкнутым маршрутом нечетной длины. Противоречие. Следовательно, граф G -двудольный.
Следствие. Двудольный граф не содержит треугольников (т.е. подграфов, изоморфных К3),
