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

Изоморфизм графов. Один и тот же граф геометрически можно изобразить различными способами

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

 

Один и тот же граф геометрически можно изобразить различными способами. Так, на рис.2.9 приведены изображения одного и того же графа. Такие графы называют изоморфными.

Рис. 2.9.

В связи с этим возникает следующая задача. Если имеется два изображения графов, то как узнать, не представляют ли они собой один и тот же граф? Ответить на этот вопрос сразу достаточно трудно. На практике обычно предварительно определяют некоторые параметры обоих графов. Такими параметрами могут быть число вершин, число ребер, число компонент связности, последовательность степеней вершин в убывающем порядке. Если какие-то из этих параметров у двух графов различны, то эти графы различны. Однако, если все параметры у двух графов совпали, то это не гарантирует, что графы изоморфны. Например, на рис. 2.10. приведены два графа, у которых все параметры совпадают, и тем не менее они различны.

Рис. 2.10.

 

 


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.004 сек.)