3.2. Изоморфизм графов.

f: V_L V_R —перевод. f()= означает, что  переводится словом , f({₁,...,_k})={f(₁),...,f(_k)}.

Для изоморфизма графов G_R и G_L необходимо совпадение любых легко вычислимых характеристик.

1. Если граф G_L связный, то и граф G_R связный, число вершин и ребер в графах совпадает.

2. Убывающие вектора степеней вершин S(V_R) и S(V_L) совпадают.

3. V(k) - множество вершин графа G ={V, E}, имеющих степень k, |V| - мощность множества V, |V_R(k)|=|V_L(k)| и f(V_L(k))=V_R(k) для каждого k. В т.ч., если V_L(k)={} и V_R(k)={}, то f()=.

4. N(,k) — множество вершин,смежных с вершиной , и имеющих степень k, N() = U N(,k) f()=  S(N())=S(N()) и f(N(,k))=N(,k) при каждом k.

5. V_L(k)={,} и V_R(k)={,}  минимальное число ребер на пути из  в  d_L(,)=d_R(,).

6. f()= и f()=d_L(,)=d_R(,). Вершину  надо искать на расстоянии d(,) от вершины .

7. Число циклов длины k в обоих графах совпадает при всех k.

8. C(k, m)  множество вершин, входящих ровно в m циклов длины k,  |C_L(k,m)| = |C_R(k,m)| и f(C_L(k,m))= C_R(k,m) при всех k и m.

Свойства 3, 4, 6 и 8 позволяют частично формировать соответствие f.

№ 18. Лингвистическая задача, использующая изоморфизм графов.

Дано множество L слов языка суахили {kibuzi, mbuzi, mgeni, mtu, jitu, jito } и множество R их переводов на русский язык {великан, человек, большая река, козочка, коза, гость}. Выделить морфемы в словах из L и перевести их.

Решение. Все русские переводы можно представить в виде пар повторяющихся имен объектов (человек, коза, гость, река) и их размеров (большой, маленький, средний): великан = большой человек, козочка = маленькая коза, коза = средняя коза. Нарисуем граф G_R множества русских слов из R. Выделим повторяющиеся части в словах языка суахили: buzi повторяется с ki и m, с m еще встречаются tu и geni, с tu – ji, с ji – to. Естественно предположить, что это морфемы язы­ка суахили, имеющие самостоятельное значение. Нарисуем на них граф G_L.

Оба графа – деревья, содержащие по одной вершине степени 3: m=средний, причем все 3 поддерева являются цепочками из различного числа элементов. Значит, равны цепочки: geni=гость, buzi-ki=коза-маленький, tu-ji-to=человек-большой-река.

В неориентированных графах есть только ребра дерева и B-ребра. Стрелки удобно указывать на ребрах дерева T – в сторону предков, на B-ребрах – в сторону потомков.

Пусть вершины пронумерованы в порядке их раскрытия при поиске сначала вглубь, π(i) – непосредственный предок вершины i в дереве поиска T (0 для начальных вершин компонент связности), k=|π ^-1(0)| = число компонент. Тогда T={(i,π(i)) | π(i)>0}, |T|=|V|-k, E=T+B. Большинство ребер графа –B-ребра, каждое из них при добавлении в дерево T порождает T-цикл.

Пусть low(i) = min номер вершины, лежащей на T-циклах, содержащих i.

П оиск простейших узких мест графа за o(|e|).

Вершину графа называют точкой раздела, а ребро – мостом, если при их удалении число компонент графа возрастает.

Цикл по eT позволяет провести декомпозицию графа.

e=(i,j)E является мостом  eT & low(i)=i.

jV суть точка раздела  π(j)=0 & |π ^-1(j)|>1 или π(j)>0 & j=π(i) & low(i){i,j}.

low(i), проставленный в примере рядом с номером вершины, можно вычислить так:

for i=1 to n {low(i)=0;} for i=1 to n {if low(i)=0 then low(i)=i; for all jB_i {k=j;

while k>0 & low(k)=0 {low(k)=i; k=π(k)}}} Здесь B_i – список B-ребер, исходящих из i.

В примере получаем: мосты при i=5, 6, 11; точки раздела – 2,3,5,6,8 при i=3,5,6,7,11. Удалив все мосты, а затем все изолированные точки, выделим двусвязные компоненты.

Дальнейший поиск изоморфизма ведется на более мелких компонентах (аналог разложимых СП).