Аноним

Изоморфизм графов: различия между версиями

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
Строка 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]