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

1. Графы. Основные понятия

Определение 1. Графом называется произвольное
множество элементов V и произвольное семейство E
пар из V. Обозначение: G = (V, E).
Определение 2. Если элементы из E рассматривать
как неупорядоченные пары, то граф называется
неориентированным, а пары называются рёбрами.
Если же элементы из E рассматривать как
упорядоченные, то граф ориентированный, а пары —
дуги.
Определение 3. Пара вида (a, a) называется петлёй,
если пара (a, b) встречается в семействе E несколько
раз, то она называется кратным ребром (кратной
дугой).

2.

Определение 4. В дальнейшем условимся граф без
петель и кратных рёбер называть неориентированным
графом (или просто графом), граф без петель —
мультиграфом, а мультиграф, в котором разрешены
петли — псевдографом.
Определение 5. Две вершины графа называются
смежными, если они соединены ребром.
Определение 6. Говорят, что вершина и ребро
инцидентны, если ребро содержит вершину.
Определение 7. Степенью вершины (deg v)
называется количество рёбер, инцидентных данной
вершине. Для псевдографа полагают учитывать петлю
дважды.

3. Представление графов в ЭВМ

1. Матрица смежности вершин
М : array [1..p, 1..p] of 0..1
2. Матрица инциденций
Н :array [1..p, 1..q] of 0..1
(для орграфов Н :array [1..p, 1..q] of -1..1)

4.

3. Списки смежности
G : array [1..p] of *N
N : record v : 1..p; n: *N endrecord
4. Массив дуг
Е : array [1..q] of record b,е : 1..p endrecord

5. Маршруты, циклы, цепи…

Маршрут
Если все рёбра различны, то маршрут
называется цепью. Если все вершины (а значит,
и рёбра) различны, то маршрут называется
простой цепью.
Замкнутая цепь называется циклом; замкнутая
простая цепь называется простым циклом.
Число циклов в графе G обозначается z(G). Граф
без циклов называется ациклическим.
Для орграфов цепь называется путем, а цикл —
контуром.

6. Обход графа

• Вход: граф G(V, Е)
• Выход: последовательность вершин обхода.

7.

• Алгоритм
for v in V do
x[v]: =0 { вначале все вершины не отмечены }
end for
T = {}
выбор v in V{ начало обхода — произвольная вершина }
v ->Т{ помещаем v в структуру данных Т ... }
x[v]: = 1{ ... и отмечаем вершину v }
repeat
u <- T { извлекаем вершину из структуры данных Т ... }
вывод u { ... и возвращаем ее в качестве очередной
пройденной вершины }
for w in E(u) do
if x[w] = 0 then
w -> Т { помещаем w в структуру данных Т ... }
x[w] := 1 { ... и отмечаем вершину w }
end if
end for
until T = {}
• T — стек, то обход поиском в глубину.
• Т —очередь, то обход поиском в ширину.

8. Лабораторная работа Представление графов в ЭВМ

• Написать программу обработки информации о
маршрутах автобусов
• Дано:
• N – количество маршрутов; М – количество
остановок
• Для каждого маршрута указаны его остановки
• Внести информацию в компьютер
• Провести проверку возможности проезда из пункта А
в пункт В (четные варианты – поиск в глубину,
нечетные – в ширину)

9. Компоненты связности графа

10. Связные компоненты

• Граф неориентированный G(V,E)
• Вершины x1, x2 связные, если существует маршрут
из x1 в x2
• Каждый неориентированный граф распадается
единственным образом на сумму непересекающихся
компонент связности
• Пусть G – простой граф с p вершинами и k
компонентами связности. Число ребер не более
C(2,p-k+1)=(p-k+1)(p-k)/2

11. Алгоритм выделения компонент связности

for v in V do
M[v]=0
endfor
count=0
for v in V do
if M[v]=0 then
count=count+1
Component(v,count)
endif
enddo
procedure Component(v,count)
M[v]=Count
for w in G[v] do
if M[w]=0 then
Component(w,Count)
endif
endfor
end