Обмен опытом

См. также:

Уважаемые коллеги. Размещение авторского материала на страницах электронного справочника "Информио" является бесплатным. Для получения бесплатного свидетельства необходимо оформить заявку

Положение о размещении авторского материала

Размещение информации

О распознавании изоморфизма графов бержа с использованием понятия перестановочной матрицы

16.05.2018 359 574
Артюхина Дарья Дмитриевна
Артюхина Дарья Дмитриевна, преподаватель

Козловский Богдан Юрьевич
Козловский Богдан Юрьевич, студент

Оскольский политехнический колледж

Проблема изоморфизма графов является одной из центральных в теории графов. В данной работе рассматривается нетрадиционный подход к ее решению с привлечением понятия перестановочной матрицы и степени перестановочной матрицы. На основе полученных результатов могут быть построены эффективные алгоритмы распознавания изоморфизма графов различных типов.

1.1 Рассмотрим сначала наиболее тяжелый случай распознавания изоморфизма – случай однородных графов.

Прежде всего, напомним понятие перестановочной матрицы: перестановочной называется матрица, в каждом столбце и в каждой строке которой находится ровно по одному единичному элементу, а все прочие ее элементы равны нулю.

Умножение любой матрицы А на перестановочную матрицу S слева означает некоторую перестановку строк матрицы А, справа – столбцов.

 

Читать работу полностью (оригинал работы):

О распознавании изоморфизма графов бержа с использованием понятия перестановочной матрицы




Назад к списку


Добавить комментарий
Прежде чем добавлять комментарий, ознакомьтесь с правилами публикации
Имя:*
E-mail:
Должность:
Организация:
Комментарий:*
Введите код, который видите на картинке:*