Лабораторная по теории графов

Задача 1. Диаметр и радиус

По матрице смежности неориентированного графа найти расстояния между всеми вершинами, эксцентриситет каждой вершины, диаметр, радиус, центр и периферию.

Как работает

Из каждой вершины запускается обход в ширину (BFS). Обход идёт «слоями»: сначала соседи стартовой вершины (расстояние 1), затем их ещё не посещённые соседи (расстояние 2) и так далее. Так получается строка матрицы расстояний.

Эксцентриситет вершины — наибольшее расстояние от неё до остальных. Диаметр — максимум эксцентриситетов, радиус — минимум. Центр — вершины с эксцентриситетом, равным радиусу, периферия — равным диаметру. Если какая-то вершина недостижима, граф несвязный, и диаметр с радиусом бесконечны.

Ввод

Задача 2. Смежность → инцидентность

По матрице смежности построить матрицу инцидентности. Тип каждого ребра программа определяет сама.

Как работает

Перебираем пары вершин в порядке i от 0, j от i. Единица на диагонали — петля. Пара единиц A[i][j] = A[j][i] = 1 — одно неориентированное ребро (один столбец, а не два). Единица только с одной стороны — дуга в сторону этой единицы.

Каждое найденное ребро получает номер e1, e2, … и свой столбец: для ребра u—v единицы в строках u и v, для дуги u→v — -1 в начале и +1 в конце, для петли — 2.

Ввод

Задача 3. Инцидентность → смежность

По матрице инцидентности (строки — вершины, столбцы — рёбра) построить матрицу смежности.

Как работает

Каждый столбец разбирается отдельно: две единицы — неориентированное ребро, -1 и +1 — дуга от -1 к +1, одна двойка — петля. Столбец, не подходящий ни под один шаблон, — ошибка с номером столбца.

По каждому ребру ставятся единицы в матрицу смежности: ребро u—v даёт A[u][v] и A[v][u], дуга u→v — только A[u][v], петля — A[v][v]. Кратные рёбра матрицей из 0/1 не представить, поэтому они тоже считаются ошибкой. Задачи 2 и 3 взаимно обратны.

Ввод

Задача 4. Матрица достижимости

По матрице смежности (ориентированного или неориентированного графа) построить матрицу достижимости: R[i][j] = 1, если из i есть путь в j.

Как работает

Алгоритм Уоршелла. Начинаем с R = A и ставим единицы на диагонали — каждая вершина достижима из самой себя.

Затем три вложенных цикла k, i, j: если из i можно дойти до k, а из k — до j, то из i можно дойти до j. После прохода по всем промежуточным вершинам k матрица содержит транзитивное замыкание. Если она целиком из единиц, граф сильно связен.

Ввод

Задача 5. Изоморфизм графов

Даны две матрицы смежности. Определить, изоморфны ли графы, и если да — указать соответствие вершин.

Как работает

Сначала быстрые инварианты: число вершин, число рёбер, ориентированность и отсортированная последовательность степеней. Если хоть что-то не совпало, графы точно не изоморфны — дальше не проверяем.

Если инварианты совпали, перебираем все перестановки p вершин (itertools.permutations) и проверяем A2[p[i]][p[j]] == A1[i][j] для всех i, j. Первая подходящая перестановка и есть изоморфизм: вершина i первого графа переходит в p[i] второго. Перестановок n!, поэтому при n > 8 выдаётся предупреждение.

Ввод