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

объектов и связей
Истоки: задача о Кенигсбергских мостах, о расстановке ферзей, о перевозке грузов и др.

все семь мостов, стоявших тогда в городе Кёнигсберге (современный Калининград, Россия), побывав на каждом по одному разу? Перед вами план Кёнигсберга – можете попробовать!

и соединявший остров Ломзе с южной стороной. Своему появлению этот мост обязан самой задаче Эйлера-Канта. А произошло это вот как. Кайзер (император) Вильгельм славился своей прямотой, простотой мышления и солдатской «недалёкостью». Однажды, находясь на светском рауте, он чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на приёме. Они показали кайзеру карту Кёнигсберга, и попросили попробовать решить эту знаменитую задачу, которая по определению была нерешаемой. Ко всеобщему удивлению, кайзер попросил перо и лист бумаги, сказав, что решит задачу за полторы минуты. Ошеломлённый немецкий истеблишмент не мог поверить своим ушам, но бумагу и чернила быстро нашли. Кайзер положил листок на стол, взял перо, и написал: «приказываю построить восьмой мост на острове Ломзе». Так в Кёнигсберге и появился новый мост, который так и назвали — мост кайзера.

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

пар вершин E={e1,e2,…em}. Граф обозначается так: G={V, E}.
Неупорядоченная пара вершин называется ребром, а упорядоченная дугой.
Граф содержащий только ребра называется неориентированным.
Граф содержащий только дуги называется ориентированным или орграфом.

пар вершин E={e1,e2,…em}. Граф обозначается так: G={V, E}.
Неупорядоченная пара вершин называется ребром, а упорядоченная дугой.
Граф содержащий только ребра называется неориентированным.
Граф содержащий только дуги называется ориентированным или орграфом.

Вершина v1 инцидентна ребру e6.
Ребро (u, v) соединяет вершины u и v.
Дуга начинается в вершине u и заканчивается в вершине v

Вершины v2 v3 и v4 соседи вершины v1

соседей, или число ребер смежных vi, или число инцидентных ей ребер.
Для орграфа используется выражение «полустепень захода» и «полустепень исхода»
Опр. Полустепенью захода vi вершины графа G, называется число заходящих в неё дуг. Полустепенью исхода vi вершины графа G, называется число исходящих из неё дуг.

v3

v6

v1

v2

v4

v5

Для вершины v3 1 полустепень захода и
4 полустепени исхода

|Е|.
Сумма степеней вершин неориентированного графа равна 2|Е|, где |Е| число ребер.
Вершина vi графа G называется изолированной, если ее степень di=0. Если степень di=1, то вершина называется концевой.

V2 (концевая)

V1 (изолированная)

v3

v4

v5

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

Полный граф

Неполный граф G

Дополнение графа G

v1

v2

v3

v4

v1

v2

v3

v4

v1

v2

v3

v4

на два непересекающихся подмножества 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

выбранное так, что никакие два ребра (дуги) из E´не являются смежными, т.е. не имеют общей вершины




E´={(a,e),(b,g),(c,f),(d,h)} E´={,,}

a

b

c

d

e

f

g

h

m

n

p

q

r

t

u

часто называют сетью

a

b

c

d

e

4

5

6

2,3

2,5

8

3

переходов
(a,c) (c,d) (d,e)
(a,d) (b,f) (f,j)
(a,d) (d,c) (c,b) (b,g) (g,j)

. . en, что каждые два соседних ребра ei-1, ei имеют общую инцидентную им вершину.
Записывается последовательностью вершин
a,c,f,j
a,d,c,b,f,g
d,c,f,e
Если первая и последняя вершина совпадают то маршрут называется циклическим.

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

графа в точности по одному разу.
Граф G={V,E}, содержащий гамильтоновый цикл, называется гамильтоновым графом.
Один из гамильтоновых
циклов 1,2,3,4

4

цепь с началом ei и концом ek.
Граф или орграф G={V,E} называется связным, если все его вершины связан между собой, иначе называется несвязным.

f

e

d

c

b

a

Связный граф

Несвязный граф

мост

называется висячей вершиной.
Всякое ребро в дереве является мостом.

Все различные деревья с шестью вершинами

деревом. Выделенная вершина - корень, а висячие вершины листья.

Неориентированное корневое дерево

Ориентированное корневое дерево