Теория графов - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Теория графов. Доклад-сообщение содержит 52 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Теория графов Лекция 1

Слайд 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

Описание слайда:

взвешенные метаграфы

Слайд 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 – смежны

Слайд 13

Описание слайда:

Пример

Слайд 14

Описание слайда:

Степень вершины Степень вершины (d(vi)) – число рёбер, инцидентных вершине d(v1)=2 d(v2)=2 d(v3)=3 d(v4)=1

Слайд 15

Описание слайда:

Теорема В любом конечном графе число вершин нечётной степени чётно.

Слайд 16

Описание слайда:

Свойства степеней графа Gp,q

Слайд 17

Описание слайда:

Степень графа Степень графа (максимальная степень вершины) Минимальная степень вершины графа

Слайд 18

Описание слайда:

Локальная структура ориентированного графа uk= (vi,vj) – дуга uk положительно инцидентна vi, дуга uk отрицательно инцидентна vj, uk= (vi,vj), un= (vi,vm) – uk и un – смежны

Слайд 19

Описание слайда:

Пример

Слайд 20

Описание слайда:

Степени вершин в орграфе d+(vi) – число положительно инцидентных дуг вершины vi. d-(vi) – число отрицательно инцидентных дуг вершины vi.

Слайд 21

Описание слайда:

Свойства степеней орграфа Для любого ориентированного графа

Слайд 22

Описание слайда:

Свойства степеней орграфа Для любого ориентированного графа

Слайд 23

Описание слайда:

Матричное представление графа Матрица смежности А:

Слайд 24

Описание слайда:

Пример

Слайд 25

Описание слайда:

Матрица инцидентности В

Слайд 26

Описание слайда:

Пример

Слайд 27

Описание слайда:

Матрица смежности орграфа А:

Слайд 28

Описание слайда:

Пример

Слайд 29

Описание слайда:

Матрица инцидентности В

Слайд 30

Описание слайда:

Пример

Слайд 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

Описание слайда:

Свойства изоморфизма Отношение рефлексивно симметрично транзитивно Эквивалентность

Слайд 39

Описание слайда:

Пример изоморфных графов

Слайд 40

Описание слайда:

Пример не изоморфных графов

Слайд 41

Описание слайда:

Инварианты графа Количественная или качественная характеристики, неизменные для всех изоморфных между собой графов (орграфов) называется ИНВАРИАНТОМ Поиск полной системы инвариантов графа, задающей граф с точность до изоморфизма – основная задача теории графов (полная система инвариантов ещё не найдена)

Слайд 42

Описание слайда:

Полный граф Kn Граф полный, если каждая вершина смежна с каждой. Полный граф с n вершинами - Kn

Слайд 43

Описание слайда:

Двудольный граф Граф двудольный, если множество вершин графа можно разбить на два непересекающихся подмножества, в каждом из которых никакая пара вершин не смежна. G=, V=V1V2, V1V2=, UV1V2

Слайд 44

Описание слайда:

Двудольные графы. Примеры

Слайд 45

Описание слайда:

Полный двудольный граф Km,n Km,n - граф двудольный и каждая вершина из множества V1 смежна с каждой вершиной из V2, V1=m, V2=n. G=, V=V1V2, V1V2=, U=V1V2