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

Презентация к уроку "Основы теории графов"



Внимание! Сегодня последний день приёма заявок на
Международный конкурс "Мириады открытий"
(конкурс сразу по 24 предметам за один оргвзнос)


  • Информатика
Введение в теорию графов 11 класс * начать
Введение в теорию графов Граф отображает элементный состав системы и структур...
Граф - это множество точек или вершин и множество линий или ребер, соединяющи...
Петля это дуга, начальная и конечная вершина которой совпадают. Пустым (нулев...
Нулевой граф Граф, состоящий из «изолированных» вершин, называется нулевым гр...
Неполный граф Графы, в которых не построены все возможные ребра, называются н...
Степень графа Количество рёбер, выходящих из вершины графа, называется степен...
Заметим, что если полный граф имеет n вершин, то количество ребер равно n(n-1...
Примеры полных графов Задание 2.Построить полный граф для 5 вершин.
Составьте схему проведения розыгрыша кубка по олимпийской системе, в которой...
Ориентированный граф Два ребра, у которых есть общая вершина, также называютс...
Рис. 5. Примеры неориентированного и ориентированного графов (А и Б) Ориентир...
Задание 3.Построить граф по заданному условию: В соревнованиях по футболу уча...
Не следует путать изображение графа с собственно графом (абстрактной структур...
Изображение графа Один и тот же граф может выглядеть на рисунках по-разному....
Задание 4. Определить изображают ли фигуры на рисунке один и тот же граф или...
Путём в графе называется такая последовательность ребер, в которой каждые два...
Задание 5. (А1 А4); (А4 А5). (А1 А2); (А2 А4); (А4 А5). (А1 А4); (А4 А2); (А2...
Путь называется простым, если он не проходит ни через одну из вершин графа бо...
Понятие цикла в графе Циклом называется путь, в котором совпадают его начальн...
a) 4 ребра; b) 6 ребер; c) 5 ребер; d) 10 ребер. Какие из этих циклов являют...
ОТВЕТ (AB, BC, CE, EA), (CD, DA, AB, BC), (EB, BC, CD, DE) и т.д. – простые ц...
Построить полный граф, если известно что он содержит в себе 7 вершин. Составь...
1 из 24

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

№ слайда 1 Введение в теорию графов 11 класс * начать
Описание слайда:

Введение в теорию графов 11 класс * начать

№ слайда 2
Описание слайда:

№ слайда 3 Введение в теорию графов Граф отображает элементный состав системы и структур
Описание слайда:

Введение в теорию графов Граф отображает элементный состав системы и структуру связей.

№ слайда 4 Граф - это множество точек или вершин и множество линий или ребер, соединяющи
Описание слайда:

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

№ слайда 5 Петля это дуга, начальная и конечная вершина которой совпадают. Пустым (нулев
Описание слайда:

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

№ слайда 6 Нулевой граф Граф, состоящий из «изолированных» вершин, называется нулевым гр
Описание слайда:

Нулевой граф Граф, состоящий из «изолированных» вершин, называется нулевым графом Рис. 2. Нулевой граф

№ слайда 7 Неполный граф Графы, в которых не построены все возможные ребра, называются н
Описание слайда:

Неполный граф Графы, в которых не построены все возможные ребра, называются неполными графами. Рис. 3. Неполный граф

№ слайда 8 Степень графа Количество рёбер, выходящих из вершины графа, называется степен
Описание слайда:

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

№ слайда 9 Заметим, что если полный граф имеет n вершин, то количество ребер равно n(n-1
Описание слайда:

Заметим, что если полный граф имеет n вершин, то количество ребер равно n(n-1)/2 Задание 1. Существует ли полный граф с семью ребрами? Решение: Зная количество ребер, узнаем количество вершин. n(n-1)/2=7. n(n-1)=14. Заметим, что n и (n-1) – это два последовательных натуральных числа. Число 14 нельзя представить в виде произведения двух последовательных натуральных чисел, значит, данное уравнение не имеет решений. Следовательно, такого графа не существует. ОТВЕТ

№ слайда 10 Примеры полных графов Задание 2.Построить полный граф для 5 вершин.
Описание слайда:

Примеры полных графов Задание 2.Построить полный граф для 5 вершин.

№ слайда 11 Составьте схему проведения розыгрыша кубка по олимпийской системе, в которой
Описание слайда:

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

№ слайда 12 Ориентированный граф Два ребра, у которых есть общая вершина, также называютс
Описание слайда:

Ориентированный граф Два ребра, у которых есть общая вершина, также называются смежными (или соседними). Граф называется ориентированным (или орграфом), если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет. Если ребра ориентированы, что обычно показывают стрелками, то они называются дугами. Рис. 4. Ориентированный граф

№ слайда 13 Рис. 5. Примеры неориентированного и ориентированного графов (А и Б) Ориентир
Описание слайда:

Рис. 5. Примеры неориентированного и ориентированного графов (А и Б) Ориентированный и неориентированный графы

№ слайда 14 Задание 3.Построить граф по заданному условию: В соревнованиях по футболу уча
Описание слайда:

Задание 3.Построить граф по заданному условию: В соревнованиях по футболу участвуют 6 команд. Каждую из команд обозначили буквами А, B, C, D, E и F. Через несколько недель некоторые из команд уже сыграли друг с другом: A с C, D, F; B c C, E, F; С с A, B; D с A, E, F; E с B, D, F; F с A, B, D. ОТВЕТ

№ слайда 15 Не следует путать изображение графа с собственно графом (абстрактной структур
Описание слайда:

Не следует путать изображение графа с собственно графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет. Запомнить!

№ слайда 16 Изображение графа Один и тот же граф может выглядеть на рисунках по-разному.
Описание слайда:

Изображение графа Один и тот же граф может выглядеть на рисунках по-разному. На рисунке 6 (а, б, в) изображен один и тот же граф. Рис. 6. Примеры изображения графа

№ слайда 17 Задание 4. Определить изображают ли фигуры на рисунке один и тот же граф или
Описание слайда:

Задание 4. Определить изображают ли фигуры на рисунке один и тот же граф или нет. 1) 2) 3) ОТВЕТ Рисунок 1 и рисунок 2 являются изображениями одного графа. Рисунок 3 изображением другого графа

