Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Изоморфизм графов

Читайте также:
  1. I.Способы задания графов. Степени вершин, матрицы инцидентности и смежности.
  2. ВАЖНЕЙШИЕ КЛАССЫ ГРАФОВ
  3. Возникновение и особенности развития библиографоведения в дореволюционной России
  4. Дополнительные характеристики графов
  5. Дополнительные характеристики графов
  6. История теории графов

Говорят, что два графа G1(V1,E1) и G2(V2,E2) изоморфны (обозначается G1~ G2), если существует биекция h: V1 V2, сохраняющая смежность.

Графы рассматриваются с точностью до изоморфизма.

Пример

Три внешне различные диаграммы, приведенные на рис. 3.6, являются диаграм­мами одного и того же графа К3,3.

Рис. 3.6. Диаграммы изоморфных графов

Числовая характеристика, одинаковая для всех изоморфных графов, называется инвариантом графа. Так, p(G) и q(G) - инварианты графа G.

Не известно никакого набора инвариантов, определяющих граф с точностью до изоморфизма.

Рис. 3.8. Диаграммы неизоморфных графов с совпадающими инвариантами

2.2.Представление графов в ЭВМ

Следует подчеркнуть, что конструирование структур данных для пред­ставления в программе объектов математической модели - это основа искус­ства практического программирования. Мы приводим два различных базовых представления графов.

Выбор наилучшего представления определяется требова­ниями конкретной задачи. Более того, при решении конкретных задач исполь­зуются, как правило, некоторые комбинации или модификации указанных пред­ставлений, общее число которых необозримо. Но все они, так или иначе, основаны на тех базовых идеях, которые описаны в этом разделе.


Дата добавления: 2015-10-13; просмотров: 102 | Нарушение авторских прав


Читайте в этой же книге: История теории графов | Определения | Гамильтоновы графы |
<== предыдущая страница | следующая страница ==>
Смежность и инцидентность| Матрица инциденций

mybiblioteka.su - 2015-2024 год. (0.006 сек.)