55716

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

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

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

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

Русский

2014-03-28

126 KB

7 чел.

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

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

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

ВВЕДЕНИЕ

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

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

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

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

Представим геометрическую фигуру, состоящую из определенного количества точек (положим, 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.


 

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

65705. Внутрішньомозкові і внутрішньошлуночкові крововиливи в результаті розриву аневризм переднього півкільця артеріального кола головного мозку (клініка, діагностика, лікування) 281.5 KB
  Необхідне подальше вивчення та практичне вдосконалення хірургічного лікування хворих з розривами АА, ускладненими ВМГ і ВШК, шляхом подальшого визначення показань і протипоказань, оптимальних строків, методів і обсягів оперативних втручань...
65706. Структурні зміни в нирках при експериментальній артеріальній гіпертензії та її фармакологічній корекції 139 KB
  Перспективним напрямком дослідження структурних змін нирок за умов АГ є використання експериментальних моделей зокрема щурів лінії СІСАГ спадково індукована стресом артеріальна гіпертензія. Тому використання вказаних щурів дає можливість прослідкувати поетапність...
65707. Внутрішньоісламські протиріччя в мусульманській уммі Криму: природа, стан, еволюція 160.5 KB
  Генезис та ескалація внутрішньорелігійних протиріч в ісламі який на теренах України переживає процес відродження та реінтеграції у нове для нього суспільне буття стали ще одним підтвердженням складності й багаторівневості релігійних процесів в умовах конфліктогенного...
65708. Наукові основи технологій одержання заряджених полімерних мембран з антибактеріальними властивостями 1.56 MB
  Мембранні технології в сучасному світі відіграють значну роль як у вирішенні локальних галузевих питань так і глобальних проблем що постали перед людством серед яких: забезпечення населення якісними продуктами харчування питною водою та сучасними джерелами енергії охорона...
65709. УДОСКОНАЛЕНІ ЗАХОДИ ДОГЛЯДУ ЗА НАСІННИКАМИ ЦУКРОВИХ БУРЯКІВ В УМОВАХ НЕСТІЙКОГО ЗВОЛОЖЕННЯ ЛІСОСТЕПУ УКРАЇНИ 303 KB
  Одним із надійних шляхів підвищення урожайності та якості насіння гібридів цукрових буряків є впровадження у виробництво удосконалених технологій вирощування які забезпечували б високу продуктивність насінників тобто максимальну реалізацію їх біологічного потенціалу...
65710. Комп’ютерний комплекс моделювання динаміки фізіологічного стану людини при роботі у приміщенні 360 KB
  Забезпечення належних умов праці на робочому місці безпека технологічних процесів санітарнопобутові умови праці та створення комфортних умов перебування людини у приміщенні набувають особливого значення оскільки більшу частину свого часу людина проводить саме в приміщенні.
65711. ПУБЛІЧНИЙ КОНТРОЛЬ ЗА ДІЯЛЬНІСТЮ ОРГАНІВ ДЕРЖАВНОЇ ВЛАДИ: ТЕОРЕТИКО-МЕТОДОЛОГІЧНИЙ АНАЛІЗ 199 KB
  Одним із ефективних засобів розвитку та функціонування сучасного постмодерного суспільства є налагодження діалогу між державою та громадянином між відповідними гілками влади політичними партнерами культурами та цивілізаціями.
65712. Податкова політика російського царату в українському селі у другій половині ХІХ – на початку ХХ ст.: історичний аспект 143.5 KB
  Трансформаційні процеси в аграрному секторі економіки України кінця ХХ – початку ХХІ ст. стимулюють зростання значного інтересу як дослідників-фахівців, так і широкої громадськості до специфічних особливостей перебігу аграрних перетворень, що мали місце в українському селі у минулому.
65713. Теплоізоляційні матеріали на основі модифікованих лужних алюмосилікатних композицій, здатних до спучування 927 KB
  Отже враховуючи все вищезазначене особливої актуальності набуває питання щодо розробки принципово нових видів теплоізоляційних матеріалів на основі модифікованих лужних алюмосилікатних композицій здатних до спучування які можуть бути виготовлені з використанням недорогої...