№ слайда 18 Путём в графе называется такая последовательность ребер, в которой каждые два
Описание слайда:

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

№ слайда 19 Задание 5. (А1 А4); (А4 А5). (А1 А2); (А2 А4); (А4 А5). (А1 А4); (А4 А2); (А2
Описание слайда:

Задание 5. (А1 А4); (А4 А5). (А1 А2); (А2 А4); (А4 А5). (А1 А4); (А4 А2); (А2 А1); (А1 А4); (А4, А5). (А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А4); (А4, А5). Определить какая из перечисленных последовательностей путём не является. ОТВЕТ Третья последовательность (А1 А4); (А4 А2); (А2 А1); (А1 А4); (А4, А5).

№ слайда 20 Путь называется простым, если он не проходит ни через одну из вершин графа бо
Описание слайда:

Путь называется простым, если он не проходит ни через одну из вершин графа более одного раза. (А1 А4); (А4 А5). (А1 А2); (А2 А4); (А4 А5). (А1 А4); (А4 А2); (А2 А1); (А1 А4); (А4, А5). (А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А4); (А4, А5). Задание 6. Определите, какие последовательности ребер являются путями, и какие из них простые. Если последовательность не является путем укажите почему. Первая, вторая и четвертая последовательности являются путями, а третья нет, т.к. ребро (А1, А4) повторяется. Первая и вторая последовательность являются простыми путями, а четвертая нет, т.к. вершины А1 и А4 повторяются. ОТВЕТ

№ слайда 21 Понятие цикла в графе Циклом называется путь, в котором совпадают его начальн
Описание слайда:

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

№ слайда 22 a) 4 ребра; b) 6 ребер; c) 5 ребер; d) 10 ребер. Какие из этих циклов являют
Описание слайда:

a) 4 ребра; b) 6 ребер; c) 5 ребер; d) 10 ребер. Какие из этих циклов являются простыми? Задание 7. Назовите в графе циклы, содержащие ОТВЕТ

№ слайда 23 ОТВЕТ (AB, BC, CE, EA), (CD, DA, AB, BC), (EB, BC, CD, DE) и т.д. – простые ц
Описание слайда:

ОТВЕТ (AB, BC, CE, EA), (CD, DA, AB, BC), (EB, BC, CD, DE) и т.д. – простые циклы. (DB, BE, EA, AB, BC, CD), (EC, CA, AB, BC, CD, DE) и т.д. – циклы. (AB, BC, CD, DE, EA), (AC, CE, EB, BD, DA) и т.д. – простые циклы. (AC, CE, EB, BD, DA, AB, BC, CD, DE, EA), (EB, BD, DA, AC, CE, EA, AB, BC, CD, DE) и т.д. – циклы. Решение:

№ слайда 24 Построить полный граф, если известно что он содержит в себе 7 вершин. Составь
Описание слайда:

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



57 вебинаров для учителей на разные темы
ПЕРЕЙТИ к бесплатному просмотру
(заказ свидетельства о просмотре - только до 11 декабря)


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

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

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

 

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

Автор
Дата добавления 07.03.2015
Раздел Информатика
Подраздел Презентации
Просмотров418
Номер материала 426181
Получить свидетельство о публикации
Похожие материалы

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