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

Изоморфизм графов. Определение. Графы ( , ) и изоморфны

Определение. Графы (, ) и изоморфны, если существует взаимно однозначное отображение h: , сохраняющее смежность:

Изоморфизм графов есть отношение эквивалентности. Графы рассматриваются с точностью до изоморфизма, то есть рассматриваются классы эквивалентности по отношению изоморфизма.

Пример. Все приведенные графы являются изоморфными

Если графы являются изоморфными, то они имеют одинаковое количество вершин и ребер, а соответствующие вершины имеют одинаковую валентность. Обратное неверно.

39. Связанность графа. Маршрут, цепь, простая цепь, цикл. Лемма о цепи.

Определение. Маршрутом в графе называется последовательность вершин и ребер вида , в которой

Это определение подходит также для псевдо-, мульти-, и орграфов.

Для неориентированного графа достаточно указать только последовательность вершин либо только последовательность ребер.

Определение. Если все ребра в маршруте различны, то маршрут называется цепью. Если все вершины (а значит и ребра) в маршруте различны, то маршрут называется простой цепью. В цепи , вершины называются концами цепи. Говорят, что цепь с концами u, v соединяет вершины u, v (обозначается <u,v>).

Лемма. Если есть цепь, соединяющая вершины u, v, то есть и простая цепь, соединяющая вершины u, v.

Док-во. Индукция по длине цепи. Цепь, состоящая из одного ребра, является простой, следовательно, для нее утверждение верно. Пусть оно верно для цепей длины 1,2,…k-1. Рассмотрим цепь длины k. Пусть в цепи есть две одинаковые вершины, то есть цепь выглядит следующим образом . Выбросив участок , получим новую цепь , длина которой меньше k, и из которой, по индуктивному предположению, можно выделить простую цепь.

Определение. Если , цепь называется замкнутой.

Определение. Замкнутая цепь называется циклом, замкнутая простая цепь называется простым циклом. Для орграфов цепь называется путем, а цикл контуром.

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