Рабочие листы
к вашим урокам
Скачать
1 слайд
Введение в теорию графов
11 класс
10.06.2022
начать
2 слайд
3 слайд
Введение в теорию графов
Граф отображает элементный состав системы и структуру связей.
4 слайд
Граф - это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек.
Вершины, прилегающие к одному и тому же ребру, называются смежными. Два ребра, у которых есть общая вершина, также называются смежными (или соседними).
Рис. 1. Граф с шестью вершинами и семью ребрами
Понятие графа
5 слайд
Петля это дуга, начальная и конечная вершина которой совпадают.
Пустым (нулевым)называется граф без ребер.
Полным называется граф, в котором каждые две вершины смежные.
Элементы графа
6 слайд
Нулевой граф
Граф, состоящий из «изолированных» вершин, называется нулевым графом
Рис. 2. Нулевой граф
7 слайд
Неполный граф
Графы, в которых не построены все возможные ребра, называются неполными графами.
Рис. 3. Неполный граф
8 слайд
Степень графа
Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.
Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.
9 слайд
Заметим, что если полный граф имеет n вершин, то количество ребер равно
n(n-1)/2
Задание 1. Существует ли полный граф с семью ребрами?
Решение: Зная количество ребер, узнаем количество вершин.
n(n-1)/2=7.
n(n-1)=14.
Заметим, что n и (n-1) – это два последовательных натуральных числа. Число 14 нельзя представить
в виде произведения двух последовательных натуральных чисел, значит, данное уравнение не имеет решений. Следовательно, такого графа
не существует.
ОТВЕТ
10 слайд
Примеры полных графов
Задание 2.Построить полный граф для 5 вершин.
11 слайд
Составьте схему проведения розыгрыша кубка по олимпийской системе, в которой участвуют 8 команд.
8
2
2
2
2
1
1
1
1
1
1
1
12 слайд
Ориентированный граф
Два ребра, у которых есть общая вершина, также называются смежными (или соседними).
Граф называется ориентированным (или орграфом), если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет. Если ребра ориентированы, что обычно показывают стрелками, то они называются дугами.
Рис. 4. Ориентированный граф
13 слайд
Рис. 5. Примеры неориентированного
и ориентированного графов (А и Б)
Ориентированный и неориентированный графы
14 слайд
Задание 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.
Определить изображают ли фигуры на рисунке один и тот же граф или нет.
1)
2)
3)
ОТВЕТ
Рисунок 1 и рисунок 2 являются изображениями одного графа. Рисунок 3 изображением
другого графа
18 слайд
Путём в графе называется такая последовательность ребер, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза.
Путь в графе
19 слайд
Задание 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 ребер.
Какие из этих циклов являются простыми?
Задание 7.
Назовите в графе циклы, содержащие
ОТВЕТ
23 слайд
ОТВЕТ
(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 вершин.
Составьте схему проведения розыгрыша кубка по олимпийской системе, в которой участвуют 10 команд.
Задание 2.
Рабочие листы
к вашим урокам
Скачать
Каждый день в нашей жизни мы принимаем решения, связанные с личными и общественными делами, с бизнесом. В древности люди принимали решения, основываясь на интуиции, заключениях астрологов и т.д.
Развитие науки, усложнение экономических и социальных связей и отношений привели к разработке специальной области научных знаний – теории принятия решений, основанной на различных разделах математики. Реальные задачи планирования связаны с выбором таких решений, которые позволили бы получить некие оптимальные результаты. Например, достичь максимальной прибыли предприятия, закончить комплекс работ в кратчайший срок, соединить компьютеры локальной сетью минимальной длины и т. д. Во всех этих задачах можно выделить цель (в математике она записывается в виде целевой функции, которую необходимо исследовать на минимум или максимум, то есть, оптимизировать). Кроме того, в каждой такой задаче существуют ограничения, которые тоже можно записать в математических терминах. В этом случае говорят, что построена математическая модель изучаемого явления. Под математической моделью понимают приближенное описание изучаемого явления, выраженное в математических терминах (в виде формул).
Выработаны специальные математические методы решения таких задач. Мы будем рассматривать такие задачи теории принятия решения, которые связаны с применением математической теории графов: задачи кратчайшего пути, минимизации дерева расстояний, максимального потока в сети и задачу управления комплексом взаимосвязанных работ. Мы научимся строить сетевые графики и рассчитывать параметры сети. Кроме того, покажем, как с помощью специально разработанного метода «критического пути» можно принимать решения по управлению комплексом работ.
6 663 776 материалов в базе
Настоящий материал опубликован пользователем Рыжкова Ольга Александровна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс профессиональной переподготовки
500/1000 ч.
Курс профессиональной переподготовки
300 ч. — 1200 ч.
Курс профессиональной переподготовки
600 ч.
Курс профессиональной переподготовки
300/600 ч.
Мини-курс
3 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.