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

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

Определение. Графы и называют изоморфными (обозначение: G ₁ ~G ₂), если между множествами вершин V ₁, V ₂ можно установить взаимно однозначное соответствие (биекцию), сохраняющее смежность. Вершины v ₁, v ₂ в графе G смежны тогда и только тогда, когда смежны соответствующие им вершины v ₁¢, v ₂¢ в графе G ¢.

Рис.8

Фактически, изоморфные графы – это один и тот же граф.

На рис. 9 показаны три изоморфных графа – граф K _3,3.

Рис. 9

У изоморфных графов одинаковое число вершин и ребер. Но этого недостаточно для изоморфизма. На рис. 10 показаны неизоморфные графы, у которых совпадают числа вершин и ребер, а также одинаковое число вершин одной и той же степени. Но графы различны: в графе G ₂ вершины степени 3 соединены ребрами в «четырехугольник». В графе G ₁ такого «четырехугольника» нет.

Рис. 10

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