§ 27. Проблеми кліки, ізоморфної вкладності та ізоморфної підграфи

Нехай G і G '- два графи. Потрібно встановити, чи існує у графі G' підграф, ізоморфний графу G. Ця проблема ізоморфного підграфа є однією з найважчих алгоритмічних проблем теорії графів.

Інший варіант цієї проблеми — проблема ізоморфної вкладності: потрібно встановити, чи існує в графі G' породжена підграфа, ізоморфна графу G. Проблема ізоморфної підграфи перетвориться на проблему ізоморфізму графів, якщо додатково покласти \G\ = \G'\ і \EG\ = lEG'l. Аналогічна проблема ізоморфної вкладу перетвориться на проблему ізоморфізму, якщо покласти G = G '.

Проблему кліки часто розглядають у такому вигляді: задані граф G та натуральне число с; встановити, чи правильна нерівність фі (G)c

Очевидно, що проблема кліки є окремим випадком як проблеми ізоморфної підграфи, так і проблеми ізоморфної вкладності: потрібно встановити, чи є повний граф Кс підграфом графа G. Насправді ці три проблеми еквівалентні, тобто і проблема ізоморфної вкладності, і проблема ізоморфного подграфа можуть розглядатися, своєю чергою, як окремі випадки проблеми кліки. Цей факт першим довів Г. Візинг, використавши свою конструкцію модульного твору графів. Зручніше розглядати не сам твір Візінга, а додатковий до нього граф, саме ця конструкція названа нижче модульним проведенням.

Модульним твором G<>G' графів G і G' називається граф, який визначається наступними умовами:

V(G <> G'> = VGx VG' — декартовий добуток множин VG і VG'

вершини (і, і'] і (v, v') графа G<>G' суміжні тоді і тільки тоді, коли одночасно і  v, u'  v'

ізоморфної

uv EG, uv' EG', або uv EG, u'v' EG' рис. 27.1).

Теорема27.1(В. Г. Візинг, 1975).Граф G ізоморфно вкладається в граф G' тоді і тільки тоді, коли γ(G<>G')>=G.

► Покладемо G=n. Нехай у графі G' існує. народжений підграф G, ізоморфний графу G, VG->

VН - ізоморфізм графів, VG = , ψ (i) = vi = 1, n. З визначення модульного твору безпосередньо випливає, що вершини (1, v1), (2, v2), ., (n, vn) попарно суміжні в графі G<>G' і, отже, ψ (G<>G' )n.

Назад, нехай ψ (G<G')<>n, С — кліка в графі: G<>G', що містить рівно п верпшн. Тоді C = ((1, v1), 2, V2). (n,vn)>, причому вершини vi (i = l, n) n-парно різні. Покладемо H = G '(v1, v2. vn). Очевидно, що відповідність i-gt;vi є ізоморфізмом графів G і Н.

Зауважимо, що вершини (i, vi) з рівними однойменними координатами не суміжні, тому γ(G<>G')n.

Отже, нерівність із формулювання попередньої теореми насправді є рівністю.

Перейдемо до проблеми ізоморфної підграфії. Тут потрібно трохи змінити конструкцію модульного твору.

Великим модульним твором G<Gr графів G і G' назвемо граф, який визначається наступними умовами:

вершини (u, і') і (v, v') графа G<>G' суміжні тоді і тільки тоді, коли u v, і'v' або uv  EG, u'v EG', або uv EG.

Теорема27.2.У графі G є підграф, ізоморфний графу G, тоді і тільки тоді, коли γ (G <> G') = = G.

Доказ аналогічний доказу попередньої теореми.