55716

Исследования графов и их изучение

Научная статья

Педагогика и дидактика

Точки графа называются его вершинами а отрезки соединяющие их ребрами графа. Более того графы являются эквивалентными либо попросту одним и тем же графом если соответствующие вершины одного графа соединены так же как и соответствующие вершины другого то есть соединены...

Русский

2014-03-28

126 KB

5 чел.

Исследования графов и их изучение

Т.Ю. Каламбет

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

ВВЕДЕНИЕ

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

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

ОПРЕДЕЛЕНИЕ ГРАФА

Существует множество различных трактовок понятия «граф», пригодных на разных этапах изучения теории графов, и различающихся не только математической базой, используемой при определении, но также и с точки зрения интуитивного либо формального подхода. Для изучения графов в рамках этой работы будем использовать следующий, наиболее обобщенный подход к определению.

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

Рисунок 1

Здесь следует отметить, что пересечение таких соединяющих отрезков, которое не является точкой фигуры, не рассматривается как таковое — то есть граф мыслится таким образом, что его отрезки пересекаются только в его вершинах. Более того, графы являются эквивалентными (либо попросту одним и тем же графом), если соответствующие вершины одного графа соединены так же, как и соответствующие вершины другого (то есть, соединены или не соединены ребром). Таким образом, графы А и Б, изображенные на рисунке 2, являются эквивалентными.

Рисунок 2

Ребра у графа могут быть как направленные (следующие из одной вершины в другую и схематически обозначающиеся стрелкой), так и ненаправленные (предполагается, что они направлены в обе стороны). Также каждое ребро может иметь свой вес (вес ребра — скалярная величина, которая, условно говоря, характеризует силу связи между вершинами количественным образом, например, описывающая расстояние между одним и другим объектом). В зависимости от этого возникает и классификация графов на направленные и ненаправленные, а также на графы со взвешенными ребрами (рисунок 3). В более общем случае рассматривается граф, у которого ненаправленные ребра, и каждое из них имеет вес, равный 1. Еще одним подвидом ребра графа является так называемая петля, то есть ребро, соединяющее вершину с самой собой (как на рисунке 4).

Рисунок 3

Рисунок 4

В заключение следует рассмотреть характеристику графа, которая позволяет дать его исчерпывающее описание. Речь идет о матрице связности графа — матрице значений весов ребер, соединяющих соответствующие строкам и столбцам вершины. Такая матрица является квадратной и подходит для описания всех рассмотренных выше графов (в случае ненаправленных ребер в графе матрица является симметричной). Например, матрица А соответствует графу Б, изображенному на рисунке 3:

.

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

КЛЮЧЕВЫЕ ПРОБЛЕМЫ

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

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

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

Окрашивание графа. Что собой представляет процесс окрашивания графа? Это такой процесс, при котором каждой вершине графа присваивается значение (цвет), причем эти значения (цвета) могут как быть одинаковыми, так и различаться. Обязательным условием является различие цветов, присваиваемых «соседним» вершинам (то есть вершинам, соединенным ребром). Таким образом, главным вопросом является нахождение минимального количества таких цветов, которыми можно было бы «окрасить» все вершины графа с соблюдением данного условия.

Блуждание и покрытие. Еще одним, достаточно широким аспектом применения моделей графа является изучение процесса блуждания на графе. Блужданием на графе, попросту говоря, называется некое движение частицы из одной вершины графа в другую по ребрам, соединяющим их. Характер такого движения тесно связан с вероятностями перехода частицы по одному из ребер, то есть возможностью перехода по тому или иному конкретному ребру. Этот процесс представляет особый интерес для учеников, которые уже знакомы с основами теории вероятностей, и в силу этого способны более подробно изучить такое блуждание. Неразрывно связан такой процесс и с процессом покрытия графа, то есть процессом посещения той или иной вершины, добавляя эту вершину к множеству посещенных (покрытых) вершин. Одной из ключевых задач покрытия является исследование времени покрытия графа, то есть количества шагов, необходимых частице, чтобы в ходе блуждания покрыть все вершины графа.

ИЗУЧЕНИЕ ГРАФОВ

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

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

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

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

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

ВЫВОДЫ

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

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

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

ЛИТЕРАТУРА

1. Харари Ф. Теория графов / Харари Фрэнк Пер. с англ. и предисл. В.П. Козырева. Под ред. Г.П. Гаврилова. Изд. 2-е. — М.:Едиториал УРСС, 2003. — 296 с.

2. Зыков А.А. Основы теории графов / Зыков А.А. — М.: Наука, 1987. — 384 с.

3. Durrett R. Probability : theory and examples, 4-th ed. / Rick Durrett. — 1951. — 440 p.


 

А также другие работы, которые могут Вас заинтересовать

8069. Цель воспитания и задача воспитания. Реализация целей воспитания в деятельности работника в сфере культуры 25.24 KB
  Цель воспитания и задача воспитания. Реализация целей воспитания в деятельности работника в сфере культуры Одной из фундаментальных проблем в педагогической науке является проблема целеполагания. Существуют разные подходы к определению цели воспитан...
8070. Понятие и характеристика общих закономерностей воспитательного процесса 27.11 KB
  Понятие и характеристика общих закономерностей воспитательного процесса Эффективность воспитания зависит от следующих факторов: От сложившихся воспитательных отношений. Воздействие на ребенка осуществляется через его отношение к окружающему, в...
8071. Понятие принцип воспитания. Характеристика основных принципов воспитания 31.02 KB
  Понятие принцип воспитания. Характеристика основных принципов воспитания Принципы воспитательного процесса (принципы воспитания) - это общие исходные положения, в которых выражены основные требования к содержанию, методам, организации воспитате...
8072. Финансовая устойчивость организации на примере ОАО КАМАЗ 138.4 KB
  Введение Финансовая устойчивость - составная часть общей устойчивости предприятия, сбалансированность финансовых потоков, наличие средств, позволяющих организации поддерживать свою деятельность в течение определенного периода времени...
8074. Разработка бизнес-плана горнолыжного курорта в Приэльбрусье 364.5 KB
  Разработка бизнес-плана горнолыжного курорта в Приэльбрусье Введение Каждый предприниматель, начиная свою деятельность, должен ясно представлять потребность на перспективу в финансовых, материальных, трудовых и интеллектуальных ресурсах, источники и...
8075. Бізнес-план для діяльності виробничого підприємства ТОВ КРУЧА 692.5 KB
  ВСТУП Актуальність теми дослідження. З кожним роком зростає роль економічного аналізу господарської діяльності підприємств як складової системи економічної інформації та управління. Управління підприємством вимагає систематичної, точної і достовірно...
8076. Бизнес план компьютерного клуба интернет кафе 281.5 KB
  Введение. Бизнес-план - это документ, отражающий основные стороны деятельности предприятия: производственные, коммерческие, социальные. Бизнес-план составляется на два-три года с разбивкой по годам, а первый год по месяцам, регулярно корректиру...
8077. Обгрунутвання бізнес плану присвячений розробці випуску нового виду продукції підприємства ЗАТ Мясокомбінат Товстун 352.5 KB
  ВСТУП Вирішивши зайнятися бізнесом, підприємець повинен ретельно спланувати його організацію. Мова йде про бізнес-плани, з яких у всьому світі прийнято починати будь-яке комерційне захід. В умовах ринку подібні плани необхідні всім: банкірам і потен...