Матрица - смежность - граф
Cтраница 4
В случае когда достижимость ограничена путями единичной длины ( просто дугами), ограниченные базы называют минимальными доминирующими множествами. Ограниченная матрица достижимостей графа О соответствует тогда матрице смежности графа С; граф О может быть назван ограниченным транзитивным замыканием графа О ( в соответствии с определением транзитивного замыкания, приведенным в разд. [46]
В случае когда достижимость ограничена путями единичной длины ( просто дугами), ограниченные базы называют минимальными доминирующими множествами. Ограниченная матрица достижимостей графа G соответствует тогда матрице смежности графа G; граф G может быть назван ограниченным транзитивным замыканием графа G ( в соответствии с определением транзитивного замыкания, приведенным в разд. [47]
После того как тем или иным путем получены образующие подстановки изучаемого представления, можно приступать к построению базисных графов. Разбиение множества N X N на 2-орбиты группы ( G, N) удобно интерпретировать как полный ориентированный цветной граф, дуга ( а, Ь) которого окрашена в цвет k, когда ( a, b) Qk. Если транзитивная группа задана произвольной системой образующих, построение матрицы смежности цветного графа производится в два этапа. Сначала генерируются образующие фиксатора Gt точки 1 в группе G, с помощью которых строится первая строка матрицы, и находятся представители смежных классов G no GI в виде слов от образующих. Затем действием представителей смежных классов на первую строку вычисляются все остальные строки матрицы смежности цветного графа. Наиболее трудоемкой частью этого алгоритма является генерация образующих фиксатора точки. Трудоемкость существенно снижается, если в системе порождающих подстановок явно выделена подсистема, порождающая фиксатор точки. Следует отметить, что и алгоритм Тодда - Коксетера и индуцирование позволяют в принципе получить в качестве побочного продукта образующие фиксатора точки. [48]
 |
Представление функции f ( x, у с помощью графа. [49] |
В этой статье нами вводится новая теоретико-графовая трактовка мебиусовских систем [15], основанная на рассмотрении непланар-ных графов, которые, хотя и непредставимы адекватно на плоскости ( поскольку могут иметь место пересечения), могут быть уложены на римановой поверхности. Будет видно, что при таком формализме отрицательные элементы полученных матриц смежности обусловлены совершенно естественным образом топологией римано-вых поверхностей, а не вводятся искусственно, как это было в прежнем подходе [5], в результате более случайных и более интуитивных физических соображений. Подчеркнем также, что условия теоремы Перрона-Фробениуса [16] для неотрицательных матриц неприменимы к матрицам смежности мебиусовских графов; нами обсуждается важность этого обстоятельства для собственных значений и собственных векторов таких графов. [50]
Изучены мебиусовские системы с использованием нового теоретико-графового метода, включающего рассмотрение непланарных графов, которые могут быть уложены без пересечений на двулистной римановой поверхности. В рамках такого формализма появление отрицательных элементов в полученных матрицах смежности связано совершенно естественным образом с математическим аппаратом римановых поверхностей, при этом отпадает необходимость прибегать к довольно интуитивным физическим соображениям. Кроме того, подчеркивается, что условия теоремы Перрона-Фро - бениуса для неотрицательных матриц неприменимы к матрицам смежности мебиусовских графов, и обсуждается важность этого обстоятельства для собственных значений и собственных векторов таких графов. [51]
Особенно наглядно преимущество матричного языка перед аналитическим становится ощутимым при изучении алгебраических операций над смешанными графами. Кроме того, при формулировке критериев разложения графов по алгебраическим операциям приходится обращаться к различным видам матриц смежности графов, по которым легко получить соответствующее разложение графа по той или иной операции. [52]
Тривиальный алгоритм нахождения ПКМ с минимальным числом единиц для графа G заключается в следующем. Применим произвольную подстановку t e Т к матрице R, где Т - симметрическая группа подстановок. Сравнивая ф и ф), выбираем ПКМ с наименьшим числом единиц. Продолжая этот процесс, после п сравнений находим матрицу смежности графа Я, который является минимальным изоморфным продолжением графа G, и разложим по операции умножения в произведение двух графов с k и / вершинами соответственно. [53]
Страницы: 1 2 3 4