Применение теории графов в информатике

ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ
ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ
КАФЕДРА МАТЕМАТИКИ И ИНФОРМАТИКИ
Курсовая работа
по дисциплине «Информатика»
на тему: «Применение теории графов в информатике»
УФА 2010
Содержание
Введение
Теоретическая часть
1.1 История возникновения теории графов
1.2 Основные понятия теории графов
1.3 Основные теоремы теории графов
1.4 Способы предоставления графов в компьютере
1.4.1 Требования к предоставлению графов
1.4.2 Матрица смежности
1.4.3 Матрица инциденций
1.4.4 Списки смежности
1.4.5 Массив дуг
1.5 Обзор задач теории графов
1.6 Программа определения кратчайшего пути в графах
1.6.1 Язык программирования Delphi
1.6.2 Программа «Определения кратчайшего пути в графе»
Практическая часть
2.1 Общая характеристика задачи
2.2 Описание алгоритма решения задачи
Заключение
Введение
Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждении о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок подавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач–проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая проблема не вызывала столь многочисленных и остроумных работ в области теории графов.
Настоящее столетие было свидетелем неуклонного развития теории графов, которая за последние десять – двадцать лет вступила в новый период интенсивных разработок. В этом процессе явно заметно влияние запросов новых областей: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем психологии и биологии.
Вследствие этого развития предмет теории графов является уже обширным, что все его основные направления невозможно изложить в одном томе. В настоящем первом томе предлагаемого двухтомного труда сделан акцепт на основные понятия и на результаты, вызывающие особый систематический интерес.
1. Теоретическая часть
1.1 История возникновения теории графов
Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783) [3, стр. 36]. Однако теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.
Задача о Кенигсбергских мостах. На рис. 1 представлен схематический план центральной части города Кенигсберг (ныне Калининград), включающий два берега реки Перголя, два острова в ней и семь соединяющих мостов. Задача состоит в том, чтобы обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку. Эта задача была решена (показано, что решение не существует) Эйлером в 1736 году.
/>
Рис. 1. Схематическое изображение Кенигсбергских мостов
Задача о трех домах и трех колодцах. Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 2). Эта задача была решена (показано, что решение не существует) Куратовским в 1930 году [2, стр. 51].
Рис. 2 Схематичное изображение трех домов и трех колодцев
Задача о четырех красках. Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом (рис. 3). С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно – объем перебора выходит далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они сделали все правильно.
/>

