Итак, получается следующая картина.
Задача. Дан список порядков вершин предполагаемого графа, надо:
- Убедиться, что существует "химическая формула" для такого списка, т.е. связный мультиграф.
- Если существует, построить любой пример.
На первый вопрос можно ответить численно, проверив следующие критерии:
- Сумма порядков является четной
- Полусумма порядков больше или равна числу вершин, уменьшенному на

- Наибольший порядок меньше или равен сумме остальных порядков
Мне было интересно попытаться построить сам граф, да и вопрос существования решить не численным, а алгоритмическим путем.
В
данной статье приведены необходимые алгоритмы, которые я реализовал на Wolfram Mathematica.
Краткое описание:
- Произвольным образом привязываем к каждому порядку номер вершины (вложенный список, словарь и т.д.)
- Сортируем порядки по убыванию
- Выбираем (один из) наибольших и (один из) наименьших
- Уменьшаем каждый из них на 1 и добавляем ребро, соединяющее соответствующие вершины
- Удаляем порядки равные 0. Если (в одной из итераций) оба порядка стали нулевыми,
значит полученный мультиграф будет несвязным. Мы можем продолжить его построение,
либо сразу сделать останов с сообщением Non connected - Если остался один ненулевой элемент, значит граф (даже несвязный!) построить нельзя.
Останов с сообщением None - Если осталось пустое множество, мы достигли результата, либо продолжаем итерации с п.2
Данный алгоритм строит
один из возможных графов. Например, для списка порядков
![$[3,3,3,3]$ $[3,3,3,3]$](https://dxdy-02.korotkov.co.uk/f/5/7/f/57fd479f72deecf405a356c4a76d303882.png)
получается следующий простой, но
непланарный граф:

хотя предполагается что это должна быть "молекула тетразета":

Но химическое соединение может быть непланарным, поэтому свою задачу алгоритм выполняет.
И еще пример результата работы алгоритма:
Список порядков:
![$[5, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1]$ $[5, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1]$](https://dxdy-02.korotkov.co.uk/f/d/e/a/deab1ffe7dc9043c0c5933e481584ade82.png)
Граф:
