Изоморфизм графа

Изоморфные графы могут быть получены один из другого путем перенумерации их вершин. Очевидно, что изоморфизм есть отношение эквивалентности на графах. Если изоморфные преобразования проводятся с графом, заданным матрицей смежности, то они сводятся к перестановке местами соответствующих строк и столбцов. Известно, что в общем случае для определения изоморфизма графов необходимо сделать п сравнений или перестановок строк и столбцов матрицы, что для графов с л>30 не под силу даже современной ЭВМ. Поэтому необходимо применить тот или иной эвристический алгоритм поиска по дереву решений. [c.211]

Граф содержит информацию о структуре системы и определяет связь между переменными (отклонениями параметров), т. е. дает основу для записи уравнений, отражающих структурные особенности системы. Однозначное соответствие графа и системы доказано и носит название изоморфизма графа и физической системы. [c.231]

Заметим, что это отношение эквивалентности является более слабым, чем изоморфизм графов (см. п. 0.2.1). Например, два графа, изображенные на рис. 9, эквивалентны, но простран-ства их путей совершенно различны. [c.37]

Топология соединения вершин НФ задается матрицей циклов. Заметим, что, несмотря на то, что теоретически матрица циклов для помеченного неориентированного графа не определяет сам граф с точностью до изоморфизма [130], в случае использования алгоритмов формирования математической модели НФ [59, 98] в указанной матрице циклов из всего многообразия циклов на графе останутся только те, которые определяют фундаментальный набор циклов, т. е. циклов однозначно соответствуюш,их исходным матрицам смежности вершин и инцидентности вершин и ребер, поэтому в качестве исходных данных для алгоритма формирования топологии соединения вершин СФ взята именно матрица циклов как конечный результат работы алгоритмов [59, 98] и реализующих их программ. [c.143]

Зная топологию системы и уравнения компонент, можно получить уравнения системы [6]. Эта возможность, как показано в работе [13], вытекает из изоморфизма (в смысле обобщенных законов Кирхгоффа) между механической системой и описывающим ее графом. [c.56]

Ясно, что если дана произвольная матрица порядка Z X Z, то ее можно рассматривать как матрицу смежностей некоторого графа, причем этот граф матрицей определяется совершенно однозначно (с точностью до изоморфизма). Для того чтобы убедиться в этом, достаточно нанести на плоскость z перенумерованных вершин и направить стрелку с весом aij из вершины j в вершину i, если ац Ф 0. [c.101]

Взаимнооднозначное отображение f Z Z множества Z снова в Z, сохраняющее смежность вершин, называется автоморфизмом графа Г. Другими словами, автоморфизм есть изоморфизм графа в себя. [c.14]

До сих пор ничего не говорилось о способах сравнения производных шести и пятиверщинных графов с /Сз, 3 и Ks- Это легко можно сделать путем визуального сопоставления их топологических представлений (или с помощью квадратиков и кружков), однако решение задачи изоморфизма графов с помощью ЭВМ требует определенных затрат времени, которые тем больше, чём больше производных графов порождается из исходного. [c.184]

Полученный граф моментов Гм может отличаться от Г<о лишь наличием двух дополнительных вершин Мвх и Мвых- В остальном при соответствующем сопоставлении (О- и М-вершин они совпадают с точностью до изоморфизма и ориентации дуг. [c.133]

Ниже описывается один из способов, позволяющий упростить проблему изоморфизма шестивершинных графов. При этом отпадает необходимость в построении производных графов, содержащих по пять вершин. [c.184]

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...