Как сгенерировать все возможные графы из 3, 5 и т. д. вершин?
Пусть даны 4 точки (A,B,C,D) Как сгенерировать все возможные связи ? Я могу сгенерировать на python все возможные ребра, но вот как сгенерировать именно графы?
Т. е., например А->B->C->D, A->B->A->C->D и т. д. - как найти все возможные маршруты для всех комбинаций пар вершин?
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Для размера n<=6 подойдёт простой метод с отсевом несвязных графов:
Проходим все числа в диапазоне n-1..2n*(n-1)/2-1, каждое представляем в бинарной записи. Нулевой бит в k-й позиции означает отсутствие k-го ребра, 1 - наличие.
Число в показателе степени - это количество возможных рёбер, а начинаем с n-1 - поскольку это минимальное число рёбер для образования связного графа.
Проверяем граф на связность.
Для n=6 это всего 32 тыс. графов. Далее уже будет сложнее...