Рис. 3. Схематичное изображение задачи о четырех красках
1.2 Основные понятия теории графов
Графом G(V,E) называется совокупность двух множеств – непустого множества V(множества вершин) и множества E двухэлементных подмножеств множества V(E – множество ребер).
Ориентированным называется граф, в котором /> — множество упорядоченных пар вершин вида (x,y), где x называется началом, а y – концом дуги. Дугу (x, y) часто записывают как />. Говорят также, что дуга />ведет от вершины x к вершине y, а вершина y смежная с вершиной x./>
Если элементом множества E может быть пара одинаковых (не различных) элементов V, то такой элемент множества E называется петлей, а граф называется графом с петлями (или псевдографом).
Если E является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом.
Если элементами множества E являются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества E называются гипердугами, а граф называется гиперграфом.
Если задана функция F: V → M и/или F: E → M, то множество M называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа. Если функция F инъективна, то есть разные вершины (ребра)имеют разные пометки, то граф называют нумерованным.
Подграфом называется граф G′(V′,E′), где />и/или />.
Если V′ = V, то G′ называется остовным подграфом G.
Если />, то граф G′ называется собственным подграфом графа G.
Подграф G′(V′,E′) называется правильным подграфом графа G(V,E), если G′ содержит все возможные рёбра G.
Степень (валентность) вершины – это количество ребер, инцидентных этой вершине (количество смежных с ней вершин).
Маршрутом в графе называется чередующаяся последовательность вершин и ребер />, в которой любые два соседних элемента инциденты.
Если />, то маршрут замкнут, иначе открыт.
Если все ребра различны, то маршрут называется цепью.
Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью.
Замкнутая цепь называется циклом.
Замкнутая простая цепь называется простым циклом.
Граф без циклов называется ациклическим.
Для орграфов цепь называется путем, а цикл – контуром.
Рис. 4. Маршруты, цепи, циклы
Пример
В графе, диаграмма которого приведена на рис.4:
v1, v3, v1, v4 – маршрут, но не цепь;
v1, v3, v5, v2, v3, v4 – цепь, но не простая цепь;
v1, v4, v3, v2, v5 – простая цепь;
v1, v3, v5, v2, v3, v4, v1 – цикл, но не простой цикл;
v1, v3, v4, v1 – простой цикл.
Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом.
Если граф имеет простой цикл, содержащий все вершины графа (по одному разу), то такой цикл называется гамильтоновым циклом.--PAGE_BREAK--
Деревом называется связный граф без циклов.
Остовом называется дерево, содержащее все вершины графа.
Паросочетанием называется множество ребер, в котором никакие два не смежны.
Паросочетание называется максимальным, если никакое его надмножество не является независимым.
Две вершины в графе связаны, если существует соединяющая их простая цепь.
Граф, в котором все вершины связаны, называется связным.
Граф, состоящий только из изолированных вершин, называется вполне несвязным.
Длиной маршрута называется количество ребер в нем (с повторениями).
Расстоянием между вершинами u и v называется длина кратчайшей цепи />, а сама кратчайшая цепь называется геодезической.
Диаметром графа G называется длина длиннейшей геодезической.
Эксцентриситетом вершины v в связном графе G(V,E) называется максимальное расстояние от вершины v до других вершин графа G.
Радиусом графа G называется наименьший из эксцентриситетов вершин.
Вершина v называется центральной, если ее эксцентриситет совпадает с радиусом графа.
Множество центральных вершин называется центром графа.
Рис. 5 Эксцентриситеты вершин и центры графов (выделены)
1.3 Основные теоремы теории графов
Опираясь на приведенные выше определения теории графов, приведем формулировки и доказательства теорем, которые затем найдут свои приложения при решении задач.
Теорема1.Удвоенная сумма степеней вершин любого графа равна числу его ребер. [1, стр. 66]
Доказательство. Пусть А1, А2, А3,..., An — вершины данного графа, a p(A1), p(А2),..., p(An) – степени этих вершин. Подсчитаем число ребер, сходящихся в каждой вершине, и просуммируем эти числа. Это равносильно нахождению суммы степеней всех вершин. При таком подсчете каждое ребро будет учтено дважды (оно ведь всегда соединяет две вершины).
Отсюда следует: p(A1)+p(А2)+... +p(An)=0,5N,или2(p(A1)+p(А2)+...+p(An))=N, где N — число ребер.
Теорема2.Число нечетных вершин любого графа четно.
Доказательство. Пусть a1, a2, a3, …, ak— это степени четных вершин графа, а b1, b2, b3, …, bm— степени нечетных вершин графа. Сумма a1+a2+a3+…+ak+b1+b2+b3+…+bmровно в два раза превышает число ребер графа. Сумма a1+a2+a3+…+akчетная (как сумма четных чисел), тогда сумма b1+b2+b3+…+bm должна быть четной. Это возможно лишь в том случае, если m— четное, то есть четным является и число нечетных вершин графа. Что и требовалось доказать.
Следствие 1. Нечетное число знакомых в любой компании всегда четно.
Следствие 2. Число вершин многогранника, в которых сходится нечетное число ребер, четно.
Следствие 3. Число всех людей, когда-либо пожавших руку другим людям, нечетное число раз, является четным.
Теорема3.Во всяком графе с nвершинами, где nбольше или равно 2, всегда найдутся две или более вершины с одинаковыми степенями.
Доказательство. Если граф имеет nвершин, то каждая из них может иметь степень0, 1, 2, ..., (n-1). Предположим, что в некотором графе все его вершины имеют различную степень, то есть, и покажем, что этого быть не может. Действительно, если р(А)=0, то это значит, что А— изолированная вершина, и поэтому в графе не найдется вершины Х со степенью р(Х)=n-1. В самом деле, эта вершина должна быть соединена с (n-1) вершиной, в том числе и с А, но ведь А оказалась изолированной. Следовательно, в графе, имеющем n вершин, не могут быть одновременно вершины степении (n-1). Это значит, что из nвершин найдутся две, имеющие одинаковые степени.
Теорема4.Если в графе с nвершинами (nбольше или равно 2) только одна пара имеет одинаковую степень, то в этом графе всегда найдется либо единственная изолированная вершина, либо единственная вершина, соединенная со всеми другими.
Доказательство данной теоремы мы опускаем. Остановимся лишь на некотором ее пояснении. Содержание этой теоремы хорошо разъясняется задачей: группа, состоящая из nшкольников, обменивается фотографиями. В некоторый момент времени выясняется, что двое совершили одинаковое число обменов. Доказать, что среди школьников есть либо один еще не начинавший обмена, либо один уже завершивший его.
Теорема 5. Если у графа все простые циклы четной длины, то он не содержит ни одного цикла четной длины.
Суть теоремы в том, что на этом графе невозможно найти цикл (как простой, так и непростой) нечетной длины, то есть содержащий нечетное число ребер.
Теорема 6.Для того, чтобы граф был эйлеровым, необходимо и достаточно, чтобы он был связным и все его вершины имели четную степень.
Теорема7.Для того чтобы на связном графе можно было бы проложить цепь АВ, содержащую все его ребра в точности по одному разу, необходимо и достаточно, чтобы А и В были единственными нечетными вершинами этого графа.
Доказательство этой теоремы очень интересно и характерно для теории графов. Его также следует считать конструктивным (обратите внимание на то, как использована при этом теорема3.6). Для доказательства к исходному графу присоединяем ребро (А, В); после этого все вершины графа станут четными. Этот новый граф удовлетворяет всем условиям теоремы3.6, и поэтому в нем можно проложить эйлеров цикл Ψ. И если теперь в этом цикле удалить ребро (А, В), то останется искомая цепь АВ.
На этом любопытном приеме основано доказательство следующей теоремы, которую следует считать обобщением теоремы7.
Теорема8. Если данный граф является связным и имеет 2k вершин нечетной степени, то в нем можно провести k различных цепей, содержащих все его ребра в совокупности ровно по одному разу.
Теорема9.Различных деревьев с n перенумерованными вершинами можно построить nn-2.
По поводу доказательства этой теоремы сделаем одно замечание. Эта теорема известна, в основном, как вывод английского математика А. Кэли(1821—1895). Графы-деревья издавна привлекали внимание ученых. Сегодня двоичные деревья используются не только математиками, а и биологами, химиками, физиками и инженерами (подробнее об этом – в параграфе 6).
Теорема10.Полный граф с пятью вершинами не является плоским.
Доказательство. Воспользуемся формулой Эйлера: В-Р+Г=2, где В— число вершин плоского графа, Р— число его ребер, Г— число граней. Формула Эйлера справедлива для плоских связных графов, в которых ни один из многоугольников не лежит внутри другого.
Эту формулу можно доказать методом математической индукции. Это доказательство мы опускаем. Заметим только, что формула справедлива и для пространственных многогранников. Пусть все пять вершин графа соединены друг с другом. Замечаем, что на графе нет ни одной грани, ограниченной только двумя ребрами. Если через φ1обозначить число таких граней, то φ2=0. Далее рассуждаем от противного, а именно: предположим, что исследуемый граф плоский. Это значит, что для него верна формула Эйлера. Число вершин в данном графе В=5, число ребер Р=10, тогда число граней Г=2-В+Р=2-5+10=7.
Это число можно представить в виде суммы: Г=φ1+φ2+φ3+…, где φ3 – число граней, ограниченных тремя ребрами, φ4— число граней, ограниченных четырьмя ребрами и т. д.
С другой стороны, каждое ребро является границей двух граней, а поэтому число граней равно 2Р, в то же время 2Р=20=3φ3+4φ4+… . Умножив равенство Г=7=φ3+ φ4 + φ5 +… на три, получим ЗГ=21=3( φ3 + φ4 + φ5 + …).
Ясно, что (3φ3+3φ4+3φ5+…) )или 3Г
Теорема11.(Теорема Понтрягина-Куратовского) Граф является плоским тогда и только тогда, когда он не имеет в качестве подграфа полного графа с пятью вершинами.
1.4 Способы представления графов в компьютере
Конструирование структур данных для представления в программе объектов математической модели – это основа искусства практического программирования. Далее приводится четыре различных базовых представления графов. Выбор наилучшего представления определяется требованиями конкретной задачи. Более того, при решении конкретных задач используются, как правило, некоторые комбинации или модификации указанных представлений, общее число которых необозримо. Но все они так или иначе основаны на тех базовых идеях, которые описаны в этом разделе.    продолжение
--PAGE_BREAK--
1.4.1 Требования к представлению графов
Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается, исходя из потребностей конкретной задачи. Далее приведены четыре наиболее часто используемых представления с указанием характеристики n(p,q) – объема памяти для каждого представления. Здесь p – число вершин, а q – число ребер.
1.4.2 Матрица смежности
Представление графа с помощью квадратной булевой матрицы M, отражающей смежность вершин, называется матрицей смежности, где
/>
Для матрицы смежности n(p,q) = O(p2).
Замечание
Матрица смежности неориентированного графа симметрична относительно главной диагонали, поэтому достаточно хранить только верхнюю (или нижнюю) треугольную матрицу.
1.4.3 Матрица инциденций
Представление графа с помощью матрицы H, отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа
/>
а для орграфа
/>
Для матрицы инциденций n(p,q) = O(pq).
1.4.4 Списки смежности
Представление графа с помощью списочной структуры, отражающей смежность вершин и состоящей из массива указателей на списки смежных вершин, где элемент списка представлен структурой
N: record v: 1..p; n :↑ N end record,
называется списком смежности. В случае представления неориентированных графов списками смежности n(p,q) = O(p+2q), а в случае ориентированных графов n(p,q) = O(p+q).
1.4.5 Массив дуг
Представление графа с помощью массива структур
E: array[1..q] of record b,e: 1..p end record,
отражающего список пар смежных вершин, называется массивом ребер (или, для орграфов, массивом дуг). Для массива ребер (или дуг) n(p,q) = O(2q).
1.5 Обзор задач теории графов
Развитие теории графов в основном обязано большому числу всевозможных приложений. По-видимому, из всех математических объектов графы занимают одно из первых мест в качестве формальных моделей реальных систем.[4, стр. 12-15]
Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т.п. Наибольшей популярностью теоретико-графовые модели используются при исследовании коммуникационных сетей, систем информатики, химических и генетических структур, электрических цепей и других систем сетевой структуры.
Далее перечислим некоторые типовые задачи теории графов и их приложения:
— Задача о кратчайшей цепи
· замена оборудования
· составление расписания движения транспортных средств
· размещение пунктов скорой помощи
· размещение телефонных станций
— Задача о максимальном потоке
· анализ пропускной способности коммуникационной сети
· организация движения в динамической сети
· оптимальный подбор интенсивностей выполнения работ
· синтез двухполюсной сети с заданной структурной надежностью
· задача о распределении работ
— Задача об упаковках и покрытиях
· оптимизация структуры ПЗУ
· размещение диспетчерских пунктов городской транспортной сети
— Раскраска в графах
· распределение памяти в ЭВМ
· проектирование сетей телевизионного вещания
— Связность графов и сетей
· проектирование кратчайшей коммуникационной сети
· синтез структурно-надежной сети циркуляционной связи
· анализ надежности стохастических сетей связи
— Изоморфизм графов и сетей
· структурный синтез линейных избирательных цепей
· автоматизация контроля при проектировании БИС
— Изоморфное вхождение и пересечение графов
· локализация неисправности с помощью алгоритмов поиска МИПГ
· покрытие схемы заданным набором типовых подсхем
— Автоморфизм графов
· конструктивное перечисление структурных изомеров для производных органических соединений
· синтез тестов цифровых устройств
1.6 Программа определения кратчайшего пути в графе
1.6.1 Язык программирования Delphi
Delphi — язык и среда программирования, относящаяся к классу RAD- (Rapid Application Development   «Средство быстрой разработки приложений») средств CASE — технологии. Delphi сделала разработку мощных приложений Windows быстрым процессом, доставляющим вам удовольствие. Приложения Windows, для создания которых требовалось большое количество человеческих усилий например в С++, теперь могут быть написаны одним человеком, использующим Delphi.
Интерфейс Windows обеспечивает полное перенесение CASE-технологий в интегрированную систему поддержки работ по созданию прикладной системы на всех фазах жизненного цикла работы и проектирования системы.
Delphi обладает широким набором возможностей, начиная от проектировщика форм и кончая поддержкой всех форматов популярных баз данных. Среда устраняет необходимость программировать такие компоненты Windows общего назначения, как метки, пиктограммы и даже диалоговые панели. Работая в Windows, вы неоднократно видели одинаковые «объекты» во многих разнообразных приложениях. Диалоговые панели (например Choose File и Save File) являются примерами многократно используемых компонентов, встроенных непосредственно в Delphi, который позволяет приспособить эти компоненты к имеющийся задаче, чтобы они работали именно так, как требуется создаваемому приложению. Также здесь имеются предварительно определенные визуальные и не визуальные объекты, включая кнопки, объекты с данными, меню и уже построенные диалоговые панели. С помощью этих объектов можно, например, обеспечить ввод данных просто несколькими нажатиями кнопок мыши, не прибегая к программированию. Это наглядная реализация применений CASE-технологий в современном программировании приложений. Та часть, которая непосредственно связана с программированием интерфейса пользователя системой, получила название визуальное программирование
Визуальное программирование как бы добавляет новое измерение при создании приложений, давая возможность изображать эти объекты на экране монитора до выполнения самой программы. Без визуального программирования процесс отображения требует написания фрагмента кода, создающего и настающего объект «по месту». Увидеть закодированные объекты было возможно только в ходе исполнения программы. При таком подходе достижение того, чтобы объекты выглядели и вели себя заданным образом, становится утомительным процессом, который требует неоднократных исправлений программного кода с последующей прогонкой программы и наблюдения за тем, что в итоге получилось.
Благодаря средствам визуальной разработки можно работать с объектами, держа их перед глазами и получая результаты практически сразу. Способность видеть объекты такими, какими они появляются в ходе исполнения программы, снимает необходимость проведения множества операций вручную, что характерно для работы в среде, не обладающей визуальными средствами — вне зависимости от того, является она объектно-ориентированной или нет. После того, как объект помещен в форму среды визуального программирования, все его атрибуты сразу отображаются в виде кода, который соответствует объекту как единице, исполняемой в ходе работы программы.
Размещение объектов в Delphiсвязано с более тесными отношениями между объектами и реальным программным кодом.Объекты помещаются в вашу форму, при этом код, отвечающий объектам, автоматически записывается в исходный файл. Этот код компилируется, обеспечиваясущественно более высокую производительность, чем визуальная среда, которая интерпретирует информацию лишь в ходе исполнения программы.
1.6.2 Программа «Определение кратчайшего пути в графе»
Программа «Определение кратчайшего пути в графе» разработана в среде «Delphi», работает под ОС «Windows»-95,98,2000,NT.
Программа позволяет вводить, редактировать, сохранять графы в файл, загружать из файла. Также реализован алгоритм нахождения кратчайшего пути.
/>
Рис. 6. Интерфейс программы
Верхняя панель кнопок предназначена для редактирования графа.    продолжение
--PAGE_BREAK--
Кнопка «Загрузить» предназначена для загрузки ранее сохраненного графа из файла.
/>
Рис. 7. Кнопка «Загрузить»
Кнопка «Сохранить» предназначена для сохранения графа в файл.
/>
Рис. 8. Кнопка «Сохранить»
Кнопка «Переместить» предназначена для перемещения вершин графа.
/>
Рис. 9. Кнопка «Переместить»
Кнопка «Удалить» предназначена для удаления вершин графа.
/>
Рис. 10. Кнопка «Удалить»
При нажатии на кнопку «Новый» рабочее поле программы будет очищено и появится возможность ввода нового графа.
/>
Рис. 11. Кнопка «Новый»
Кнопка «Помощь» вызывает помощь программы.
/>
Рис. 12. Кнопка «Помощь»
Для очистки результатов работы алгоритма определения кратчайшего пути в графе необходимо нажать кнопку «Обновить».
/>
Рис. 13. Кнопка «Обновить»
При нажатии на кнопку «Настройки» на экране появится окно, в котором можно настроить параметры сетки рабочего поля программы и цвета вводимого графа.
/>
Рис. 14. Кнопка «Настройка»
Окно настроек выглядит следующим образом:
/>
Рис. 15. Окно настроек
Нижняя панель кнопок предназначена для установки параметров ввода и запуска алгоритма определения кратчайшего пути в графе. Данная панель состоит из четырех кнопок:
При включенной кнопке «Показывать сетку» отображается сетка для удобства ввода вершин.
/>
Рис. 16. Кнопка «Показывать сетку»
Для автоматического ввода длины ребра графа необходимо нажать кнопку.
/>
Рис. 17. Кнопка «Автоматический ввод длинны ребра»
При включенной кнопке «Выравнивать по сетке» новые вершины будут автоматически выравниваться по координатной сетке.
/>
Рис. 18. Кнопка «Выравнивать по сетке»
Если выбрать две различные вершины (щелчком левой кнопки мыши) нажать на кнопку, то программа найдет кратчайший путь между вершинами.
/>
Рис. 19. Кнопка «Нахождение кратчайшего пути между вершинами»



