Графы. решение практических задач с использованием графов (С++)

    Дисциплина: Программирование
    Тип работы: Курсовая
    Тема: Графы. решение практических задач с использованием графов (С++)

    МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
    САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
    им. Н.Г. ЧЕРНЫШЕВСКОГО
    Кафедра теоретических основ информатики и информационных технологий
    ГРАФЫ. РЕШЕНИЕ ПРАКТИЧЕСКИХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ ГРАФОВ (С++)
    Курсовая работа
    Выполнил:
    студент 1-го курса
    факультета КНиИТ, группа № 121,
    специальность «Вычислительные машины, комплексы, системы и сети»
    Жучков Андрей Сергеевич
    Научный руководитель:
    Седина Юлия Олеговна
    Зав. Кафедрой ТОИиИТ
    Профессор, академик РАЕН, д.т.н.
    Сытник Александр Александрович
    Саратов 2005
    СОДЕРЖАНИЕ
    Введение
    История возникновения теории графов
    Основные понятия теории графов
    Основные теоремы теории графов
    Способы представления графов в компьютере
    Обзор задач теории графов
    Заключение
    Список литературы
    Приложение А
    10. Приложение Б
    Введение
    В последнее время исследования в областях, традиционно относящихся к дискретной математике, занимают все более заметное место. Наряду с такими классическими разделами
    математики, как математический анализ, дифференциальные уравнения, в учебных планах специальности \"Прикладная математика\" и многих других специальностей появились разделы по
    математической логике, алгебре, комбинаторике и теории графов. Причины этого нетрудно понять, просто обозначив круг задач, решаемых на базе этого математического аппарата.
    История возникновения теории графов.
    Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Однако теория графов многократно переоткрывалась разными авторами при решении различных
    прикладных задач.
    Задача о Кенигсбергских мостах.
    На рис. 1 представлен схематический план центральной части города Кенигсберг (ныне Калининград), включающий два берега реки Перголя, два острова в ней и семь соединяющих мостов.
    Задача состоит в том, чтобы обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку. Эта задача была решена (показано, что решение не существует)
    Эйлером в 1736 году.
    рис. 1
    Задача о трех домах и трех колодцах.
    Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 2). Эта
    задача была решена (показано, что решение не существует) Куратовским в 1930 году.
    SHAPE
    * MERGEFORMAT
    рис. 2
    Задача о четырех красках.
    Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты
    таким образом, чтобы никакие две соседние области не были закрашены одним цветом (рис. 3). С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок. В 1976
    году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось
    прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов
    потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы
    суперкомпьютера. Проверить «вручную» полученное решение невозможно – объем перебора выходит далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать
    такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам
    такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно. Таким образом, остается уповать на программистскую
    квалификацию авторов и верить, что они сделали все правильно.
    Рис. 3
    Основные понятия теории графов
    Графом
    называется совокупность двух множеств – непустого множества
    (множества вершин) и множества
    двухэлементных подмножеств множества
    – множество ребер).
    Ориентированным
    называется граф, в котором
    - множество упорядоченных пар вершин вида (
    ), где
    называется началом, а
    – концом дуги. Дугу (
    ) часто записывают как
    к вершине
    , а вершина
    смежная
    с вершиной
    Если элементом множества
    может быть пара одинаковых (не различных) элементов
    , то такой элемент множества
    называется петлей, а граф называется графом с петлями (или псевдографом).
    Если
    является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом.
    Если элементами множества
    являются не обязательно двухэлементные, а любые подмножества множества
    , то такие элементы множества
    называются гипердугами, а граф называется гиперграфом.
    Если задана функция
    и/или
    , то множество
    называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа. Если функция
    инъективна, то есть разные вершины (ребра)имеют разные пометки, то граф называют нумерованным.
    Подграфом
    называется граф
    \'(
    \',
    \'), где
    Если
    \' =
    , то
    \' называется остовным подграфом
    Если
    \' называется собственным подграфом графа
    Подграф
    \'(
    \',
    \') называется правильным подграфом графа
    ), если
    \' содержит все возможные рёбра
    Степень (валентность)
    вершины – это количество ребер, инцидентных этой вершине (количество смежных с ней вершин).
    Маршрутом
    в графе называется чередующаяся последовательность вершин и ребер
    Если
    замкнут, иначе открыт.
    Если все ребра различны, то маршрут называется цепью.
    Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью.
    Замкнутая цепь называется циклом.
    Замкнутая простая цепь называется
    простым циклом.
    Граф без циклов называется ациклическим.
    Для орграфов цепь называется путем, а цикл – контуром.
    SHAPE
    * MERGEFORMAT
    рис. 4. Маршруты, цепи, циклы
    Пример
    В графе, диаграмма которого приведена на рис.4:
    – маршрут, но не цепь;
    – цепь, но не простая цепь;
    – простая цепь;
    – цикл, но не простой цикл;
    – простой цикл.
    Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом.
    Если граф имеет простой цикл, содержащий все вершины графа (по одному разу), то такой цикл называется гамильтоновым циклом.
    Деревом
    называется связный граф без циклов.
    Остовом
    называется дерево, содержащее все вершины графа.
    Паросочетанием
    называется множество ребер, в котором никакие два не смежны.
    Паросочетание называется максимальным, если никакое его надмножество не является независимым.
    Две вершины в графе связаны, если существует соединяющая их простая цепь.
    Граф, в котором все вершины связаны, называется связным.
    Граф, состоящий только из изолированных вершин, называется вполне несвязным.
    Длиной маршрута
    называется количество ребер в нем (с повторениями).
    Расстоянием
    между вершин...

    Забрать файл

    Похожие материалы:


ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены