Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Презентации / Презентация по дискретной математике "Элементы теории графов"

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

Самые низкие цены на курсы профессиональной переподготовки и повышения квалификации!

Предлагаем учителям воспользоваться 50% скидкой при обучении по программам профессиональной переподготовки.

После окончания обучения выдаётся диплом о профессиональной переподготовке установленного образца (признаётся при прохождении аттестации по всей России).

Обучение проходит заочно прямо на сайте проекта "Инфоурок".

Начало обучения ближайших групп: 18 января и 25 января. Оплата возможна в беспроцентную рассрочку (20% в начале обучения и 80% в конце обучения)!

Подайте заявку на интересующий Вас курс сейчас: https://infourok.ru/kursy


СВИДЕТЕЛЬСТВО СРАЗУ ПОСЛЕ ПРОСМОТРА ВЕБИНАРА

Вебинар «Подростковая лень: причины, способы борьбы»

Просмотр и заказ свидетельств доступен только до 22 января! На свидетельстве будет указано 2 академических часа и данные о наличии образовательной лицензии у организатора, что поможет Вам качественно пополнить собственное портфолио для аттестации.

Получить свидетельство за вебинар - https://infourok.ru/webinar/65.html

  • Математика
Элементы теории графов
ВВЕДЕНИЕ Теория графов – часть дискретной математики, геометрический подход к...
Однажды великому математику Леонарду Эйлеру был задан вопрос: можно ли обойти...
На карте старого Кёнигсберга был ещё один мост, появившийся чуть позже, и сое...
Применение Анализ и проектирование сетей электроснабжения, водоснабжения, газ...
Опр. Граф это множество вершин 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} называются связанными, если существует маршрут...
Связный ациклический граф называется деревом. Вершина дерева, степень которой...
Дерево, у которого одна вершина выделяется среди других , называется корневым...
1 из 22

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

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

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

Идёт приём заявок на самые массовые международные олимпиады проекта "Инфоурок"

Для учителей мы подготовили самые привлекательные условия в русскоязычном интернете:

1. Бесплатные наградные документы с указанием данных образовательной Лицензии и Свидeтельства СМИ;
2. Призовой фонд 1.500.000 рублей для самых активных учителей;
3. До 100 рублей за одного ученика остаётся у учителя (при орг.взносе 150 рублей);
4. Бесплатные путёвки в Турцию (на двоих, всё включено) - розыгрыш среди активных учителей;
5. Бесплатная подписка на месяц на видеоуроки от "Инфоурок" - активным учителям;
6. Благодарность учителю будет выслана на адрес руководителя школы.

Подайте заявку на олимпиаду сейчас - https://infourok.ru/konkurs

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

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

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

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

Автор
Дата добавления 17.05.2015
Раздел Математика
Подраздел Презентации
Просмотров551
Номер материала 536578
Получить свидетельство о публикации

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

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

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

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

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

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