ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ. Задача 1. Найти маршрут минимальной длины от пункта 1 к пункту 1

Задача 1. Найти маршрут минимальной длины от пункта 1 к пункту 1.

 

7
2
7
7
2
5
5
5
5
2
3
3
3
4
4
4
4
7
6
6
6
8
8
8
9
10
11

 


Задача 2. Найти маршрут минимальной длины из вершины А в вершину В.

 

l di54bWxMj8FOwzAQRO9I/IO1SFwq6tQVaZTGqVAlLnAACh/gxG4SYa9D7Kbu37Oc6G1ndzT7ptol Z9lspjB4lLBaZsAMtl4P2En4+nx+KICFqFAr69FIuJgAu/r2plKl9mf8MPMhdoxCMJRKQh/jWHIe 2t44FZZ+NEi3o5+ciiSnjutJnSncWS6yLOdODUgfejWafW/a78PJSXh5e19cRMoXP5vHZp/mwqbX YKW8v0tPW2DRpPhvhj98QoeamBp/Qh2YJb0pCD3SsF4BI4PIcwGsoUUu1sDril9XqH8BAAD//wMA UEsBAi0AFAAGAAgAAAAhALaDOJL+AAAA4QEAABMAAAAAAAAAAAAAAAAAAAAAAFtDb250ZW50X1R5 cGVzXS54bWxQSwECLQAUAAYACAAAACEAOP0h/9YAAACUAQAACwAAAAAAAAAAAAAAAAAvAQAAX3Jl bHMvLnJlbHNQSwECLQAUAAYACAAAACEAYkb2BvIBAADrAwAADgAAAAAAAAAAAAAAAAAuAgAAZHJz L2Uyb0RvYy54bWxQSwECLQAUAAYACAAAACEA6lmUQN8AAAAKAQAADwAAAAAAAAAAAAAAAABMBAAA ZHJzL2Rvd25yZXYueG1sUEsFBgAAAAAEAAQA8wAAAFgFAAAAAA== " strokecolor="black [3040]"/>2 LnhtbEyPzU6EQBCE7ya+w6RNvGx2B1EQkWZjNvGiB3X1AQZogTg/yMyys29ve9JjpSpVX1XbaLRY aPajswhXmwQE2dZ1o+0RPt4f1wUIH5TtlHaWEE7kYVufn1Wq7NzRvtGyD73gEutLhTCEMJVS+nYg o/zGTWTZ+3SzUYHl3MtuVkcuN1qmSZJLo0bLC4OaaDdQ+7U/GISnl9fVKY356vs2a3ZxKXR89hrx 8iI+3IMIFMNfGH7xGR1qZmrcwXZeaITsJk05irC+BsF+luX8rUEoijuQdSX/H6h/AAAA//8DAFBL AQItABQABgAIAAAAIQC2gziS/gAAAOEBAAATAAAAAAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBl c10ueG1sUEsBAi0AFAAGAAgAAAAhADj9If/WAAAAlAEAAAsAAAAAAAAAAAAAAAAALwEAAF9yZWxz Ly5yZWxzUEsBAi0AFAAGAAgAAAAhAOQ4LsnxAQAA6gMAAA4AAAAAAAAAAAAAAAAALgIAAGRycy9l Mm9Eb2MueG1sUEsBAi0AFAAGAAgAAAAhADMRRSTeAAAACAEAAA8AAAAAAAAAAAAAAAAASwQAAGRy cy9kb3ducmV2LnhtbFBLBQYAAAAABAAEAPMAAABWBQAAAAA= " strokecolor="black [3040]"/>

4
А
В
1
2
3
5

 

 


Задача 3. Найти маршрут минимальной длины от пункта 1 к пункту 10.

 

3
8
1
2
6
5
4
7
9
10
4
4
4
1
1
1
1
3
3
3
2
2
2
2
5
6
9

 

 


Задача 4. Найти кратчайший путь из вершины v1 в вершину v13.

v13
v12
v11
v10
v9
v8
v7
v5
v6
v4
v3
v2
v1

 

 


§4 Задача Эйлера. Плоские, планарные и не планарные графы.

Формула Эйлера

 

Теория графов берет свое начало в 1736г. с решения знаменитым математиком Эйлером задачи о кенигсбергских мостах. Жителей Кенигсберга заинтересовал вопрос, могут ли они, начав путь с одного участка суши, обойти все семь мостов Кенигсберга, посетив каждый из этих мостов однажды, и и вернуться в пункт старта, не переплыв реки.

Эйлер переформировал задачу, изобразив участки суши в виде вершин, а мосты сделала ребрами графа. Напомним, что цепь в графе называется Эйлерова, если она содержит все ребра ровно 1 раз.

В графе с более чем одной вершиной есть эйлеров цикл тогда и только тогда, когда этот цикл включает все вершины графа.

Задача Эйлера. Обладает ли данный граф эйлеровым циклом или цепью?

Теорема Эйлера 1. Связный граф обладает эйлеровым циклом тогда и только тогда, когда все его вершины имеют четную степень.

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

Граф называется плоским, если он расположен на плоскости так, что его ребра не пересекаются, кроме как в вершинах.

Граф называется планарным, если его можно расположить на плоскости так, что ребра не будут пересекаться.

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

Так как планарный граф можно превратить в плоский, то понятие грани имеет смысл и для него.

Пусть В – вершина графа, Г – грань, Р – ребро. Тогда справедлива следующая формула (формула Эйлера): Г+В-Р=2.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 1.

 


4 – бесконечная грань.

Проверим справедливость формулы на графе из примера 1. Так как В=4; Р=6, то граней должно быть Г=2+Р-В=2+6-4=4. Получили четыре грани, указанные на рис.

Задача 2. Определить наличие эйлерова цикла или эйлеровой цепи в графе:

 

v4
v1
v2
v3
v5

 


 

Решение. Определим степень каждой из вершин графа. degv1=4; degv2=2; degv3=4; degv5=4; degv4=2. Так как все степени вершин графа четные, то по теореме Эйлера граф обладает эйлеровым циклом и как следствие не обладает эйлеровой цепью.

 

Задача 3. Выяснить, является ли граф плоским?

 

 

 

 


Решение. Так как этот граф можно распутать, т.е. преобразовать к виду

 

 

 

 


то он является планарным.