Матрицы и обратные матрицы в Python


Для проекта, который я делаю, я декомпозирую граф, созданный с помощью NetworkX, в матрицу смежности с помощью функции NetworkX adj_matrix (). Однако одна из проблем, с которой я столкнулся, заключается в том, что каждый отдельный граф, который я разлагаю, дает мне следующую ошибку, когда я пытаюсь найти обратную матрицу.

str: Traceback (most recent call last):
  File "C:eclipsepluginsorg.python.pydev.debug_1.4.7.2843pysrcpydevd_resolver.py", line 179, in _getPyDictionary
    attr = getattr(var, n)
  File "C:Python26libsite-packagesnumpycoredefmatrix.py", line 519, in getI
    return asmatrix(func(self))
  File "C:Python26libsite-packagesnumpylinalglinalg.py", line 355, in inv
    return wrap(solve(a, identity(a.shape[0], dtype=a.dtype)))
  File "C:Python26libsite-packagesnumpylinalglinalg.py", line 254, in solve
    raise LinAlgError, 'Singular matrix'
LinAlgError: Singular matrix

Я попытался создать матрицы смежности из 5 различных графов, и все они дали одну и ту же ошибку, когда я попытался найти обратную матрица смежности. Вопрос, который я ставлю, заключается в том, есть ли какой-либо способ перейти от графа NetworkX к матрице. Каков мой лучший план действий отсюда? Я понимаю, что есть и другие вопросы, связанные с матричными инверсиями, но мои несколько ограничены тем фактом, что мне нужна матрица смежности графа.

3 2

3 ответа:

Матрицы смежностине всегда обратимы . Естьстатьи по этому вопросу; я не уверен, существует ли какая-либо простая характеристика соответствующих графов. Прагматичным подходом было бы поймать исключение LinAlgError в вашем коде (попробуйте ... Кроме...) и предупредить, когда матрица смежности не обратима (и продолжайте выполнять свои вычисления в противном случае).

Я не знаю точно, как networkx производит матрицу смежности, но нет абсолютно никаких оснований для того, чтобы она была обратимой. Например, рассмотрим полный граф (все узлы соединены друг с другом), его матрица adacency полна единиц, и матрица, очевидно, имеет 0 в качестве собственного значения (как только число узлов >= 2, конечно...). Или граф с N вершинами и без ребер, его матрица смежности равна 0...

Что ты хочешь делать ? Мне никогда не приходилось думать об этом. обратная матрице смежности, но очень часто обратная I - x A для некоторого (малого) значения x. ее обратная величина

(I - x A) ^(-1) = I + xA + x^2 A2 + ...

, которая обратима для некоторого значения x (на самом деле, как только |x|

Вы спрашиваете о методе генерации графов, матрицы смежности которых не являются сингулярными? это не вина networkx или numpy, что графики, которые вы создали, имеют матрицы смежности, которые не имеют инверсий.