Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Лекция 10. Изоморфизм графов. Операции над графами

Содержание лекции: изоморфизм графов; подграфы и части графов; операции над графами; примеры различных видов графов.

Цели лекции: выяснить, в чём заключается понятие изоморфизма для графов и как его установить; рассмотреть некоторые операции над графами и некоторые важные виды графов.

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

Один и тот же граф, как указывалось выше, можно изображать по - разному. Например, на рисунке 3.2.1 изображён один и тот же граф.

       
   
   
     


Рисунок 3.2.1

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

Определение. Два графа G1=(V1,E1) и G2=(V2,E2) изоморфны (обозначается G1~G2),если существует биекция φ:, сохраняющая смежность: e1=(u,v) e2=(φ(u),φ(v)).

Теорема.Изоморфизм графов есть отношение эквивалентности.

Действительно, изоморфизм обладает всеми свойствами отношения эквивалентности: а) рефлексивностью (G~G); б) симметричностью (G1~ G2 G2~G1); в) транзитивностью (G1~G2, G2~G3 G1~G3).

Графы рассматриваются с точностью до изоморфизма. Для того чтобы граф G1 был изоморфен графу G2 , необходимо и достаточно существование какого-либо взаимно однозначного соответствия между вершинами графов, а также между их рёбрами. Иногда в изоморфизме графов можно убедиться по их графическому представлению. Так, например, графы и на рисунке 3.2.2 изоморфны, т.к. достаточно поднять вершину 3 в графе до уровня вершин 2 и 4 и перевернуть , и будет видно, что и имеют одну форму.

Рисунок 3.2.2

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

Подграфы и части графов

Определение.Граф G1=(V1,E1) называется частью графа G=(V,E), если и E1E; подграфом графа G=(V,E) называется его часть G1=(V1,E1), которой принадлежат все рёбра (дуги) с концами в V1. На рисунке 3.11 изображены граф G, его подграф G1 и его часть G2 .

Рисунок 3.2.3

<== предыдущая лекция | следующая лекция ==>
| Лекция 10. Изоморфизм графов. Операции над графами

Дата добавления: 2014-01-15; Просмотров: 224; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ‚аш ip: 54.146.27.245
Генерация страницы за: 0.092 сек.