Презентация урока "Графы" 1 курс

Слайд #1

Графы

Слайд #2

Из истории Графов
Родоначальником теории графов принято считать математика Леонарда Эйлера(1707-1783). Он предложил изящное решение знаменитой задачи о 7 Кенигсбергских мостах в 1736 году, а также придумал общий метод решения подобных задач.

Слайд #3

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

Слайд #4

Вершина - точка в графе, отдельный объект, для топологической модели графа не имеет значения координата вершины, её расположение, цвет, вкус, размер; однако при решении некоторых задачах вершины могут раскрашиваться в разные цвета или сохранять числовые значения.
Ребро - неупорядоченная пара двух вершин, которые связаны друг с другом. Эти вершины называются концевыми точками или концами ребра. При этом важен сам факт наличия связи, каким именно образом осуществляется эта связь и по какой дороге - не имеет значения; однако рёбра может быть присвоен “вес”, что позволит говорить о “нагруженном графе” и решать задачи оптимизации.
Инцидентность - вершина и ребро называются инцидентными, если вершина является для этого ребра концевой. Обратите внимание, что термин “инцидентность” применим только к вершине и ребру. 
Смежность вершин - две вершины называются смежными, если они инцидентны одному ребру.
Смежность рёбер - два ребра называются смежными, если они инцидентные одной вершине.
Говоря проще - две вершины смежные, если они соединены ребром, два ребра смежные - если они соединены вершиной.
Петля - ребро, инцидентное одной вершине. Ребро, которое замыкается на одной вершине.

Слайд #5

Путь или Маршрут - это последовательность смежных рёбер. Обычно путь задаётся перечислением вершин, по которым он пролегает.
Длина пути - количество рёбер в пути.
Цепь - маршрут без повторяющихся рёбер.
Простая цепь - цепь без повторяющихся вершин.
Цикл или Контур - цепь, в котором последняя вершина совпадает с первой. 
Длина цикла - количество рёбер в цикле.
Самый короткий цикл - это петля.

Слайд #6

Виды графов:
1) Нулевой граф
2) Неполный граф
3) Полный граф
4) Несвязный граф
5) Связный граф
6) Ориентированный граф (орграф)
7) Взвешенный граф
8) Эйлеровый граф
9) Плоский граф
10) Дерево
11) Лес

Слайд #7

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

Слайд #8

Применение
теории графов
1) В теории информации
2) В биологии
3) В химии
4) В физике
5) На транспорте

Слайд #9

Я составил три варианта ремонта кухни с помощью сетевых графиков

Слайд #10

Вариант №1

Слайд #11

Вариант №2

Слайд #12

Вариант №3

Слайд #13

Пятеро друзей встретились после каникул и обменялись рукопожатиями. Каждый, здороваясь, пожал руку. Сколько всего было сделано рукопожатий?

Ответ: 10 рукопожатий

Слайд #14

Из цифр 9, 7, 5, 0 составляют все возможные трехзначные числа, в которых нет одинаковых цифр. Сколько среди чисел, меньше 900?

Слайд #15

Заключение
Графы представляют изучаемые факты в наглядной форме. Решение многих математических задач упрощается, если удается использовать графы. Графовые задачи позволяют развивать воображение и логическое мышление.
Теория графов в настоящее время является интенсивно развивающимся разделом математики. Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации: коммуникационные сети, схемы электрических и электронных приборов, химические молекулы, отношения между людьми и многое другое.