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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Изоморфизм  графов''' ([[Graph isomorphism]]) ---
'''Изоморфизм  графов''' ([[Graph isomorphism]])
{биекция <math>\varphi: \; V(G) \rightarrow V(H)</math> множества вершин графа
биекция <math>\varphi: \; V(G) \rightarrow V(H)</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>.
<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-Полная задача|''<math>\mathcal NP </math>-Полной'']].
Отношение изоморфизма графов является [[Отношение эквивалентности|отношением эквивалентности]], т.е. оно симметрично, транзитивно и рефлексивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса изоморфны, а графы из разных классов не изоморфны. Задача установления изоморфизма графов является [[NP-Полная задача|''<math>\mathcal NP </math>-Полной'']].


==Литература==
==Литература==
[Лекции],  
* Зыков А.А. Теория конечных графов. — Новосибирск: Наука. Сиб. отд-ние, 1969.


[Зыков/69]
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

Текущая версия от 11:54, 21 февраля 2011

Изоморфизм графов (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]-Полной.

Литература

  • Зыков А.А. Теория конечных графов. — Новосибирск: Наука. Сиб. отд-ние, 1969.
  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.