Исследование изоморфизма графов с помощью жордановых форм матриц смежности

doi:10.17223/20710410/40/7

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Исследование изоморфизма графов с помощью жордановых форм матриц смежности	743 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/40/7

#жорданова форма матрицы

Title: Исследование изоморфизма графов с помощью жордановых форм матриц смежности
Title: Study of graph isomorphism using jordan forms of adjacency matrices
Creator: Володичева, Маргарита Ивановна
|
Леора, Светлана Николаевна
Date: 2018
DOI: 10.17223/20710410/40/7
Description: Для установления отсутствия изоморфизма между орграфами предлагается использовать жорданову форму матриц смежности графов. Задача приведения матрицы к жордановой форме имеет полиномиальную временную сложность, верхняя оценка необходимого числа операций для n-вершинного графа составляет O(n4). Показано, что жорданова форма матриц смежности орграфов содержит больше информации о структуре графа, чем его спектр, определяемый собственными значениями матрицы смежности и их кратностью. В результате исследования жор- дановых форм матриц смежности орграфов на отдельных примерах установлено, что изоспектральные матрицы, имеющие одинаковый набор собственных значений, могут приводиться к различным жордановым формам. Это означает, что матрицы смежности не являются подобными, т. е. не являются и перестановочно подобными, что свидетельствует об отсутствии изоморфизма между графами.