2. Практическая часть
2.1 Общая характеристика задачи
Агентство по грузоперевозкам «Летучий голландец» предоставляет услуги по перевозке грузов по различным маршрутам. Данные о маршрутах, выполненных в течение недели, по каждому водителю приведены на рис. 1.
Сведения о выполненных маршрутах
№ п/п
ФИО водителя
Марка автомобиля
№ рейса
Выполнено рейсов, шт.
Протяженность рейса, км.
Расход топлива на 100 км, л
Израсходовано топлива, л
Грузоподъемность, т
Вес перевезенного груза, т
1
Соловьев В.В.
КАМАЗ
А112
4










2
Михайлов С.С.
ЗИЛ
С431
3










3
Кузнецов Я.Я.
МАЗ
А112
5










4
Иванов К.К.
МАЗ
М023
7










5
Сидоров А.А.
ЗИЛ
В447
2










6
Волков Д.Д.
КАМАЗ
С431
8










7
Быков Л.Л.
КАМАЗ
В447
4












ИТОГО
Х
Х














В СРЕДНЕМ
Х
Х












Рис. 1. Данные о маршрутах
Справочные данные о технических характеристиках автомобилей и протяженности маршрутов представлены на рис. 2.
Протяженность рейсов
№ п/п
№ рейса
Протяженность рейса, км
1
А112
420
2
В447
310
3
М023
225
4
С431
250
Технические характеристики автомобилей    продолжение
--PAGE_BREAK----PAGE_BREAK--
№ п/п
Марка автомобиля
Расход топлива на 100 км, л
Грузоподъемность, т
1
ЗИЛ
42
7
2
КАМАЗ
45
16
3
МАЗ
53
12
Таблица№3
Протяженность рейсов
№ п/п
№ рейса
Протяженность рейса, км
1
А112
420
2
В447
310
3
М023
225
4
С431
250
Таблица №4
/>/>/>









