Материал: PZ_9_Grafy
9.6. Матрица контрдостижимости
Матрица контрдостижимости Q графа G может быть найдена из матрицы достижимости путем ее транспонирования.
9.7. Маршрут. Цепь. Цикл
Пусть G - неориентированный граф.
Маршрутом в G называется такая последовательность рёбер (e1, e2,…,ei,…ek), в которой каждые два соседних ребра ei-1 и ei имеют общую вершину. Начало маршрута – вершина x0, инцидентная ребру ei и не инциндентная ребру e2. Конец маршрута – вершина xk, инциндентная ek и не инциндентная ek-1. Маршрут называется замкнутым, если совпадают его начальные и конечные вершины(x0=xk).
Маршрут, в котором все рёбра различны, называются цепью. Цепь, не содержащая повторяющихся вершин, именуется простой цепью.
Замкнутая цепь называется циклом, простая замкнутая цепь – простым циклом.
Ниже приведены аналогичные понятия для ориентированного графа
Маршрут Замкнутый маршрут Цепь Простая цепь Цикл Простой цикл |
Путь Контур Орцепь Простая орцепь Орцикл Простой орцикл |
Граф G называется связным, если каждая пара его вершин может быть соединена цепью. Граф не являющийся связным, можно разбить на конечное число связных подграфов, называемых компонентами связности. Обозначим через k - число компонент связности графа. Так, граф G1 имеет 3 компоненты связности (рис. 9.1).
Разрезом графа называется множество рёбер, удаление которых увеличивает число компонент связности графа. Разрез называется простым, если никакая его собственная часть не является разрезом.
Вершинная связность графа – наименьшее число вершин, удаление которых приводит к несвязному графу.
Рёберная связность графа – наименьшее число ребёр, удаление которых приводит к несвязному графу.
Орграф называется сильно связным, если для любых двух различных вершин xi и xj существует по крайней мере один путь, соединяющий xi и xj.
Сильная
компонента
– максимально сильный связный подграф
графа
.
Задача 1. Найти в графе (рис. 9.3) маршрут, цепь, цикл.
Решение. {e1, e2, e3, e4, e2} – маршрут, (ребра могут совпадать) {e1, e2, e3, e4} – цепь, (Ребра различны) {e1, e2, e3, e4, e8, e7} – цикл, (замкнутая цепь) {e1, e2, e3} – простая цепь, (не сод-т повт, вершин и реб.) {e2, e3, e4} – простой цикл, (замкн. Простая цепь) {e5} – простой разрез (мост), {e2, e3, e5} – разрез, {e2, e3} – простой разрез. |
Задача 2. Построить матрицы смежности, достижимостей и контрдостижимостей для графа (рис. 9.4). Граф Матрица смежности C
М. достижимостей R М. контрдостижимостей Q
|
9.8. Операции над графами (пересечение, объединение, декартово произведение).
Дополнение
|
Удаление вершин и ребер
|
|||
Объединение графов
|
Сложение графов Суммой графов G1, G2, обозначаемой G=G1+G2, называется граф, полученный как их объединение, причем каждая вершина графа G1 соединяется ребром с каждой вершиной графа G2. При графической интерпретации операции сложения, складываемые графы просто изображаются рядом (как при операции объединения), а затем проводятся ребра от каждой вершины первого графа к каждой вершине второго графа. Полученный в итоге граф будет иметь количество вершин, равное сумме вершин исходных
|
|||
Произведение графов Произведение графов G1, G2, обозначаемой G1·G2, называется граф, множество вершин которого образовано как декартово произведение множеств вершин исходных графов V1·V2, а множество ребер как декартово произведение окрестностей соответствующих исходных вершин (рис. 6.13). V = V1·V2 = {1,2,3}·{a,b,c} = {(1,a), (1,b), (1,c), (2,a), (2,b), (2,c), (3,a), (3,b), (3,c)},
|
9.9. Деревья. Цикломатическое и коцикломатическое числа
Н-графом называется неориентированным деревом (или просто деревом), если он связен и не содержит циклов, а хначит не содержит петель, и кратных ребер.
Дерево – это минимальный связный граф в том смысле, что при удалении хотя бы одного ребра он теряет связность. В дереве с n вершинами всегда n-1 ребро.
Цикломатическое число конечного н-графа G называется
v(G)=vc+ve-vv, где
vc – число связных компонент графа:
ve – число его ребер;
vv – число вершин.
Цикломатическое число любого конечного н-графа неотрицательно. Цикломатическое число графа показывает, сколько ребер надо удалить из графа, чтобы в нем не осталось ни одного цикла.
Цикломатическое число – число рёбер, удаление которых приводит к покрывающему дереву (число хорд в графе)
Коцикломатическое число – число рёбер в остовном дереве
r = vv — vc.
Число связных компонент = 1 Число вершин =13 Число ребер 12 v(G)=0.
|
|
Домашнее задание
|
|
Графы для работы на ПЗ
Пример 6.4.
|
Пример 6.6.
|
Подграфы
|
|
Пример 1, 1.а
|
Пример 2
|
Пример 1.1
|
|
Пример 3
|
Пример 4
|
Пример 5
|
Пример 6
|
Пример 7
|
Пример 44
|
Пример 8
|
Пример 66
|
Пример 1(Москинова)
|
Пример 88
|
Пример 1. Перемножение
|
|
щ |
|
|
|
Пример 2(мой)
|
Задача 2
|
Задача 1. Найти в графе (рис. 9.3) маршрут, цепь, цикл
|
|
|
Пример 1
|
||
|
|
||
|
|||