Так что я родом из химии, и мне нравится теория графов ... По крайней мере, в теории. За исключением некоторых легких приложений для хемоинформатики, я действительно не углубился в эту область математики. Но в любом случае мои интересы вращаются вокруг представления молекул в виде графиков. Узлы - это атомы, а (ненаправленные) ребра - это связи (обратите внимание, что множественные ребра могут соединять два узла в молекулярных графах). Это представление игнорирует трехмерную реальность молекулярной геометрии, но вполне адекватно отражает топологию системы химических связей. Некоторые молекулы настолько малы и связаны, что вы можете довольно легко восстановить их трехмерную структуру, исходя только из ее топологии, и они представляют особый интерес для меня.
На самом деле, эти маленькие молекулы представляют такой интерес * Для меня 1004 * то, что я запустил программное обеспечение, направленное на их систематизацию, c теория моды и графов показалась мне наиболее подходящей теоретической основой, на которой я мог бы сформулировать свою идею, чтобы я мог программировать ее на подходящем языке программирования. .
Как видно из рисунка, графики, представляющие интересующие меня малые молекулы, имеют разные типы узлов и потенциал для несколько ребер, чтобы сформировать между каждым узлом. Существуют два правила, которые определяют, является ли данный граф действительным :
Узлы каждого типа имеют максимальную степень, которую им разрешено иметь;
Никакая пара узлов не может иметь более трех ребер между ними;
График не может быть непересекающимся.
Для заданного числа узлов и заданного набора типов узлов я хотел бы знать, существует ли алгоритм для создания исчерпывающего набора каждого действительного графа, который может быть создан. Или хотя бы информацию об алгоритме, который делает почти .
Я пытался сделать это с python модулем networkx, используя алгоритм configuration_model, но он генерирует случайные графы, которые соответствуют условию максимальной степени. Этого недостаточно, и я не знаю точно, как расширить то, что сетьx дала мне, чтобы написать соответствующий алгоритм.