Презентация на тему "графы". Презентация: Графы и их применение при решении задач А эти графы изоморфны

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

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

- Пусть R=(a,b) – одно из ребер графа. Тогда
вершины a и b называются концевыми
вершинами ребра;
- Концевые вершины одного и того же ребра
называют соседними;
- Два ребра называют смежными, если они имеют
общую концевую вершину;
- Два ребра называются кратными, если
множества их концевых вершин совпадают;
- Ребро называется петлей, если его концы
совпадают.

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

- Степенью вершины V обозначается deg(V)
называется количество ребер, для
которых эта вершина является концевой;
- Вершина называется изолированной, если
она не является концевой ни для одного
ребра;
- Вершина называется листом, если она
является концевой ровно для одного
ребра. Для листа q очевидно deg(q)=1.

Пример:

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

Еще пример:

Города B и Д – изолированные
вершины; Города Г и Е – листья.

Полный граф

Граф называется полным, если любые
две вершины соединены ребром.
Сколько ребер у полного графа
порядка n?
У полного графа порядка n число ребер
равно Cn2=n!/(2*(n-2)!) =n*(n-1)/2

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

Полный граф с двумя вершинами
содержит одно ребро – это очевидно.
Подставим n=2 в формулу n*(n-1)/2
Получим:
n*(n-1)/2=1
Формула верна при n=2

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

Предположим, что формула верна для
графа c k вершинами.
Докажем, что отсюда следует
справедливость формулы для графа
c (k+1) вершиной.

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

И соединим ее с первыми K
вершинами…

Получим:

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

K*(K-1)/2 + K
=
K*(K+1)/2
Последнее выражение получается,
если в формулу n*(n-1)/2 вместо n
подставить K+1.

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

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

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

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

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

Если ребра графа есть множество
упорядоченных пар (т.е. (a,b) ≠ (b,a)),
То граф называется ориентированным
(или орграфом)
Как придать понятию ориентации
наглядный смысл?
Очень просто – ребра снабжаются
стрелками (от начала к концу)!

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

Смешанный граф

Смешанный граф – это тройка (V, E, A).
V – множество вершин;
E – множество неориентированных
ребер;
A- множество ориентированных ребер.
Кстати, ориентированные ребра
называются дугами.

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

Пусть имеется два графа G1 и G2
Если имеется взаимно-однозначное соответствие F
между вершинами графов G1 и G2 , такое что:
- если в графе G1 есть ребро (a,b), то и в графе G2
есть ребро (F(a),F(b))
- если в графе G2 есть ребро (p,q), то и в графе G1
есть ребро (F-1(p),F-1(q))
то графы G1 и G2 называются изоморфными, а
соответствие F – изоморфизмом.

Уточнение

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

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

При каких условиях между элементами
двух конечных множеств можно
установить взаимно-однозначное
соответствие?
Тогда и только тогда, число их
элементов одинаково.
Необходимым условием изоморфизма
графов является одинаковой число
вершин.

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

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

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

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

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

Это – не изоморфизм: в G1 есть ребро (A,Д),
а образы этих ребер в G2 не соединены.

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

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

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

Увы, нет…

С точки зрения теории два
изоморфных графа – это один и тот
же объект (только, может быть, поразному изображенный…)

Пути (цепи):

Путь (цепь) это последовательность
вершин:
a1, a2, … , an
в которой соседние вершины ai и ai+1
соединены ребрами.
Длина пути есть число составляющих его
ребер

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

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

Понятие пути для орграфа сохраняет
силу, но нуждается в дополнении –
соседние вершины в
последовательности
a1, a2, … , an
должны соединяться дугами.

Циклы

Цикл – это путь, у которого начальная и
конечная вершина совпадают.
Длина цикла есть число составляющих его
ребер.
Цикл называется простым, если ребра в нем
не повторяются.
Цикл называется элементарным, если он
простой и вершины в нем не повторяются.

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

Вершины произвольного графа можно
разбить на классы, такие, что для
любых двух вершин одного класса v1
и v2 существует путь из v1 в v2
Эти классы называются компонентами
связности.
Если у графа ровно одна компонента
связности, то граф называется
связным.

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

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

- Занумеруем вершины графа G
последовательными целыми от 1 до n;
- Построим квадратную таблицу n×n и
заполним ее нулями;
- Если имеется ребро, соединяющее
вершины i и j, то в позициях (i,j) и (j,i)
поставим единицы;
- Полученная таблица называется
матрицей смежности графа G.

