При нахождении пересечения в матричной форме порядок исходных матриц можно сделать m х m, где m – мощность множества Х=Х1 Õ Х2, путем вычеркивания строк и столбцов, соответствующих вершинам, не входящим в множество Х = Х1 Õ Х2. Тогда любой элемент матрицы А оказывается конъюнкциейсоответствующих элементов полученных таким способом матриц.
В рассмотренном примере эти матрицы имеют вид:
Операцию пересечения можно распространить и на большее число графов.
5.3.Вычитание графов
Вычитание G(Х,Г) графов G1(Х1, Г1) и G2 (Х2, Г2), записываемое как
G(Х, Г) = G1(Х1, Г1) \ G2(Х2, Г2), осуществляется по следующим правилам: 1) вершинами графа G являются вершины графа G1 за исключением вершин, общих для исходных графов: Х=Х1 Х2; 2) отображением для каждой вершины графа G являются пересечение множества вершин этого графа и отображения той же вершины в графе G1: " хi Î х [Г(хi ) = Х ? Г1(хi )].
Для рассмотренного выше примера аналитическое, геометрическое и матричное представления графа G(Х, Г) = G1(Х1, Г1) \ G2(Х2, Г2) изображены на рис. 5.6.
|
Г(х2) = Х ? Г1(х2) = {х2, х4} ? {х3} = Æ
Г(х4) = Х ? Г1(х4) = {х2, х4} ? {х2,х3} = {х2}
Упражнение
|
|
6. ДЕРЕВЬЯ
Одним из наиболее важных и часто используемых понятий теории графов является дерево. Дадим определение неориентированного и ориентированного деревьев.
Неориентированное дерево есть связный граф без циклов, или связный граф, содержащий n вершин и n-1 ребер. Несвязный граф без циклов, отдельными компонентами связности которого являются деревья, называется лесом.
Ориентированное дерево представляет собой ориентированный граф без циклов, в котором полустепень захода каждой вершины, за исключением одной, называемой корнем дерева, равна единице, а полустепень захода корня дерева равна нулю. Пример ориентированного дерева с корнем – вершиной х1 приведен на рис. 6.1.
Граф–дерево часто называют минимальным графом, имея в виду, что он содержит минимальное число ребер, оставаясь связным. Граф–дерево можно рассматривать не только как минимальный граф, но и как часть некоторого исходного графа.
Остовным деревом графа называют дерево, содержащее все вершины графа.
Рис. 6.1. Рис.6.2. Рис. 6.3.
Ориентированное дерево Ориентированный граф Остовное дерево
Отметим, что в связном неориентированном графе всегда может быть построено остовное дерево, в то время как не всякий орграф содержит его. Например, орграф, изображенный на рис. 6.2, не содержит остовного дерева, т.е. нулевую полустепень захода имеют не одна, а две вершины: х1 и х3. Если же убрать ориентацию дуг, то можно построить в полученном неориентированном графе, например, остовное дерево, представленное на рис. 6.3.
Очевидно, что остовных деревьев в графе может быть некоторое множество. Полный связный неориентированный граф с n вершинами содержит n n-2 остовных деревьев; другими словами, на n вершинах можно построить n n-2 деревьев.
Если ребрам графа приписаны числа (веса), которые могут иметь различный физический смысл, то суммарный вес ребер, вошедших в дерево, называют “длиной” дерева.
Упражнения
6.1. Сколько ребер содержит лес с n вершинами и р компонентами связности?
6.2. Построить все возможные деревья для графа с четырьмя вершинами и выделить среди них неизолированные (существенные).
6.3. Доказать, что все оставшиеся деревья будут изоморфны одному из полученных в п.6.2.
7. ХАРАКТЕРИСТИЧЕСКИЕ ЧИСЛА ГРАФОВ.
К характеристическим числам графа относятся:
- цикломатическое число n(G),
- хроматическое число k (G),
- число внутренней устойчивости (число независимости) a(G),
- число внешней устойчивости (число доминирования) b(G),
- кликовое число.
Заметим, что характеристические числа не зависят от изоморфных преобразований графа.
7.1.Цикломатическое число
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
