Реализовать степени простого графа методом Хавела — Хакими

Проверить графичность последовательности степеней и при успехе построить один простой граф с точным сохранением номеров вершин.

Ваш пример

Числа и дроби: 0.5, 0,5 или 1/3. Числа в строке разделяются пробелами, строки — переносом. Выражения не выполняются.

Разбор примера

Последовательность графична

Проверяемые промежуточные данные
ВершинаСтепень
13
23
32
42
52
  1. Степень каждой исходной вершины проверена в построенной матрице.

Метод и условия расчёта

Удаляем вершину максимальной остаточной степени и соединяем с наибольшими оставшимися.

Уменьшение степеней сопровождается реальной записью рёбер, а не только ответом о чётности суммы.

Теория к методу

Последовательность степеней задаёт ограничения на соседство, а не готовый граф. Чётная сумма является лишь необходимой проверкой. Метод Хавела — Хакими последовательно снимает максимальную степень, уменьшая степени выбранных соседей, и позволяет восстановить сами рёбра.

Работа идёт с простым неориентированным графом без петель и кратных рёбер. Поэтому степень неотрицательна и меньше числа вершин. Сохраните исходные номера вершин при сортировке остаточных степеней: иначе построенная матрица может удовлетворять переставленному списку, но не исходному. При равных степенях для воспроизводимости достаточно выбирать меньший исходный номер первым.

Пример: Список (3,3,3,1) имеет чётную сумму десять. После присоединения первой вершины ко всем остальным остаются степени (2,2,0) у трёх вершин.

Вершина остаточной степени два видит лишь одного кандидата с положительной степенью. Список не графичен, хотя проверка чётности успешно прошла.

Вопросы по теме

Чётная сумма гарантирует граф?

Нет. Это необходимое условие; ограничения простого графа могут всё равно нарушаться.

Граф единственный?

Нет. Возвращается одна реализация с детерминированным разрешением равных степеней по номеру вершины.

Графы и маршруты: объяснения, примеры и практика

Основа объяснения

Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.