55716

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

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

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

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

Русский

2014-03-28

126 KB

4 чел.

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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


 

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

75300. Особенности социально-экономического и политического развития Византии в IX-XII веков 36 KB
  Золотой век Византийской империи длился примерно с 850 по 1050 гг. В эти столетия ее владения простирались от Южной Италии и Далмации до Армении Сирии и Месопотамии давняя проблема безопасности северных границ империи была решена присоединением Болгарии 1018 и восстановлением прежней римской границы по Дунаю. Были ассимилированы и подчинены империи заселившие в предшествующий период Грецию славяне. Захват Константинополя крестоносцами в 1204 и последующий раздел империи подвел черту под тысячелетним существованием Византии как великой...
75301. Византия в ХIII-ХV вв. (от Латинской империи до падения Константинополя) 63 KB
  На развалинах Византии в 1204 г. возникло новое искусственно созданное государство Латинская империя названная так в отличие от греческой империи Византии во главе с избранным крестоносцами императором Балдуином Фландрским 1204 1205. Овладев Константинополем победители мечтали о создании огромного государства включавшего не только все владения Византии но также и земли балканских славян. В результате завоевания Византии западноевропейскими феодалами складывавшиеся здесь феодальные институты получили более законченную форму.
75302. Культура Византии в IV-XV веков 51 KB
  Культура Византии в IVXV вв. В ранний период в Византии еще сохранялись старые центры античной образованности Афины Александрия Бейрут Газа. в Византии начинают применять индийские цифры в арабском написании. Однако античные космогонические представления сохраняются в Византии и в IX в.
75303. Немарксистские теории происхождения средневековых городов 33 KB
  Немарксистские теории происхождения средневековых городов. Вопрос о причинах и обстоятельствах возникновения средневековых городов представляет большой интерес. При таком подходе невозможно объяснить коренные причины происхождения городов. Романистическая теория Савиньи Тьерри Гизо Ренуар которая строилась главным образом на материале романизированных областей Европы считала средневековые города и их учреждения прямым продолжением поздних античных городов.
75304. Отечественная историография о происхождении средневекового города 42.5 KB
  Отечественная историография о происхождении средневекового города. Впервые проблема происхождения городского строя в Западной Европе была поставлена в отечественной медиевистике в начале XX в.Впервые в России обращение к городской истории произошло именно в историографическом аспекте. Интересуясь прежде всего проблемами аграрного развития Европы эпохи Средневековья и формируя общую концепцию генезиса феодализма Петрушевский не мог пройти мимо такого интересного сюжета европейской истории как возникновение городов.
75305. Характер, формы и основные этапы социальной борьбы в средневековом городе 35.5 KB
  Средневековые города возникали на земле королей а также светских и духовных феодалов. Они начали борьбу за свое освобождение добиваясь превращения сеньориального города в вольный а его жителей в свободных горожан. Позднее города стали бороться за политические привилегии: право на самоуправление и собственную юрисдикцию. Но это было по силам только очень богатым городам французским английским.
75306. Средневековое цеховое ремесло и его характер 39 KB
  Средневековое цеховое ремесло и его характер. Характерной особенностью средневекового ремесла в Европе была его цеховая организация объединение ремесленников определённой профессии в пределах данного города в особые союзы цехи. Цехи появились почти одновременно с возникновением городов. хотя окончательное оформление цехов получение специальных хартий от королей запись цеховых уставов и т.
75307. Производительные силы Западной Европы в V-XV веков 43.5 KB
  Производительные силы средневекового общества это люди с присущими им особенностями сознания трудовыми навыками природная среда их обитания и созданные ими в процессе жизнедеятельности орудия технологии и формы организации труда. Его характеризовали ручные орудия и низкая производительность труда отсутствие скольконибудь значительных материальных ресурсов простое нерасширенное воспроизводство. Даже крупные владения феодалов чаще всего представляли собой конгломерат более или менее значительных усадеб деревень или их групп...
75308. Культура Западной Европы в V-XI веках 43 KB
  Культура Западной Европы в VXI вв. Искусство Западной Европы в средние века. Книга представляет собой очерки истории искусства стран Западной Европы в средние века. Сюда были приглашены наиболее образованные люди тогдашней Европы.