Пример

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

- Если вершина изолирована, то ее строка и
столбец будут полностью нулевые;
- Количество единиц в строке (столбце)
равно степени соответствующей
вершины;
- Для неориентированного графа матрица
смежности симметрична относительно
главной диагонали;
- Петле соответствует единица, стоящая на
главной диагонали.

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

Матрицу смежности для орграфа
можно строить аналогичным
образом, но, чтобы учесть порядок
вершин, можно поступить так:
Если дуга исходит из вершины j и
входит в вершину k, то в позиции (j,k)
матрицы смежности ставить 1, а в
позиции (k,j) ставить -1.

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

- Занумеруем вершины графа G
последовательными целыми от 1 до
n;
- Построим прямоугольную таблицу с
n строками и m столбцами (столбцы
соответствуют ребрам графа);
- Если j-е ребро имеет концевой
вершиной вершину k, то в позиции
(k,j) ставится единица. Во всех
остальных случаях ставится нуль.

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

- Если j-я дуга исходит из вершины k,
то в позиции (k,j) ставится 1;
- Если j-я дуга входит в вершину k, то
в позиции (k,j) ставится -1.
- В остальных случаях в позиции (k,j)
остается нуль.

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

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

Список ребер

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

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

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

- Список ребер самый компактный, а
матрица инцидентности наименее
компактна;
- Матрица инцидентности удобна при
поиске циклов;
- Матрица смежности проще
остальных в использовании.

Обход графа

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

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

Перед выполнением поиска для графа
с n вершинами заведем массив Chk
из n элементов и заполним его
нулями.
Если Chk[i] = 0, значит i-я вершина еще
не просмотрена.

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

Заведем структуру данных
(хранилище), в котором будем
запоминать вершины в процессе
обхода. Интерфейс хранилища
должен обеспечивать три функции:
- Занести вершину;
- Извлечь вершину;
- Проверить не пусто ли хранилище;

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

Когда вершина j помещается в
хранилище, она отмечается как
просмотренная (т.е. устанавливается
Chk[j]=1)

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

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

3) Берем вершину Z из хранилища;
4) Если есть вершина Q, связанная с Z и не
отмеченная, то возвращаем Z в хранилище,
заносим в хранилище Q, печатаем Q;
5) Переходим к п.2

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

1) Берем произвольную начальную вершину и
заносим ее в хранилище;
2) Хранилище пусто? Если ДА – конец;
3) Берем вершину Z из хранилища, печатаем и
удаляем из хранилища;
4) Помещаем в хранилище все вершины,
связанные с Z и еще не отмеченные;
5) Переходим к п.2

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

- Стек (PUSH – занести; POP – извлечь)
- Очередь (ENQUE – занести; DEQUE –
извлечь)
Обе структуры позволяют проверить
наличие данных.

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

1 слайд

2 слайд

Впервые основы теории графов появились в работах Леонарда Эйлера (1707-1783; швейцарский, немецкий и российский математик) , в которых он описывал решение головоломок и математических развлекательных задач. Теория графов началась с решения Эйлером задачи о семи мостах Кёнигсберга.

3 слайд

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды? Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно. На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города - точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам: Невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

4 слайд

Существуют 4 группы крови. При переливании крови от одного человека к другому не все группы совместимы. Но известно, что одинаковые группы можно переливать от человека к человеку, т.е. 1 – 1, 2 – 2 и т.д. А также 1 группу можно переливать всем остальным группам, 2 и 3 группу только 4 группе. Задача.

5 слайд

6 слайд

Графы Граф – это информационная модель, представленная в графической форме. Граф - множество вершин (узлов), соединённых рёбрами. Граф с шестью вершинами и семью рёбрами. Вершины называют смежными, если их соединяет ребро.

7 слайд

Ориентированные графы - орграфы Каждое ребро имеет одно направление. Такие ребра называются дугами. Ориентированный граф

8 слайд

Взвешенный граф Это граф, рёбрам или дугам которого поставлены в соответствие числовые величины (они могут обозначать, например, расстояние между городами или стоимость перевозки). Вес графа равен сумме весов его рёбер. Таблице (она называется весовой матрицей) соответствует граф. 1 2 4 2 3 A B C D E

9 слайд

