Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Изоморфизм графов. Теорема об изоморфизме графов



Пусть даны графы: и .

Взаимно-однозначное соответствие называется изоморфизмом, если оно сохраняет отношение смежности:

Матрица взаимно-однозначного соответствия ( ) обозначается .

, где вершина из , вершина из .

Теорема об изоморфизме графов.

Пусть даны орграфы: и .

-матрица смежности , -матрица смежности .

Взаимно-однозначное соответствие является изоморфизмом графов , когда , где - матрица .

Доказательство.

Надо доказать: - это означает, что:

(*)

Необходимость.

Возьмем произвольную вершину

Поэтому .

Возьмем произвольную вершину

Поэтому .

Достаточность. Пусть .

Докажем .

Возьмем произвольную дугу 1-ого орграфа

Возьмем произвольную дугу 2-ого орграфа

.

Проверка на изоморфизм 2-х графов по их матрицам смежности.

1)Выписывается матрица предполагаемого изоморфизма , как матрица с неопределенными коэффициентами. .

2)Составляем матричное уравнение . Решаем систему, находим .

3)Если в каждом столбце и строке ровно одна 1, то изоморфизм есть, иначе – нет.

4)Если вершина может перейти в вершину (равные степени исхода и захода) то в матрице пишем 1(если из вершины 1-ого орграфа можно лишь единожды попасть в вершину 2-го орграфа, а если не единожды – пишем: , где – номер столбца, – номер строки), иначе – 0.

Часть графа, подграфы. Путь, цикл, цепь, длина пути и расстояние между вершинами. Достаточное условие связности нечетных вершин.

Часть орграфа - , где .

Подграф – часть орграфа.

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

Путь –последовательность ребер, в которой 2 соседних ребра имеют общую вершину и ни одно ребро не встречается более 1 раза.

Простой путь – путь, котором каждая вершина принадлежит не более, чем 2 ребрам.

Циклический путь – путь, в котором начальная вершина совпадает с конечной.

Цикл – циклический простой путь.

Цепь - нециклический простой путь.

Длина пути – кол–во ребер, входящих в путь.

Вершины связаны, если существует путь, проходящий через них. Если вершины связаны, то найдется цепь.

По определению считают, что каждая вершина связана сама с собой, тогда отношение связности – это отношение эквивалентности. Классы отношения связности называются компонентами связности (компонентами).

Теорема. Достаточное условие связности 2 нечетных вершин.



Если 2 нечетные вершины и в графе – единственные нечетные вершины, то они связаны в графе.

Доказательство.

От противного: пусть они лежат в разных компонентах связности, тогда в каждом подграфе (компоненте связности) есть лишь одна единственная нечетная вершина – противоречие, так как по лемме о рукопожатии: число нечетных вершин четно.

Достаточное условие связности графа.

Граф с универсальным отношением связности называется связным. Любые 2 вершины соединены ребром. Каждый граф является объединением своих компонентов связности.

Связный граф – граф, в котором любые 2 вершины соединены цепью.


Эта страница нарушает авторские права

allrefrs.ru - 2018 год. Все права принадлежат их авторам!