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


Введение в теорию графов

Содержание

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

Слайды и текст этой презентации

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

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

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

связей.

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

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

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

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

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

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

Граф - это множество точек или вершин и множество линий или ребер, соединяющих между собой все или

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

граф без ребер. Полным называется граф, в котором каждые две вершины

смежные.

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

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

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

Нулевой граф

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

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

неполными графами.
Рис. 3. Неполный граф

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

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

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

– чётной.

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

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

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

ребер равно
n(n-1)/2
Задание 1. Существует ли полный граф с семью

ребрами?

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

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

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

ОТВЕТ

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

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

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

которой участвуют 10 команд.

Задание 2.

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

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

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

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

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

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

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

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

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

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

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

ОТВЕТ

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

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

поскольку одному графу можно сопоставить не одно графическое представление. Изображение

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

Запомнить!

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

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

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

тот же граф.

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

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

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

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

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

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

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

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

Путь в графе

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

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

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

Слайд 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 повторяются.

ОТВЕТ

Путь называется простым, если он не проходит ни через одну из вершин графа более одного раза.(А1 А4);

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

начальная и конечная вершины. Простым циклом в графе называется цикл, не

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

Слайд 20 a) 4 ребра; b) 6 ребер; c) 5 ребер; d)

10 ребер. Какие из этих циклов являются простыми?
Задание 7.
Назовите в

графе циклы, содержащие

ОТВЕТ

a) 4 ребра;  b) 6 ребер;  c) 5 ребер;  d) 10 ребер.

Слайд 21ОТВЕТ
(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) и т.д. – циклы.

Решение:

ОТВЕТ(AB, BC, CE, EA), (CD, DA, AB, BC), (EB, BC, CD, DE) и т.д. – простые циклы.(DB,

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

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

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

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


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

Яндекс.Метрика