Задача Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). 1) 9 2) 10 3) 11 4) 12

10 слайд

1. 2. 3. 4. 5. Длина кратчайшего маршрута A-B-C-E-F равна 9 2 4 2 4 7 1 2 4 7 1 3 4 2 4 7 1 3 4 3 2 4 7 1 3 4 3 2

Граф это конечное множество вершин V и множество ребер R, соединяющих пары вершин, G=(V,R). Мощности множеств V и R равны N и M. Множество ребер может быть пустым. Примеры вершин – объекты любой природы (населенные пункты, компьютерные сети). Примеры ребер – дороги, стороны, линии.

Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его двух вершин называются инцидентными. Степень вершины – количество инцидентных ей ребер. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам.

Маршрут графа – последовательность вершин и ребер. Маршрут замкнутый (циклический), если начальная и конечная вершины совпадают. Маршрут – простая цепь, если все вершины и ребра различны. Граф связный, если каждая вершина достижима из любой другой. Вершины, не имеющие инцидентных ребер, называются изолированными.

Матрица инциденций

Списки связи

Перечень ребер

Матрица смежности связного взвешенного неориенторованного графа графа

Построение остовного связного дерева минимального веса. Алгоритм Крускала Из графа удаляют все ребра, получается остовной подграф, где все вершины изолированы. Каждая вершина помещается в одноэлементное подмножество. Ребра сортируются по возрастанию весов. Ребра последовательно, по возрастанию их весов, включаются в остовное дерево.

Существует 4 случая: 1) обе вершины включаемого ребра принадлежат одноэлементным подмножествам, тогда они объединяются в новое, связное подмножество; 2) одна из вершин принадлежит связному подмножеству, а другая нет, тогда включаем вторую в подмножество, которому принадлежит первая; 3) обе вершины принадлежат разным связным подмножествам, тогда объединяем подмножества; 4) Обе вершины принадлежат одному связному подмножеству, тогда исключаем данное ребро.

Пример построения остовного дерева минимального веса для графа GG Выполняемые действия Множество вершин Граф 1Построим остовной подграф с изолированным и вершинами Получим 5 одноэлементных подмножеств: {V 1 }, {V 2 }, {V 3 }, {V 4 }, {V 5 } 2Найдем ребро минимального веса (R 15) и добавим его в остовной подграф Образуем связное подмножество вершин: {V 1,V 5 }. Сохраняем подмножества {V 2 }, {V 3 }, {V 4 }

Выполняемые действия Множество вершинГраф 3Среди оставшихся найдем ребро минимального веса (R 45) и добавим его в остовной подграф Добавим в связное подмножество вершину: {V 1,V 5, V 4 }. Сохраняем подмножества {V 2 }, {V 3 } 4Среди оставшихся найдем ребро минимального веса (R 23) и добавим его в остовной подграф Образуем новое связное подмножество вершин: {V 2,V 3 }. Сохраняем первое связное подмножество {V 1,V 5, V 4 }.

Выполняемые действия Множество вершинГраф 5Среди оставшихся найдем ребро минимального веса (R 25) и добавим его в остовной подграф Объединяем подмножества в одно связное подмножество {V 1,V 5, V 4,V 2,V 3 }. 6Остальные ребра не включаются в граф, т.к. все их вершины уже принадлежат одному связному множеству.

Выполняемые действия Множество вершинГраф 7Получен граф, который: остовной (все вершины включены); связный (все вершины можно соединить маршрутами); дерево (нет циклов); имеет минимальный вес. 8Полученное остовное дерево имеет минимальный вес: R 12 +R 25 +R 15 +R 45 = =80 9 Циклическое число графа G равно γ=m-n+1=8-5+1=4, что соответствует количеству ребер, не включенных в дерево.

Объявление переменных Два целочисленных пятиэлементных массива X и Y для хранения координат вершин графа Целочисленный двумерный массив R для хранения весов ребер графа Целочисленные переменные i, n и k для счетчиков циклов Целочисленная переменная S для хранения суммы весов ребер дерева минимального веса

Генерация случайных координат 5-ти вершин графа (цикл по i). Вычисление весов ребер. Вывод матрицы смежности взвешенного орграфа (вложенные циклы по n и по k) Вывод матрицы смежности взвешенного неориентрованного графа – половины элементов начальной матрицы (начальное значение k=n+1) Тело программы