Графы

Основное определение

Неориентированный ГРАФ – это упорядоченная пара (V,E), где:
V – множество

Пример графа-1

Пример графа-2

Будет ли ЭТО графом?

А ЭТО?

А ЭТО?

Порядок и размер графа

Количество вершин называется порядком графа.
Количество ребер называется размером

Некоторые термины-1

Пусть R=(a,b) – одно из ребер графа. Тогда вершины a

Степенью вершины V обозначается deg(V) называется количество ребер, для которых эта

Пример:

deg(C)=4
H1,…H4 - Листья

Еще пример:

Города B и Д – изолированные вершины; Города Г и

Полный граф

Граф называется полным, если любые две вершины соединены ребром.
Сколько ребер

Давайте это докажем…

Полный граф с двумя вершинами содержит одно ребро –

Предположение индукции

Предположим, что формула верна для графа c k вершинами.
Докажем, что

Добавим к полному графу с K вершинами еще одну вершину.

И соединим

Получим:

Считаем, сколько получилось ребер…

K*(K-1)/2 + K
=
K*(K+1)/2

Последнее выражение получается, если в

Из предположения справедливости утверждения при n=k следует справедливость утверждения при n=k+1.
Теорема

Примеры полных графов

Важное уточнение

Пары, задающие ребра в неориенти-рованном графе, неупорядочены (т.е. пары

Ориентированный граф

Если ребра графа есть множество упорядоченных пар (т.е. (a,b) ≠

Пример орграфа

Смешанный граф
Смешанный граф – это тройка (V, E, A).
V – множество

Изоморфизм графов

Пусть имеется два графа G1 и G2
Если имеется взаимно-однозначное соответствие

Уточнение

Для орграфов и смешанных графов соответствие F должно сохранять ориентацию

Необходимое условия изоморфизма

При каких условиях между элементами двух конечных множеств можно

Достаточно ли это условие?

Нет, поскольку вершины могут быть соединены по-разному.

Изоморфны ли эти графы?

Число вершин одинаково – необходимое условие соблюдено…

Пробуем построить соответствие F…

Это – не изоморфизм: в G1 есть ребро

Другая попытка…

А это изоморфизм!

А эти графы изоморфны?

Увы, нет…

С точки зрения теории два изоморфных графа – это один и

Пути (цепи):

Путь (цепь) это последовательность вершин:
a1, a2, … , an
в которой

Примеры путей:

(А, Г, В) и (А, Б, Д) – пути. (А,

Понятие пути для орграфа сохраняет силу, но нуждается в дополнении –

Циклы

Цикл – это путь, у которого начальная и конечная вершина совпадают.
Длина

Компоненты связности

Вершины произвольного графа можно разбить на классы, такие, что для

Машинное представление графов.

Матрица смежности

Занумеруем вершины графа G последовательными целыми от 1 до n;
Построим

Пример

Некоторые очевидные свойства матрицы смежности

Если вершина изолирована, то ее строка и столбец

Обобщение для орграфа

Матрицу смежности для орграфа можно строить аналогичным образом, но,

Матрица инцидентности

Занумеруем вершины графа G последовательными целыми от 1 до n;
Построим

Матрица инцидентности для орграфа

Если j-я дуга исходит из вершины k, то

Поскольку столбцы матрицы инцидентности описывают ребра, то в каждом столбце может

Пример матрицы инцидентности

Список ребер

Еще один способ представления графа – двумерный массив (список пар).

Пример списка ребер

Сравнение разных способов представления

Список ребер самый компактный, а матрица инцидентности наименее

Обход графа

Обходом графа называется перебор его вершин, такой, что каждая вершина

Соглашение-1

Перед выполнением поиска для графа с n вершинами заведем массив Chk

Соглашение-2

Заведем структуру данных (хранилище), в котором будем запоминать вершины в процессе

Соглашение-3

Когда вершина j помещается в хранилище, она отмечается как просмотренная (т.е.

Алгоритм обхода-1

1) Берем произвольную начальную вершину, печатаем и заносим ее в

Алгоритм обхода-2

1) Берем произвольную начальную вершину и заносим ее в хранилище;
2)

Какие структуры данных подходят в качестве хранилища?

Стек (PUSH – занести; POP

Алгоритм-1 в сочетании со стеком называется обходом в глубину
Алгоритм-2 в сочетании

Возьмем граф:

В качестве хранилища возьмем СТЕК. Используем Алгоритм-1.
Обход начнем с

Первый шаг:

Второй шаг:

Третий шаг:

Четвертый шаг:

Пятый шаг:

Шестой шаг:

Седьмой шаг:

Восьмой шаг:

Вершины 8, 7, 4 выталкиваются из стека, т.к. их связи

Далее все вершины будут вытолкнуты из стека.
Получился следующий порядок обхода:
1,2,3,5,4,7,8,6

Теперь возьмем в качестве хранилища очередь. Будем использовать Алгоритм-2. Обход снова

Шаг первый:

Шаг второй:

Шаг третий:

Шаг четвертый:

Шаг пятый:

Шаг шестой:

Шаг седьмой:

Шаг восьмой:

Получился следующий порядок обхода:

1,2,3,4,5,7,6,8

Замечание

Оба алгоритма потребовали одинаковое число шагов. Почему?

Потому, что при обходе

Поиск в глубину

Перед выполнением поиска в глубину для графа с

Алгоритм поиска в глубину с вершины p.

Если Chk[p]=1 – выходим;
Устанавливаем

Пример-1

Пример-2

Если граф несвязный

В этом случае после обхода останутся непросмотренные вершины.
Можно

Сложность алгоритма

Вычислительная сложность алгоритма
O(n+m),
где n – число вершин, а