ПОИСК Статьи Рисунки Таблицы Представление графов с помощью матриц из "Принципы математического моделирования химико-технологических систем" Заметим, что диагональный элемент = 1, что соответствует наличию петли при вершине 2. [c.123] Матрицу [8] называют также структурной матрицей графа. [c.123] В качестве примера составим матрицы инциденций для графов, изображенных на рис. 1У-4, а, б. [c.123] Здесь 8 и 8 — подматрицы инциденций, соответствующие связным компонентам несвязного графа. [c.124] Свойства матриц инциденций отражают топологические особенности соответствующих графов и могут быть сформулированы в виде трех теорем. [c.124] Теорема 1У-3. Любой определитель, содержащийся в матрице инциденций [8], равен нулю, -Ь1Гили —1. [c.124] Если каждый столбец определителя Д, содержащегося в [3], имеет два ненулевых элемента (-1-1 и —1), то Д = О, так как сумма всех строк дает строку, все элементы которой равны нулю. Если хотя бы один столбец Д имеет только один ненулевой элемент, то при разложении Д но элементам этого столбца можно в результате прийти к определителю первого порядка. Таким образом, Д равен О, Н-1 пли —1. [c.124] Теорема 1У-4. Определитель любой подматрицы матрицы ипциденцпй, отвечающей циклу, равен нулю. [c.124] Любой цикл имеет равное число верпшн и дуг. Следовательно, ему соответствует квадратная подматрица, каждый столбец которой содержит -Ь1, —1 (обе вершины каждой дуги входят в цикл). Сумма строк такой квадратной подматрицы равна нулю, а значит ее определитель равен нулю. [c.124] Теорема 1У-5. Определитель (т—1) порядка подматрицы (т—1) ранга матрицы инциденций (т — число строк этой матрицы), отличный от нуля, отвечает дереву исходного связного графа. [c.124] Обратная теорема определитель, соответствующий дереву графа, отличен от нуля. [c.124] Число ветвей дерева, как было отмечено ранее, на единицу меньше числа вершин, следовательно, определитель дерева должен иметь порядок т — 1). Если определитель порядка т — 1) равен нулю, то, согласно теореме 1У-4, он отвечает некоторому циклу в графе и, значит, не соответствует дереву. Наоборот, если такой определитель не равен нулю, отвечающий ему граф, который имеет т — 1 дуг, не содержит циклов и, следовательно, является деревом. [c.124] Теорема 1У-5 может быть распространена и на несвязные графы. В этом случае определитель, соответствующий лесу графа, имеет порядок (т — к) и отличен от нуля, и обратно — определитель порядка т — к), отличный от нуля, отвечает лесу несвязного графа. [c.124] Таким образом, ранг матрицы инциденций всегда равен чпслу ветвей дерева (леса) графа. [c.124] Указанные конфигурации элементов представляют собой деревья графа. Подобные результаты легко получить и для несвязного графа, показанного на рис. 1У-4, б. [c.125] Из приведенных выше теорем следует важное утверждение о равенстве ранга графа, определяемого выражением (1У,6), и ранга матрицы инциденций, т. е. [c.125] Равенство рангов графа и соответствующей матрицы инциденций позволяет в ряде случаев значительно упростить вычисления. [c.126] Кроме матрицы инциденций [8], для каждого графа может быть записана другая матрица, называемая матрицей циклов [М], матрицей совпадений или соединений. [c.126] Здесь М и М — подматрицы, соответствующие связным компонентам несвязного графа. [c.127] Теорема 1Л -6. Ранг матрицы циклов равен числу хорд соответствующего графа, т. е. [c.127] Вернуться к основной статье