Инфоурок / Математика / Презентации / Презентация по дискретной математике "Элементы теории графов"
Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

Педагогическая деятельность в соответствии с новым ФГОС требует от учителя наличия системы специальных знаний в области анатомии, физиологии, специальной психологии, дефектологии и социальной работы.

Только сейчас Вы можете пройти дистанционное обучение прямо на сайте "Инфоурок" со скидкой 40% по курсу повышения квалификации "Организация работы с обучающимися с ограниченными возможностями здоровья (ОВЗ)" (72 часа). По окончании курса Вы получите печатное удостоверение о повышении квалификации установленного образца (доставка удостоверения бесплатна).

Автор курса: Логинова Наталья Геннадьевна, кандидат педагогических наук, учитель высшей категории. Начало обучения новой группы: 27 сентября.

Подать заявку на этот курс    Смотреть список всех 216 курсов со скидкой 40%

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

библиотека
материалов
Элементы теории графов
ВВЕДЕНИЕ Теория графов – часть дискретной математики, геометрический подход к...
Однажды великому математику Леонарду Эйлеру был задан вопрос: можно ли обойти...
На карте старого Кёнигсберга был ещё один мост, появившийся чуть позже, и сое...
Применение Анализ и проектирование сетей электроснабжения, водоснабжения, газ...
Опр. Граф это множество вершин V={v1,v2,…vn} и множество неупорядоченных и уп...
Опр. Граф это множество вершин V={v1,v2,…vn} и множество неупорядоченных и уп...
Смешанный граф Смешанный граф Неориентированный граф Ориентированный граф ре...
Смежные вершины Смежные ребра (дуги) v1 v2 v3 v4 e1 e6 e5 e4 e3 e2 Ребро e5 и...
Опр. Степенью vi вершины графа G, обозначаемой di, называется число ее соседе...
Сумма полустепеней исходов (заходов) в орграфе G равно числу его ребер |Е|. С...
Опр. Граф G называется полным, если он не содержит петель и каждые две различ...
Граф G={V,E} называется двудольным, если множество его вершин V можно разбит...
Паросочетанием графа G={V,E} называется подмножество его ребер (дуг) E´ E, в...
Граф G={V,E} называется взвешенным, если его ребрам (дугам) приписаны веса. В...
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 исто...
Маршрутом в неориентированном графе G={V,E} называется такая последовательнос...
Маршрут называется цепью, если каждое ребро графа (вершина) встречается в мар...
Гамильтоновым циклом в графе G={V,E} называется цикл, проходящий через каждую...
Вершины ei, ek графа G={V,E} называются связанными, если существует маршрут...
Связный ациклический граф называется деревом. Вершина дерева, степень которой...
Дерево, у которого одна вершина выделяется среди других , называется корневым...
22 1

УЖЕ ЧЕРЕЗ 10 МИНУТ ВЫ МОЖЕТЕ ПОЛУЧИТЬ ДИПЛОМ

от проекта "Инфоурок" с указанием данных образовательной лицензии, что важно при прохождении аттестации.


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


Список всех тестов можно посмотреть тут - https://infourok.ru/tests

Описание презентации по отдельным слайдам:

№ слайда 1 Элементы теории графов
Описание слайда:

Элементы теории графов

№ слайда 2 ВВЕДЕНИЕ Теория графов – часть дискретной математики, геометрический подход к
Описание слайда:

ВВЕДЕНИЕ Теория графов – часть дискретной математики, геометрический подход к изучению объектов и связей Истоки: задача о Кенигсбергских мостах, о расстановке ферзей, о перевозке грузов и др.

№ слайда 3 Однажды великому математику Леонарду Эйлеру был задан вопрос: можно ли обойти
Описание слайда:

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

№ слайда 4 На карте старого Кёнигсберга был ещё один мост, появившийся чуть позже, и сое
Описание слайда:

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

№ слайда 5 Применение Анализ и проектирование сетей электроснабжения, водоснабжения, газ
Описание слайда:

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

№ слайда 6 Опр. Граф это множество вершин V={v1,v2,…vn} и множество неупорядоченных и уп
Описание слайда:

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

№ слайда 7 Опр. Граф это множество вершин V={v1,v2,…vn} и множество неупорядоченных и уп
Описание слайда:

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

№ слайда 8 Смешанный граф Смешанный граф Неориентированный граф Ориентированный граф ре
Описание слайда:

Смешанный граф Смешанный граф Неориентированный граф Ориентированный граф ребро дуга вершина Мультиграф Псевдограф Кратные ребра и дуги петля

№ слайда 9 Смежные вершины Смежные ребра (дуги) v1 v2 v3 v4 e1 e6 e5 e4 e3 e2 Ребро e5 и
Описание слайда:

Смежные вершины Смежные ребра (дуги) 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 вершины графа G, обозначаемой di, называется число ее соседей, или число ребер смежных vi, или число инцидентных ей ребер. Для орграфа используется выражение «полустепень захода» и «полустепень исхода» Опр. Полустепенью захода vi вершины графа G, называется число заходящих в неё дуг. Полустепенью исхода vi вершины графа G, называется число исходящих из неё дуг. v3 v6 v1 v2 v4 v5 Для вершины v3 1 полустепень захода и 4 полустепени исхода

№ слайда 11 Сумма полустепеней исходов (заходов) в орграфе G равно числу его ребер |Е|. С
Описание слайда:

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

№ слайда 12 Опр. Граф G называется полным, если он не содержит петель и каждые две различ
Описание слайда:

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

№ слайда 13 Граф G={V,E} называется двудольным, если множество его вершин V можно разбит
Описание слайда:

Граф 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, в
Описание слайда:

Паросочетанием графа 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} называется взвешенным, если его ребрам (дугам) приписаны веса. В
Описание слайда:

Граф 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 исто
Описание слайда:

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} называется такая последовательнос
Описание слайда:

Маршрутом в неориентированном графе 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} называется цикл, проходящий через каждую вершину графа в точности по одному разу. Граф G={V,E}, содержащий гамильтоновый цикл, называется гамильтоновым графом. Один из гамильтоновых циклов 1,2,3,4 4 1 2 3

№ слайда 20 Вершины ei, ek графа G={V,E} называются связанными, если существует маршрут
Описание слайда:

Вершины 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 Дерево, у которого одна вершина выделяется среди других , называется корневым
Описание слайда:

Дерево, у которого одна вершина выделяется среди других , называется корневым деревом. Выделенная вершина - корень, а висячие вершины листья. Неориентированное корневое дерево Ориентированное корневое дерево

Краткое описание документа:

Презентация по дискретной математике "Элементы теории графов" подготовлена для изучения нового материала по теме "Теория графов" для студентов СПО специальности "Программирование в компьютерных системах".

В презентации представлены первоначальные сведения по теории графов, приведены исторические материалы, области применения, рассматриваются различные типы графов (орграфы, неориентированный, двудольные, взвешенные и др.). Слайды содержат примеры графический изображений графов. 

Материал может использоваться при объяснении нового материала, повторении, самоподготовке студентов к практическим занятиям.

Общая информация

Номер материала: 536578

Похожие материалы