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

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


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

Исследование досуговых предпочтений детей г. Волгограда
Цель нашего исследования – выявить досуговые предпочтения учащихся школ г. Волгограда и проанализировать результаты проведённого нами социологического обследования. Анкетным опросом было охвачено 700 детей и 300 родителей г. Волгограда. В бюджете времени учащихся обычно выделяют учебное и внеучебно ...

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

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

Меню сайта

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