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

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

Представление графов в ЭВМ
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)

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

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

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

Алгоритм
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 — стек, то обход поиском в глубину.
Т —очередь, то обход поиском в ширину.

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

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

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