Слайд 2
![Определение 4. В дальнейшем условимся граф без петель и кратных](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/165744/slide-1.jpg)
Определение 4. В дальнейшем условимся граф без петель и кратных рёбер
называть неориентированным графом (или просто графом), граф без петель — мультиграфом, а мультиграф, в котором разрешены петли — псевдографом.
Определение 5. Две вершины графа называются смежными, если они соединены ребром.
Определение 6. Говорят, что вершина и ребро инцидентны, если ребро содержит вершину.
Определение 7. Степенью вершины (deg v) называется количество рёбер, инцидентных данной вершине. Для псевдографа полагают учитывать петлю дважды.
Слайд 3
![Представление графов в ЭВМ 1. Матрица смежности вершин М :](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/165744/slide-2.jpg)
Представление графов в ЭВМ
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](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/165744/slide-3.jpg)
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
![Маршруты, циклы, цепи… Маршрут Если все рёбра различны, то маршрут](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/165744/slide-4.jpg)
Маршруты, циклы, цепи…
Маршрут
Если все рёбра различны, то маршрут называется цепью. Если
все вершины (а значит, и рёбра) различны, то маршрут называется простой цепью.
Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом.
Число циклов в графе G обозначается z(G). Граф без циклов называется ациклическим.
Для орграфов цепь называется путем, а цикл — контуром.
Слайд 6
![Обход графа Вход: граф G(V, Е) Выход: последовательность вершин обхода.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/165744/slide-5.jpg)
Обход графа
Вход: граф G(V, Е)
Выход: последовательность вершин обхода.
Слайд 7
![Алгоритм for v in V do x[v]: =0 { вначале](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/165744/slide-6.jpg)
Алгоритм
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
![Лабораторная работа Представление графов в ЭВМ Написать программу обработки информации](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/165744/slide-7.jpg)
Лабораторная работа
Представление графов в ЭВМ
Написать программу обработки информации о маршрутах автобусов
Дано:
N – количество маршрутов; М – количество остановок
Для каждого маршрута указаны его остановки
Внести информацию в компьютер
Провести проверку возможности проезда из пункта А в пункт В (четные варианты – поиск в глубину, нечетные – в ширину)
Слайд 9
![Компоненты связности графа](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/165744/slide-8.jpg)
Компоненты связности графа
Слайд 10
![Связные компоненты Граф неориентированный G(V,E) Вершины x1, x2 связные, если](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/165744/slide-9.jpg)
Связные компоненты
Граф неориентированный G(V,E)
Вершины x1, x2 связные, если существует маршрут из
x1 в x2
Каждый неориентированный граф распадается единственным образом на сумму непересекающихся компонент связности
Пусть G – простой граф с p вершинами и k компонентами связности. Число ребер не более C(2,p-k+1)=(p-k+1)(p-k)/2