Комбинаторное создание подграфов между заданной верхней и нижней границей (Sage)

Я новичок в sage, и я читал документацию, но это очень новая для меня территория, и немного сложно понять все.

Что я хочу сделать, так это, учитывая матрицу смежности, верхние и нижние границы, сгенерировать все пути через эту матрицу, где «путь» состоит из одной записи из каждой строки, так что вес пути равен равны или находятся между границами.

Еще лучше было бы, если бы я мог упорядочить заданные пути по 1.) Количество ребер с меньшим весом в каждой строке, чем запись в пути, и/или 2.) Минимальное перекрытие с другими путями в отношении #1 .

Для наглядности быстрый пример. Учитывая матрицу 4x4:

[[1,2,3,4],
 [5,6,7,8],
 [10,11,12,13],
 [20,21,22,23]]

И верхняя граница 38, и нижняя граница 37, возможные пути могут быть:

2,5,10,20 3,5,10,20 2,6,10,20 2,5,11,20 2,5,10,21 и т.д. так что, надеюсь, вы поняли идею.

Еще лучше было бы, если бы я мог быстро отфильтровать избыточность, не включая пути, которые являются подмножествами других путей (например, 2, 5, 10, 20 охватывается 3, 5, 10, 20, поскольку для каждого пути я планирую при включении всех ребер с меньшим весом каждой соответствующей строки).


python combinatorics sage
person Travis Black    schedule 27.02.2018    source источник
comment
Я чувствую, что сбит с толку; как эта матрица является матрицей смежности?   -  person kcrisman    schedule 21.03.2018
comment
Значения в матрице являются весами ребер. Позиция строки и позиция столбца являются узлами данного ребра. Итак, скажем, вес 6 в этой матрице — это ребро (1,1). Теперь, конечно, у нас не должно быть ребра, идущего от узла к самому себе, и это немного небрежно с моей стороны, но я пытался быстро передать концепцию. У него должны были быть 0, идущие по диагонали.   -  person Travis Black    schedule 21.03.2018
comment
Понятно, взвешенная матрица смежности. Тогда разве он не должен быть симметричным? В любом случае, я до сих пор не уверен на 100%, как это связано, но я, по крайней мере, выложу несколько ссылок, которые могут вам помочь.   -  person kcrisman    schedule 22.03.2018

Ответы (1)


arrow_upward
0
arrow_downward

If you have a symmetric matrix (with or without diagonal entries nonzero) you can сделайте это.

M = matrix([[0,2,3,4],[2,0,7,8], [3,7,0,13], [4,8,13,0]])
G = Graph(M,format='weighted_adjacency_matrix')
G.graphplot(edge_labels=True,spring=True).show()

И, надеюсь, из самого G вы могли бы делать то, что хотите. (Если это не имеет ничего общего с графиками, а только с матрицей, и в этом случае вам может понадобиться совсем другое.)

Я не уверен, что именно вы пытаетесь сделать (как «пути» соответствуют подграфам?), и, вероятно, описание этого выходит за рамки этого сайта (в отличие от math.SX.com), но общая документация по графам содержит некоторые методы пути и ненаправленная документация также может оказаться полезной.

person kcrisman    schedule 22.03.2018