Задачи для самостоятельного решения
Задача 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. Найти маршрут минимальной длины из вершины А в вершину В.
| 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.
§4 Задача Эйлера. Плоские, планарные и не планарные графы.
Формула Эйлера
Теория графов берет свое начало в 1736г. с решения знаменитым математиком Эйлером задачи о кенигсбергских мостах. Жителей Кенигсберга заинтересовал вопрос, могут ли они, начав путь с одного участка суши, обойти все семь мостов Кенигсберга, посетив каждый из этих мостов однажды, и и вернуться в пункт старта, не переплыв реки.
Эйлер переформировал задачу, изобразив участки суши в виде вершин, а мосты сделала ребрами графа. Напомним, что цепь в графе называется Эйлерова, если она содержит все ребра ровно 1 раз.
В графе с более чем одной вершиной есть эйлеров цикл тогда и только тогда, когда этот цикл включает все вершины графа.
Задача Эйлера. Обладает ли данный граф эйлеровым циклом или цепью?
Теорема Эйлера 1. Связный граф обладает эйлеровым циклом тогда и только тогда, когда все его вершины имеют четную степень.
2. Связный граф обладает эйлеровой цепью тогда и только тогда, когда ровно две его вершины имеют нечетную степень.
Граф называется плоским, если он расположен на плоскости так, что его ребра не пересекаются, кроме как в вершинах.
Граф называется планарным, если его можно расположить на плоскости так, что ребра не будут пересекаться.
Гранью плоского графа называется часть плоскости, ограниченная ребрами и не содержащая в себе ни ребер, ни вершин.
Так как планарный граф можно превратить в плоский, то понятие грани имеет смысл и для него.
Пусть В – вершина графа, Г – грань, Р – ребро. Тогда справедлива следующая формула (формула Эйлера): Г+В-Р=2.
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
Задача 1.
4 – бесконечная грань.
Проверим справедливость формулы на графе из примера 1. Так как В=4; Р=6, то граней должно быть Г=2+Р-В=2+6-4=4. Получили четыре грани, указанные на рис.
Задача 2. Определить наличие эйлерова цикла или эйлеровой цепи в графе:
Решение. Определим степень каждой из вершин графа. degv1=4; degv2=2; degv3=4; degv5=4; degv4=2. Так как все степени вершин графа четные, то по теореме Эйлера граф обладает эйлеровым циклом и как следствие не обладает эйлеровой цепью.
Задача 3. Выяснить, является ли граф плоским?
Решение. Так как этот граф можно распутать, т.е. преобразовать к виду
то он является планарным.
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
Задача 1. Считая данные графы планарными, выяснить, сколько граней получится после преобразования их в плоские:
1) 2)
Задача 2. Выяснить, являются ли данные графы плоскими (планарными).
1) 2)
Задача 3. Выяснить, обладают ли данные графы эйлеровой цепью.
1) 2)
3)
Раскраска графа. Хроматическое число
И характеристический индекс графа
Многие задачи о графах формулируются в терминах цветов, красок. Граф допускает правильную n-цветную раскраску вершин, если его вершины можно раскрасить n разными красками так, чтобы никакие две смежные вершины не имели m одинаковый цвет. минимальное число n, при котором граф G допускает n цветную раскраску вершин, называется хроматическим числом графа и обозначается hB.
Воспользуйтесь поиском по сайту:
