f: V → SV — распределение меток вершин,
g: E → SE — распределение меток ребер.
Пусть граф G=(V, E) помечен с помощью функций f и g, a
G1 =( V1, Е1) помечен с помощью f1 и g1. Графы G и G1 называются эквивалентно помеченными, если существует биекция h: V →V1, такая что
а) G и G1 эквивалентны как непомеченные графы;
б) f(v) = f1(h(v)) для всех v V, поэтому соответствующие вершины имеют одну и ту же пометку;
в) g([v, w]) = g1([h(v), h(w)]) для всех v, w V, т. e. соответствующие ребра имеют одну и ту же пометку.
Часто бывают помеченными только ребра или же только вершины. Вышесказанное применимо и в этом случае. Тогда
Ребра или вершины (или те и другие вместе) помеченного графа несут информацию, которая дополняет или заменяет обычную идентификацию с помощью имен.
Пример 2.
Пусть
V={ v1, v2, v3, v4), E={[ v1, v3], [v2, v3], [v3, v4]},
f: V → {города Великобритании}, g: E → N,
f (v1) — Лондон, g([ v1, v3])=105,
f(v2)- Кардифф, g([ v1, v3])=196,
f(v3) — Бирмингем, g([ v3, v4]) = 292,
f (v4) — Эдинбург.
Этот граф изображен на рис. 3.
Рис. 3.
Пусть графы
помечены так же, как указано на рис. 4; G1 и G2 являются эквивалентно помеченными графами (вершины не помечены).
Рис. 4
Определение.
а) Граф G = (V, E) называется полным, если для всех v1, v2 V
имеем [v1, v2] E. Полный граф с вершинами обозначается через Кп.
б) Граф G = (V, E) называется двудольным, если существует разбиение V = (V1, V2) такое, что никакие две вершины из V1 илп из V2 не являются смежными. Двудольный граф называется полным, если для любой пары v1 V1 и v2 V2 имеем [v1, v2] E. Если |V1|=m и
|V2|=n, то полный двудольный граф (V, Е) обозначается через Кт,п.
Маршруты, циклы и связность
Обратим сейчас внимание на понятие маршрута в графе. Значительная часть теории графов и ее приложений занимается вопросами существования и свойств маршрутов. Некоторые важные свойства вытекают из следующих определений.
Определение.
а) Пусть G = (V, E) — граф. Маршрутом длины k в графе G из v в w называется последовательность < v0, v1, ..., vk> вершин (необязательно различных) vi V таких, что v0 = v, vk = w, a
[vi-1, vi] Е для всех i = 1, ..., k. Маршрут называется замкнутым, если v0 = vk. Маршрут называется цепью, если все его вершины различны. Замкнутая цепь называется циклом. Цикл называется простым циклом, если только v0 = vk, а остальные vi различны.
б) Если существует маршрут из v в w, v, w V, то говорят, что w достижима из v.
в) Граф без циклов называется ациклическим.
Заметим, что понятие замкнутости, в сущности, соответствует своему названию.
Определение.
а) Граф G = (V, E) называется связным, если каждая пара различных вершин может быть соединена маршрутом.
б) Деревом называется связный ациклический граф.
в) Корневым деревом называется дерево с выделенной вершиной, называемой корнем.
г) Остовным деревом для G= (V, E) называется остовный подграф, являющийся деревом.
В 1.1 мы отметили, что вычисления с матрицей смежности обнаруживают важную информацию о природе графа. Следующие результаты являются примерами внутренних связей между алгеброй и топологией в теории графов.
В приведенной ниже теореме и ее следствиях степени Ak вычисляются в M(п, Z), а не в M(п, В). Следовательно, в Аk могут возникать числа, большие чем 1.
Теорема. Пусть А — матрица смежности графа G = (V, Е) и |V| = п. Тогда (Аk)ij есть число маршрутов длины k от vi к vj.
Доказательство. Будем использовать индукцию по k. Для k = 1 маршрут длины 1 как раз является ребром G. Следовательно, результат теоремы при k = 1 вытекает из определения А. Пусть
тогда
Пусть результат имеет место для k — 1. Тогда, если αiq — элементы матрицы Аk-1, то αiq — число маршрутов длины k — 1 от vi к vq; по определению αqj — число маршрутов длины 1 от vq к vj. Следовательно, αiqαqj — число маршрутов длины k из vi к vj, где vq есть предпоследняя вершина маршрута.
Отсюда следует, что
есть число маршрутов длины k от vi к vj. Это завершает доказательство.
Следствие.
а) Маршрут от vi к vj (i≠j) в G = (V, E) существует тогда и только тогда, когда (i, j)-й элемент матрицы порядка п×п (п = | V |):
А + А2 +... + Ап-1
не равен нулю.
б) Если не использовать условие i≠j, то требуемая матрица имеет вид
Доказательство.
А+А2 + ... + Ап-1 + Ап.
а) Пусть < vi, v1, ..., vj > — маршрут из vi в vj, в G. Если не существует повторяющихся вершин, то (так как | V| =n) маршрут содержит не более п —1 ребер, и необходимое утверждение следует из теоремы.
Пусть существует повторяющаяся вершина. Тогда маршрут имеет вид
Если мы удалил все такие замкнутые маршруты, то задача сведется к предыдущему случаю, когда вершины не повторялись. Таким образом,
в одну сторону требуемый результат получен. В обратную сторону рассуждения очевидны.
б) Если разрешается i=j, то существование маршрута из vi в vj влечет то, что существует последовательность < vi, v1, ..., vj >. Если не существует повторяющихся вершин (за исключением, возможно, случая vi = vj), тогда маршруты состоят из более чем п + 1 вершин (не более п ребер). Следовательно, (i, j)-й элемент матрицы не равен нулю. Тогда при |V|= n отсюда следует
Наломним, что для произвольного бинарного отношения R величина
R+ определялась как
и если R V×V при |V| = п, то отсюда следует, что
Аналогично
В этом параграфе для упрощения обозначений будем теперь обозначать А(Rk (Е)) через A(Rk), A(R+(E)) через A(R+), a A(R*(E)) через A(R*). Алгоритм Уоршолла требует 4n3 операций для определения A(R+), тогда как при помощи приведенных выше соотношений тре- буется 4n4 — 7п3 операций. Можно получить и другие еще более эффективные алгоритмы для больших зпачений п.
Матрицу C = A(R*) называют матрицей связи, связности или достижимости графа G = (V, Е). Маршрут из vi к vj (i≠j) существует в G тогда и только тогда, когда (i, j)-й элемент из С равен 1. Граф G является связным тогда и только тогда, когда Cіj = 1 для всех 1≤i, j ≤п. Важные свойства отношения R* могут быть сформулированы следующим образом.
Утверждение. R* — отношение эквивалентности на V.
Доказательство. Так как по определению R* является рефлексивным замыканием R, то необходимо только проверить симметричность R*. Выполнение vR*w влечет существование маршрута 1, ..., vk, w> от v к w в G, т. е.
Следовательно,
Таким образом,
k, vk-1, ..., v2, v1, v>
есть маршрут из w в v в G, откуда следует wR*v.
Отношение R* определяет важный класс подграфов, который сейчас будет определен. Будут также даны некоторые сопутствующие понятия; они будут важны при обсуждении «пересечения» графа.
Определение. Пусть {Vі: 1≤i≤p} — разбиение графа, определяемое отношением R*. Тогда говорят, что р —число связности G. Подграфы (Vі Еі), порожденные классами эквивалентности, называют компонентами связности графа G.
Достарыңызбен бөлісу: |
