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

Страница 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


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

И.Б. Дерманова. Методика "Закончи историю"
Цель - изучить понимание детьми старшего дошкольного возраста нравственных норм (щедрость - жадность, трудолюбие - лень, правдивость – лживость, внимание к людям - равнодушие). Определить умение детей соотносить эти нормы с реальными жизненными ситуациями, разрешать проблемные ситуации на основе нр ...

Результаты интегрированного обучения и его значение
Опыт работы по данной теме позволяет сделать выводы о результатах и значении интегрированного обучения, которые сводятся к следующему. Интегрированное обучение: · способствует развитию научного стиля мышления учащихся; · даёт возможность широкого применения учащимися естественнонаучного метода позн ...

Этюд «Курочка-рябушечка»
(для театра картинок на фланелеграфе) Для проведения этюда потребуется: фланелеграф и картинка с изображением курочки. Ведущий выкладывает на фланелеграфе картинку курочки и читает малышам несколько раз потешку. Затем задает им вопросы (приведены ниже) по содержанию. После этого нужно выучить с дет ...

Меню сайта

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