Теория графов. 02 Теория графов. 2. теория графов общие понятия теории графов
 Скачать 1.41 Mb.
|
|
Определения Диаметром графа G называется величина ) , ( max ) ( , w v d G d V w v ∈ = Пусть V v ∈ Максимальным удалением (эксцентриситетом) в графе G от вершины v называется величина ) , ( max ) ( w v d v r V w ∈ = Радиусом графа G называется величина ) ( min ) ( v r G r V v ∈ = Центром графа G называется любая вершина V w∈ такая, что ) ( ) ( G r w r = Замечание.Приведенные метрические характеристики (диаметр, эксцентриситет, центр, радиус) определяются и в орграфе. Пусть ) , ( X V D = орграф, V v ∈ – некоторая вершина, V V ⊆ 1 Обозначим } ) , ( | { ) ( X w v V w v D ∈ ∈ = – образ вершины v; 19 } ) , ( | { ) ( 1 X v w V w v D ∈ ∈ = − – прообраз вершины v; U 1 ) ( ) ( 1 V v v D V D ∈ = – образ множества вершин V 1 ; U 1 ) ( ) ( 1 1 1 V v v D V D ∈ − − = – прообраз множества вершин V 1 Замечание.В графе G образ и прообраз вершины совпадают. Определение.Нагруженный граф – граф G = (V, X) (D = (V, X)), на множестве ребер (дуг) которого определена некоторая функция → X u : R, которую называют весовой функцией. Пример Пусть D = (V, X) – нагруженный орграф (рис. 2.14). Цифра над дугой обозначает вес дуги. Рис. 2.14. Пример нагруженного графа Для любого пути П нагруженного орграфа D через l(П) обозначаем сумму длин дуг, входящих в путь П. (Каждая дуга считается столько раз, сколько раз она входит в путь П). Введем матрицу длин дуг C(D) = [c ij ] порядка n, причем ( ) ( ) ( ) ∉ ∞ ∈ = , , , , , , X v v X v v v v u c j i j i j i ij Величина u называется длиной пути. Если выбрать веса равными 1, то придем к ненагруженному графу. Определение. Путь в нагруженном орграфе из вершины v в вершину w, где v ≠ w, называется минимальным, если он имеет наименьшую длину. Замечание.Аналогично определяется минимальный маршрут в нагруженном неориентированном графе. 20 Заметим, что иногда веса дуг (ребер) могут быть отрицательными . При этом важно знать, есть ли контуры (циклы) отрицательного веса. Если из вершины v i можно добраться до контура (цикла) отрицательного веса, то потом можно его обходить сколь угодно долго, и вес будет все уменьшаться, так что для вершин этого контура (цикла) кратчайших путей (маршрутов) не существует. Свойства минимальных путей (маршрутов) в нагруженном графе 1. Если для любой дуги (ребра) X x ∈ , 0 ) ( > x u , то любой минимальный путь (маршрут) является простой цепью. 2. Если k v v v ,..., , 2 1 минимальный путь (маршрут), то для любых i, j: k j i ≤ ≤ ≤ 1 путь (маршрут) j j i i v v v v 1 1 − + тоже является минимальным. 3. Если pw v... – минимальный путь (маршрут) среди путей (маршрутов) из v в w, содержащих не более k + 1 дуг (ребер), то p v... – минимальный путь (маршрут) из v в p среди путей (маршрутов), содержащих не более k дуг (ребер). Деревья Определение.Граф G называется деревом, если он является связным и не имеет циклов. Определение.Граф G называется лесом, если все его компоненты связности – деревья. Следующие утверждения эквивалентны: 1. Граф G есть дерево. 2. Граф G является связным и число его ребер ровно на 1 меньше числа вершин. 3. ∀ две различные вершины графа G можно соединить единственной (и при этом простой) цепью. 4. Граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один и притом простой цикл. 21 Утверждение 4 Если у дерева G имеется, по крайней мере, одно ребро, то у него найдется висячая вершина. Утверждение 5 Пусть G – связный граф, а v – висячая вершина в G, граф G′ получается из G в результате удаления вершины v и инцидентного ей ребра. Тогда G′ тоже является связным. Определение.Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом. Пусть G – связный граф. Тогда остовное дерево графа G должно содержать n(G) – 1 ребер. Значит, для получения остовного дерева из графа G нужно удалить ( ) 1 ) ( − − n G m ребер. Определение. Число 1 ) ( ) ( ) ( + − = G n G m G v называется цикломатическим числом графа G. Теорема Кирхгофа. Число остовных деревьев в связном графе G порядка 2 ≥ n равно алгебраическому дополнению любого элемента матрицы Кирхгофа. Пример Рассмотрим граф G на рис. 2.15. Рис. 2.15. Пример графа для нахождения количества остовных деревьев Матрица Кирхгофа для этого графа имеет вид = K − − − − − − − − 2 1 1 0 1 3 1 1 1 1 2 0 0 1 0 1 4 3 2 1 4 3 2 1 v v v v v v v v 22 Найдем алгебраическое дополнение элемента 11 K 3 2 1 1 1 3 1 1 1 2 11 = − − − − − − = K Действительно, у графа G три остовных дерева: Рис. 2.16. Остовные деревья графа, показанного на рис. 2.15 Определения Ориентированным деревомназывается орграф без циклов, во все вершины которого, кроме одной, входит ровно одна дуга. Единственная вершина, из которой дуги только выходят, называется корнем дерева. Остальные вершины называются узлами дерева. Вершины с нулевой полустепенью исхода (из которых не исходит ни одна дуга) называются листьями. Путь из корня в лист называется ветвью дерева. Пример На рис. 2.17 приведены примеры ориентированных деревьев. Рис. 2.17. Ориентированные деревья Из определения дерева следует, что корень единственным путем связан с любой другой вершиной дерева. Частный случай ориентированных деревьев – корневые деревья, при этом корневые деревья бывают и неориентированные. Данный 23 вид деревьев используется в процедурах поиска в информационных системах, при переборе вариантов в компьютерных программах и др. Рассмотрим корневое изображение – «геометрическое» представление корневого дерева. Множество вершин произвольного дерева G можно разбить в объединение непустых попарно непересекающихся подмножеств V 0 ,V 1 ,...,V k так, что будут выполнены следующие условия: 1) множество V 0 состоит из одной вершины; 2) для всякого i= 1,...,k никакие вершины из V i не смежны; 3) для всякого i= 1,...,k любая вершина из V i смежна ровно с одной вершиной из V i−1 и не смежна ни с одной вершиной из V i−2 ,...,V 0 На рис. 2.18 приведены дерево и одно из его корневых изображений (одно и то же дерево имеет много корневых изображений в зависимости от выбора корня). Рис. 2.18. Дерево и одно из его корневых изображений Определение. Упорядоченным корневым деревом называется корневое дерево G , в котором задан порядок его поддеревьев и каждое поддерево – упорядоченное дерево. Упорядоченное корневое дерево получается помещением корневого дерева в полуплоскость и заданием порядка (например слева направо) ребер, инцидентных каждому узлу. Получим оценку числа упорядоченных корневых деревьев. Для этого введем кодировку упорядоченных корневых деревьев. Дереву ( ) ∅ , v поставим в соответствие пустое слово. Пусть упорядоченное корневое дерево имеет поддеревья m G G G , , , 2 1 K и каждому 24 поддереву i G поставлен в соответствие код i K . Тогда кодом дерева G будет код 1 0 1 10 0 2 1 m K K K K K = Так как корневыми деревьями являются только деревья, которые могут быть построены в соответствии с определением, то все они могут быть закодированы. Из определения кода дерева следует, что код дерева – это слово из нулей и единиц. Лемма о коде дерева Пусть K – код упорядоченного корневого дерева ( ) X V G , . Обозначим через ( ) K n – число нулей, ( ) K e – число единиц в коде, K – общее число символов. Пусть K K K ′′ ′ = , где K ′ и K ′′ два подслова. Тогда а) m K 2 = , где − m число ребер в дереве G ; б) ( ) ( ) K e K n = ; в) ( ) ( ) K e K n ′ ≥ ′ , причем равенство достигается только тогда, когда 1 0 1 10 0 2 1 s K K K K K = ′ , где s K K K , , , 2 1 K – коды первых s поддеревьев дерева G . В коде дерева можно выделить коды отдельных поддеревьев. Для этого надо найти точки, где количество нулей совпадает с количеством единиц, т. е. надо найти 1 10 0 2 1 K K и т. д. Затем в каждом i K проделать такую же процедуру. Таким образом, по коду упорядоченного корневого дерева можно восстановить само дерево. Теорема о числе упорядоченных корневых деревьев Число упорядоченных корневых деревьев с m ребрами не превосходит m 4 Доказательство. Так как между упорядоченными корневыми деревьями и их кодами существует биекция, то их число равно числу кодов деревьев. Код дерева с m ребрами – слово длины m 2 , состоящее из нулей и единиц. Число кодов не превосходит общего числа слов длины m 2 , состоящих из 0 и 1 , которое равно m m 4 2 2 = . Таким образом, число упорядоченных корневых деревьев с m ребрами не превосходит m 4 Следствия 1. Число попарно неизоморфных неупорядоченных корневых 25 деревьев с m ребрами не превосходит числа упорядоченных корневых деревьев и, следовательно, не превосходит m 4 2. Число попарно неизоморфных деревьев с m ребрами не превосходит числа корневых деревьев с m ребрами, так как они различаются выбором корневой вершины, следовательно, не превосходит m 4 Пример Деревья, приведенные на рис. 2.19, попарно изоморфны, но различны с точки зрения корневых деревьев. Рис. 2.19. Изоморфные деревья Задача о соединении городов. Пусть есть n городов, расстояние между каждыми двумя городами известно. Надо соединить их дорогой минимальной длины (или минимальной стоимости, если известна цена дороги между каждыми двумя городами). Эту задачу можно сформулировать на языке теории графов, полагая города вершинами, а расстояния – ребрами нагруженного графа. Пусть каждому ребру графа поставлено в соответствие положительное число ) (x u (расстояние между городами или стоимость прокладываемой дороги). Обозначим вес всего графа ) (G u , тогда ∑ ∈ = X x i i x u G u ) ( ) ( Стоит следующая задача: дан простой полный граф на n вершинах, задан вес каждого ребра, надо построить связный подграф минимального веса. (Требование полноты исходного графа необязательно, достаточно, чтобы он был связным). Очевидно, что минимальный связный граф – дерево, поэтому задачу можно уточнить: построить остовное дерево минимального веса. 26 Алгоритм Краскала Данный алгоритм используется дляпостроения остовного дерева минимального веса. Выберем ребро минимального веса, обозначим его 1 x . Если несколько ребер имеют один и тот же вес, берем любое. Затем выбираем ребро минимального веса из оставшихся, обозначим его 2 x . Затем снова выбираем ребро минимального веса из оставшихся, но так чтобы оно не образовывало цикла с выбранными ранее ребрами. Выбрав таким образом 1 − n ребро, получим остовное дерево T , причем ). ( ) ( ) ( ) ( 1 3 2 1 − ≤ ≤ ≤ ≤ n x u x u x u x u L Покажем, что не будет остовных деревьев с весом меньшим, чем вес дерева T Пусть есть остовное дерево S такое, что ) ( ) ( T u S u < . Пусть k x – первое ребро из T , не вошедшее в S . Рассмотрим граф k x S ∪ , он не является деревом, следовательно, в нем существует цикл C . Пусть C x ∈ ′ и T x ∉ ′ , такое ребро существует, так как T – дерево и не содержит циклов, удалив это ребро из графа k x S ∪ , получим граф x x S k ′ ∪ \ ) ( , он связный граф, в нем 1 − n ребро, следовательно, он дерево. При этом графы T и x x S k ′ ∪ \ ) ( содержат на одно общее ребро больше, чем графы T и S . ( ) ( ) ), ( ) ( ) ( ) ( \ S u x u x u S u x x S u k k ≤ ′ − + = ′ ∪ так как ) ( ) ( x u x u k ′ ≤ , иначе при построении дерева T по алгоритму Краскала вместо ребра k x взяли бы ребро x′ (ребра 1 2 1 ,..., , − k x x x ) у деревьев S и T общие и x′ не образует с ними цикла). Пусть j x следующее ребро из T , не вошедшее в S . Присоединим его к графу x x S k ′ ∪ \ ) ( , вновь образуется цикл, удалим из него ребро S x ∈ ′′ и T x ∉ ′′ . Получим граф ( ) ( ) ( ) , \ \ x x x x S j k ′′ ∪ ′ ∪ этот граф и граф T будут иметь на два общих ребра больше, чем графы S и T , при этом ( ) ( ) ( ) [ ] = ′′ ∪ ′ ∪ x x x x S u j k \ \ ( ) ( ) ( ) ( ) ) ( \ ) ( ) ( \ S u x x S u x u x u x x S u k j k ≤ ′ ∪ ≤ ′′ − + ′ ∪ = 27 Повторив эту процедуру конечное число раз, перестроим граф S в T и получим противоречие ) ( ) ( ) ( T u S u T u < ≤ Подробнее сам алгоритм и пример его использования приведены в параграфе 2.7.10. Дерево порядка n называется помеченным, если его вершинам присвоены некоторые метки, например 1, 2, ..., n. Как ранее было сказано, каждому дереву можно поставить в соответствие некоторый код. С помощью этого кода можно восстановить дерево с точностью до изоморфизма. Существуют различные способы кодирования деревьев, которые позволяют решать конкретные задачи (подсчет деревьев, установление изоморфизма, генерирование всех неизоморфных деревьев и т. д.). Таким образом, кодирование графасостоит в записи информации о нем, однозначно и полностью восстанавливающей структуру графа. Рассмотрим так называемый код Прюфера, который представляет из себя способ однозначного кодирования помеченного дерева с помощью последовательности чисел. С помощью кода Прюфера в том числе демонстрируется решение задачи о количестве способов добавить в заданный граф ребра, чтобы превратить его в связный. |