Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 24

Нарисуем эти деревья. Четвертому вектору соответствуют два неизоморфных дерева!!! В одном из них соседями единственной вершины степени 3 являются 2 висячих вершины и одна со степенью 2, а во второй – наоборот.

3.2. ИЗОМОРФИЗМ ГРАФОВ.

В качестве необходимого условия изоморфизма графов подойдет совпадение любых легко считаемых характеристик: мин.разрез, наличие цикла, вектор степеней вершин и т.д. После этого задача установления изоморфизма разбивается на более мелкие задачи. Аналог разложимых СП.

V(k) — множество вершин графа G ={V, E}, имеющих степень k, |V| ¾ мощность множества V,

S(V) — убывающий вектор степеней вершин из множества V,

N(a) — множество вершин, смежных с вершиной a,

N(a,k) — множество вершин из N(a), имеющих степень k,

C(k, m) ¾ множество вершин, входящих ровно в m циклов длины k,

d(a,g) ¾  минимальноечисло ребер на пути из a  в g ,

f: V_L® V_R —перевод. f(a)=b означает, что a переводится словом b, f({a₁,...,a_k})={f(a₁),...,f(a_k)}.

Выделим часть необходимых условий изоморфизма графов G_R и G_L.

1)  Число вершин и ребер в графах G_R и G_L совпадает.

2)  Если граф G_L связный, то и граф G_R связный.

3)  Вектора степеней вершин S(V_R) и S(V_L) совпадают.

4)  |V_R(k)|=|V_L(k)| и f(V_L(k))=V_R(k) для каждого k. В т.ч., если V_L(k)={a} и V_R(k)={b}, то f(b)=a.

5)  f(a)=b Þ S(N(a))=S(N(b)) и f(N(a,k))=N(b,k) при каждом k.

6)  V_L(k)={a,g} и V_R(k)={b,d} Þ d_L(a,g)=d_R(b,d).

7)  f(a)=b и f(g)=dÞd_L(a,g)=d_R(b,d). Вершину d надо искать на расстоянии d(a,g) от вершины b.

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

9)  |C_L(k,m)| = |C_R(k,m)| и f(C_L(k,m)= C_R(k,m) при всех k и m.

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

Выделение двусвязных компонент в графе за O(|E|). Классификация ребер.

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

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

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

Нарисуем граф множества морфем языка суахили.

В каждом слове языка суахили одна морфема принадлежит трехэлементному множеству {ji, m, ki}, а вторая четырехэлементному множеству {to, tu, geni, buzi}. Þ {ji, m, ki} – размеры, а {to, tu, geni, buzi} - объекты.

Размеры различаются по числу повторений, значит
ki = маленький, m = средний, а ji = большой. Размер ki встречается только в слове kibuzi, а маленькой в русском тексте бывает только коза, значит buzi = коза. Средний размер m встречается кроме козы в повторяющемся 1 раз слове geni=гость и 2 раза слове tu=человек. В графах осталось по одному неопознанному слову. Значит to=река.

Решить задачу можно проще. Оба графа – деревья, содержащие по одной вершине степени 3: m=средний, причем все 3 поддерева являются цепочками из различного числа элементов.

3.3. ОСТОВНЫЕ ДЕРЕВЬЯ.