Графы. Основные определения

1.

ЧАСТЬ 2

2.

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

3.

Задача о трех домах и трех колодцах.
Имеется три дома и три колодца. Провести от
каждого дома к каждому колодцу тропинку так,
чтобы тропинки не пересекались.
Эта задача была решена Куратовским в 1930
году.

4.

Задача о четырех красках.
Любую карту на плоскости раскрасить
четырьмя красками так, чтобы никакие две
соседние области не были закрашены одним
цветом
1
3
2
4
2

5.

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
Графом G (V , Е) называется совокупность двух
множеств —
непустого множества V (множества вершин) и
множества Е – бинарного отношения,
определённого на множестве V .
Число вершин графа G обозначим n, а число ребер m:

6.

ДИАГРАММЫ
V1
V2
V3
V0
V4
V5
Обычно граф изображают
диаграммой: вершины —
точками (или кружками),
ребра — линиями.

7.

СМЕЖНОСТЬ
Пусть v1, v2 — вершины, e = (v2, v1) — соединяющее
их ребро. Тогда:
вершина v1 и ребро е инцидентны, вершина v2
и ребро е также инцидентны.
Два ребра, инцидентные одной вершине,
называются смежными;
две вершины, инцидентные одному ребру,
также называются смежными.

8.

v1
e1
e4
v4
v2
e5
e3
e2
v3

9.

ВИДЫ ГРАФОВ
Если элементами множества Е являются
упорядоченные пары, то граф называется
ориентированным (или орграфом). В этом
случае элементы множества V называются
узлами, а элементы множества Е — дугами.
V0
V4
V1
V3
V2

10.

Если бинарное отношение Е является
симметричным, то граф называется
неориентированным (или неорграфом).
В этом случае симметричные пары (а,b) и (b,а)
будем обозначать [a,b]
V1
V2
V3
V0
V4
V5

11.

Если элементом множества Е может быть пара
одинаковых (не различных)элементов V, то такой
элемент множества Е называется петлей, а граф
называется графом с петлями (или
псевдографом).
x1
x4
x2
x3

12.

Граф, содержащий как ориентированные , так и
неориентированные ребра, называется смешанным.
V2
V3
V1
V5
V4

13.

Если Е является не множеством, а набором,
содержащим несколько одинаковых элементов,
то эти элементы называются кратными ребрами,
а граф называется мультиграфом.
Vi
Vj

14.

Если элементами множества Е являются не
обязательно двухэлементные, а
любые подмножества множества V, то такие
элементы множества Е называются гипердугами,
а граф называется гиперграфом.
с
и
а
ы
р
о

15.

Если задана функция F: V→М и/или F: Е→М, то
множество М называется множеством пометок, а
граф называется помеченным (или нагруженным).
В качестве множества пометок обычно используются
буквы или целые числа.
B
1
2
2
A
2
C
2
3
1
D

16. Способы задания графа

17.

Пусть G= (М, R) - граф, в котором множество
вершин имеет n элементов:
М = (a1, a2, ... ,an}.
Матрицей смежности
A= (Aij) графа G называется матрица порядка n,
определенная следующим образом:
Aij = ቐ
1, если