Решение задач на графах

  • 03 июня 2010 г.
  • 1413 Слова
Министерство образования Республики Беларусь
Учреждение образования
«Гомельский государственный университет им. Ф. Скорины»
Математический факультет
Кафедра МПУ

Курсовая работа
Решение задач на графах

Исполнитель:
Студентка группы М-42
Макарченко А.Ю.

Научный руководитель:
олинский М.С.

Гомель 2006
Введение

Существует целый класс олимпиадных задач по программированию,которые проще решаются, если ученик владеет определенным набором знаний, умений и навыков в области алгоритмов на графах. Это происходит потому, что такие задачи могут быть переформулированы в терминах теории графов.
Теория графов содержит огромное количество определений, теорем и алгоритмов. И поэтому данный материал не может претендовать, и не претендует, на полноту охвата материала. Однако, помнению автора, предлагаемые сведения являются хорошим копромиссом между объемом материала и его "коэффициентом полезного действия" в практическом программировании и решении олимпиадных задач.
Необходимо отметить, что данный материал в существенной степени опирается на наличие у ученика определенных навыков в использовании рекурсивных функций и рекуррентных соотношений, которые, в частности, могутпоявится при работе над авторскими материалами [9] и [10] соответственно.
Далее материал построен следующим образом. Приводится минимальное количество базовой теории, после чего приводится решение большого количества задач из Белорусских республиканских и международных (IOI - International Olympiad in Informatics) олимпиад по информатике для школьников.
Автору представляется наиболее эффективнымследующий способ изучения излагаемого материала. После ознакомления с общими сведениями, разбор каждой новой задачи проводить в таком порядке. Прочитав условия, отложить материал в сторону и попытаться решить задачу самостоятельно. Если же Вам покажется, что Вы зашли в тупик, и дальнейшие размышления не могут привести к полезному результату, нужно возвращаться к материалу, прочитать полное решение исамостоятельно реализовать его на компьютере. Чем полнее и напряженнее будет проведенная Вами работа над текущей задачей, тем больше шансов, что Вы решите следующую задачу самостоятельно. Более того, такая работа над каждой из приведенных в данном материале задач, приведет к значительному увеличению шансов на то, что Вы решите новые задачи такого класса, которые Вам обязательно встретятся. И, наоборот, поверхностноечтение может привести, в лучшем случае, к тому, что Вы просто поймете и, возможно, запомните решение десятка приведенных задач. Это, конечно, тоже не мало, ведь Вам могут встретиться эти, либо похожие, задачи. Но автор ставит другую задачу - помочь Вам научиться решать новые задачи такого класса.
1. Общие сведения об алгоритмах на графах

Прежде всего несколько слов о том, как возникает понятиеграфа из естественных условий задач. Приведем несколько примеров.
Пусть мы имеем карту дорог, в которой для каждого города указано расстояние до всех соседних с ним. Здесь два города называются соседними, если существует дорога, соединяющая непосредственно эти два города.
Аналогично, можно рассмотреть улицы и перекрестки внутри одного города. Заметим, что могут быть улицы с односторонним движением.Сеть компьютеров, соединенных проводными линиями связи.
Набор слов, каждое из которых начинается на определенную букву и заканчивается на эту же или другую букву.
Множество костей домино. Каждая кость имеет 2 числа: левую и правую половину кости.
Устройство, состоящее из микросхем, соединенных друг с другом наборами проводников.
Генеалогические деревья, указывающие родственные отношения междулюдьми.
И, наконец, собственно графы, указывающие отношения между какими либо абстрактными понятиями например, числами.
Итак, неформально, граф можно определить как набор вершин (города, перекрестки, компьютеры, буквы, цифры кости домино, микросхемы, люди) и связей между ними: дороги между городами; улицы между перекрестками; проводные линии связи между...
tracking img