Добавить материал

и получить 10 документов
и свидетельство СМИ

Изображение пользователя Харченко Вера Дмитриевна Харченко Вера Дмитриевна

Основные понятия Теории графов

  • Презентации учебные
  • ppt
  • 24.01.2018
Публикация в СМИ для учителей

Публикация в СМИ для учителей

Бесплатное участие. Свидетельство СМИ сразу.
Мгновенные 10 документов в портфолио.

Добавить материал
Презентация по дисциплине ЕН.01 "Математика" для групп 2 курса СПО в ГБПОУ КК "АМТ" по теме: "Основные понятия Теории графов". В данной презентации даны определения основных видов граф, в качестве примера рассматривается задача Эйлера. Закрепляется материал решением задач и построением граф.
Иконка файла материала Граф 1 !МОЯ.ppt
Графы
Помните задачу из детства: — необходимо нарисовать открытый конверт, не отрывая карандаша от бумаги, и не проходя дважды по любой из сторон?
Определение   Граф G — это совокупность двух конечных множеств: множества точек, которые называются вершинами, и множества пар вершин, которые называются ребрами.
Ребра могут быть:  смежными - пара неориентированных рёбер, имеющих общую вершину. кратными -вершины соединяются более, чем одним ребром. Если же концы одного ребра совпадают, то такое ребро называется петлей.
Степенью вершины  называют количество инцидентных ей ребер (т.е. ребер, входящих в вершину). При этом петли считают дважды.
таких Теория графов зародилась в ходе решения головоломок двести с лишним лет назад. Одной из задач- головоломок была задача о кенигсбергских мостах, которая привлекла к себе внимание Леонарда Эйлера (1707-1783), долгое время жившего и работавшего в России (с 1727 по 1741 год и с 1766 до конца жизни).
Задача Эйлера Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды? Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок.
Для решения этой задачи  Эйлер вводит понятие  «графа» как множества  непересекающихся рёбер ,  соединяющих пары вершин.  Вот так выглядит этот граф,  если наложить вершины и  связи на карту  города  Вывод: В графе, имеющим более  двух вершин с нечетной  степенью, такого обхода не  существует
П р а в и л о Э й л е р П р а в и л о Э й л е р а:а: 1.В графе, не имеющем вершин нечетных степеней, существует обход всех рёбер (причем каждое ребро проходится в точности один раз) с началом в любой вершине графа. 2.В графе, имеющем две и только две вершины с нечетными степенями, существует обход с началом в одной вершине с нечетной степенью и концом в другой. 3.В графе, имеющим более двух вершин с нечетной степенью, такого обхода не существует
С графами встречаются: С графами встречаются:
Задача:
Виды графов Ориентированный Неориентированный Взвешенный 2 3 1 5 ОриентированныйНеориентированныйВзвешенный
Неориентированный граф – в котором связи не направлены. Маша Петя Таня Саша Катя Аня Коля Миша Граф дружбы МашаПетяМишаКоляАняКатяТаняСашаГраф дружбы
Ориентированный граф – в котором связи направлены. Рождени е Юность Зрелость Старость Граф жизни Смерть РождениеЮностьЗрелостьСтаростьСмертьГраф жизни
Взвешенный граф в котором рёбра содержат дополнительную информацию. 10 5 1 +9 -5 -7 -1 8 9 +2 -1 7 6 +9 0 -6 189105760
Взвешенный граф союз СССР война США война ЯПОНИЯ война война ГЕРМАНИЯ союз СССРГЕРМАНИЯСШАЯПОНИЯ
Граф-дерево Деревом называется любой связный граф, не имеющий циклов. Так выглядит схема участников в Олимпийских играх. Чемпион Финалисты Полуфиналисты Четвертьфиналисты Первоначальные игроки Так выглядит схема участников в Олимпийских играх.
Иерархический граф Иерархия – это расположение частей или элементов целого в порядке от высшего к низшему. Это – граф отношения подчиненности в школе: Директор Заместитель директора Учителя Ученики Иерархия – это расположение частей или элементов целого в порядке от высшего к низшему. Это – граф отношения подчиненности в школе:ДиректорЗаместитель директораУченикиУчителя
Если в графе существуют кратные ребра, то есть вершины соединены более чем одним ребром, то такой граф называется мультиграфом. Если в графе существуют еще и петли, то такой граф называется псевдографом.
Итак, виды графов: Ориентированный Неориентированный Взвешенный Иерархический Дерево Мультиграф Псевдограф
Задача: На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.
Задача: У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?
Задача. В бутылке, стакане, кувшине и банке  находятся молоко, лимонад, квас и вода.  Известно, что вода и молоко не в бутылке,  сосуд с лимонадом стоит между кувшином и  сосудом с квасом, в банке не лимонад и не  вода. Стакан стоит около банки и сосуда с  молоком. Куда налита каждая жидкость? Начертим таблицу: Молоко Лимонад Квас Вода Бутылка Стакан Кувшин Банка
Бутылка Стакан Кувшин Банка Молоко Лимонад Квас - - - + - - + - + - - - Вода - + - - 1. Вода и молоко не в бутылке. 2. В банке не лимонад и не вода. 3. Молоко  Банка  Стакан. (?) 4. В кувшине молоко, поэтому везде, кроме молока, ставим -. 5. Тогда понятно, что квас налит в банку. 6. Вода в стакане. 7. Лимонад в бутылке.
Решение с помощью графа: Красными линиями соединим вершины, которые не могут быть связаны друг с другом. Синими линиями соединим вершины, которыми возможно могут быть связаны друг с другом. Зелеными линиями соединим вершины, которые связаны друг с другом. БУТЫЛКА СТАКАН БАНКА КУВШИН МОЛОКО ЛИМОНА Д КВАС ВОДА Ответ: бутылка-лимонад, стакан-вода, банка-квас, кувшин-молоко. БУТЫЛКАСТАКАНБАНКАКУВШИНМОЛОКОЛИМОНАДКВАСВОДА
Графы придают условиям задачи наглядность, упрощают решение, выявляют сходство задач. Сейчас в любой отрасли науки и техники встречаешься с графами: Электротехники при построении электрических схем Тур-компании при систематизации маршрутов
Вывод:                                                 Граф  — это  совокупность двух конечных множеств:  множества точек, которые называются  вершинами, и множества пар вершин, которые  называются ребрами. Степенью вершины  называется число ребер, которым принадлежит  вершина. С помощью графов часто упрощается  решение задач, сформулированных в различных  областях знаний: в автоматике, электронике,  физике, химии и др.
Составить граф 1) (1, 2), (2, 3), (3, 1), (3, 5),(5, 4), (4, 2) (1, 3) , (2, 1), (3, 2), (3, 4), (4, 5), 3). (5, 3).
Задача: (дополнительно) В группе учатся 40 студентов. Из них по русскому языку имеют «пятерки» 19 человек, по математике – 17 человек и по информатике – 22 человека. Только по одному предмету имеют «пятерки»: по русскому языку – 4 человека, по математике – 4 человека, по информатике – 11 человек. Семь студентов имеют «пятерки» и по математике и по информатике, а 5 студентов – «пятерки» по всем предметам. Сколько человек учится без «пятерок»? Сколько человек имеют «пятерки» по двум из трех предметов?

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

Посмотрите также