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

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

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

of 0..1


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

: 1..p; n: *N endrecord

4. Массив дуг
Е : array [1..q] of record b,е : 1..p endrecord

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

вершины не отмечены }
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 – количество маршрутов; М – количество остановок
Для каждого маршрута указаны его остановки
Внести информацию в компьютер
Провести проверку возможности проезда из пункта А в пункт В (четные варианты – поиск в глубину, нечетные – в ширину)

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

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