Неориентированое дерево есть связный граф без циклов, или связный граф, содержащий n вершин и n-1 ребер. Несвязный граф без циклов, отдельными компонентами связности которого являются деревья, называется лесом.
Ориентированное дерево представляет собой ориентированный граф без циклов, в котором полустепень захода каждой вершины, за исключением одной, назы2Ҁаемой корнем дерева, равна единице, а полустепень захода корня дерева равна нулю. Пример ориентированного дерева с корнем – вершиной х1 приведен на рис. 6.1.
Граф – дерево часто называют минимальным графом, имея в виду, что он содержит минимальное число ребер, оставаясь связным. Граф – дерево можно рассматривать не только как минимальный граф, но и какчасть некоторого исходного графа.
Остовным деревом графа называют дерево, содержащее все вершины графа.
Рис. 6.1.
Рис.6.2. Рис. 6.3.
Ориентированное Ориентированный Остовное дерево дерево граф
Отметим, что в связном неориентированном графе всегда может быть построено остовное дерево, в то время как не всякий орграф содержит его. Например, орграф, изображенный на рис. 6.2., не содержащий остовного дерева, т.т. нулевую полустепень захода имеют не одна, а две вершины: х1 и х3. Если же убрать ориентацию дуг, то можно построить в полученном неориентированном графе, например, остовное дерево, представленное на рис. 6.3.
Очевидно, что остовных деревьев в графе может быть некоторое множество. Полный связный неориентированный граф с n вершинами содержит n n-2 остовных деревьев; другими словами, на n вершинах можно построить n n-2 деревьев
Если ребрам графа приписаны числа (веса), которые могут иметь различный физический смысл, то суммарный вес ребер, вошедших в дерево, называют “длиной” дерева.
Упражнения.
Сколько ребер содержит лес с n вершинами и р компонентами связности?
Построить все возможные деревья для графа с четырьмя вершинами и выделить среди них не изолированные (существенные).
Доказать, что все оставшиеся деревья будут изоморфны одному из полученных в п.6.2.
Характеристические числа графов.
К характеристическим числам графа относятся:
цикломатическое число n(G), хроматическое число k (G), число внутренней устойчивости (число независимости) a(G), число внешней устойчивости (число доминирования) b(G), кликовое число.
Заметим, что характеристические ч8Ѐсла не зависят от изоморфных преобразований графа.
Цикломатическое число.
При рассмотрении связного неориентированого графа G(Х, А) без петель с n вершинами и m ребрами . Величину n((G)=m-n+1
называют цикломатическим числом графа[(1,2,](. Принимая во внимание, что дерево с n вершинами имеет n-1 ребро, можно сказать, что цикломатическое число равно числу ребер, которые необходимо удалить из данного графа, чтобы получить дерево.
Основное свойство цикоматического числа состоит в том, что оно равно максимальному числу независимых циклов. Циклы считаются независимыми, если в каждом из них содержится по крайней мере одно ребро, не входящее в другие циклы графа. Если граф несвязный и содержит р компонент связности, то циклическое число определяется так:
n(G) = m – n + р.
Упражнения.
7.1. Граф G(Х, А) задан матрицей смежности А2 из упражнения 5.1.
А) Построить его геометрическое изображение.
Б) Определить цикломатическое число.
В) Указать независимые циклы.
6.1. Хроматическое число.
Неориентированный граф G(Х, А) без петель называется r – хроматическим, если его вершины могу быть раскрашены в r цветов (красок) так, что не найдется двух смежных вершин одного цвета. Наименьшее число r, в которое таким образом могут быть раскрашены вершины графа называется хроматическим числом графа G [1,2,4]. Обозначим его К(G).
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.