🗊Презентация Теория графов

Категория: Математика
Нажмите для полного просмотра!
Теория графов, слайд №1Теория графов, слайд №2Теория графов, слайд №3Теория графов, слайд №4Теория графов, слайд №5Теория графов, слайд №6Теория графов, слайд №7Теория графов, слайд №8Теория графов, слайд №9Теория графов, слайд №10Теория графов, слайд №11Теория графов, слайд №12Теория графов, слайд №13Теория графов, слайд №14Теория графов, слайд №15Теория графов, слайд №16Теория графов, слайд №17Теория графов, слайд №18Теория графов, слайд №19Теория графов, слайд №20Теория графов, слайд №21Теория графов, слайд №22Теория графов, слайд №23Теория графов, слайд №24Теория графов, слайд №25Теория графов, слайд №26Теория графов, слайд №27Теория графов, слайд №28Теория графов, слайд №29Теория графов, слайд №30Теория графов, слайд №31Теория графов, слайд №32Теория графов, слайд №33Теория графов, слайд №34Теория графов, слайд №35Теория графов, слайд №36Теория графов, слайд №37Теория графов, слайд №38Теория графов, слайд №39Теория графов, слайд №40Теория графов, слайд №41Теория графов, слайд №42Теория графов, слайд №43Теория графов, слайд №44Теория графов, слайд №45Теория графов, слайд №46Теория графов, слайд №47Теория графов, слайд №48Теория графов, слайд №49Теория графов, слайд №50Теория графов, слайд №51Теория графов, слайд №52
Скачать

Содержание ▲

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

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

Слайд 1


Теория графов Лекция 1
Описание слайда:
Теория графов Лекция 1

Слайд 2


Литература В.А. Горбатов Дискретная математика М.: АСТ; Астрель, 2003 Харари Ф. Теория графов, 2003г Кристофидес, Н. Теория графов. Алгоритмический подход. 1978 Кузнецов О.П., Дискретная математика для инженера, 2009. Тихомирова А.Н. Теория графов, МИФИ,
Описание слайда:
Литература В.А. Горбатов Дискретная математика М.: АСТ; Астрель, 2003 Харари Ф. Теория графов, 2003г Кристофидес, Н. Теория графов. Алгоритмический подход. 1978 Кузнецов О.П., Дискретная математика для инженера, 2009. Тихомирова А.Н. Теория графов, МИФИ,

Слайд 3


Задача о Кёнигсбергских мостах Леонард Эйлер(1707-1783)
Описание слайда:
Задача о Кёнигсбергских мостах Леонард Эйлер(1707-1783)

Слайд 4


Основные объекты графов носитель метаграфа (конечное множество вершин). V={v1,v2, … vp} сигнатура метаграфа (конечное множество связей между вершинами). U={u1,u2, … uq}
Описание слайда:
Основные объекты графов носитель метаграфа (конечное множество вершин). V={v1,v2, … vp} сигнатура метаграфа (конечное множество связей между вершинами). U={u1,u2, … uq}

Слайд 5


Понятие графа и орграфа Граф G=<V,U>, где V={v1,v2,…,vn}, n1 – множество вершин (носитель), UVV (сигнатура).
Описание слайда:
Понятие графа и орграфа Граф G=<V,U>, где V={v1,v2,…,vn}, n1 – множество вершин (носитель), UVV (сигнатура).

Слайд 6


Неориентированный граф (граф) G = <V, U>, V = {v1,v2,…,vn},n1, UVV (vi,vj) = (vj, vi) (vi,vj) – ребро графа (vi, vi) - петля
Описание слайда:
Неориентированный граф (граф) G = <V, U>, V = {v1,v2,…,vn},n1, UVV (vi,vj) = (vj, vi) (vi,vj) – ребро графа (vi, vi) - петля

Слайд 7


Ориентированный граф (орграф) G=<V,U>, V={v1,v2,…,vn},n1 UVV (vi,vj) ≠ (vj, vi) (vi,vj) - дуга
Описание слайда:
Ориентированный граф (орграф) G=<V,U>, 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 - тривиальный граф
Описание слайда:
Обозначение Gp,q V= p, U= q G1,0 - тривиальный граф

Слайд 10


типы метаграфов ГИПЕРГРАФ (модельный граф) Сигнатура (U) - множество граней, каждая из которых связывает некоторое подмножество вершин. Грань – подмножество вершин гиперграфа
Описание слайда:
типы метаграфов ГИПЕРГРАФ (модельный граф) Сигнатура (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 – смежны
Описание слайда:
Локальная структура графа (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
Описание слайда:
Степень вершины Степень вершины (d(vi)) – число рёбер, инцидентных вершине d(v1)=2 d(v2)=2 d(v3)=3 d(v4)=1

Слайд 15


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

Слайд 16


Свойства степеней графа Gp,q
Описание слайда:
Свойства степеней графа Gp,q

Слайд 17


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

Слайд 18


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

Слайд 19


Пример
Описание слайда:
Пример

Слайд 20


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

Слайд 21


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

Слайд 22


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

Слайд 23


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

Слайд 24


Пример
Описание слайда:
Пример

Слайд 25


Матрица инцидентности В
Описание слайда:
Матрица инцидентности В

Слайд 26


Пример
Описание слайда:
Пример

Слайд 27


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

Слайд 28


Пример
Описание слайда:
Пример

Слайд 29


Матрица инцидентности В
Описание слайда:
Матрица инцидентности В

Слайд 30


Пример
Описание слайда:
Пример

Слайд 31


Функциональный способ задания графов G=<V,Г> Г- функция окрестности вершин Г:VP(V) Г(v)={vi  vi смежна с v}
Описание слайда:
Функциональный способ задания графов G=<V,Г> Г- функция окрестности вершин Г:VP(V) Г(v)={vi  vi смежна с v}

Слайд 32


Пример Г(v1)={v2, v3} Г(v2)={v1, v3} Г(v3)={v1, v2,v4} Г(v4)={v3}
Описание слайда:
Пример Г(v1)={v2, v3} Г(v2)={v1, v3} Г(v3)={v1, v2,v4} Г(v4)={v3}

Слайд 33


Функциональный способ задания орграфов G=<V,Г+> G=<V,Г-> Г+, Г- - функции положительной и отрицательной полуокрестности вершины, соответственно
Описание слайда:
Функциональный способ задания орграфов G=<V,Г+> G=<V,Г-> Г+, Г- - функции положительной и отрицательной полуокрестности вершины, соответственно

Слайд 34


Пример Г(v1)+={v2, v3} Г(v2)+={v3} Г(v3)+={v2,v4} Г(v4)+=
Описание слайда:
Пример Г(v1)+={v2, v3} Г(v2)+={v3} Г(v3)+={v2,v4} Г(v4)+=

Слайд 35


Пример Г(v1)-= Г(v2)- ={v1,v3} Г(v3) -={v1,v2} Г(v4)-={v3}
Описание слайда:
Пример Г(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
Описание слайда:
Функциональное задание изоморфизма графов Два графа 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
Описание слайда:
Полный граф Kn Граф полный, если каждая вершина смежна с каждой. Полный граф с n вершинами - Kn

Слайд 43


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

Слайд 44


Двудольные графы. Примеры
Описание слайда:
Двудольные графы. Примеры

Слайд 45


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

Слайд 46


Полные двудольные графы Km,n
Описание слайда:
Полные двудольные графы Km,n

Слайд 47


Операции над графами Удаление ребра G=<V, U>, G\u=<V, U\{u}>
Описание слайда:
Операции над графами Удаление ребра G=<V, U>, G\u=<V, U\{u}>

Слайд 48


Удаление вершины G=<V, U>, G\v=<V’, U’> V’=V\{v}, U’=U(V’ V’)
Описание слайда:
Удаление вершины G=<V, U>, G\v=<V’, U’> V’=V\{v}, U’=U(V’ V’)

Слайд 49


Подграфы G’=<V’, U’> - подграф графа G=<V, U>, если V’V, U’=U(V’ V’) (порождённый подграф)
Описание слайда:
Подграфы G’=<V’, U’> - подграф графа G=<V, U>, если V’V, U’=U(V’ V’) (порождённый подграф)

Слайд 50


Подграфы G’=<V’, U’> - частичный подграф графа G=<V, U>, если V’V, U’U(V’ V’) (частичный граф, подграф)
Описание слайда:
Подграфы G’=<V’, U’> - частичный подграф графа G=<V, U>, если V’V, U’U(V’ V’) (частичный граф, подграф)

Слайд 51


Дополнение графа =<V, U’> - дополнение графа G=<V,U>, если U’=((VV)\U)\I
Описание слайда:
Дополнение графа =<V, U’> - дополнение графа G=<V,U>, если U’=((VV)\U)\I

Слайд 52


Самодополнительные графы Граф, изоморфный своему дополнению - самодополнительный
Описание слайда:
Самодополнительные графы Граф, изоморфный своему дополнению - самодополнительный

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию