Графы. Вершина. Ребро. Представление задачи с помощью графов

1. Графы. Вершина. Ребро. Представление задачи с помощью графов.

2.

Слово «граф» в математике означает
картинку, где нарисовано несколько точек,
некоторые из которых соединены линиями.
В процессе решения задач математики
заметили, что удобно изображать объекты
точками,
а
отношения
между
ними
отрезками или дугами.

3.

Примеры графов: карта дорог, схема
метро, электросхема, чертеж
прямоугольника и т.п.

4.

Графом называется
конечное множество
точек, некоторые из
которых соединены
линиями.
Точки называются
вершинами графа, а
соединяющие линии –
рёбрами.
(Каждое ребро
соединяет ровно две
вершины).
Рёбра графа
Вершины графа

5.

6. Примеры различных графов

7.

Определение.
Вершина графа, не принадлежащая ни одному
ребру называется изолированной.
Пример.
Вершина 5 является
изолированной.
Задание.
Вершины графа представляют жителей городка N, а
ребра, соединяющие две вершины, - тот факт, что эти
люди знакомы. Какую ситуацию изображает
приведенный на рисунке граф?

8.

Определение.
Вершина А графа,
принадлежащая одному ребру,
называется висячей.
Пример
Вершины А и Б - висячие.
Задание
Укажите висячие вершины.
Есть ли здесь изолированные вершины?

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

рисунке могут пересечься, но
эта точка не является
вершиной графа.

10. Задание 1. Начертите граф, содержащий четыре висячих и две изолированные вершины. Задание 2. Начертите граф, содержащий шесть

висячих и три
изолированные вершины.

11. Задание 3. Сколько ребер и вершин в графе? Укажите висячие вершины. Есть ли здесь изолированные вершины?

а)
б)
D
F
B
C
E
G
H
.R
A

12. Домашнее задание по вероятности.

Задание 1.
Начертите граф, содержащий пять висячих и четыре
изолированные вершины.
Задание 2.
Начертите граф, содержащий две висячих и пять
изолированные вершины.
Задание 3. Сколько ребер и вершин в графе? Укажите
висячие вершины.
Есть ли здесь изолированные вершины?