Рабочие листы
к вашим урокам
Скачать
1 слайд
Элементы теории графов
2 слайд
ВВЕДЕНИЕ
Теория графов – часть дискретной математики, геометрический подход к изучению объектов и связей
Истоки: задача о Кенигсбергских мостах, о расстановке ферзей, о перевозке грузов и др.
3 слайд
Однажды великому математику Леонарду Эйлеру был задан вопрос: можно ли обойти все семь мостов, стоявших тогда в городе Кёнигсберге (современный Калининград, Россия), побывав на каждом по одному разу?
Перед вами план Кёнигсберга – можете попробовать!
4 слайд
На карте старого Кёнигсберга был ещё один мост, появившийся чуть позже, и соединявший остров Ломзе с южной стороной. Своему появлению этот мост обязан самой задаче Эйлера-Канта. А произошло это вот как. Кайзер (император) Вильгельм славился своей прямотой, простотой мышления и солдатской «недалёкостью». Однажды, находясь на светском рауте, он чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на приёме. Они показали кайзеру карту Кёнигсберга, и попросили попробовать решить эту знаменитую задачу, которая по определению была нерешаемой. Ко всеобщему удивлению, кайзер попросил перо и лист бумаги, сказав, что решит задачу за полторы минуты. Ошеломлённый немецкий истеблишмент не мог поверить своим ушам, но бумагу и чернила быстро нашли. Кайзер положил листок на стол, взял перо, и написал: «приказываю построить восьмой мост на острове Ломзе». Так в Кёнигсберге и появился новый мост, который так и назвали — мост кайзера.
5 слайд
Применение
Анализ и проектирование сетей электроснабжения, водоснабжения, газоснабжения, телефонизации.
Анализ и проектирование транспортных сетей, грузовых и пассажирских перевозок.
Проектирование и возведение строительных объектов.
Разработка новых технологий и изделий
Разработка и эксплуатация компьютерных сетей. Маршрутизация данных в Интернете и т.д.
6 слайд
Опр. Граф это множество вершин V={v1,v2,…vn} и множество неупорядоченных и упорядоченных пар вершин E={e1,e2,…em}. Граф обозначается так: G={V, E}.
Неупорядоченная пара вершин называется ребром, а упорядоченная дугой.
Граф содержащий только ребра называется неориентированным.
Граф содержащий только дуги называется ориентированным или орграфом.
7 слайд
Опр. Граф это множество вершин V={v1,v2,…vn} и множество неупорядоченных и упорядоченных пар вершин E={e1,e2,…em}. Граф обозначается так: G={V, E}.
Неупорядоченная пара вершин называется ребром, а упорядоченная дугой.
Граф содержащий только ребра называется неориентированным.
Граф содержащий только дуги называется ориентированным или орграфом.
8 слайд
Смешанный граф
Смешанный граф
Неориентированный граф
Ориентированный граф
ребро
дуга
вершина
Мультиграф
Псевдограф
Кратные ребра и дуги
петля
9 слайд
Смежные вершины
Смежные ребра (дуги)
v1
v2
v3
v4
e1
e6
e5
e4
e3
e2
Ребро e5 инцидентное вершинам v4 и v3.
Вершина v1 инцидентна ребру e6.
Ребро (u, v) соединяет вершины u и v.
Дуга <u, v> начинается в вершине u и заканчивается в вершине v
Вершины v2 v3 и v4 соседи вершины v1
10 слайд
Опр. Степенью vi вершины графа G, обозначаемой di, называется число ее соседей, или число ребер смежных vi, или число инцидентных ей ребер.
Для орграфа используется выражение «полустепень захода» и «полустепень исхода»
Опр. Полустепенью захода vi вершины графа G, называется число заходящих в неё дуг. Полустепенью исхода vi вершины графа G, называется число исходящих из неё дуг.
v3
v6
v1
v2
v4
v5
Для вершины v3 1 полустепень захода и
4 полустепени исхода
11 слайд
Сумма полустепеней исходов (заходов) в орграфе G равно числу его ребер |Е|.
Сумма степеней вершин неориентированного графа равна 2|Е|, где |Е| число ребер.
Вершина vi графа G называется изолированной, если ее степень di=0. Если степень di=1, то вершина называется концевой.
V2 (концевая)
V1 (изолированная)
v3
v4
v5
12 слайд
Опр. Граф G называется полным, если он не содержит петель и каждые две различные его вершины соединены ребром.
Опр. Дополнением графа G называется граф с теми же вершинами что и граф G, и с теми ребрами, которые необходимо добавить к графу G, чтобы получить полный граф.
Полный граф
Неполный граф G
Дополнение графа G
v1
v2
v3
v4
v1
v2
v3
v4
v1
v2
v3
v4
13 слайд
Граф G={V,E} называется двудольным, если множество его вершин V можно разбить на два непересекающихся подмножества Vα Vβ, что каждое ребро (дуга) графа имеет один конец в Vα, а другой в Vβ .
Vα ={a,b,c,d}, Vα ={e,f,g,h},
Vβ ={m,n,p,q,s} Vβ ={x,r,t}
a
b
c
d
e
f
g
h
m
n
p
q
s
x
r
t
14 слайд
Паросочетанием графа G={V,E} называется подмножество его ребер (дуг) E´ E, выбранное так, что никакие два ребра (дуги) из E´не являются смежными, т.е. не имеют общей вершины
E´={(a,e),(b,g),(c,f),(d,h)} E´={<n,t>,<p,u>,<r,q>}
a
b
c
d
e
f
g
h
m
n
p
q
r
t
u
15 слайд
Граф G={V,E} называется взвешенным, если его ребрам (дугам) приписаны веса.
Взвешенный граф часто называют сетью
a
b
c
d
e
4
5
6
2,3
2,5
8
3
16 слайд
a
b
g
j
f
e
d
c
2
6
1,5
1,2
1,1
6,5
2,5
2,5
0,8
2,0
3,1
0,8
5,5
2
1,2
a исток сети (начальная вершина графа)
J сток сети (конечная вершина графа)
Примеры переходов
(a,c) (c,d) (d,e)
(a,d) (b,f) (f,j)
(a,d) (d,c) (c,b) (b,g) (g,j)
17 слайд
Маршрутом в неориентированном графе G={V,E} называется такая последовательность ребер e1, e2,. . . en, что каждые два соседних ребра ei-1, ei имеют общую инцидентную им вершину.
Записывается последовательностью вершин
a,c,f,j
a,d,c,b,f,g
d,c,f,e
Если первая и последняя вершина совпадают то маршрут называется циклическим.
18 слайд
Маршрут называется цепью, если каждое ребро графа (вершина) встречается в маршруте не более одного раза.
Граф не содержащий циклов, называется ациклическим.
Для орграфа аналогом маршрута является путь.
19 слайд
Гамильтоновым циклом в графе G={V,E} называется цикл, проходящий через каждую вершину графа в точности по одному разу.
Граф G={V,E}, содержащий гамильтоновый цикл, называется гамильтоновым графом.
Один из гамильтоновых
циклов 1,2,3,4
1
2
3
4
20 слайд
Вершины ei, ek графа G={V,E} называются связанными, если существует маршрут или цепь с началом ei и концом ek.
Граф или орграф G={V,E} называется связным, если все его вершины связан между собой, иначе называется несвязным.
f
e
d
c
b
a
c
a
b
d
e
f
Связный граф
Несвязный граф
мост
21 слайд
Связный ациклический граф называется деревом. Вершина дерева, степень которой равна 1 называется висячей вершиной.
Всякое ребро в дереве является мостом.
Все различные деревья с шестью вершинами
22 слайд
Дерево, у которого одна вершина выделяется среди других , называется корневым деревом. Выделенная вершина - корень, а висячие вершины листья.
Неориентированное корневое дерево
Ориентированное корневое дерево
Рабочие листы
к вашим урокам
Скачать
Презентация по дискретной математике "Элементы теории графов" подготовлена для изучения нового материала по теме "Теория графов" для студентов СПО специальности "Программирование в компьютерных системах".
В презентации представлены первоначальные сведения по теории графов, приведены исторические материалы, области применения, рассматриваются различные типы графов (орграфы, неориентированный, двудольные, взвешенные и др.). Слайды содержат примеры графический изображений графов.
Материал может использоваться при объяснении нового материала, повторении, самоподготовке студентов к практическим занятиям.
6 665 104 материала в базе
Настоящий материал опубликован пользователем Толоконников Александр Владимирович. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс профессиональной переподготовки
500/1000 ч.
Курс профессиональной переподготовки
300/600 ч.
Курс повышения квалификации
36/72 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Мини-курс
2 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.