- Главная
- Разное
- Бизнес и предпринимательство
- Образование
- Развлечения
- Государство
- Спорт
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Религиоведение
- Черчение
- Физкультура
- ИЗО
- Психология
- Социология
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Что такое findslide.org?
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Обратная связь
Email: Нажмите что бы посмотреть
Презентация на тему к уроку Основы теории графов
Содержание
- 3. Введение в теорию графовГраф отображает элементный состав системы и структуру связей.
- 4. Граф - это множество точек или вершин
- 5. Петля это дуга, начальная и конечная вершина
- 6. Нулевой графГраф, состоящий из «изолированных» вершин, называется нулевым графомРис. 2. Нулевой граф
- 7. Неполный графГрафы, в которых не построены все возможные ребра, называются неполными графами. Рис. 3. Неполный граф
- 8. Степень графаКоличество рёбер, выходящих из вершины графа,
- 9. Заметим, что если полный граф имеет n
- 10. Примеры полных графов Задание 2.Построить полный граф для 5 вершин.
- 11. Составьте схему проведения розыгрыша кубка по олимпийской системе, в которой участвуют 8 команд.822221111111
- 12. Ориентированный графДва ребра, у которых есть общая
- 13. Рис. 5. Примеры неориентированного и ориентированного графов (А и Б)Ориентированный и неориентированный графы
- 14. Задание 3.Построить граф по заданному условию:В соревнованиях
- 15. Не следует путать изображение графа с собственно
- 16. Изображение графаОдин и тот же граф может
- 17. Задание 4. Определить изображают ли фигуры на
- 18. Путём в графе называется такая последовательность ребер,
- 19. Задание 5.(А1 А4); (А4 А5). (А1 А2);
- 20. Путь называется простым, если он не проходит
- 21. Понятие цикла в графеЦиклом называется путь, в
- 22. a) 4 ребра; b) 6
- 23. ОТВЕТ(AB, BC, CE, EA), (CD, DA, AB,
- 24. Скачать презентацию
- 25. Похожие презентации
Введение в теорию графовГраф отображает элементный состав системы и структуру связей.
Слайд 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 нельзя представить
в виде произведения двух последовательных натуральных чисел, значит, данное уравнение не имеет решений. Следовательно, такого графа
не существует.
ОТВЕТ
Слайд 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) и т.д. – циклы.
Решение:
