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.


 

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

12302. Ипотекалық несие түсінігі 69.5 KB
  ЖОСПАР Кіріспе I. Ипотекалық несие түсінігі 1.1.Ипотекалық несиелендіру жүйесі: ұғымы бағыттары түрлері 1.2.Ипотекалық несиелендірудің Қазақстандағы рөлі мен алғышарттары Қорытынды ...
12303. «Саясаттану» жалпы білім беру курсы бойынша силлабус 939 KB
  1 силлабус; 2 оқу пәні бойынша глоссарий; 3 дәрістің қысқаша конспектісі; 4 негізгі және қосымша әдебиеттер тізімі; 5 семинар практикалық және/немесе зертханалық сабақтарды өткізу жоспары; 6 еңбек көлемі есептелген білім алу алушының өздік жұмысының та
12305. ПӘНДЕР МОДУЛІНІҢ ОҚУ-ӘДІСТЕМЕЛІК КЕШЕНІ 1.21 MB
  ПӘНДЕР МОДУЛІНІҢ ОҚУӘДІСТЕМЕЛІК КЕШЕНІ Пәндер модулінің оқуәдістемелік кешенін дайындауға жауаптылар: саяси ғылымдарының докторы профессор Бәкір Ә.Қ. әлеуметтік ғылымдарының магистрі аға оқытушы Сембина Ж.Ж. Оқытушы туралы мәлімет және байланыс мағлұматы: ...
12306. ПӘННІҢ ОҚУ-ӘДІСТЕМЕЛІК КЕШЕНІ 918.5 KB
  Пәнді оқытудың мақсаты. Студенттердің санасында қоғам мен оның құрылымы жайлы, ондағы әлеуметтік құбылыстар мен байланыстар жайлы дұрыс ғылыми көзқарас қалыптастыру. Оларды бүгінгі таңдағы қоғамда болып жатқан өзгерістермен таныс ете отырып, ол өзгерістерге талдау жасап, жеке тұлға ретінде баға беруге баулу.
12307. ПӘНДЕРДІҢ ОҚУ - ӘДІСТЕМЕЛІК КЕШЕНІ 1.15 MB
  ПӘНДЕРДІҢ ОҚУ ӘДІСТЕМЕЛІК КЕШЕНІ Пәндердің оқу әдістемелік кешенінің мазмұны 1. Пәннің типтік оқу бағдарламасы егер пән таңдау компоненті бойынша болса онда пәннің оқу бағдарламасы 2. Студенттер үшін пәннің оқу бағдарламасы syllabus Пәннің сипаттамасы а...
12308. Егемен Қазақстанның саяси проблемалары 511 KB
  Саяси болжамдау Саяси болжамдау ұғымы мәні мен ерекшеліктері. Саяси болжам аясы және негізгі принциптері. Саяси болжамдаудың мақсаты объективті негіздері және міндеттері. Болжамдаудың кезеңдері және типтері. Ғылыми болжамның әдістері және құралдары. Саяси болжамдау
12309. Орта ғасыр мен Қайта өрлеу дәуіріңдегі саяси ұғымдар 163.16 KB
  Орта ғасыр мен Қайта өрлеу дәуіріңдегі саяси ұғымдар Саяси ой тарихында орта ғасырлардағы феодалдық қоғамның орны ерекше. Батыс Еуропада феодализм мың жылдан артыққа созылды V XVI ғасырлар. Бұл дәуірде рухани өмірде дін түгелдей үстемдік етті. Христиан діні феодалдық қ...
12310. ПӘНДЕР МОДУЛІНІҢ ОҚУ-ӘДІСТЕМЕЛІК КЕШЕНІ. Қазақстан Республикасының демократиялық негіздерінің қалыптасуы: саяси-құқықтық аспект 333.96 KB
  Саясаттану пәні, объектісі, әдісі, әлеуметтік-гуманитарлық пәндер жүйесіндегі орны. Саясаттанудың болашақ маман тұлғасын, азаматты қалыптастырудағы орны. Саяси ой дамуының негізгі кезеңдері. Саясат қоғамдық құбылыс ретінде, оның табиғаты, түрлері, мүмкіндіктері, шекаралары мен келешегі. Саясаттанудың субъектісі