Главная > Математика > Конечные графы и сети
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.32. Графы и собственные значения неотрицательных матриц

Далмэдж и Мендельсон [17] использовали аппарат - ориентированных графов для исследования различных свойств характеристических уравнений и собственных значений матриц, появляющихся при исследованиях в области стохастических процессов, экономике и численном анализе. Ориентированный граф является контурно -разделимым тогда и только тогда, когда множество вершин V можно разделить на множеств так, что все дуги удовлетворяют следующему свойству: если некоторая дуга имеет начальную вершину в то ее конечная вершина находится в при при Любой -матрнце можно поставить в соответствие ориентированный граф, коэффициенты матрицы смежности которого равны единице, если соответствующие Если этот граф контурно -разделимый, то разделению соответствует перестановочная матрица такая, что

где нулевые матрицы и каждый элемент не принадлежащий равен нулю. Матрицы известны под названием циклических ломпонент А,

Таким образом, контурно -разделимый граф имеет структуру, показанную на рис. 6.74. Заметим, что любая последовательность из дуг (в частности, каждый путь и контур) обладает следующим свойством.

Рис. 6.74.

Если ее начальная и конечная вершины находятся в и соответственно, то В частности, длина каждого контура кратна

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

Многочлен, в котором коэффициент при члене высшего порядка равен единице, называется нормированным. Имеет место следующая теорема [17].

Теорема 6.12. Если А — такая матрица, что соответствующий ей ориентированный граф циклически -раз-делимый и множество диагональных компонент то существует нормированный многочлен и неотрицательное целое число такие, при этом характеристический многочлен Лесть а характеристический многочлен есть Кроме того, существуют целые числа с суммой, равной такие, что характеристический многочлен есть и для любого ненулевого корня простейшие делители одинаковы для каждого

Упражнение 6.32. (см. скан)

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление