Нахождение всех возможных путей между всеми вершинами графа

Question

У меня есть ориентированный граф с 13 вершинами, и я хотел бы изучить все возможные простые пути любой длины (максимум =12). Я пробовал формулу FindPath[Graph,Vertex1,Vertex2,12,All], но мне пришлось вводить эту функцию 13*12 раз из-за того, что я не знаю, как быстрее и проще извлечь пути. Есть ли способ извлечь все пути (из каждой вершины в любую другую вершину) с помощью одной формулы вместо 156 формул? У меня также есть доступ к Матрице смежности, которая может указывать на другой возможный путь, но я не знаю, как извлечь пути из Матрицы смежности. Я знаю, что было много вопросов о том, как найти все возможные пути между двумя вершинами, но мне нужно большее изображение.

Answer 1

Главное, что вы не знаете примитивов для отображения функции на двумерный массив или треугольник. Уважать Map, Outer, Table, Scan, MapThreadи т. д. в документации Mathematica.

Один из способов сделать это (адаптирован к вашему случаю):

Flatten[ Table[ Table[ 
  FindPath[ mygraph, vertexlist[[i]],  vertexlist[[j]], 12, All ],
    {j,i+1, Length[vertexlist] }], {i, 1, Length[vertexlist]-1 }], 1]

при условии, что вы поместили в список вершин идентификаторы ваших вершин. Если это просто целые числа от 1 до 13, вы можете просто поставить i вместо vertexlist[[i]] и т. Д.

Вы получите n*(n-1)/2 списков путей между двумя разными вершинами, отсортированных по начальной вершине. Если ваш график ориентирован, вы можете вместо этого использовать целое n * (n-1). Простые модификации приведенного выше кода дадут вам это.