Хозяйке на заметку: nauty

Пакет инструментов gtools, входящий в состав nauty, отлично подходит для генерирования графов и различных их характеристик, а также манипулирования графами тучей разных способов. Собирается на Cygwin без малейших затруднений.

Пример: сгенерировать все связные графы из 5 вершин с максимальной степенью вершины 4 и диаметром 2, записать в файл в формате g6.

$ ./geng -cD4 5 | ./pickg --e -Z2 - "output.g6"
>A ./geng -cd1D4 n=5 e=4-10
>Z 21 graphs generated in 0.00 sec
>A ./pickg --e -Z2 - output.g6
1 graphs : e=4
2 graphs : e=5
4 graphs : e=6
4 graphs : e=7
2 graphs : e=8
1 graphs : e=9
>Z 21 graphs read from stdin; 14 written to output.g6; 0.000 sec

После чего полученный файл можно загрузить в Wolfram Mathematica и любоваться результатами.

Import["output.g6"]


С этим дальше можно играться. Например, получить представление в виде списка ребер для всех графов с 7 ребрами из этого файла.

EdgeRules /@ Select[Import["output.g6"], EdgeCount[#] == 7 &] // Column
{1->4,1->5,2->4,2->5,3->4,3->5,4->5}
{1->3,1->4,1->5,2->4,2->5,3->5,4->5}
{1->3,1->4,1->5,2->5,3->4,3->5,4->5}
{1->3,1->4,1->5,2->3,2->4,2->5,3->5}