Венгерский математик
в 1936 году впервые ввел
термин «граф»
первая
работа
Но
графов
принадлежала перу великого Леонардо Эйлера
и была написана еще в 1736 году
по теории
пара
точек
в
графе
может
соединена линиями. Линия указывает
Графы – это рисунки, которые состоят из точек
Графы
и линий, соединяющих эти точки.
Каждая
быть соединена линиями
связь между двумя точками.
на связь между двумя точками
вершинами
Точки
называются вершинами
рёбрами.
линиями рёбрами
Ребро может
Ребро
указывается стрелочкой.
вершины.
У графа обязательно есть вершины
пустым.
Граф без рёбер называется пустым
графа,
графа
иметь
направление,
которое
а
Данная форма модели применяется тогда, когда элементы
моделируемого объекта находятся в состоянии какоголибо
подчинения и
есть отношение
подчинения и
иерархичности.
иерархичности
соподчинения, когда
соподчинения
Задача 1.
У Юры два автомобиля, четыре медвежонка и три мяча. Он хочет выбрать из
этих игрушек один автомобиль, одного медвежонка и один мяч.
Сколько у него есть вариантов выбора?
Ответ: 24 варианта.
24 варианта.
Задача 2.
ВинниПух решил навестить своих друзей: Пяточка, Кролика и Ослика. Ему
нужно побывать у каждого из них и вернуться домой. Если он к комуто не
зайдет, то его друг обидится. Но ВинниПух не любит длительных
путешествий. Помогите ему выбрать кратчайший путь, если известно, как
расположены домики друзей и на каком расстоянии они находятся друг от
друга:
Дано:
И – Ослик
В – ВинниПух
П – Пяточек
К – Кролик
Найти:
Кратчайший путь
Рассуждения:
1. Построить граф, используя условия задачи,
расставить на нем расстояния.
2. Определить пары симметричных вариантов
(например: В – К – П – И – В и В – И – П – К – В)
и вычеркнуть на графе один вариант из каждой
пары.
3. Выписать оставшиеся варианты и подсчитать
расстояния:
В – К – П – И – В = 60 + 50 + 55 + 30
В – К – И – П – В = 60 + 45 + 55 + 40
В – И – К – П – В = 30 + 45 + 50 + 40
1. Выстраиваем вспомогательные линии
2. Строим граф, используя условия задачи
3. Расставляем расстояния, используя данные рисунка
4. Определяем пары симметричных вариантов
5. Выписываем оставшиеся варианты и подсчитываем результаты
195195
200200
165165
В – К – П – И – В = 60 + 50 + 55 + 30 =
В – К – П – И – В = 60 + 50 + 55 + 30 =
В – К – И – П – В = 60 + 45 + 55 + 40 =
В – К – И – П – В = 60 + 45 + 55 + 40 =
В – И – К – П – В = 30 + 45 + 50 + 40 =
В – И – К – П – В = 30 + 45 + 50 + 40 =
В
В
30
И
55
П
50
40
П
55
И
45
К
В
30
И
45
К
50
В
60
К
45
И
55
60
П
40
В
30
В
В
60
П
50
К
55
40
К
50
П
45
И
Пятачок решил навестить своих друзей – ВинниПуха,
Кролика и Ослика. Ему надо побывать у каждого и
выбрать
вернуться
кратчайший путь. Расположение домиков:
домой. Помогите Пятачку
Ответ: 165
презентация к графам.ppt
