Материал: PZ_9_Grafy

ПЗ 9. Графы.

Матрица смежности и инцидентности для неорграфа и орграфа. Матрица достижимости и контрдостижимости. Возведение в степень матрицы смежности орграфа. Маршрут, цепь, простая цепь, цикл, простой цикл в графе. Операции над графами (пересечение, объединение, декартово произведение). Деревья, цикломатическое и коцикломатическое числа.

9.1. Графы

Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.

Ребро – соединение двух вершин.

Концами ребра {a, b} называются вершины a, b.

Ребро {a, b} также называют инцидентным к вершинам a, b.

Смежные вершины – это вершины, инцидентны к одному ребру, т.е. которые являются концами одного ребра.

Ребра смежные, если они инцидентны к общей вершине.

Петля – ребро, которое соединяет вершину с самой собой. Если в графе допускается наличие петель, то он называется графом с петлями.

Мультиграф – граф, в котором допускается наличие более одного ребра между двумя вершинами.

Размеченный граф – каждая вершина графа отмечена.

Псевдограф – граф, в котором допускается наличие петель и существование более одного ребра между двумя вершинами.

Пример. Подграфы.

Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром.

Граф называется связным, если имеет путь между любыми двумя вершинами.

Ориентированный граф (кратко орграф) — (мульти) граф, рёбрам которого присвоено направление.

Граф, ни одному ребру которого не присвоено направление, называется неориентированным графом или неорграфом.

Степенью вершины v, обозначается deg(v), называется количество ребер, инцидентных этой вершине. Вершина степени 0 называется изолированной. В н-графе сумма степеней вершин всегда четна.

Граф В называется подграфом графа А, если каждая вершина и ребро графа В принадлежат графу А.

Для вершин орграфа определится две локальные степени:

1. p₁(v) – число ребер с начало в вершине v, или количество выходящих из v ребер;

2. p₂(v) – количество входящих в v ребер, для которых эта вершина является концом.

Петля дает вклад в обе эти степени.

Пример 1.1. Задать аналитически граф, представленный на рисунке ниже. (рис. А)

Способы задания графом:

1. Матрица инцидентности;

2. Матрица смежности;

3. Списком ребер графа.

9.2. Матрица ицидентности

Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам.

Матрица инцидентности для неорграфа

Если вершина инцидентна ребру, то ставим 1. Если вершина не инцидентна ребру, то в соответствующую ячейку ставим 0.

Матрица инцидентности для орграфа

Если вершина является началом ребра, то ставим 1. Если вершина является концом ребра, то ставим -1. Если не инцидентна ребру, то ставим 0. Если петля, то ставим любое другое число (например 2).

9.3. Матрица смежности

Матрица смежности S - это квадратная матрица, в которой и число строк, и число столбцов равно n - числу вершин графа. В ячейки матрицы смежности записываются некоторые числа в зависимости от того, соединены соответствующие вершины рёбрами или нет, и от типа графа.

Матрица смежности для неориентированного графа

Элемент матрицы смежности sij неориентированного графа определяется следующим образом:

- равен единице, если вершины vi и vj смежны;

- равен нулю, если вершины vi и vj не смежны.

Если на диагонали матрицы стоят 1, то это показывает наличие петель.

Таким образом, матрица смежности неориентированного графа симметрична относительно главной диагонали.

Матрица смежности для ориентированного графа

Элемент матрицы смежности sij ориентированного графа определяется следующим образом:

- равен единице, если из вершины vi в вершину vj входит дуга;

- равен нулю, если из вершины vi в вершину vj дуга не входит.

Если на диагонали матрицы стоят 1, то это показывает наличие петель.

Таким образом, матрица смежности ориентированного графа не симметрична.

9.4. Список ребер

9.1-9.4

9.5. Матрица достижимости

Матрица достижимости простого ориентированного графа G=(V,E) — бинарная матрица замыкания по транзитивности отношения E (оно задаётся матрицей смежности графа). Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.

Возведение в степень матрицы смежности орграфа показывает, за сколько шагов (величина степени) можно достичь некой вершины.

Способы построения матрицы достижимости:

1. Перемножение матриц

2. Алгоритм Уоршелла

3. Связанные понятия