Задача на нахождение количества дорог
Применение теории графов при решении задач.
Задачи на вычерчивание фигур одним росчерком.
Попытки нарисовать одним росчерком пера каждую из следующих фигур приводят к неодинаковым результатам.
|
| Рис. 13 |
Если нечетных точек в фигуре нет, то она всегда поддается вырисовыванию одним росчерком пера, безразлично, с какого места ни начинать черчение. Таковы фигуры 1 и 5.
Если в фигуре имеется только одна пара нечетных точек, то такую фигуру можно нарисовать одним росчерком, начав черчение в одной из нечетных точек (безразлично вкакой).
Легко сообразить, что вычерчивание должно оканчиваться во второй нечетной точке. Таковыфигуры 2, 3, 6. В фигуре 6, например, вычерчивание надо начинать либо из точки А, либо из точки В.
|
| Рис. 14 |
Если фигура имеет более одной пары нечетных точек, то она вовсе не может быть нарисована одним росчерком. Таковы фигуры 4 и 7, содержащие по две пары нечетных точек. Сказанного достаточно, чтобы безошибочно распознавать, какие фигуры нельзя нарисовать однимросчерком и какие можно, а также, с какой точки надо начинать вычерчивание.
Предлагаем начертить одним росчерком следующие фигуры. (рис 14)
Комбинаторные задачи.
Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес. При встрече все они поздоровались друг с другом за руку. Сколько мальчиков поехали за город, если всего было 10 рукопожатий?
|
|
|
Решение: Сделаем рисунок. Точки будут изображать мальчиков, а отрезки рукопожатия.
1) 
2) 
3) 
4) 
Рис. 15
Из рисунка видно, что на вокзале встретились 5 мальчиков.
Задача о нахождении кратчайшего пути в графе.
Во многих задачах, особенно решаемых на ЭВМ, графы удобно описывать матрицами.Матрица – это прямоугольная таблица чисел.
|
| a | b | c | d | ||
| a | 0 | 1 | 1 | 0 | ||
| b | 1 | 0 | 1 | 0 | ||
| c | 1 | 1 | 0 | 1 | ||
| d | 0 | 0 | 1 | 0 | ||
| Рис. 17 |
| |||||
Для хранения информации об узлах и связях графа можно использовать матрицу смежности. Единица на пересечении строки А и столбца В означает, что между узлами А и В есть связь.
|
| A | B | C | D | |
| A | 12 | 8 | 0 | ||
| B | 12 | 5 | 6 | ||
| C | 8 | 5 | 4 | ||
| D | 0 | 6 | 4 | ||
| Рис. 17 | |||||
Если в примере с дорогами между населенными пунктами нас интересуют еще и расстояния между поселками, каждой связи нужно сопоставить число – километры между населенными пунктами. В графе это число называется весом, а сам граф - взвешенным. Хранить информацию о таком графе необходимо в весовой матрице – в таблицу необходимо записывать не 1 или 0 (есть связь или нет связи), а вес ребра. Если связи между двумя узлами нет, на бумаге можно оставить ячейку таблицы пустой.
|
|
|
Широко распространены задачи нахождения кратчайшего пути. В таких задачах задается граф (сеть дорог) и начальная вершина (пункт отправления). Каждому ребру можно присвоить вес - длина дороги.
а) Между населёнными пунктами A, B, C, D, E, F построены дороги,
протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
1) 9 2) 10 3) 11 4) 12
Решение:Построим граф
| 
|
| Рис. 18 | Рис. 19 |
Найдем все пути из А в F
1) АBEF 2+7+2 = 11
2) ABCEF 2+1+4+2 = 9
3) ABCDEF 2+1+3+3+2 = 11
4) ACEF 4+4+2 = 10
5) ACDEF 4+3+3+2 = 12
Кратчайший путь ABCEF = 9Ответ: 1
б) Дана карта дорог между городами, где указана длина каждой дороги (данные не совпадают с настоящими). Найти: а) все кратчайшие пути из Санкт-Петербурга до Омска; б) все кратчайшие пути из Санкт-Петербургадо Магнитогорска.
Решение:
а) По данному графу можно рассмотреть все возможные варианты пути от Санкт-Петербурга до Омска, но таких вариантов получается очень много.
|
| Рис. 20 |
200+50+30+90+90=460 или
150+100+30+90+90=460
Т. е., кратчайшее рас-стояние от Санкт-Петербур-га до Омска равно 460.
|
|
|
б) 200+50+30+90=370.
Получаем, что кратчайшее расстояние от Санкт-Петербурга до Магнитогорска равно 370.
Ориентированные графы.
Существуют значительные классы практических задач, которые решить с помощью ранее рассмотренных типов графов невозможно.Так, например, схема дорог и площадей города изображается с помощью плоского графа. Но если нужно этой схемой воспользоваться с целью проезда по городу на автомашине, а движение на отдельных (или на всех) улицах одностороннее?
Граф, на рёбрах которого расставлены стрелки, называется ориентированным.
Задача на нахождение количества дорог
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.Сколько существует различных путей из города А в город К?
|
| Рис. 21 |
Решение 1:Перебираем все возможные пути из А в К, подсчитываем их количество
АБДИК, АБДК, АБВДК, АБВДИК, … и т.д.
Ответ: 13
Решение 2:
Используем метод динамического программирования, который позволяет получить решение, не прибегая к полному перебору вариантов.
Будем последовательно находить количество путей от А до Б, В, Г, и т.д.
|
| Рис. 22 |
В Б можно попасть одним способом, из А
|
|
|
В В можно попасть тремя способами, из А из Б и из Г
В Г можно попасть одним способом, из А (рис.22)
|
| Рис. 23 |
В Д можно попасть из Б и их В, количество путей равно 1+3=4
В Е можно попасть из Г, количество путей равно 1
В Ж можно попасть из В и из Е, количество путей равно 3+1=4 (рис. 23)
|
| Рис. 24 |
В И можно попасть из Д, количество путей равно 4
В К можно попасть из И, из Д, из Ж и из Е, количество путей равно 4+4+4+1 = 13 (рис. 24)
Ответ: 13
Дата добавления: 2018-06-27; просмотров: 2621; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!