Материал конференции: "XIV международный научный семинар "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (20-25 июня 2022 г., Москва)"
Авторы:Курапов С.В., Давидовский М.В.
Диакоптика и структуры графа
Аннотация:
В данной работе рассматриваются вопросы определения изоморфизма сепарабельных графов. Показано, что для графа любого вида можно применить методы диакоптики, то есть разбить множество вершин графа на два подмножества. Первое подмножество вершин характеризует несепарабальную часть графа и представляет собой несепарабельный граф. Второе подмножество характеризует дополнительную часть графа и состоит из определенных частей графа. Первый этап проверки изоморфизма заключается в проверке изоморфизма несепарабальных частей графов. Затем проверяется на соответствие дополнительные части графов. Если несепарабельная часть и дополнительные части изоморфны, то изоморфны и сепарабельные графы.
