Реализовать степени простого графа методом Хавела — Хакими
Проверить графичность последовательности степеней и при успехе построить один простой граф с точным сохранением номеров вершин.
Ваш пример
Разбор примера
Последовательность графична
| Вершина | Степень |
|---|---|
| 1 | 3 |
| 2 | 3 |
| 3 | 2 |
| 4 | 2 |
| 5 | 2 |
- Степень каждой исходной вершины проверена в построенной матрице.
Метод и условия расчёта
Удаляем вершину максимальной остаточной степени и соединяем с наибольшими оставшимися.
Уменьшение степеней сопровождается реальной записью рёбер, а не только ответом о чётности суммы.
Теория к методу
Последовательность степеней задаёт ограничения на соседство, а не готовый граф. Чётная сумма является лишь необходимой проверкой. Метод Хавела — Хакими последовательно снимает максимальную степень, уменьшая степени выбранных соседей, и позволяет восстановить сами рёбра.
Работа идёт с простым неориентированным графом без петель и кратных рёбер. Поэтому степень неотрицательна и меньше числа вершин. Сохраните исходные номера вершин при сортировке остаточных степеней: иначе построенная матрица может удовлетворять переставленному списку, но не исходному. При равных степенях для воспроизводимости достаточно выбирать меньший исходный номер первым.
Пример: Список (3,3,3,1) имеет чётную сумму десять. После присоединения первой вершины ко всем остальным остаются степени (2,2,0) у трёх вершин.
Вершина остаточной степени два видит лишь одного кандидата с положительной степенью. Список не графичен, хотя проверка чётности успешно прошла.
Вопросы по теме
Чётная сумма гарантирует граф?
Нет. Это необходимое условие; ограничения простого графа могут всё равно нарушаться.
Граф единственный?
Нет. Возвращается одна реализация с детерминированным разрешением равных степеней по номеру вершины.
Графы и маршруты: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.