Информационные модели. Графы. Презентация: Графы и их применение при решении задач Примеры полных графов

Слайд 2

Граф – это конечная совокупность вершин, некоторые из которых соединены ребрами т.е. это совокупность точек, называемых вершинами, и линий, соединяющих некоторые из вершин, называемых ребрами или дугами в зависимости от вида графа.(н-р, схема метрополитена, генеалогическое дерево, дерево папок и каталогов и др.)

Слайд 3

Виды (примеры) графов:

Обычный (неориентированный) граф 2 вершины могут быть соединены только одним ребром. Соединяющие линии называются ребрами. (смежные вершины – это 2 вершины, соединенные ребром)

Слайд 4

Ориентированный граф (орграф) - это граф, у которого на линиях, соединяющих вершины, указано направление (соединяющие линии называются дугами)

Слайд 5

Нагруженный граф - это граф, у которого около каждого ребра проставлено число, характеризующее связь между соответствующими вершинами (граф с помеченными ребрами).

Слайд 6

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

Слайд 7

Решение задачи, моделируемой нагруженным графом или сетью, сводится, как правило, к нахождению оптимального в том или ином смысле маршрута, ведущего от одной вершины к другой

Слайд 8

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

Слайд 9

Мультиграф 2 вершины соединены 2 ребрами и более (кратные ребра)

Слайд 10

Петля в графе (ребро соединяет вершину саму с собой)

Слайд 11

Понятие степени вершины графа – это количество ребер, выходящих из одной вершины

Слайд 12

СВОЙСТВА ГРАФОВ:

1) Для любого графа сумма степеней вершин равна удвоенному количеству ребер 2) Для любого графа количество вершин нечетной степени всегда четно (аналог задачи: в любой момент времени количество людей, сделавших нечетное количество рукопожатий, четно) 3) В любом графе есть по крайней мере 2 вершины, имеющие одинаковую степень.

Слайд 13

1) Маршрут на графе – это последовательность ребер, в которой конец одного ребра служит началом следующего (циклический маршрут – если конец последнего ребра последовательности совпадает с началом 1-го ребра)2) Цепь – это маршрут, в котором каждое ребро содержится не более одного раза3) Цикл – это цепь, являющаяся циклическим маршрутом4) Простая цепь – это цепь, проходящая через каждую свою вершину ровно 1 раз5) Простой цикл – это цикл, являющийся простой цепью6) Связанные вершины – это вершины (например, А и B), для которых существует цепь, начинающаяся в А и заканчивающаяся в B7)Связный граф – это граф, у которого любые 2 вершины связанны. Если граф несвязен, то в нем можно выделить так называемые связанные компоненты (т.е. множества вершин, соединенных ребрами исходного графа, каждое из которых является связным графом)Один и тот же граф может быть изображен по-разному.

Слайд 14

Пример 1

V={1,2,3,4,5,6,7,8,9,10}-это множество вершин графа. Для каждого из перечисленных ниже случаев изобразите граф и определите все степени вершин а) вершины x y соединены ребром тогда и только тогда, когда (x-y)/3 целое число б) вершины x y соединены ребром тогда и только тогда, когда x+y=9 в) вершины x y соединены ребром тогда и только тогда, когда x+y содержится в множестве V={1,2,3,4,5,6,7,8,9,10} г) вершины x y соединены ребром тогда и только тогда, когда |x-y|

1 слайд

2 слайд

Впервые основы теории графов появились в работах Леонарда Эйлера (1707-1783; швейцарский, немецкий и российский математик) , в которых он описывал решение головоломок и математических развлекательных задач. Теория графов началась с решения Эйлером задачи о семи мостах Кёнигсберга.

3 слайд

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды? Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно. На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города - точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам: Невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

4 слайд

Существуют 4 группы крови. При переливании крови от одного человека к другому не все группы совместимы. Но известно, что одинаковые группы можно переливать от человека к человеку, т.е. 1 – 1, 2 – 2 и т.д. А также 1 группу можно переливать всем остальным группам, 2 и 3 группу только 4 группе. Задача.

5 слайд

6 слайд

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

7 слайд

Ориентированные графы - орграфы Каждое ребро имеет одно направление. Такие ребра называются дугами. Ориентированный граф

8 слайд

Взвешенный граф Это граф, рёбрам или дугам которого поставлены в соответствие числовые величины (они могут обозначать, например, расстояние между городами или стоимость перевозки). Вес графа равен сумме весов его рёбер. Таблице (она называется весовой матрицей) соответствует граф. 1 2 4 2 3 A B C D E

9 слайд

Задача Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). 1) 9 2) 10 3) 11 4) 12

10 слайд

1. 2. 3. 4. 5. Длина кратчайшего маршрута A-B-C-E-F равна 9 2 4 2 4 7 1 2 4 7 1 3 4 2 4 7 1 3 4 3 2 4 7 1 3 4 3 2

Граф это конечное множество вершин V и множество ребер R, соединяющих пары вершин, G=(V,R). Мощности множеств V и R равны N и M. Множество ребер может быть пустым. Примеры вершин – объекты любой природы (населенные пункты, компьютерные сети). Примеры ребер – дороги, стороны, линии.

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

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

Матрица инциденций

Списки связи

Перечень ребер

Матрица смежности связного взвешенного неориенторованного графа графа

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

Существует 4 случая: 1) обе вершины включаемого ребра принадлежат одноэлементным подмножествам, тогда они объединяются в новое, связное подмножество; 2) одна из вершин принадлежит связному подмножеству, а другая нет, тогда включаем вторую в подмножество, которому принадлежит первая; 3) обе вершины принадлежат разным связным подмножествам, тогда объединяем подмножества; 4) Обе вершины принадлежат одному связному подмножеству, тогда исключаем данное ребро.

Пример построения остовного дерева минимального веса для графа GG Выполняемые действия Множество вершин Граф 1Построим остовной подграф с изолированным и вершинами Получим 5 одноэлементных подмножеств: {V 1 }, {V 2 }, {V 3 }, {V 4 }, {V 5 } 2Найдем ребро минимального веса (R 15) и добавим его в остовной подграф Образуем связное подмножество вершин: {V 1,V 5 }. Сохраняем подмножества {V 2 }, {V 3 }, {V 4 }

Выполняемые действия Множество вершинГраф 3Среди оставшихся найдем ребро минимального веса (R 45) и добавим его в остовной подграф Добавим в связное подмножество вершину: {V 1,V 5, V 4 }. Сохраняем подмножества {V 2 }, {V 3 } 4Среди оставшихся найдем ребро минимального веса (R 23) и добавим его в остовной подграф Образуем новое связное подмножество вершин: {V 2,V 3 }. Сохраняем первое связное подмножество {V 1,V 5, V 4 }.

Выполняемые действия Множество вершинГраф 5Среди оставшихся найдем ребро минимального веса (R 25) и добавим его в остовной подграф Объединяем подмножества в одно связное подмножество {V 1,V 5, V 4,V 2,V 3 }. 6Остальные ребра не включаются в граф, т.к. все их вершины уже принадлежат одному связному множеству.

Выполняемые действия Множество вершинГраф 7Получен граф, который: остовной (все вершины включены); связный (все вершины можно соединить маршрутами); дерево (нет циклов); имеет минимальный вес. 8Полученное остовное дерево имеет минимальный вес: R 12 +R 25 +R 15 +R 45 = =80 9 Циклическое число графа G равно γ=m-n+1=8-5+1=4, что соответствует количеству ребер, не включенных в дерево.

Объявление переменных Два целочисленных пятиэлементных массива X и Y для хранения координат вершин графа Целочисленный двумерный массив R для хранения весов ребер графа Целочисленные переменные i, n и k для счетчиков циклов Целочисленная переменная S для хранения суммы весов ребер дерева минимального веса

Генерация случайных координат 5-ти вершин графа (цикл по i). Вычисление весов ребер. Вывод матрицы смежности взвешенного орграфа (вложенные циклы по n и по k) Вывод матрицы смежности взвешенного неориентрованного графа – половины элементов начальной матрицы (начальное значение k=n+1) Тело программы

Коробова Анастасия, студентка гр. 14-ПГС-48Д

В наше время актуально изучение различных методов, свойств и нестандартных применений. Мы рассмотрим применение метода «Граф» в окружающей нас действительности.

Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Прежде всего, стоит сказать о том, что графы, о которых пойдет речь, к аристократам былых времен никакого отношения не имеют. Наши «графы» имеют корнем греческое слово «графо», что значит «пишу». Тот же корень в словах «график», «биография».

Первая работа по теории графов принадлежит Леонарду Эйлеру, и появилась она в 1736 году в публикациях петербургской Академии наук.

С графами встречаются:

в физике - при построении электрических схем

в химии и биологии – при изучении молекул их цепочек

в истории – при составлении генеалогических древ (родословной)

в географии – при составлении карт

в геометрии – чертежи многоугольников, многогранников, пространственных фигур

в экономике – при решении задач о выборе оптимального пути для потоков грузового транспорта (схем авиалиний, метро, железных дорог)

Теория графов применяется при решении заданий математических олимпиад. Графы придают условиям задачи наглядность, упрощают решение, выявляют сходство задач.

Сейчас в любой отрасли науки и техники встречаешься с графами.

Скачать:

Предварительный просмотр:

Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com

Подписи к слайдам:

Презентация по математике Тема: «Графы» Выполнила Студентка группы 14-ПГС-48Д Коробова Анастасия

Графом называют фигуру, состоящую из точек и линий, связывающих эти точки. Линии называют ребрами графа, а точки - вершинами. Вершины, из которых выходит четное число ребер, называют четными, нечетное число – нечетными. Примеры графов Теория графов

Леонард Эйлер (4 апреля 1707, Базель, Швейцария - 7 сентября 1783, Санкт-Петербург, Российская империя) - швейцарский, немецкий и российский математик, внёсший значительный вклад в развитие математики, а также механики, физики, астрономии и ряда прикладных наук. Эйлер - автор более чем 800 работ по математическому анализу, дифференциальной геометрии, теории чисел, приближённым вычислениям, небесной механике, математической физике, оптике, баллистике, кораблестроению, теории музыки и др.

Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной. Закономерность 1. Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них. (рис. А) Закономерность 2 . Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком »(рис. Б) Эйлеровы графы Б А

Закономерность 3. Если все вершины графа четные, то можно не отрывая карандаш от бумаги, проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды? Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок Задача о кенигсбергских мостах.

Это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые - неориентированными. Смешанный граф

Взвешенный граф 1 2 4 2 3 A B C D E

Деревом называется любой связный граф, не имеющий циклов. Деревья Деревья

Это (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами. Ориентированный граф

С графами встречаются:

Теория графов применяется при решении заданий математических олимпиад. Графы придают условиям задачи наглядность, упрощают решение, выявляют сходство задач. Сейчас в любой отрасли науки и техники встречаешься с графами.

Спасибо за внимание!