ФИО водителя
№ рейса
Выполнено рейсов, шт
Израсходовано топлива, л


Соловьев В.В.
А112
4
189


Михайлов С.С.
С431
3
105


Кузнецов Я.Я.
А112
5
222,6


Иванов К.К.
М023
7
119,25


Сидоров А.А.
В447
2
130,2


Волков Д.Д.
С431
8
112,5


Быков Л.Л.
В447
4
139,5


ИТОГО


33
1018,05




Бухгалтер _________________________
Таблица №5
/>
Заключение
В работе были рассмотрены задачи из теории графов, которые уже стали классическими. Особенно часто в практическом программировании возникают вопросы о построении кратчайшего остова графа и нахождении максимального паросочетания. Известно также, что задача о нахождении гамильтонова цикла принадлежит к числу NP-полных, т.е. эффективный алгоритм для ее решения не найден. Таким образом, задачи теории графов актуальны, так как могут принести экономию времени и средств на производстве и в быту. Теория графов находит широкое применение в различных областях науки и техники:
Графы и информация
Двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.
Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо «да», либо «нет». Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. «Опрос» завершается, когда удается установить то, что требовалось.
Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.
Графы и химия
Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:
CnH2n+2
Молекула каждого предельного углеводорода представляет собой дерево. Если удалить все атомы водорода, то оставшиеся атомы углеводорода также будут образовывать дерево, каждая вершина которого имеет степень не выше 4. Следовательно, число возможных структур предельных углеводородов, т. е. число гомологов данного вещества, равно числу деревьев с вершинами степени не больше четырех.
Таким образом, подсчет числа гомологов предельных углеводородов также приводит к задаче о перечислении деревьев определенного типа. Эту задачу и ее обобщения рассмотрел Д. Пойа.
Графы и биология
Деревья играют большую роль в биологической теории ветвящихся процессов. Для простоты мы рассмотрим только одну разновидность ветвящихся процессов – размножение бактерий. Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево.
Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.
Графы и физика
Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.
Печатной схемой называют пластинку из какого-либо диэлектрика (изолирующего материала), на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы и другие), их пересечение в других местах вызовет замыкание электрической цепи.
В ходе решения этой задачи необходимо вычертить плоский граф, с вершинами в указанных точках.
Итак, из всего вышесказанного неопровержимо следует практическая ценность теории графов.