Изоморфизм графов: различия между версиями
KVN (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 3: | Строка 3: | ||
<math>G</math> на множество вершин графа <math>H</math>, сохраняющая [[Смежность |''отношение смежности'']]; другими словами, для любых вершин <math>u</math> и <math>v</math> графа <math>G</math> их образы <math>\varphi(u)</math> и <math>\varphi(v)</math> [[Смежные вершины |смежны]] в <math>H</math> тогда и только тогда, когда <math>u</math> и <math>v</math> смежны в <math>G</math>. | <math>G</math> на множество вершин графа <math>H</math>, сохраняющая [[Смежность |''отношение смежности'']]; другими словами, для любых вершин <math>u</math> и <math>v</math> графа <math>G</math> их образы <math>\varphi(u)</math> и <math>\varphi(v)</math> [[Смежные вершины |смежны]] в <math>H</math> тогда и только тогда, когда <math>u</math> и <math>v</math> смежны в <math>G</math>. | ||
Отношение изоморфизма графов является [[Отношение эквивалентности|отношением эквивалентности]], т.е. оно симметрично, транзитивно и рефлексивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса изоморфны, а графы из разных классов не изоморфны. Задача установления изоморфизма графов является [[NP-Полная задача|''NP-Полной'']]. | Отношение изоморфизма графов является [[Отношение эквивалентности|отношением эквивалентности]], т.е. оно симметрично, транзитивно и рефлексивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса изоморфны, а графы из разных классов не изоморфны. Задача установления изоморфизма графов является [[NP-Полная задача|''<math>\mathcal NP </math>-Полной'']]. | ||
==Литература== | ==Литература== | ||
[Лекции], | [Лекции], | ||
[Зыков/69] | [Зыков/69] | ||
Версия от 12:25, 15 октября 2009
Изоморфизм графов (Graph isomorphism) --- {биекция [math]\displaystyle{ \varphi: \; V(G) \rightarrow V(H) }[/math] множества вершин графа [math]\displaystyle{ G }[/math] на множество вершин графа [math]\displaystyle{ H }[/math], сохраняющая отношение смежности; другими словами, для любых вершин [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math] графа [math]\displaystyle{ G }[/math] их образы [math]\displaystyle{ \varphi(u) }[/math] и [math]\displaystyle{ \varphi(v) }[/math] смежны в [math]\displaystyle{ H }[/math] тогда и только тогда, когда [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math] смежны в [math]\displaystyle{ G }[/math].
Отношение изоморфизма графов является отношением эквивалентности, т.е. оно симметрично, транзитивно и рефлексивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса изоморфны, а графы из разных классов не изоморфны. Задача установления изоморфизма графов является [math]\displaystyle{ \mathcal NP }[/math]-Полной.
Литература
[Лекции], [Зыков/69]