Графы. Применение графов к решению задач

Страница 1

Графы

– это рисунки, которые состоят из точек и линий, соединяющих эти точки.

Каждая пара точек в графе может быть соединена линиями

. Линия указывает на связь между двумя точками

. Точки называются вершинами графа

, а линии - рёбрами.

С какими графами вы встречаетесь повседневной в жизни? (схемы авиалиний, которые часто вывешивается в аэропортах, схемы метро, а на географических картах – изображение железных дорог). С помощью графов изображаются схемы дорог, газопроводов, тепло и электросетей.

Особым видом графа является дерево. Дерево (граф

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

Рассмотрим одну из простейших задач: Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?

Решение: Нарисуем схему условия: планеты изобразим точками, их у нас 9, а маршруты ракет – направляющими линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.

Запишем еще одно определение: Степенью вершины графа

называется количество выходящих из нее ребер. В связи с этим, вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной.

1). В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими ?

Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным15·5/2=37,5. Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.

Ответ. Соединить телефоны таким образом невозможно.

2).

В государстве 100 городов к из каждого города выходит 4 дороги. Сколько всего дорог в государстве.

Решение. Подсчитаем общее количество выходящих городов дорог – 100 . 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200.

4).

Обрисовать фигуру, не отрывая карандаша от бумаги и не проводя два раза по одной линии. Обозначьте точки пересечения, в скобках укажите, сколько линий выходит из данной точки. Если число линий четное – то вершина четная, если число линий нечетное – то вершина нечетная. Пометить вершину, с которой надо начинать обход.

1.2.3.4.

Все ли фигуры у вас получилось нарисовать? (все, кроме фигуры №1). Как вы думаете почему? Как это связано с количеством четных и нечетных вершин?

Сделаем вывод:

· Если все вершины графа четные, то нарисовать фигуру возможно, и начать можно с любой вершины (№4).

· Если же из этих вершин две нечетные, то нарисовать фигуру можно, но только начинать необходимо в одной из этих двух нечетных вершин, а заканчивать во второй нечетной вершине (№2, №3).

· Если в графе более двух нечетных вершин, то нарисовать фигуру невозможно (№1).

Вопрос о разрешимости таких задач входит в теорию графов. Впервые ее исследовал Л.Эйлер в 1736г., решая задачу о Кенигсбергских мостах.

5).

Город Кенигсберг расположен на берегах и двух островах реки Преголя. Части города соединены между собой семью мостами. В воскресные дни горожане совершили прогулки по городу. И возник вопрос, можно ли выбрать такой маршрут, чтобы пройти по каждому мосту только один раз и вернуться в начальную точку пути?

Страницы: 1 2


Новое в образовании:

Спектакль «Аленушка и лиса»
(для театра картинок на фланелеграфе) Для проведения этого спектакля потребуется фланелеграф и картинки с изображением героев в разных ситуациях (см. ниже текст сказки): старик, старуха, Аленушка, подружки в разных видах (см. ниже текст сказки), медведь, волк, лиса; а также декорации: изба, внутрен ...

Высшее образование, «короткий» цикл
Высшее образование «короткого» цикла доступно только при наличии степени бакалавра. Его называют «коротким» циклом, потому что оно длится обычно 2 года. Это обучение пользуется спросом в обществе, так как дает возможность реального и быстрого трудоустройства. Следует выделить следующие общеобразова ...

Проблема образовательной среды и ее влияния на развитие личности
Проблема образовательной среды и ее влияния на развитие личности занимает одно из центральных мест в системе проблем современного образования. Прежде всего, остановимся на определении понятия «среда» и ее влиянии на развитие человека. Следуя определению, предложенному Л.И. Новиковой, мы рассматрива ...

Меню сайта

Copyright © 2019 - All Rights Reserved - www.powereducator.ru