Графы. Теорема Эйлера

            indeg(c)=2              outdeg(c)=2

            indeg(d)=2              outdeg(d)=2

            indeg(e)=2              outdeg(e)=2

Следовательно, по теореме 5, граф имеет эйлеров цикл.

в)   Граф связный, найдём степени вершин:

            indeg(a)=2              outdeg(a)=2

            indeg(b)=1              outdeg(b)=1

            indeg(c)=3              outdeg(c)=1

Условия теоремы 5 не выполняются, значит, граф не имеет эйлерова цикла.

г)  )  Граф связный, найдём степени вершин:

            indeg(a)=2              outdeg(a)=1

Следовательно, т.к. условия теоремы 5 не выполняются то, граф не имеет эйлерова цикла.

 

8. Какие из следующих ориентированных  графов имеют эйлеровы циклы? [1]

 

Решение:

а)  Граф связный, найдём степени вершин:

            indeg(a)=1              outdeg(a)=1

            indeg(b)=5              outdeg(b)=1

Т.к. второе условие теоремы 5 не выполняется, значит, граф не имеет эйлерова цикла.

 

б)  Граф не связный, то есть первое условие теоремы 5 не выполняется. Значит, граф не имеет эйлерова цикла.

в)  Граф связный, найдём степени вершин:

            indeg(a)=2              outdeg(a)=1

Второе условие теоремы 5 не выполняется, значит, граф не имеет эйлерова цикла.

г)  Граф связный, найдём степени вершин:

            indeg(a)=2              outdeg(a)=2

            indeg(b)=3             outdeg(b)=1

Граф не имеет эйлерова цикла, т.к. не выполняется  второе условие    теоремы 5.

 

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

                                 

1		2
3	4			5	6
7	8			9	10
11	12		13	14	15
16	17		18	19
20	21

Построим граф, вершинами которого являются комнаты подземелья, а рёбрами – двери. Затем найдём такой путь, чтобы пройти по всем  рёбрам (через все двери) в точности по одному разу.

 

 

 

 

Данный граф имеет эйлеров путь, так как только две вершины имеют нечётную степень, это вершины 6 и 18. Значит, вход и выход могут быть только в вершинах 6 и 18.

Так как  комната 6 является крайней, то в ней будет вход, значит, последней комнатой будет 18-ая, следовательно сокровища скрыты в этой комнате.

 

Заключение

В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Теория графов рассматривается как одна из ветвей топологии; непосредственное отношение она имеет также к алгебре и к теории чисел. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач, нахождении максимального потока в сети, кратчайшего расстояния, максимального паросочетания, проверки планарности графа и др. А благодаря возможностям различных математических пакетов, графы имеют все большую возможность использования в жизни и науки.

 

Литература

1. Басакер Р., Саати Т., Конечные графы и сети, М., Наука, 1974.

2. Белов В.В., Воробьев Е.М., Шаталов В.Е., Теория графов, М., Наука,1976.

3. Берж К., Теория графов и ее применения, М., ИЛ,1962.

4. Березина Л.Ю., Графы и их применение, М., Просвещение, 1976.

5. Болтянский В.Г., Наглядная топология, М., Просвещение, 1982.

6. Оре О., Графы и их применение, Новокузнецкий Физико-математический институт, 2000.

7. Оре О., Теория графов, М., Наука, 1968.

8. Прохоров Г.В., Леденев М.А., Колбеев В.В., Пакет символьных вычислений Maple .

9. Татт У., Теория графов, М., Наука, 1977.

10. Уилсон Р., Введение в теорию графов, М., Мир, 1977

11. Харари Ф. Теория графов. – М.: Мир, 1973.