Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть

Презентация на тему Введение в теорию графов

Содержание

2. Введение в теорию графовГраф отображает элементный состав системы и структуру связей.
3. Граф - это множество точек или вершин
4. Петля это дуга, начальная и конечная вершина
5. Нулевой графГраф, состоящий из «изолированных» вершин, называется нулевым графомРис. 2. Нулевой граф
6. Неполный графГрафы, в которых не построены все возможные ребра, называются неполными графами. Рис. 3. Неполный граф
7. Степень графаКоличество рёбер, выходящих из вершины графа,
8. Заметим, что если полный граф имеет n
9. Построить полный граф, если известно что он
10. Ориентированный графДва ребра, у которых есть общая
11. Рис. 5. Примеры неориентированного и ориентированного графов (А и Б)Ориентированный и неориентированный графы
12. Задание 3.Построить граф по заданному условию:В соревнованиях
13. Не следует путать изображение графа с собственно
14. Изображение графаОдин и тот же граф может
15. Задание 4. Определить изображают ли фигуры на
16. Путём в графе называется такая последовательность ребер,
17. Задание 5.(А1 А4); (А4 А5). (А1 А2);
18. Путь называется простым, если он не проходит
19. Понятие цикла в графеЦиклом называется путь, в
20. a) 4 ребра; b) 6
21. Скачать презентацию
22. Похожие презентации

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

Граф - это множество точек или вершин и множество линий или ребер,

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

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

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

Степень графаКоличество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа,

Заметим, что если полный граф имеет n вершин, то количество ребер равно

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

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

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

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

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

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

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

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

Задание 5.(А1 А4); (А4 А5). (А1 А2); (А2 А4); (А4 А5). (А1

Путь называется простым, если он не проходит ни через одну из вершин

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

ОТВЕТ(AB, BC, CE, EA), (CD, DA, AB, BC), (EB, BC, CD, DE)

Слайды презентации

Слайд 2 Введение в теорию графов
Граф отображает элементный состав системы

и структуру связей.

Слайд 3 Граф - это множество точек или вершин и

Граф - это множество точек или вершин и множество линий или

множество линий или ребер, соединяющих между собой все или

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

Рис. 1. Граф с шестью вершинами и семью ребрами

Понятие графа

Слайд 4 Петля это дуга, начальная и конечная вершина которой

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

совпадают. Пустым (нулевым)называется граф без ребер. Полным называется граф, в котором

каждые две вершины смежные.

Элементы графа

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

графом
Рис. 2. Нулевой граф

Слайд 6 Неполный граф
Графы, в которых не построены все возможные

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

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

Степень графаКоличество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина

степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной,

а чётную степень – чётной.

Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.

Слайд 8 Заметим, что если полный граф имеет n вершин,

Заметим, что если полный граф имеет n вершин, то количество ребер

то количество ребер равно
n(n-1)/2
Задание 1. Существует ли полный

граф с семью ребрами?

Решение: Зная количество ребер, узнаем количество вершин.

n(n-1)/2=7.
n(n-1)=14.

Заметим, что n и (n-1) – это два последовательных натуральных числа. Число 14 нельзя представить
в виде произведения двух последовательных натуральных чисел, значит, данное уравнение не имеет решений. Следовательно, такого графа
не существует.

ОТВЕТ

Слайд 9 Построить полный граф, если известно что он содержит

Построить полный граф, если известно что он содержит в себе 7

в себе 7 вершин.
Составьте схему проведения розыгрыша кубка по

олимпийской системе, в которой участвуют 10 команд.

Задание 2.

Слайд 10 Ориентированный граф
Два ребра, у которых есть общая вершина,

Ориентированный графДва ребра, у которых есть общая вершина, также называются смежными

также называются смежными (или соседними).
Граф называется ориентированным (или

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

Рис. 4. Ориентированный граф

Слайд 11 Рис. 5. Примеры неориентированного
и ориентированного графов (А

и Б)

Ориентированный и неориентированный графы

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

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

футболу участвуют 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.

ОТВЕТ

Слайд 13 Не следует путать изображение графа с собственно графом

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

(абстрактной структурой), поскольку одному графу можно сопоставить не одно

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

Запомнить!

Слайд 14 Изображение графа
Один и тот же граф может выглядеть

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

на
рисунках по-разному. На рисунке 6 (а, б, в)

изображен один и тот же граф.

Рис. 6. Примеры изображения графа

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

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

один и тот же граф или нет.
1)
2)
3)
ОТВЕТ
Рисунок 1 и

рисунок 2 являются изображениями одного графа. Рисунок 3 изображением
другого графа

Слайд 16 Путём в графе называется такая последовательность ребер, в

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

которой каждые два соседних ребра имеют общую вершину и

никакое ребро не встречается более одного раза.

Путь в графе

Слайд 17 Задание 5.
(А1 А4); (А4 А5).
(А1 А2); (А2

Задание 5.(А1 А4); (А4 А5). (А1 А2); (А2 А4); (А4 А5).

А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).

Слайд 18 Путь называется простым, если он не проходит ни

Путь называется простым, если он не проходит ни через одну из

через одну из вершин графа более одного раза.
(А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 повторяются.

ОТВЕТ