ГРАФЫ-1

1.

Элементы и множества. Графы.

2.

• Впервые понятие
«граф» ввел в
Денни Кенинг
1936 г.
венгерский
математик Денни
Кёниг.

3.

• Но первая работа
по теории графов
принадлежала
Леонард Эйлер
перу великого
Леонарда Эйлера
и была написана
еще в 1736 г.

4.

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

5.

6.

7.

Задача о Кёнигсбергских мостах
Впервые над задачей описанного выше типа задумался Леонард Эйлер после
посещения города Кенигсберга (ныне Калининград).
В городе было семь мостов через реку Прегель.
A
D
B
D
C
C
Гостям города предлагали задачу: пройти по всем мостам ровно один раз. Никому
из гостей не удавалось справиться с задачей.
Эйлер отметил на карте города по одной точке на каждом берегу реки и на
каждом острове.
Затем он соединил эти точки в соответствии с расположением мостов. Задача
обхода мостов свелась к задаче изображения одним росчерком следующей
картинки
Эта задача была решена Эйлером в 1736 году.
7

8.

Графом называется фигура G=(V,E), которая состоит из
множества точек, называемых вершинами, и множества
отрезков, соединяющих некоторые эти вершины
Отрезок, который соединяет две любые вершины
графа будем называется ребром.
Граф G=(V, E)
V={v1, v2, v3, v4, v5} ;
E={e1, e2, e3, e4, e5, e6, e7}

9.

• Две вершины называются смежными, если они
связаны ребром.
• Два ребра называются смежными, если они имеют
общую вершину.
• Ребра графа называются кратными, если они
соединяют одну и ту же пару вершин.
• Ребро, связанное с вершиной,
называется инцидентным данной вершине.

10.

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

11.

Орграф
• Граф с направленными связями
(вершины соединены дугами)
называют ориентированным графом
орграфом.

12.

Степень вершины графа
• Число ребер инцидентных данной вершине
называется её степенью.
• Степень вершины Vi обычно обозначают
как degVi
• Вершина степени 1 называется висячей.
• Вершина степени 0 называется изолированной. 2
Петля дает степень вершины 2.
1
.7
3
4
6
5

13.

Граф G4 содержит четыре вершины:
V= (A,В, С, D)
и шесть ребер Е= {р, q, r, s, t, и}.
Записать, чему равна
степень вершин:
deg (A) = 3
deg (В) = 3
deg (С) = 4
deg (D) = 2

14.

Пустой граф (нуль-граф)
Граф называется пустым, если множество
ребер пусто:
Рис. 21. Пустой граф
14

15.

Полный граф
Граф называется полным, если
любые две вершины связаны ребром:
Рис. Полный
граф
15

16.

Простой граф
• Граф, у которого нет петель и кратных ребер
называется простым графом

17.

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

18.

Мультиграф
• Граф, у которого между двумя
вершинами существует более одной
связи называется мультиграфом

19.

Назовите виды графов

20.

СПОСОБЫ ОПИСАНИЯ ГРАФОВ
Перечисление элементов
Изображение
Матрица смежности
Матрица инциденций
чтобы задать граф, достаточно перечислить множества
его вершин и ребер (т.е. пары вершин)