Условный изоморфизм подграфов

Question

Я искал это по всему Интернету около двух или трех дней подряд, но пока не повезло.

Я знаю, что существует множество библиотек и реализация для изоморфизма субграфов в дикой природе, но все они работают для невзвешенных графов. Например, двумя из наиболее распространенных алгоритмов являются алгоритм VF2 и Улемана. Здесь мой вопрос: существуют ли какие-либо методы, которые дают граф (G) и график запросов (g), можно ли найти, является ли g подграфом (и изоморфным) G или нет? (Обратите внимание, что следующий список канта графов.)

G 
1 2 c 
1 3 d 
1 4 c 
2 3 a 
... 
g 
1 3 d 
2 3 a 

В этом случае г подграф и изоморфна G, но если у нас есть что-то вроде этого:

g 
1 3 t 
2 3 a 

Теперь g уже не является подграфом G и не является изоморфным.

ОБНОВЛЕНИЕ: Оба графика неориентированы.

Answer 1

g = {(1 2 a)} не изоморфно G, так как вес этого ребра в G является «c» не «a».

Это странно. Проще говоря, графы G, G '(фактически, любые алгебраические структуры) равны isomorphic, если существует некоторая функция f из {G < -> G'}, так что для любого отношения R (g1, g2) (g1, g2 в G) , R '(f (g1), f (g2)) также выполняется для G' и наоборот. Таким образом, любой граф G ', полученный из G переименованием (перестановкой) вершин, изоморфен G.

Как вам кажется, вам интересно узнать, существует ли для любого отмеченного края g ребро, соединяющее одни и те же вершины и с той же меткой в ​​G. Самый простой способ сделать это - дублирование краев G и сортировка их по компонентам. Тогда для каждого ребра запроса g примет O (log (| G |)), чтобы проверить, имеет ли G одно и то же ребро (и имеет тот же знак). Таким образом, общее время - O (| G | * log (| G |)) для подготовки графа G и O (| g | * log (| G |)) для обработки каждого последующего запроса.

Обн: Под «сортировки края G от компонента» Я имел в виду следующее: построить массив (или бинарное дерево) ребер, сортируются по первой вершины затем второй вершины. Чтобы легко найти край, его следует дублировать. Например, край (1, 2, c) должен присутствовать как (1, 2, c) и (2, 1, c). Так что, в виде массива, G из примера выше, становится

(1, 2, c) 
(1, 3, d) 
(1, 4, c) 
(2, 1, c) 
(2, 3, a) 
(3, 1, d) 
(3, 2, a) 
(4, 1, c) 

На заднем числе, это может быть лучше писать оба край G и г с вершиной с меньшим числом первым - это способом, никакого дублирования не требуется.