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

Содержание

Слайд 2

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

Граф отображает элементный состав системы и структуру

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

Слайд 3

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

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

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

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

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

Слайд 4

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

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

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

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

Слайд 5

Нулевой граф

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

Рис. 2.

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

Слайд 6

Неполный граф

Графы, в которых не построены все возможные ребра, называются

неполными графами.

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

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

Слайд 7

Степень графа

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

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

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

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

Слайд 8

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

ребер равно

n(n-1)/2

Задание 1. Существует ли полный граф с семью ребрами?

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

ОТВЕТ

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

Слайд 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. Примеры изображения графа

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

Слайд 15

Задание 4.

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

тот же граф или нет.

1)

2)

3)

ОТВЕТ

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

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

Слайд 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).

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

ОТВЕТ

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

Слайд 19

Понятие цикла в графе

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

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

Слайд 20

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

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

Задание 7.

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

ОТВЕТ

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