АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

ОПРЕДЕЛЕНИЕ. Графы G1=(V1,U1) и G2 =(V2, U2) называются изоморфными, если существует такое биективное отображение h: V1®V2

Прочитайте:
  1. I. Доход от прироста стоимости при реализации ценных бумаг (инвестор самостоятельно несет ответственность за определение и выплату налогов в бюджет Республики Казахстан)
  2. I. ОПРЕДЕЛЕНИЕ ОСНОВНЫХ ТЕРМИНОВ
  3. I. Определение СКФ по клиренсу креатинина
  4. II. Договорные отношения могущие влиять на определение управомоченного лица
  5. А. Определение группы крови стандартными изогемагглютинирующими сыворотками.
  6. Аборты. Определение, классифиация, диагностика и профилактика.
  7. Ангины: 1) определение, этиология и патогенез 2) классификация 3) патологическая анатомия и дифференциальная диагностика различных форм 4) местные осложнения 5) общие осложнения
  8. Антигены. Определение. Свойства. Виды.
  9. Асептика, антисептика. Определение понятий. Способы проведения.
  10. Б. Определение группы крови с помощью цоликлонов (моноклональных антител)

Графы G 1 = (V 1, U 1) и G 2 = (V 2, U 2) называются изоморфными, если существует такое биективное отображение h: V 1® V 2, для которого ((a, b)Î U 1 Û (h (a), h (b))Î U 2).

 

Нетрудно проверить, что для графов G 1 и G 2, изображенных на рис. 5.4, такое биективное отображение существует. Например, это может быть отображение, которое представлено на следующей диаграмме:

a 1

b 2

c 3

d 4

E 5

F 6

g 7

h 8

Для доказательства изоморфизма произвольных двух графов G 1 и G 2 на основе определения изоморфизма необходимо построить подходящее биективное отображение. Простейший способ поиска такого отображения состоит в последовательном построении всех возможных биективных отображений множества вершин одного графа на множество вершин другого графа. Для каждого такого отображения проверяется выполнение условий изоморфизма.

При этом графы являются неизоморфными, если ни одно проверяемое отображение не устанавливает изоморфизм между G 1 и G 2.

Из определения изоморфизма следует, что изоморфные графы имеют общие свойства, в которых не используется именование вершин. Например, если графы G 1 и G 2 изоморфные и h – подходящая биекция вершин этих графов, то ребра (a, b) и (h (a), h (b)) одновременно являются ориентированными или неориентированными.

 

Аналогично, если в одном графе имеется вершина степени 5, то и в другом графе должна иметься вершина с таким же свойством.

Поэтому неизоморфны графы, изображенные на рис. 5.5:

       
   
 
 

 


 

G 1 G 2

 

Рис. 5.5

 

Действительно, в G 2 имеется вершина степени 4, а в G 1 нет вершин, с таким свойством.

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

 

ПЛАНАРНОСТЬ ГРАФОВ

 

Рассмотрим вопрос о возможности геометрической реализации произвольных графов на плоскости. Поскольку ориентированность ребер не влияет на возможность геометрической реализации графов, то без ограничения общности можно рассматривать только неориентированные графы. Отметим также что, что на планарность графа не влияет наличие петель.

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

 

Дата добавления: 2015-09-27 | Просмотры: 420 | Нарушение авторских прав

При использовании материала ссылка на сайт medlec.org обязательна! (0.003 сек.)