АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Изоморфизм графов. Пусть и - графы и - взаимно-однозначное соответствие

Читайте также:
  1. Билет 2. Изоморфизм линейных пространств.
  2. Виды и способы задания графов
  3. Гомоморфизм и Изоморфизм
  4. Изоморфизм векторных пространств
  5. Изоморфизм векторных пространств
  6. Изоморфизм графов
  7. Изоморфизм графов
  8. История теории графов
  9. Контррельефы Владимира Евграфовича Татлина (1885-1953).
  10. Лицевая панель осциллографов С1-93 и С1-83
  11. Матрица графов

 

Пусть и - графы и - взаимно-однозначное соответствие. (Заметим, что ). Отображение называется изоморфизмом графов и , если для любых вершин и графа их образы и смежные в графе тогда и только тогда, когда и смежные в . Если такое отображение существует, то графы и называются изоморфными.

Очевидно, что отношение изоморфизма графов является отношением эквивалентности.

Другими словами: графы и изоморфны, если существует такое взаимно-однозначное соответствие между множеством вершин и , что любые две вершины одного графа смежные тогда и только тогда, когда соответствующие им вершины другого графа также смежны. На рис. 2.8. приведены изоморфные графы: и ; и .

 

Рис. 2.8

Теорема. Графы изоморфны тогда и только тогда, когда их матрицы смежностей можно получить одну из другой одинаковыми перестановками строк и столбцов.

Доказательство.

Пусть заданы два изоморфных графа. и . Перенумеруем вершины графов и целыми числами от 0 до . . и - матрицы смежностей графов и соответственно. Если , то все доказано. В противном случае графы и отличаются лишь нумерацией вершин. Значит, существует такая подстановка на множестве вершин , которая сохраняет смежность, т.е. если , то . Тогда получаем , где . Теорема доказана.

Следует заметить, что теорема об изоморфизме графов остается справедливой, если рассматривать не матрицы смежностей, а матрицы Кирхгофа.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)