Матрицы и обратные матрицы в Python - PullRequest
Новая
       51

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

2 голосов
/ 04 декабря 2009

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

str: Traceback (most recent call last):
  File "C:\eclipse\plugins\org.python.pydev.debug_1.4.7.2843\pysrc\pydevd_resolver.py", line 179, in _getPyDictionary
    attr = getattr(var, n)
  File "C:\Python26\lib\site-packages\numpy\core\defmatrix.py", line 519, in getI
    return asmatrix(func(self))
  File "C:\Python26\lib\site-packages\numpy\linalg\linalg.py", line 355, in inv
    return wrap(solve(a, identity(a.shape[0], dtype=a.dtype)))
  File "C:\Python26\lib\site-packages\numpy\linalg\linalg.py", line 254, in solve
    raise LinAlgError, 'Singular matrix'
LinAlgError: Singular matrix

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

Ответы [ 3 ]

4 голосов
/ 04 декабря 2009

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

2 голосов
/ 04 декабря 2009

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

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

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

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

1 голос
/ 04 декабря 2009

Вы запрашиваете метод для генерации графов, матрицы смежности которых неособы? сетьx или нампи не виноваты в том, что сгенерированные вами графы имеют матрицы смежности, которые не имеют обратных.

...