Графы. Теория графов

Сентябрь 13, 2022

Главная
Математика
Графы. Теория графов

Содержание

2. Теория графов Лектор: Гладких Борис Афанасьевич, профессор кафедры прикладной информатики Gladkikh_ba@yahoo.com Факультет информатики, 2016
3. Введение Теория графов – раздел дискретной математики, изучающий свойства конечных или счетных множеств с точки зрения
4. Леонард Эйлер (1707-1783) 1. Задача о кенигсбергских мостах (1736) Современный Калининград Заслуга Эйлера в том, что
5. Впервые понятие «граф» ввел в 1936 году венгерский математик Денеш Кëниг. Он же написал первую книгу
6. 2. Задача Кенига о деревенских свадьбах (задача о назначении, о наибольшем паросочетании) Андрей Борис Витя Гена
7. 3. Задача о раскраске плоского графа (проблема четырех красок) Задача поставлена в 1852(?) г. шотландским физиком
8. В 1976 г. ведущие математики всего мира получили письма с почтовым штемпелем «Четырех красок достаточно». В
9. Во 2-й половине 20 века теория графов превратилась в разветвленную математическую дисциплину, имеющую множество приложений: в
10. Глава 1. Основные понятия
11. 1.1. Типы графов. Основная терминология
12. Терминология теории графов очень разнообразна и не окончательно устоялась. Почти каждый автор начинает учебник с объяснения
13. Приведенный на примере граф относится к числу самых простых, он называется обыкновенным или простым (simple). В
14. Андрей Борис Витя Гена Дима Аня Бэла Валя Галя Даша Обыкновенный граф, вершины которого можно разбить
15. Неориентированный мультиграф (2-граф) Ориентированный граф с петлями В более сложных случаях вершины могут соединяться более чем
16. В общем случае все варианты ребер могут присутствовать одновременно. На рисунке пример частично ориентированного 3-графа с
17. В некоторых графовых моделях ребрам приписываются некоторые числа (веса ), которые означают длины ребер, пропускные способности
18. Инцидентность (incidency) и смежность (ajacency). В данном графе вершина 2 инцидентна ребрам a и b. Вершины
19. Степень и валентность вершин Количество ребер, инцидентных вершине, называется степенью вершины (degree of a vertex). При
20. 1.2. Части графа
21. Подграф Подграф (subgraph) – часть графа, в которой сохраняется подмножество вершин и ВСЕ ИНЦИДЕНТНЫЕ ИМ РЕБРА
22. Пустой подграф
23. Суграф Суграф – часть графа, в которой сохраняются все вершины и часть ребер. В англоязычной литературе
24. 1.3. Математическое определение графа
25. Для понятия «граф» существуют несколько строгих математических определений, каждое из которых удобно для определенного класса графов:
26. Обыкновенный граф Пример
27. Граф как бинарное отношение (Оре) Пример Скобки 〈〉 обозначают упорядоченность.
29. Ойстин Оре (1899—1968) Определение графа -- бинарного отношения использует норвежский математик О. Оре в монографии «Теория
30. Граф как многозначное отображение (Берж) Пример
31. -
33. Claude Jacques Berge (5 June 1926 – 30 June 2002) was a French mathematician, recognized as
34. Граф общего вида как трехместный предикат (Зыков)
35. 1. 2. 3.
37. Это определение охватывает все виды графов – ориентированные и неориентированные, униграфы и мультиграфы.
38. Зыков, Александр Александрович (1922—2013)
39. Изоморфизм графов
40. t Пример
41. . Тем самым оказываются несущественными как природа элементов, составляющих множества V и E , так и
42. Способы задания графов
43. 1.4. Задание графа матрицами
44. Матрица инциденций
45. Для обыкновенного графа достаточно двух символов, скажем, 0 и 1. Единица ставится, когда соответствующее ребро инцидентно
46. Для ориентированного графа понадобятся три символа, например, 0, -1, 1, при этом 1 соответствует вершине исхода,
47. Для графа общего вида понадобятся три символа, например, 0, -1, 1, при этом 1 соответствует вершине
48. Матрица смежности
49. c
50. c
52. Скачать презентацию

Слайд 2

Теория графов
Лектор: Гладких Борис Афанасьевич,
профессор кафедры прикладной информатики
Gladkikh_ba@yahoo.com
Факультет информатики, 2016

Слайд 3

Введение
Теория графов – раздел дискретной математики, изучающий свойства конечных или счетных

множеств с точки зрения отношений между их элементами.
Особенностью теории графов является геометрический (т. е. графический) подход к построению моделей изучаемых множеств.
Первая работа по теории графов была написана еще в 1736 году Леонардом Эйлером, в которой он решил «задачу о Кëнигсбергских мостах»: как пройти по семи мостам через реку Преголя, не проходя ни по одному из них дважды.

Слайд 4

Леонард Эйлер (1707-1783)
1. Задача о кенигсбергских мостах (1736)
Современный Калининград
Заслуга Эйлера

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

Слайд 5

Впервые понятие «граф» ввел в 1936 году венгерский математик Денеш Кëниг.

Он же написал первую книгу по теории графов: «Теория конечных и бесконечных графов»

Денеш Кениг (1884-1944)

Слайд 6

2. Задача Кенига о деревенских свадьбах (задача о назначении, о наибольшем паросочетании)
Андрей
Борис
Витя
Гена
Дима
Аня
Бэла
Валя
Галя
Даша

Слайд 7

3. Задача о раскраске плоского графа (проблема четырех красок)
Задача поставлена в

1852(?) г. шотландским физиком Фредериком Гутри как головоломка. Теорема о пяти красках, утверждающая, что достаточно пяти цветов, имела короткое несложное доказательство и была доказана в конце XIX века, но доказательство теоремы для случая четырёх цветов столкнулось со значительными трудностями. Более 100 лет проблема 4 красок интриговала ученых.

Слайд 8

В 1976 г. ведущие математики всего мира получили письма с почтовым

штемпелем «Четырех красок достаточно». В письмах была статья математиков Кеннета Аппеля и Вольфганга Хакена из Иллинойского университета, содержащая доказательство теоремы.
Это была первая крупная математическая теорема, доказанная с помощью компьютера. Первым шагом доказательства была демонстрация того, что существует определенный набор из 1936 карт, ни одна из которых не может содержать карту меньшего размера, которая опровергала бы теорему. Аппель и Хакен использовали специальную компьютерную программу, чтобы доказать это свойство для каждой из 1936 карт. Доказательство этого факта заняло сотни страниц.

Слайд 9

Во 2-й половине 20 века теория графов превратилась в разветвленную математическую

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

Слайд 10

Глава 1. Основные понятия

Слайд 11

1.1. Типы графов.
Основная терминология

Слайд 12

Терминология теории графов очень разнообразна и не окончательно устоялась. Почти каждый

автор начинает учебник с объяснения используемой им терминологии.
Составлен «Толковый словарь по теории графов в информатике и программировании» под ред. В.А.Евстигнеева и В.Н. Касьянова. - Новосибирск: Наука, 1999. – 291 с.
Краткий словарь по теории графов можно найти на сайте Lmatrix
http://lmatrix.ru/news/theory/glossarijj-teorii-grafov_507.html
На интуитивном уровне граф (graph) представляет собой абстрактную схему, состоящую из точек и соединяющих их линий.
Точки называются вершинами (vertex - vertices) или узлами (node - nodes), а соединяющие их линии – ребрами (edge - edges).
Несущественны содержание вершин, их взаимное расположение, а также форма, толщина, длина или цвет линий. Важен лишь факт соединения вершин ребрами.

Слайд 13

Приведенный на примере граф относится к числу самых простых, он называется

обыкновенным или простым (simple). В обыкновенном графе ребра не имеют ориентации, вершины соединены не более чем одним ребром (униграф), а у вершин нет петель.

Типы графов

Слайд 14

Андрей
Борис
Витя
Гена
Дима
Аня
Бэла
Валя
Галя
Даша
Обыкновенный граф, вершины которого можно разбить на два противоположных множества так,

что ребра соединяют только вершины противоположных множеств, называется двудольным графом (bipartite graph) или графом Кенига или бихроматическим графом (bichromatic graph).

Двудольный граф

Слайд 15

Неориентированный мультиграф (2-граф)
Ориентированный граф с петлями
В более сложных случаях вершины могут

