Михаил Анатольевич Иорданский – доктор физико-математических наук, профессор кафедры информатики и информационных технологий в образовании НГПУ имени Козьмы Минина
При решении многих логических, комбинаторных задач (головоломок) рука невольно тянется к изображению исходных данных, их структуры в виде рисунка, состоящего из точек (вершин) и линий (ребер), соединяющих вершины между собой. Эти рисунки являются графами решаемых задач. Большое число популярных головоломок поддается формулировке непосредственно в терминах теории графов. При желании много занимательных задач, решаемых с помощью графов, можно найти в [1].
В классической теории графы задаются множествами вершин и ребер с использованием различных матричных или списковых структур. При этом свойства графов определяются, как правило, в терминах запрещенных подграфов. Так, например, для того, чтобы все ребра графа можно было провести на плоскости так, чтобы они не пересекались (такие графы называются планарными), требуется отсутствие в графе подграфов К3,3 и К5:
Для графов большого размера установление фактов наличия или отсутствия в них подграфов К3,3 или К5 представляет собой довольно сложную задачу.
В рамках конструктивной теории графы рассматриваются как результаты некоторых процессов их построения из заданных исходных графов с помощью операций объединения с пересечением (операции склейки). Накладывая ограничения на операции склейки, можно сохранять требуемые свойства графов, «выращивая» графы с наперед заданными свойствами. Так, для построения любого связного планарного графа, содержащего более одной вершины, в качестве исходных планарных графов достаточно выбрать графы К2, склеивая их затем по одной или двум вершинам с уже построенным текущим графом (вначале с другим К2). Для сохранения свойства планарности при склейке К2 с текущим графом по двум вершинам требуется, чтобы они принадлежали одной его грани – части плоскости, ограниченной со всех сторон вершинами и ребрами графа.
При использовании конструктивного подхода для решения прикладных задач на графах в качестве исходных выбираются графы, для которых рассматриваемая задача решается наиболее эффективно. Далее из них строится суперпозиция, реализующая заданный граф. Анализ структуры графа упрощается, если строить его «по кирпичику», когда, по крайней мере, один из графов-операндов каждой операции склейки принадлежит множеству исходных графов. Так, при рассмотренном построении планарных графов таким кирпичиком являлся граф К2.
Наличие конструктивных описаний графов позволяет «сжимать» информацию о графах, задавая алгоритмы их построения вместо перечисления множеств вершин и ребер. Использование нумераций вершин графов, отражающих порядок их построения, упрощает алгоритмы декодирования – восстановления графов по их кодам. Заинтересованный читатель может прочитать обо всех этих задачах в [2-3].
Литература:
- Мельников О.И. Занимательные задачи по теории графов. – Минск: НТ ООО "Тетра Системс", 2001. – 144 с.
- Иорданский М.А. Введение в теорию графов. – Н. Новгород: НГПУ им. К.Минина, 2014. – 80 с. (www.iordanskyma.wordpress.com)
- Иорданский М.А. Конструктивная теория графов и ее приложения. – Н. Новгород: Кириллица, 2016. – 172 с. (www.iordanskyma.wordpress.com)
При грантовой поддержке Минобрнауки России в рамках Десятилетия науки и технологий