Основы теории графов. Лекция №7.1

Содержание

Слайд 2

Лекция №7.1

План
1. Возникновение теории графов.
2. Основные понятия и определения теории графов.
3.

Лекция №7.1 План 1. Возникновение теории графов. 2. Основные понятия и определения теории графов. 3.

Слайд 3

Задачи, приводящие к понятию графа

Теория графов – это раздел дискретной математики, особенностью

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

Слайд 4

Задачи, приводящие к понятию графа

Подобные схемы впервые назвал «графами» венгерский математик Денеш

Задачи, приводящие к понятию графа Подобные схемы впервые назвал «графами» венгерский математик
Кёниг в 1936 г. При этом начало теории графов как отдельной дисциплины было положено еще в 1736 году Леонардом Эйлером в его знаменитом рассуждении о семи Кенигсбергских мостах.
Бывший Кенигсберг (ныне - Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены.

Слайд 5

Задача о кенигсбергских мостах
Кенигсберцы предлагали приезжим следующую задачу: пройти по всем мостам

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

Эйлер доказал, что это невозможно и изобрёл таким образом эйлеровы циклы. Однако эта статья была единственной в течение почти ста лет.

Слайд 6

Интерес к проблемам теории графов возродился к середине 19 столетия благодаря исследованиям

Интерес к проблемам теории графов возродился к середине 19 столетия благодаря исследованиям
электрических сетей, моделей кристаллов, структур молекул. Большое число популярных головоломок тех времен поддавались формулировкам именно в терминах графов. Одна из них – задача о трех колодцах и трех домах.

Задача о трех колодцах и трех домах

Три соседа поссорились. Все три имеют по колодцу. Возможно ли проложить тропинки от дома каждого соседа к каждому колодцу так, чтобы эти тропинки не пересекались?
Как видим, ответ отрицательный.

Слайд 7

Теорема о четырёх красках — утверждение о том, что всякую расположенную на

Теорема о четырёх красках — утверждение о том, что всякую расположенную на
сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке общей границей для них не считаются.
Эта теорема была сформулирована Фрэнсисом Гутри (англ.) в 1852 году, однако доказать её долгое время не удавалось. В течение этого времени было предпринято множество попыток как доказательства, так и опровержения, и эта задача носила название проблемы четырёх красок.

Теорема о четырёх красках

Слайд 8

Период интенсивной разработки общей теории графов начался в 50-х годах ХХ века

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

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

Слайд 9

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

Графы применяются:

Банковское дело

Промышлен-ность

Медицина

Молекулярная биология

Применение графов Графы применяются: Банковское дело Промышлен-ность Медицина Молекулярная биология

Слайд 10

Лекция доктора технических наук, профессора Владимира Алексеевича Кузнецова Петрозаводский государственный университет (РФ)

.

Лекция доктора технических наук, профессора Владимира Алексеевича Кузнецова Петрозаводский государственный университет (РФ) .

Слайд 11

Рассмотрим пример.
Пусть V – множество городов России, Е – множество пар аэропортов,

Рассмотрим пример. Пусть V – множество городов России, Е – множество пар
между которыми установлено гражданское авиасообщение.

Основные понятия и определения теории графов

Москва

Санкт-Петербург

Ростов-на-Дону

Екатеринбург

На рисунке 1 изображен граф G=G(V,E).

Рис. 1

Слайд 12

Определение графа

Пусть V - непустое множество, состоящее из соединенных некоторым образом точек Xi. Множество

Определение графа Пусть V - непустое множество, состоящее из соединенных некоторым образом
V называется множеством вершин 
(или узлов).
Обозначим E - множество пар u =(Xi, Xj), где Xi, Xj – элементы множества V. Пара u =(Xi, Xj) называется ребром (дугой).
Графом называется упорядоченная пара G=G(V,E).
Иными словами, граф – это непустое множество точек (вершин) и отрезков (ребер), концы которых принадлежат заданному множеству точек.

Слайд 13

Определение графа

Ребро u=(Xi, Xj) называется неориентированным, если (Xi, Xj) = (Xj, Xi).
Ребро

Определение графа Ребро u=(Xi, Xj) называется неориентированным, если (Xi, Xj) = (Xj,
u=(Xi, Xj) называется ориентированным (или дугой), если
(Xi, Xj) ≠ (Xj, Xi).
При этом дуга направлена от вершины Xi к вершине Xj.
Xi – начало, Xi – конец дуги.
Ребро (дуга) называется петлёй, если его концы совпадают, то есть  u =(Xi, Xi).

Слайд 14

Определение графа

Множество V, а значит и множество E, обычно считаются конечными множествами. Граф

Определение графа Множество V, а значит и множество E, обычно считаются конечными
называется конечным, если он имеет конечное число вершин (рис 2). В противном случае граф называется бесконечным (рис. 3).

Рис. 2

Рис. 3

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

Слайд 15

Определение графа

Вершины и рёбра графа называются также элементами графа,
число вершин в

Определение графа Вершины и рёбра графа называются также элементами графа, число вершин
графе, т.е. |V|  называется порядком графа,
число рёбер, т.е. |E| - размером графа.  

Слайд 16

Определение графа

Две концевые вершины одного и того же ребра называются смежными.
Если u =(Xi,

Определение графа Две концевые вершины одного и того же ребра называются смежными.
Xj), то ребро u инцидентно вершинам Xi и Xj, а вершины Xi и Xj инцидентны ребру u.
Вершины Xi и Xj называются концевыми вершинами (или просто концами) ребра  u =(Xi, Xj).

Слайд 17

Определение графа

Степенью  вершины  называют количество инцидентных ей рёбер (при этом петли считают дважды). Обозначают:

Определение графа Степенью вершины называют количество инцидентных ей рёбер (при этом петли
ρ(Xi).
Вершина называется изолированной, если она не принадлежит ни одному ребру, т.е. ρ(Xi)=0; 
вершина называется висячей (или листом), если она принадлежит ровно одному ребру, т.е. ρ(Xi)=1.
Граф, состоящий только из изолированных вершин, называется нуль-графом. Нуль-граф не содержит ребер.

Слайд 18

Виды графов

Граф G=G(V,A) называется ориентированным (или орграфом), если все его связи заданы

Виды графов Граф G=G(V,A) называется ориентированным (или орграфом), если все его связи
дугами (рис. 4). A – множество дуг.
Граф G=G(V,E) называется неориентированным, если все его связи заданы ребрами (рис. 5). E – множество ребер.
Граф G=G(V,E,A) называется смешанным, если он содержит ребра и дуги (рис. 6).

Рис. 4

Рис. 6

Рис. 5

Слайд 19

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

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

Неориентированный мультиграф

Ориентированный
мультиграф

Мультиграф

Слайд 20

Псевдограф – граф,
имеющий петли
и/или кратные связи.

Полный граф – граф, в

Псевдограф – граф, имеющий петли и/или кратные связи. Полный граф – граф,
котором любые две вершины соединены между собой, т.е. все вершины соединены со всеми.

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

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

Псевдограф

Полный граф

Слайд 21

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

Плотный

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

Слайд 22

Двудольный граф – граф, множество вершин которого можно разбить на две части

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

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

Слайд 23

Изоморфные графы

Изоморфные графы

Слайд 24

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

Геометрический.
Пусть задан граф G=G(X,V).
Графы имеют наглядную геометрическую интерпретацию в виде

Способы задания графов Геометрический. Пусть задан граф G=G(X,V). Графы имеют наглядную геометрическую
диаграмм, состоящих из точек и линий, соединяющих некоторые из этих точек. Точки соответствуют вершинам графа (элементам множества X), а линии – его ребрам (дугам). При этом форма и длина линий значения не имеют. Важно лишь, что две данные точки соединены или не соединены линией.

Слайд 25

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

Геометрический
Пример:
Рис. 1 Рис. 2

Способы задания графов Геометрический Пример: Рис. 1 Рис. 2

Слайд 26

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

Аналитический.
Всякий граф G=G(X,V) можно рассматривать как совокупность множества элементов X

Способы задания графов Аналитический. Всякий граф G=G(X,V) можно рассматривать как совокупность множества
и подмножества V упорядоченных пар (Xi, Xj) декартового произведения X×X, т.е. V ⊆ X2. Таким образом, аналитически граф можно считать бинарным отношением, заданным на множестве X.

Слайд 27

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

Аналитический.
Чтобы задать граф аналитически, необходимо указать:
Множество вершин X.
Множество ребер (дуг)

Способы задания графов Аналитический. Чтобы задать граф аналитически, необходимо указать: Множество вершин

V={(Xi, Xj)| Xi, Xj ∈ X} .
3) Множество изолированных вершин.

Слайд 28

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

Аналитический.
Пример:

Способы задания графов Аналитический. Пример:
Имя файла: Основы-теории-графов.-Лекция-№7.1.pptx
Количество просмотров: 40
Количество скачиваний: 0