PPt4Web Хостинг презентаций

Главная / Информатика / Введение в теорию графов
X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

Чтобы скачать данную презентацию, порекомендуйте, пожалуйста, её своим друзьям в любой соц. сети.

После чего скачивание начнётся автоматически!

Кнопки:

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


Скачать эту презентацию

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


Скачать эту презентацию



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

№ слайда 10 Ориентированный граф Граф называется ориентированным (или орграфом), если некото
Описание слайда:

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

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

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

№ слайда 12 Задание 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.

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

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

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

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

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

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

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

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

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

Задание 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).

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

Путь называется простым, если он не проходит ни через одну из вершин графа более одного раза. Задание 6. (А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) повторяется.Первая и вторая последовательность являются простыми путями, а четвертая нет, т.к. вершины А1 и А4 повторяются.

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

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

№ слайда 20 Задание 7. Назовите в графе циклы, содержащие a) 4 ребра; b) 6 ребер; c) 5 ребер
Описание слайда:

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

№ слайда 21 ОТВЕТ Решение: (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) и т.д. – циклы.

Скачать эту презентацию


Презентации по предмету
Презентации из категории
Лучшее на fresher.ru