Изоморфизм графов с отношением эквивалентности на множестве вершин

9

Цветной граф можно описать как кортеж где - граф, а - раскраска. Два цветных графа и называются изоморфными, если существует такой изоморфизм , что выполняется раскраска, т.е. для всех v \ в V (G) .(G,c)Gc:V(G)N(G,c)(H,d)π:V(G)V(H)c(v)=d(π(v))vV(G)

Это понятие отражает изоморфизм цветных графов в очень строгом смысле. Рассмотрим случай, когда у вас есть две политические карты одного региона, но они используют разные наборы цветов. Если спросить, окрашены ли они одинаково, можно предположить, что это означает, существует ли биективное отображение между двумя наборами цветов, так что цвета обеих карт совпадают посредством этого отображения. Это понятие может быть оформлено путем описания цветных графов , как кортеж (G,) , где является отношение эквивалентности на множестве вершин G . Тогда мы можем сказать, что два таких графа (G,1) и (H,2) изоморфны, если существует такой изоморфизм π:V(G)V(H) , что для всех парv1,v2V(G) он утверждает, что

v11v2 iff π(v1)2π(v2)

Мой вопрос заключается в том, изучалась ли ранее эта концепция в поисках канонических форм и т. Д. И если да, то под каким названием она известна?

Джон Д.
источник
3
Пожалуйста, не используйте обозначение " = " для чего-либо, кроме отношения равенства!
Дэвид Ричерби

Ответы:

9

Проблема, которую вы описываете, определенно была рассмотрена (я помню, как обсуждала ее в аспирантуре, и в то время она уже обсуждалась задолго до этого), хотя я не могу указать на какие-либо конкретные ссылки в литературе. Возможно, потому что он линейно эквивалентен изоморфизму неокрашенных графов следующим образом (это верно даже для канонических форм). Назовите проблему, которую вы описываете EQ-GI.

GI - это особый случай EQ-GI, где каждый граф имеет только один класс эквивалентности, состоящий из всех вершин.

В другом направлении, чтобы свести EQ-GI к GI, пусть будет графом с отношением эквивалентности с вершинами, ребрами и классами эквивалентности. Построить граф , множество вершин которого состоит из вершин вместе с новыми вершинами , по одному для каждого класса эквивалентности в , а также новых вершин . Соедините по пути , соедините каждый с и для каждой вершины в(G,G)nmcGGv1,,vc=Gn+c+1w0,,wn+cwiw0w1w2wn+cviw0G , связать его с соответствующей вершиной класса эквивалентности . Тогда имеет не более вершин и может быть построено по существу с одной временной привязкой. (Он также имеет не более ребер - что является для связных графов - но это несколько меньше актуальные , поскольку большинство алгоритмов GI есть проточный раз , что существенно зависеть только от .)viGn+2c+n+1O(n)m+n+c+(n+c+1)m+4n+1O(m+n)O(m)n

Обновление : так как в комментариях была некоторая путаница, я добавляю здесь набросок правильности приведенного выше аргумента. Учитывая и , пусть и - графики, построенные, как указано выше; пусть обозначает вершину сверху в , а - вершину в , и аналогично для и . Если существует изоморфизм , он должен отправить к для всех(G1,1)(G2,2)G1G2vi,1viG1vi,2G2wi,1wi,2G1G2wi,1wi,2iпоскольку в каждом графе является уникальной вершиной, которая является конечной точкой любого пути длиной не менее . В частности, отображается на . Так как соседи , не являются в точности , изоморфизм должен отображать множество на множество (и, в частности, и должны иметь одинаковое число, , классов эквивалентности). Обратите внимание, что изоморфизм не должен посылать в для всехwn+cn+c+1w0,1w0,2w0w1vi{v1,1,,vc,1}{v1,2,,vc,2}12cvi,1vi,2i , но разрешено переставлять индексы , пока соответствующие классы эквивалентности могут быть сопоставлены друг с другом. И наоборот, основываясь на этом описании того, как могут выглядеть изоморфизмы между и , легко видеть, что если то это дает изоморфизм ,vG1G2(G1,1)(G2,2)G1G2

Джошуа Грохов
источник
Насколько я понимаю, есть фундаментальная проблема с вашим сокращением. Вы в основном применяете уникальное свойство инварианта на множестве вершин каждого класса эквивалентности. В этом случае вы выбрали эксцентриситет вершины в качестве инвариантного свойства. Для графаG позволять fбыть окраской. Скажем=f это отношение эквивалентности, вызванное fт.е. u=fv тогда и только тогда f(u)=f(v),
Джон Д.
Теперь рассмотрим уменьшение EQ-GI до цветного GI. По вашему аргументу для входа(G,=1),(H,=2) достаточно пройти G,H и выбрать раскраски c1,c2 которые побуждают =1,=2, Проблема здесь в том, что(G,c)(H,d) подразумевает (G,=c)(H,=d)но другое направление не обязательно верно, потому что мы не знаем соответствия между двумя наборами классов эквивалентности априори.
Джон Д.
Другими словами, я не вижу, как можно было бы просто преобразовать граф, чтобы уменьшить EQ-GI до цветного GI из-за более сложных ограничений. Однако ясно, что ваша конструкция будет работать, чтобы уменьшить цветной GI до GI.
Джон Д.
@ user17410 EQ-GI - цветной GI. «Назовите проблему, которую вы описываете EQ-GI». Конечно, для преобразования графа возможно привести EQ-GI к GI: фактически это можно сделать для любой проблемы изоморфизма реляционных структур в GI. Сокращение Джошуа выглядит правильным для меня; Я думал о немного более простом, который добавляет довольно больше вершин.
Дэвид Ричерби
1
Ваш аргумент правильности убедил меня. Я быстро сделал выводы, прежде чем нашел время проанализировать ваше сокращение, прошу прощения.
Джон Д.
3

Я прочитал ваш последний комментарий в правильном ответе Иисуса Навина; если вам нужно преобразовать EQ-GI в цветной GI (т. е. у вас проблемы с цветами, назначенными классам эквивалентности), вы можете использовать следующее сокращение:

Предположим, что начальные графы G1=(V1,E1), G2=(V2,E2) и здесь qклассы эквивалентности; затем вы можете добавить к каждому графу «перестановку», то есть полный граф на|V1|+1=|V2|+1 узлы (K|V1|+1,K|V2|+1) и использовать q+1 цвета c1,...,cq,cq+1,

В обоих K а также K, q узлы различаются и окрашиваются c1,...,cq остальные узлы окрашены cq+1, УзлыG1 окрашены цветом cq+1 и узлы в том же классе эквивалентности связаны с соответствующим цветом в K; узлыG2 окрашены цветом q+1 и узлы в том же классе эквивалентности связаны с соответствующим цветом в K,

Также обратите внимание, что вы можете отбросить цвета и получить эквивалентный экземпляр GI :-)

enter image description here
Сокращение основных соответствует примеру в вашем комментарии

Марцио де Биаси
источник
Это выглядит многообещающе. Я проверю правильность позже.
Джон Д.
@ user17410: хорошо, дайте мне знать, если вам нужно больше разъяснений
Марцио Де Биаси,