Основные понятия теории графов

1.

2.

3.

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

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 нельзя представить
в виде произведения двух последовательных натуральных чисел,
значит, данное уравнение не имеет решений. Следовательно, такого
графа
не существует.

10.

Примеры полных графов
K1: 0
K2: 1
K3 : 3
K4: 6
Задание 2.Построить полный граф для 5
вершин.

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
B
С
D
E
F
с
c
с
с
с
с
C, D, F;
C, E, F;
A, B;
A, E, F;
B, D, F;
A, B, D.

15.

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

16.

Вероятностно – статистическая линия
становится сегодня неотъемлемой
частью школьного курса математики. Не
исключено, что задачи, связанные с
вычислением вероятности, войдут в
материалы ЕГЭ. Но способы их
решения обычно специфичны и
требуют прочного знания специальной
теории.

17.

Графы помогают легко находить
вероятность в задачах различного
уровня сложности.

18.

Граф называется вероятностным, если с каждым ребром графа
исходов некоторого испытания записать вероятность события,
соответствующего его начальной вершине ребра (ориентация
рёбер задаётся, например, на дереве , расстоянием от его корня).
P1
P2
A1
P3
A2
Pn-1
A3
Pn
An-1
An
Назовем произведение
весом ветви, проходящей через
корень дерева и вершины, соответствующие событиям
Сумма веса ветвей дерева исходов, соответствующих
«благоприятному» событию, равна вероятности
данного события.

19.

Пример
• В урне 3 чёрных и 4 белых шара.
Вынимают один из них, возвращают
обратно, перемешивают и вынимают
другой. Какова вероятность достать 2
белых шара,2 чёрных, шары разных
цветов?
• Составим вероятностное дерево
исходов:

20.

Решение
1-й шар
2-й шар
исход
Вероятность
=

21.

Ответ:
Вероятность достать два белых шара
равна
, два чёрных-
разных цветов-
.
, шары

22.

Пример 2
В урне 3 чёрных и 4 белых шара.
Последовательно вынимают два
шара, но не возвращают их. Какова
вероятность достать два белых
шара, два чёрных, шары разных
цветов?

23.

Решение
1-й шар
2-й шар
исход
Вероятность

24.

Ответ
Вероятность достать два белых шара
равна
, два чёрных- , шары разных
цветов-
.

25.

Задача 3
Слово «МАТЕМАТИКА»
разделено на отдельные буквы, из
них произвольным образом
отбираются и выкладываются по
порядку четыре буквы. Какова
вероятность получения слова
«МАМА»?

26.

Решение
М
А
Р=
М
А

27.

Ответ:
Вероятность получения слова
«МАМА» равна
.

28.

Задача 4
В цехе работают 6 мужчин и 4
женщины. По табельным номерам
отобраны 3 человека. Найдите
вероятность того, что все отобранные
лица окажутся:
а) мужчинами;
б) женщинами.

29.

Решение:
Заменим условие
задачи урновой схемой.
Всего 10 шаров:
6 чёрных(мужчины) и
4 белых (женщины).

30.

1-ый шар
2-ой шар
3-ий шар
Исход
Вероятность

31.

Ответ
Вероятность того, что все отобранные лица
окажутся мужчинами равна
, а женщинами-

32.

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

33.

Решение
Существует 2 способа
размещения шаров по урнам.
1 способ: по два шара;
2 способ: 1 шар и 3 шара.

34.

1 способ
а)
б)

35.

2 способ
а)
б)

36.

Ответ
Звездочёту надо в одну урну положить
один белый шар, а все остальные во
вторую. Тогда вероятность выжить
составит

37.

ВЫВОД:
применение графов значительно
упрощает нахождение вероятности
в задачах различного уровня
сложности.