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.


 

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

42139. Создание HTML-страницы для ввода данных 31.5 KB
  Теория В целом для создания HTMLкода чаще всего используются следующие теги: Теги начала и окончания HTMLстраницы html html Теги начала и окончания заголовка HTMLстраницы hed hed Теги начала и окончания названия HTMLстраницы title title Тег для установки кодировки HTMLстраницы met httpequiv= ContentType content= text html; chrset=windows1251 Теги начала и окончания основного тела HTMLстраницы body body Теги начала и окончания абзаца параграфа в теле HTMLстраницы p p Тег пропуска строки br Теги начала и...
42140. ПОДГОТОВКА И АНАЛИЗ ДАННЫХ 444 KB
  Очень часто происходит ситуация когда анализ данных проводимый между этапом сбора данных и собственно эконометрическим моделированием позволяет сократить количество лишней работы связанной с фактическим выбором модели и анализом технической информации во время моделирования. Предварительный анализ данных можно условно разделить на три этапа: графический анализ данных; фильтрация очистка рядов данных; анализ выборочных характеристик рассматриваемых рядов. Эконометрическое исследование проводится как минимум для двух рядов...
42142. Задачі лінійної оптимізації в системі Maple 213 KB
  Задачі оптимізації в Maple розв’язуються за допомогою вбудованих функцій minimize та maximize, що входять до пакету Simplex.Класична задача лінійного програмування записується у такому форматі:minimize (цільова функція, {обмеження}, NONNEGATIVE).Останній параметр вказує на невід’ємність змінних, що входять до математичної моделі задачі. Для геометричної інтерпретації задачі оптимізації необхідно підключити пакет plots і задати систему лінійних нерівностей задачі, використовуючи процедуру inequal.
42143. ПАРНАЯ РЕГРЕССИЯ 338.5 KB
  модель вида yi = 0 1 xi i где yi – значение зависимой переменной для наблюдения i xi – значение независимой переменной для наблюдения i 0 и 1 – коэффициенты регрессии εi – значение случайной ошибки для наблюдения i n – число наблюдений. Оценки коэффициентов парной линейной регрессии и определяются методом наименьших квадратов МНК. Оценки коэффициентов уравнения регрессии полученные МНК могут обладать следующими свойствами: несмещенность состоятельность эффективность. Содержание МНК свойств оценок полученных...
42144. ОПРЕДЕЛЕНИЕ ЭЛЕКТРОДВИЖУЩЕЙ СИЛЫ МЕТОДОМ КОМПЕНСАЦИИ 51 KB
  Для существования стационарного тока в цепи необходим какой-нибудь источник энергии электродвижущей силы ЭДС который способен поддерживать электрическое поле. В источнике ЭДС перемещение носителей заряда производится с помощью запасенной энергии. Рассмотрим замкнутую цепь состоящую из источника ЭДС и нагрузки внешней цепи. Таким образом ЭДС это физическая величина численно равная работе сторонних сил по перемещению единичного положительного заряда по замкнутой цепи.
42145. ОПРЕДЕЛЕНИЕ СОПРОТИВЛЕНИЯ С ПОМОЩЬЮ МОСТА УИТСТОНА 81 KB
  Сопротивления R1 R2 R0 Rх называются плечами моста Rх  измеряемое неизвестное R0 – известное R1 R2 – регулировочные сопротивления. Сопротивления плеч моста измеряют и подбирают таким образом чтобы ток гальванометра был равен нулю. Для однородного проводника сопротивления отдельных его участков относятся как их длины.
42146. ОПРЕДЕЛЕНИЕ НЕИЗВЕСТНОЙ ЕМКОСТИ КОНДЕНСАТОРА С ПОМОЩЬЮ МОСТА СОТТИ 80.5 KB
  В настоящей работе измерение электрической емкости осуществляется с помощью моста переменного тока  моста Сотти рис. Плечи моста плечо моста – это участок цепи включенный между двумя узлами включают конденсатор неизвестной емкости Сх конденсатор эталонной емкости Сэ и два резистора имеющих сопротивления R1 и R2. В диагональ СD моста включают источник переменного напряжения трансформатор.
42147. ОПРЕДЕЛЕНИЕ НЕИЗВЕСТНОЙ ИНДУКТИВНОСТИ С ПОМОЩЬЮ МОСТИКА МАКСВЕЛЛА 73.5 KB
  ПОСТАНОВКА ЗАДАЧИ В настоящей работе измерение индуктивности осуществляется с помощью моста переменного тока  моста Максвелла рис.Плечи моста состоят из эталонной индуктивности L0 неизвестной индуктивности Lх их сопротивлений R R двух резисторов имеющих сопротивления R1 и R2. Принцип измерения индуктивности катушки Lх при помощи мостика Максвелла основан на подборе такого значения отношения сопротивлений при котором ток через гальванометр отсутствует.