Летние международные олимпиады для 1-11 классов Участвовать→
Конкурс разработок «Пять с плюсом» июнь 2021
Добавляйте свои материалы в библиотеку и получайте ценные подарки
Конкурс проводится с 1 июня по 30 июня

Конспект лекции по теме "Двудольные, изоморфные, эйлеровы и гамильтоновы графы"

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

Тема: Двудольные, изоморфные, эйлеровы и гамильтоновы графы

 

Опр.: Говорят, что два графа g1(v1,1) и g2(v2,2)изоморфны (обозначается gg2), если существует биекция h : v1 v2 , сохраняющая смежность:

e1 (u,)1 e2 (h(u),h())2

1(u),h1())1   e2 (u,)2 e1 (h

Опр.: Числовая характеристика, одинаковая для всех изоморфных графов называется инвариантом графа. Так p(g) и q(g) – инварианты графа g.

Неизвестно никакого набора инвариантов, определяющих граф с точностью до изоморфизма. Опр.: Двудольный граф (или биграф, или чётный граф) – это граф g(v,), такой что множество V разбито на два непересекающихся множества v1 и v2 (v1 2 v&1 2 ), причѐм всякое ребро из инцидентно вершине из 1 и вершине из 2 (т.е. соединяет вершину из 1с вершиной из 2).

Опр.: Множества  1 и 2 называются долями двудольного графа.

Опр.: Если двудольный граф содержит все рѐбра, соединяющие множества 1 и 2, то он называется полным двудольным графом.

Теорема: Граф является двудольным тогда и только тогда, когда все его простые циклы имеют чѐтную длину.

imageimageimageа) в)

б)

г) д) е)

 

Опр.: Эйлеровым путём в графе называется путь, содержащий все рѐбра графа в точности по одному разу.

Опр.: Эйлеровым циклом в графе называется цикл, содержащий все рѐбра графа в точности по одному разу.

Опр.: Эйлеров граф – граф, обладающий эйлеровым циклом.

Опр.: Гамильтоновым путём называется путь, содержащий все вершины графа в точности по одному разу.

Опр.: Гамильтоновым циклом в графе называется цикл, содержащий все вершины графа в точности по одному разу.

Опр.: Гамильтонов граф – граф, обладающий гамильтоновым циклом.

Задача: Нарисуйте граф с 8-ю вершинами, который имеет эйлеров цикл и эйлеров путь, не имеет эйлеров цикл и эйлеров путь, имеет простой путь, содержащий все рѐбра графа.

imageа, б                                                в, г     image               д        image

 

Теорема 1: Если граф обладает эйлеровым циклом, то он связный и все его вершины чѐтные. Теорема 2: Если граф обладает эйлеровым путѐм с концами А и В (А не совпадает с В), то граф связный и А и В единственные нечѐтные его вершины.

Теорема 3: Если связный граф имеет 2k-нечѐтных вершин, то найдѐтся семейство из k-путей, которые в совокупности содержат все рѐбра графа в точности по одному разу.

Теорема 4: Если граф связный, то можно построить циклический маршрут, содержащий все рѐбра графа в точности 2 раза (по одному в каждом направлении).

Доказательство Тарри: Теорема была доказана по правилу Тарри

imageB                                                                                             image

A2; 23; 32; 21; 15; 54; 4А; А1; 12; 2А;А4; 45;

                                                                                                                   51; 1А                                                                      

Теорема 5: Конечный неориентированный граф g тогда и только тогда эйлеров, когда он связный и степени всех его вершин чѐтные.

Замечание: В графе задачи о кѐнигсбергских мостах все вершины имеют нечѐтную степень. Следовательно, еѐ решение невозможно.

Теорема 6: Для того, чтобы связный граф g содержал эйлерову цепь, необходимо и достаточно, чтобы он имел ровно две вершины нечѐтной степени.

Опр.: Граф, содержащий эйлеров путь, называется полуэйлеровым.

Замечание: Эйлеров цикл содержит не только все рѐбра (по одному разу), но и все вершины графа (возможно по несколько раз). Ясно, что эйлеровым может быть только связный граф.

Теорема 7: Если граф g связный и нетривиальный, то следующие утверждения эквивалентны:

1.      g – эйлеров граф.

2.      Каждая вершина g имеет чѐтную степень.

3.      Множество рѐбер g можно разбить на простые циклы.

Алгоритм нахождения эйлерова цикла в эйлеровом графе Принцип действия этого алгоритма заключается в следующем.

Начиная с произвольной вершины, строим путь, удаляя рѐбра и запоминая вершины в стеке, до тех пор, пока множество смежности очередной вершины не окажется пустым, что означает, что путь удлинить нельзя. Заметим, что при этом мы с необходимостью придѐм в ту вершину, с которой начали. В противном случае это означало бы, что вершина имеет нечѐтную степень, что невозможно по условию. Таким образом, из графа были удалены рѐбра цикла, а вершины цикла были сохранены в стеке S. Заметим, что при этом степени всех вершин остались чѐтными. Далее вершина выводится в качестве первой вершины эйлерова цикла, а процесс продолжается, начиная с вершины, стоящей на вершине стека.

Замечание: Гамильтонов цикл не обязательно содержит все рѐбра графа. Ясно, что гамильтоновым может быть только связный граф. 

Замечание: Любой граф g можно превратить в гамильтонов, добавив достаточное количество вершин.

Теорема 8: Если граф g обладает гамильтоновым циклом, то в нѐм отсутствуют точки сочленения. Замечание: Простейшим достаточным условием существования гамильтоновых путей и циклов является его полнота, т.е. если граф полный, то в нѐм существуют гамильтоновы циклы, а две его вершины могут быть соединены гамильтоновым путѐм.

 

Информация о публикации
Загружено: 26 марта
Просмотров: 75
Скачиваний: 1
Фоминых Ирина Владимировна
Прочее, СУЗ, Уроки

Проверьте знания своих учеников интересными заданиями

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

Скачать материал