Скрытые графы на олимпиадных задачах
Основные определения в теории графов, его виды и способы представления в информатике. Понятие соотношения инцидентности. Примеры решения задач республиканских олимпиад по программированию через графы: "Тетраэдр", "Стены", "Блокада" и "Мудрый правитель".
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | практическая работа |
| Язык | русский |
| Дата добавления | 07.09.2009 |
| Размер файла | 62,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
2
Учебно-исследовательская работа
«Скрытые графы на олимпиадных задачах»
Исполнитель: Алексютович Евгений Олегович,
учащийся 10А класса
Научный руководитель: Горский Сергей Михайлович,
учитель информатики
Государственного учреждения образования
«Гимназия №71 г.Гомеля»
Гомель, 2008
Содержание
- Введение
- 1. Определение графа
- 1.1 Способы представления графа в информатике
- 1.2 Отношение инцидентности
- 2. Примеры
- 2.1 Задача «Тетраэдр»
- 2.2 Задача «Стены»
- 2.3 Задача «Блокада»
- 2.4 Задача «Мудрый правитель»
- Заключение
- Список использованных источников
Введение
Графы являются существенным элементом математических моделей в самых разнообразных областях науки и практики. Они помогают наглядно представить взаимоотношения между объектами или событиями в сложных системах. Многие алгоритмические задачи дискретной математики могут быть сформулированы как задачи, так или иначе связанные с графами, например задачи, в которых требуется выяснить какие-либо особенности устройства графа, или найти в графе часть, удовлетворяющую некоторым требованиям, или построить граф с заданными свойствами.
Легко найти примеры графов в самых разных областях науки и практики. Сеть дорог, трубопроводов, электрическая цепь, структурная формула химического соединения, блок-схема программы -- в этих случаях графы возникают естественно и видны "невооруженным глазом". При желании графы можно обнаружить практически где угодно. Это наглядно показано в книге Д.Кнута [D.E.Knuth, "The Stanford GraphBase"] -- графы извлекаются из романа "Анна Каренина", из картины Леонардо да Винчи, из материалов Бюро Экономического Анализа США и из других источников. То, что столь многие различные структуры могут быть смоделированы с использованием одного формализма, дает образованному программисту большое преимущество.
В теории алгоритмов графы -- это одна из универсальных тем, абстрактное представление. В программировании графы используют не только для решения определенных задач, но и для анализа и тестирования программ, организации вычислительного процесса, [2, с. 294-309].
Учитывая количество алгоритмов для графов, проблема состоит не в решении задач, используя графы, а в переформулировании условия задачи на язык теории графов. Именно этому и посвящена данная работа.
1. Определение графа
Граф или неориентированный граф G -- это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:
V -- это множество вершин или узлов,
E -- это множество пар (неупорядоченных) различных вершин, называемых рёбрами.
V (а значит и E) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становятся ложными в случае бесконечных множеств.
Вершины и рёбра графа называются также элементами графа, число вершин в графе (| V |)-- порядком, число рёбер (| E |)-- размером графа.
Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.
Два ребра называются смежными, если они имеют общую концевую вершину.
Два ребра называются кратными, если множества их концевых вершин совпадают.
Ребро называется петлёй, если его концы совпадают, то есть e = {v,v}.
Степенью вершины v называют количество рёбер, для которых она является концевой (при этом петли считают дважды).
Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.
Ориентированный граф (сокращенно орграф) G -- это упорядоченная пара G: = (V,A), для которой выполнены следующие условия:
V -- это множество вершин или узлов,
A -- это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.
Дуга -- это упорядоченная пара вершин (v,w), где вершину v называют началом, а w -- концом дуги. Можно сказать, что дуга v w ведёт от вершины v к вершине w.
Смешанный граф G -- это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые -- неориентированными. Записывается упорядоченной тройкой G: = (V,E,A), где V, E и A определены так же, как выше.
Понятно, что ориентированный и неориентированный графы являются частными случаями смешанного.
Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершиной ребром.
Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер.
Бинарное отношение на множестве вершин графа, заданное как "существует путь из u в v", является отношением эквивалентности, и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.
Граф называется:
ь связным, если для любых вершин u, v есть путь из u в v.
ь сильно связным или ориентированно связным, если он ориентированный, и из любой вершины в любую другую имеется ориентированный путь.
ь деревом, если он связный и не содержит простых циклов.
ь полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром.
ь двудольным, если его вершины можно разбить на два непересекающихся подмножества V1 и V2 так, что всякое ребро соединяет вершину из V1 с вершиной из V2.
ь полным двудольным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества
ь планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер.
ь взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра.
1.1 Способы представления графа в информатике
Ш Матрица смежности -- таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот).
Ш Матрица инцидентности. Каждая строка соответствует определенной вершине графа, а столбцы соответствуют связям графа. В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается 1 в случае если связь j "выходит" из вершины i, -1 если связь "входит" в вершину, любое число отличное от 0,1,-1 если связь является петлей, и 0 во всех остальных случаях.
Ш Список рёбер -- это тип представления графа в памяти, подразумевающий, что каждое ребро представляется двумя числами -- номерами вершин этого ребра. Список ребёр более удобен для реализации различных алгоритмов на графах по сравнению с матрицей смежности.
Более абстрактно, граф можно задать как тройку (V, E, f), где V и E -- некоторые множества (вершин и рёбер, соотв.), а f -- функция инцидентности (или инцидентор), сопоставляющая каждому ребру из E (упорядоченную или неупорядоченную) пару вершин u и v из V (его концов). Частными случаями этого понятия являются:
мультиграфы -- графы с кратными рёбрами, имеющими своими концами одну и ту же пару вершин;
псевдографы -- это мультиграфы, допускающие наличие петель;
простые графы -- не имеющие петель и кратных рёбер.
Под данное выше определение не подходят некоторые другие обобщения:
гиперграф -- если ребро может соединять более двух вершин.
ультраграф -- если между элементами xi и uj существуют бинарные отношения инцидентности.
1.2 Отношение инцидентности
В геометрическом смысле две области (фигуры) на плоскости называются инцидентными (смежными) если они имеют общую границу. Для перехода к графам вершинам графа сопоставляют сами области, а ребрам графа -- состояние инцидентности. То есть ребра проводятся между вершинами, соответствующими смежным областям. Такими областями могут быть треугольники (задача «Тетраэдр»), многоугольники (задача «Стены»), наборы смежных квадратных клеток (задача «Блокада»). Более того, смежность может быть нестандартной, например клетки шахматной доски могут быть смежными в том смысле, что из одной клетки можно попасть в другую ровно за один ход шахматного коня (задача «Мудрый правитель»), или смежными будут считаться валы, связанные ременной передачей (задача «Ременная передача» [1]).
2. Примеры
2.1 Задача «Тетраэдр»
Республиканская олимпиада по информатике, Минск, 1999
Дано треугольное поле в виде равностороннего треугольника. Оно разбито на маленькие одинаковые равносторонние треугольники со сторонами, в M раз меньшими, чем сторона большого треугольника.
Рис. 1. Общий вид треугольного поля для задачи «Тетраэдр»
Маленькие треугольники пронумерованы подряд с верхнего ряда вниз по рядам, начиная с 0. Числами показаны номера треугольников. I-му треугольнику приписана пометка Pi.
Имеется также тетраэдр (правильная треугольная пирамида) с ребром, равным длине стороны маленького треугольника. Тетраэдр установлен на S-м треугольнике. Все грани тетраэдра пронумерованы следующим образом:
1) основание тетраэдра;
2) правая грань тетраэдра, если смотреть сверху тетраэдра в направлении стороны АВ перпендикулярно ей;
3) левая грань тетраэдра, если смотреть сверху тетраэдра в направлении стороны АВ перпендикулярно ей;
4) оставшаяся грань.
Например, при S = 2 жирной линией выделено нижнее ребро третьей грани, а при S = 3 жирной линией выделено нижнее ребро второй грани. J-я грань тетраэдра имеет пометку Rj.
Имеется возможность перекатывать тетраэдр через ребро, но при каждом перекатывании взимается штраф, равный квадрату разности между пометками совмещаемой грани тетраэдра и треугольника. Требуется перекатить тетраэдр с треугольника S на D с наименьшим суммарным штрафом.
Перейдем к графу следующим образом: вершина -- маленький треугольник. Ребро -- наличие возможности перекатить тетраэдр через ребро из одного треугольника в другой. Тогда, например, поле, изображенное на рис. 2, превратится в граф на рис. 3.
Рис. 2. Пример треугольного поля для задачи «Тетраэдр»
Рис. 3. Начальное положение развертки тетраэдра
На этом графе требуется найти путь минимальной стоимости из одной вершины в другую. Поскольку веса ребер в этом графе зависят от того, какой именно гранью тетраэдр придет на соответствующий треугольник, то воспользуемся поиском в ширину.
2.2 Задача «Стены»
Международная олимпиада по информатике, 2000
В некоторой стране стены построены таким образом, что каждая стена соединяет ровно два города, и стены не пересекают друг друга. Таким образом, страна разделена на отдельные части. Чтобы добраться из одной области в другую, необходимо либо пройти через город, либо пересечь стену. Два любых города A и B могут соединяться не более чем одной стеной (один конец стены в городе A, другой -- в городе B). Более того, всегда существует путь из города A в город B, проходящий вдоль каких-либо стен и через города.
Существует клуб, члены которого живут в городах. В каждом городе может жить либо один член клуба, либо вообще ни одного. Иногда у членов клуба возникает желание встретиться внутри одной из областей, но не в городе. Чтобы попасть в нужную область, каждый член клуба должен пересечь какое-то множество стен, возможно, равное нулю. Члены клуба путешествуют на велосипедах. Они не хотят въезжать ни в один город из-за интенсивного движения на городских улицах. Они также хотят пересечь минимально возможное количество стен, так как пересекать стену с велосипедом довольно трудно. Исходя из этого, нужно найти такую оптимальную область, чтобы суммарное количество стен, которые требуется пересечь членам клуба, называемое суммой пересечений, было минимальным из всех возможных.
Города пронумерованы целыми числами от 1 до N, где N -- количество городов. На рис. 4 пронумерованные вершины обозначают города, а линии, соединяющие вершины, обозначают стены. Предположим, членами клуба являются три человека, которые живут в городах с номерами 3, 6 и 9. Сумма пересечений равна 2, так как членам клуба требуется пересечь две стены: человеку из города 9 требуется пересечь стену между городами 2 и 4, человеку из города 6 требуется пересечь стену между городами 4 и 7, а человек из города 3 не пересекает стен вообще.
Рис. 4. Пример треугольного поля для задачи «Тетраэдр»
2.3 Задача «Блокада»
Всероссийская командная олимпиада школьников по программированию, 2001
Государство Флатландия представляет собой прямоугольник размером M x N, состоящий из единичных квадратиков. Флатландия разделена на K провинций (2 < K < 100). Каждая провинция представляет собой связное множество квадратиков, то есть из каждой точки провинции можно дойти до любой другой ее точки, при этом разрешается переходить с квадратика на квадратик, только если они имеют общую сторону (общей вершины недостаточно). Во Флатландии нет точки, которая граничила бы более чем с тремя провинциями (то есть четыре квадратика, имеющие общую вершину, не могут принадлежать четырем разным провинциям).
Каждая провинция имеет свой символ. Столица Флатландии находится в провинции, имеющей символ A (заглавная латинская буква A). Провинция называется пограничной, если она содержит граничные квадратики. Провинция, в которой находится столица Флатландии, не является пограничной.
Король Ректилании, соседнего с Флатландией королевства, решил завоевать Флатландию. Для этого он хочет захватить столицу Флатландии. Однако он знает, что сил его армии недостаточно, чтобы сделать это сразу. Поэтому сначала он хочет окружить центральную провинцию, ослабить силы противника долгой блокадой, а потом захватить столицу.
Чтобы окружить провинцию, требуется захватить все провинции, с которыми она граничит. Две провинции граничат, если существует два квадрата, имеющие общую сторону, один из которых принадлежит первой из них, а другой -- второй. Чтобы захватить провинцию, надо чтобы выполнялось одно из двух условий: либо она пограничная, либо граничит с какой-либо уже захваченной провинцией.
Чтобы сберечь силы своей армии, король Ректилании хочет установить блокаду центральной провинции, захватив как можно меньше провинций. Помогите ему выяснить, сколько провинций потребуется захватить. Захватывать саму центральную провинцию нельзя, поскольку для этого сил армии Ректилании пока недостаточно.
Переход к графам осуществляем следующим образом: вершина -- область (обозначается символом с возможным кодом от 32 до 255). Ребро отображает смежность двух областей. При вводе исходных данных анализируются две смежные строки: соседние (горизонтально) символы во второй строке и соседние (вертикально) символы первой и второй строк. По этим данным пополняются ребра графа.
2.4 Задача «Мудрый правитель»
Командный чемпионат школьников Санкт-Петербурга по программированию, 2000
Известно, что о создателе шахмат ходит множество легенд. Недавно в одной древней библиотеке была обнаружена еще одна. В ней утверждается, что когда создатель игры рассказал правителю о своем изобретении и попросил скромную награду, правитель сказал ему следующее: «Возьми шахматную доску и поставь на нее коня. На ту клетку, на которую ты поставишь коня, я положу 2N золотых монет. На те клетки, на которые ты сможешь дойти конем за 1 ход, я положу 2N - 1 золотых монет. И вообще, если с клетки, на которую ты поставишь коня, ты сможешь дойти до некоторой клетки самое меньшее за P Ј N ходов, я положу на нее 2N - P золотых монет. Но если ты проявишь чрезмерную жадность и не сможешь унести все монеты, которые я выложу на доску, то я прикажу отрубить тебе голову!»
Ученым известно, что создатель шахмат был очень умным человеком. Он знал, что сможет унести не более M монет. Поэтому он поставил коня на такую клетку, чтобы получить как можно больше монет и остаться живым. Если бы такой клетки не было, то он бы тихо покинул город. Помогите ученым узнать, сколько монет заработал создатель шахмат своим изобретением и на какую клетку он поставил коня.
ПРИМЕЧАНИЕ
Напоминаем, что шахматная доска имеет форму квадрата, поделенного на клетки; столбцы называются латинскими буквами от a до h, а строки -- цифрами от 1 до 8, клетка имеет название в виде пары буква-цифра, в зависимости от того, на пересечении какого столбца и какой строки она находится. Конь ходит буквой «Г» -- на 2 клетки в горизонтальном или вертикальном направлении и затем на одну клетку в перпендикулярном направлении. Разумеется, конь не может выходить за пределы доски.
Для перехода к задаче на графе вводим следующие аналогии: вершина -- клетка доски, ребро -- наличие возможности хода шахматного коня из одной клетки в другую. Ребрам присваиваем веса: 0 -- для ребра к самой себе; 1 -- для ребра к клетке, в которую можно добраться ровно за 1 ход; -1 -- в остальных случаях.
Заключение
В данной работе были рассмотрены одни из наиболее типичных приемов решения олимпиадных задач по программированию через графы. Учитывая количество алгоритмов решения задач на графах, самое сложное в олимпиадных задачах является переформулировка задачи на язык теории графов. К сожалению, из-за малого количества места не были рассмотрены другие задачи.
Список использованных источников
Долинский М.С., Решение сложных и олимпиадных задач по программированию [текст]/ Долинский М.С.--СПб.: Питер, 2006.--368с.
Евстигнеев В.А., Применение теории графов в программировании [текст]/ Евстигнеев В.А.--М.: Наука, 1985.--352с.
Кристофидес Н., Теория графов. Алгоритмический подход [текст]/Кристофидес Н.--М.: Мир, 1978.--216с.
Скиена С.С., Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям [текст]/ Скиена С.С., Ревилла М.А.-- М.: Кудиц-Образ, 2005.--416с.
Алексеев В.Е., Графы и алгоритмы [текст]/ Алексеев В.Е. -- Нижний Новгород, 2000.--68с.
Подобные документы
Применение теории графов и алгоритмов на графах среди дисциплин и методов дискретной математики. Граф как совокупность двух множеств. Основные способы численного представления графа. Элементы и изоморфизмы графов. Требования к представлению графов в ЭВМ.
курсовая работа [162,2 K], добавлен 04.02.2011Основные понятия и определения алгоритмов на графах. Связные графы без циклов, свободное дерево или дерево без корня. Ориентированные графы (орграфы), их использование для представления отношений между объектами. Матрицы смежности и инциденций.
презентация [93,9 K], добавлен 13.09.2013Представление задач в виде графов AND/OR, примеры. Задача с ханойской башней. Формулировка процесса игры в виде графа. Основные процедуры поиска по заданному критерию. Эвристические оценки и алгоритм поиска. Пример отношений с определением задачи.
лекция [154,6 K], добавлен 17.10.2013Определение понятия графа как набора вершин и связей между ними. Способы решения задач по программированию согласно теории графов на примерах заданий "Дороги", "Перекрестки", "Скрудж Мак-Дак", используя рекурсивные функции и рекуррентные соотношения.
курсовая работа [36,2 K], добавлен 10.03.2010История возникновения, основные понятия и теоремы теории графов. Способы предоставления графов в компьютере. Матрица смежности, инциденций, списки смежности и массив дуг. Программа определения кратчайшего пути в графах. Язык программирования Delphi.
курсовая работа [823,5 K], добавлен 24.11.2010Графы: определения, примеры, способы изображения. Смежные вершины и рёбра. Путь в ориентированном и взвешенном графе. Матрица смежности и иерархический список. Алгоритм Дейкстры - алгоритм поиска кратчайших путей в графе. Работа в программе "ProGraph".
презентация [383,8 K], добавлен 27.03.2011Области применения теории графов. Алгоритм решения задачи поиска инвариантного и полного графа. Реализация программы с графическим интерфейсом пользователя на основе алгоритма. Реализация редактора графа и вывод полученных результатов в понятной форме.
курсовая работа [493,3 K], добавлен 27.12.2008Понятие и основные определения гамильтоновых графов, теоремы их достаточности и особенности методов нахождения циклов. Сущность метода перебора Робертса и Флореса и его улучшение. Задачи отыскания гамильтоновых циклов в графах, создание программы.
курсовая работа [76,5 K], добавлен 01.07.2010Математические графы, области их применения. Способы раскраски вершин и ребер графов, задачи на их применение. Разработка алгоритма, работающего на основе операций с матрицей смежности. Описание логической структуры программы. Пример зарисовки графа.
курсовая работа [145,5 K], добавлен 27.01.2013Алгоритм решения функциональной задачи. Выбор системы команд специализированной ЭВМ. Форматы команд и операндов. Содержательные графы микропрограмм операций АЛУ. Разработка объединенной микропрограммы работы АЛУ. Закодированные алгоритмы микропрограмм.
курсовая работа [265,5 K], добавлен 17.11.2010
