Реферат по дисциплине: «Основы теоретического мышления младших школьников» на тему «Графы и их применение при решении задач»

Графы и их применение при решении задач

Легко нарисовать окружность, не отрывая карандаша от бумаги и не проводя никакую линию дважды. Это можно сделать и когда надо нарисовать окружность вместе с ее диаметром: выйдем из конца диаметра, пройдем его, а потом по окружности вернемся обратно. Но как провести и второй диаметр? Как бы мы не старались, нарисовать такую фигуру одним росчерком пера (или одним движением карандаша) не удастся.

Рис 5

Какие же фигуры можно нарисовать таким образом?

Рассмотрим следующую задачу:
ЗАДАЧА: Между планетами введено космическое сообщение по следующим маршрутам: З-К, П-В, З-П, П-К, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?
РЕШЕНИЕ: Попробуем решить эту задачу графически, изобразим схему-чертеж маршрутов, где точками обозначим названия пунктов З, К, П, В и т.д, а отрезками - их соединяющие маршруты. Получается следующий чертеж: рис.6.

рис 6
Глядя на него можно ответить, что от З до М добраться нельзя. Таким образом эта задача решена с помощью графов.
Что же такое граф?
ОПРЕДЕЛЕНИЕ: ГРАФОМ называются схемы, состоящие из точек (вершины графов) и соединяющих эти точки отрезков, прямых или кривых (ребра графов).
В жизни мы часто встречаемся с графами. Это всевозможные схемы маршрутов рейсовых автобусов, городской метрополитен, элементы электрических цепей и т.д. Графы упрощают решение многих логических задач, экономических, физических и других. Графы имеют разные виды: их можно изобразить в виде геометрической фигуры, прямоугольника, окружности, овала, в виде дерева, в виде леса, в виде плоской фигуры.
Схема, состоящая из изолированных вершин, несоединенных ребрами, называется нулевым графом.
Графы, в которых не построены все возможные ребра, называется неполным.
Графы, в которых построены все возможные ребра, называется полным. В полном графе число ребер равно: n(n-1)\2, где n-число вершин графа.
Каждая вершина в графе имеет свою степень. Степенью вершины графа называется число, соответствующее количеству ребер графа, исходящих из данной вершины. Вершина называется четной, если степень этой вершины четная и нечетной, если она нечетная.