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

Страница 1

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

Каждая пара точек в графе может быть соединена линиями. Линия указывает на связь между двумя точками. Точки называются вершинами графа, а линии - рёбрами.

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

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

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

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

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

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

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

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

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

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

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

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

1. 2. 3.

Страницы: 1 2


Актуально о образовании:

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

Проблемы внедрения и возможные пути развития личностно-ориентированного обучения
"Индивидуализация", "дифференцированное обучении", "личностно-ориентированное образование" - все это понятия в педагогике далеко не новые. С ними в той или иной степени знаком каждый школьный учитель. И все-таки проанализируем, как эти понятия "работают" на п ...

Метод мозгового штурма
Метод мозгового штурма (мозговой штурм, мозговая атака, англ. brainstorming) — оперативный метод решения проблемы на основе стимулирования творческой активности, при котором участникам обсуждения предлагают высказывать как можно большее количество вариантов решения, в том числе самых фантастичных. ...

Категории

Copyright © 2018 - All Rights Reserved - www.centraleducation.ru