Предположим, у нас есть два изоморфных друг другу графа (G и H). У нас также есть биекция между вершинами этих двух графов. Теперь мы добавляем по одному ребру к каждому графу (G + e, H + e). Есть ли простой способ узнать, являются ли полученные графы изоморфными или нет? А еще среди узлов найти излишества? Я искренне ценю любую помощь.
Изоморфизм графов двух графов, имеющих изоморфные подграфы
Ответы (1)
Точно не знаю, но думаю, что нет. Знание одной возможной биекции между двумя изоморфными графами, похоже, не дает много информации. Если ваша биекция все еще работает после добавления ребра, то да, вы знаете, что они изоморфны, но если биекция больше не работает, то либо два графика больше не изоморфны, либо существует другая биекция, которая действительно работает.
Если бы вы также знали, что эти два графа не имеют автоморфизма, тогда знание биекции, безусловно, помогло бы. Тогда вы узнаете, что ваша биекция уникальна, и вы можете просто применить ее к двум новым графикам, чтобы увидеть, изоморфны они или нет.
person
user3635700
schedule
11.04.2018
