Слайд 2
Литература
В.А. Горбатов Дискретная математика М.: АСТ; Астрель, 2003
Харари Ф. Теория графов, 2003г
Кристофидес, Н. Теория графов. Алгоритмический
подход. 1978
Кузнецов О.П., Дискретная математика для инженера, 2009.
Тихомирова А.Н. Теория графов, МИФИ,
Слайд 3
Задача о Кёнигсбергских мостах
Леонард Эйлер(1707-1783)
Слайд 4
Основные объекты графов
носитель метаграфа (конечное множество
вершин). V={v1,v2, … vp}
сигнатура метаграфа (конечное множество связей
между вершинами). U={u1,u2, … uq}
©П.Порешин
Слайд 5
Понятие графа и орграфа
Граф G=, где
V={v1,v2,…,vn}, n≥1
– множество вершин (носитель),
U⊆V×V (сигнатура).
Слайд 6
Неориентированный граф (граф)
G = ,
V =
{v1,v2,…,vn},n≥1,
U⊆V×V
(vi,vj) = (vj, vi)
(vi,vj) – ребро графа
(vi,
vi) - петля
Слайд 7
Ориентированный граф (орграф)
G=,
V={v1,v2,…,vn},n≥1
U⊆V×V
(vi,vj) ≠ (vj,
vi)
(vi,vj) - дуга
Слайд 8
Геометрический граф
Граф
Орграф
Слайд 9
Обозначение
Gp,q ⏐V⏐= p, ⏐U⏐= q
G1,0 - тривиальный
граф
Слайд 10
типы метаграфов
ГИПЕРГРАФ (модельный граф)
Сигнатура (U) - множество
граней, каждая из которых связывает некоторое подмножество вершин. Грань
– подмножество вершин гиперграфа
©П.Порешин
Слайд 11
взвешенные метаграфы
f: V→N - весовая функция для носителя
(вершин)
g: U →K - весовая функция для сигнатуры
(ребер или дуг)
N, K – некоторые множества (весовые характеристики)
©П.Порешин
Слайд 12
Локальная структура графа
(vi,vj)∈U – vi и vj –
смежны
uk= (vi,vj) – uk инцидентно vi,
uk инцидентно vj, vi
инцидентно uk
vj инцидентно uk
uk= (vi,vj), un= (vi,vm) –
uk и un – смежны
Слайд 14
Степень вершины
Степень вершины (d(vi)) – число рёбер, инцидентных
вершине
d(v1)=2
d(v2)=2
d(v3)=3
d(v4)=1
Слайд 15
Теорема
В любом конечном графе число вершин нечётной степени
чётно.
Слайд 17
Степень графа
Степень графа (максимальная степень вершины)
Минимальная степень вершины
графа
Слайд 18
Локальная структура ориентированного графа
uk= (vi,vj) – дуга uk
положительно инцидентна vi,
дуга uk отрицательно инцидентна vj,
uk= (vi,vj),
un= (vi,vm) –
uk и un – смежны
Слайд 20
Степени вершин в орграфе
d+(vi) – число положительно инцидентных
дуг вершины vi.
d-(vi) – число отрицательно инцидентных дуг
вершины vi.
d+(v1) =2, d-(v1) =0;
d+(v2) =1, d-(v2) =2.
Слайд 21
Свойства степеней орграфа
Для любого ориентированного графа
Слайд 22
Свойства степеней орграфа
Для любого ориентированного графа
Слайд 23
Матричное представление графа
Матрица смежности А:
Слайд 31
Функциональный способ задания графов
G=
Г- функция окрестности вершин
Г:V→P(V)
Г(v)={vi ⎢ vi смежна с v}
Слайд 32
Пример
Г(v1)={v2, v3}
Г(v2)={v1, v3}
Г(v3)={v1, v2,v4}
Г(v4)={v3}
Слайд 33
Функциональный способ задания орграфов
G= G=
Г+, Г- -
функции положительной и отрицательной полуокрестности вершины, соответственно
Слайд 34
Пример
Г(v1)+={v2, v3}
Г(v2)+={v3}
Г(v3)+={v2,v4}
Г(v4)+=∅
Слайд 35
Пример
Г(v1)-=∅
Г(v2)- ={v1,v3}
Г(v3) -={v1,v2}
Г(v4)-={v3}
Слайд 36
Изоморфизм графов
Графы изоморфны, если существует взаимно однозначное соответствие
между множествами вершин, сохраняющее отношение смежности
Слайд 37
Функциональное задание изоморфизма графов
Два графа Ga=〈Va,Ua〉 и Gb=〈Vb,Ub〉
изоморфны, если существует взаимно однозначная функция
h: Va→Vb такая,
что:
1) если (va1 ,va2 )∈ Ua, то (h(va1),h(va2)) ∈ Ub;
2) если (vb1,vb2) ∈ Ub, то (h-1(vb1),h-(vb2)) ∈ Ua
Слайд 38
Свойства изоморфизма
Отношение
рефлексивно
симметрично
транзитивно
Эквивалентность
Слайд 41
Инварианты графа
Количественная или качественная характеристики, неизменные для
всех изоморфных между собой графов (орграфов) называется ИНВАРИАНТОМ
Поиск полной
системы инвариантов графа, задающей граф с точность до изоморфизма – основная задача теории графов
(полная система инвариантов ещё не найдена)
Слайд 42
Полный граф Kn
Граф полный, если каждая вершина смежна
с каждой.
Полный граф с n вершинами - Kn
Слайд 43
Двудольный граф
Граф двудольный, если множество вершин графа можно
разбить на два непересекающихся подмножества, в каждом из которых
никакая пара вершин не смежна.
G=, V=V1∪V2, V1∩V2=∅, U⊆V1×V2
Слайд 45
Полный двудольный граф Km,n
Km,n - граф двудольный и
каждая вершина из множества V1 смежна с каждой вершиной
из V2, ⎜V1⎜=m, ⎜V2⎜=n.
G=, V=V1∪V2, V1∩V2=∅, U=V1×V2
Слайд 47
Операции над графами
Удаление ребра
G=, G\u=
Слайд 48
Удаление вершины
G=, G\v=
V’=V\{v}, U’=U∩(V’× V’)
Слайд 49
Подграфы
G’= - подграф графа G=, если
V’⊆V, U’=U∩(V’× V’)
(порождённый подграф)
Слайд 50
Подграфы
G’= - частичный подграф графа G=,
если
V’⊆V, U’⊆U∩(V’× V’) (частичный граф, подграф)