соединяться более чем одним ребром , т.е. кратными ребрами. Это мультиграф (multigraph).
При вершинах могут быть петли (loops) .
Ребра могут иметь ориентацию, такой граф называется ориентированным или орграфом (oriented graph). Ориентированные ребра называются дугами (arc - arcs).

Мультиграф и орграф

Слайд 16

В общем случае все варианты ребер могут присутствовать одновременно. На рисунке

пример частично ориентированного 3-графа с петлями, имеющего 4 вершины. Вершина 4 изолированная.

Граф общего вида

Слайд 17

В некоторых графовых моделях ребрам приписываются некоторые числа (веса ), которые

означают длины ребер, пропускные способности каналов связи и т. д.
Такие графы называются взвешенными (weighted graph).
Пример – задачи о кратчайшем пути на местности, о наибольшем потоке данных в сети связи и т. д.

Взвешенный граф

Слайд 18

Инцидентность (incidency) и смежность (ajacency).
В данном графе вершина 2 инцидентна ребрам

a и b.
Вершины 1 и 2 смежны, так как они имеют общее ребро a
Ребра a и b смежны, так как они имеют общую вершину 2

Слайд 19

Степень и валентность вершин
Количество ребер, инцидентных вершине, называется степенью вершины (degree

of a vertex).
При подсчете валентности (valency) петля считается дважды.

Слайд 20

1.2. Части графа

Слайд 21

Подграф
Подграф (subgraph) – часть графа, в которой сохраняется подмножество вершин и

ВСЕ ИНЦИДЕНТНЫЕ ИМ РЕБРА

Слайд 22

Пустой подграф

Слайд 23

Суграф
Суграф – часть графа, в которой сохраняются все вершины и часть

ребер. В англоязычной литературе также называется subgraph.

Слайд 24

1.3. Математическое определение графа

Слайд 25

Для понятия «граф» существуют несколько строгих математических определений, каждое из которых

удобно для определенного класса графов:
- для обыкновенных графов;
- для ориентированных графов (Оре, Берж);
- для графов общего вида (Зыков).

Слайд 26

Обыкновенный граф

Пример

Слайд 27

Граф как бинарное отношение (Оре)

Пример

Скобки 〈〉 обозначают упорядоченность.

Слайд 28

Слайд 29

Ойстин Оре (1899—1968)
Определение графа -- бинарного отношения использует норвежский математик
О. Оре

в монографии «Теория графов ». – М: Наука, Гл. ред. физ.-мат. лит.,
1980.– 336 с. (второе издание)

Слайд 30

Граф как многозначное отображение (Берж)

Пример

Слайд 31

-

Слайд 32

Слайд 33

Claude Jacques Berge (5 June 1926 – 30 June 2002) was a

French mathematician, recognized as one of the modern founders of combinatorics and graph theory.

Слайд 34

Граф общего вида как трехместный предикат (Зыков)

Слайд 35

1.

2.

3.

Слайд 36

Слайд 37

Это определение охватывает все виды графов – ориентированные и неориентированные,

униграфы и мультиграфы.

Слайд 38

Зыков, Александр Александрович (1922—2013)

Слайд 39

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

Слайд 40

t
Пример

Слайд 41

.
Тем самым оказываются несущественными как природа элементов, составляющих множества V и

E , так и конкретный смысл предиката P .

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

Слайд 42

Способы задания графов

Слайд 43

1.4. Задание графа матрицами

Слайд 44

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

Слайд 45

Для обыкновенного графа достаточно двух символов, скажем, 0 и 1. Единица

ставится, когда соответствующее ребро инцидентно вершине.

Слайд 46

Для ориентированного графа понадобятся три символа, например, 0, -1, 1, при

этом 1 соответствует вершине исхода, а -1 – вершине захода.

Слайд 47

Для графа общего вида понадобятся три символа, например, 0, -1, 1,

при этом 1 соответствует вершине исхода, а -1 –вершине захода.

Слайд 48

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

Слайд 49

c

Слайд 50

Графы. Теория графов

Содержание

Теория графовЛектор: Гладких Борис Афанасьевич, профессор кафедры прикладной информатикиGladkikh_ba@yahoo.comФакультет информатики, 2016

Введение Теория графов – раздел дискретной математики, изучающий свойства конечных или счетных

Леонард Эйлер (1707-1783)1. Задача о кенигсбергских мостах (1736) Современный КалининградЗаслуга Эйлера