Реферат: Графы. решение практических задач с использованием графов (С++)
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
им.Н.Г. ЧЕРНЫШЕВСКОГО
Кафедра теоретических основ информатики иинформационных технологийГРАФЫ. РЕШЕНИЕ ПРАКТИЧЕСКИХ ЗАДАЧ СИСПОЛЬЗОВАНИЕМ ГРАФОВ (С++)
Курсовая работа
Выполнил:студент1-го курса<span Arial",«sans-serif»; mso-font-kerning:16.0pt;mso-bidi-font-weight:bold">факультета КНиИТ, группа №121,
<span Arial",«sans-serif»; mso-font-kerning:16.0pt;mso-bidi-font-weight:bold">специальность«Вычислительные машины, комплексы, системы и сети»
<span Arial",«sans-serif»; mso-font-kerning:16.0pt;mso-bidi-font-weight:bold">Жучков Андрей Сергеевич
<span Arial",«sans-serif»;mso-font-kerning:16.0pt; mso-ansi-language:EN-US;mso-bidi-font-weight:bold"><span Arial",«sans-serif»;mso-font-kerning:16.0pt">Научный руководитель:
<span Arial",«sans-serif»; mso-font-kerning:16.0pt;mso-bidi-font-weight:bold">Седина Юлия Олеговна
<span Arial",«sans-serif»; mso-font-kerning:16.0pt;mso-bidi-font-weight:bold">
<span Arial",«sans-serif»; mso-font-kerning:16.0pt;mso-bidi-font-weight:bold">Зав. Кафедрой ТОИиИТ
<span Arial",«sans-serif»; mso-font-kerning:16.0pt;mso-bidi-font-weight:bold">Профессор, академик РАЕН,д.т.н.
<span Arial",«sans-serif»; mso-font-kerning:16.0pt">Сытник Александр Александрович
<span Arial",«sans-serif»;mso-ansi-language:EN-US">Саратов2005
<span Arial",«sans-serif»;mso-fareast-font-family: «Times New Roman»;mso-font-kerning:16.0pt;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">СОДЕРЖАНИЕ
1.<span Times New Roman"">
Введение2.<span Times New Roman"">
История возникновения теории графов3.<span Times New Roman"">
Основные понятия теории графов4.<span Times New Roman"">
Основные теоремы теории графов5.<span Times New Roman"">
Способы представления графов в компьютере6.<span Times New Roman"">
Обзор задач теории графов7.<span Times New Roman"">
Заключение8.<span Times New Roman"">
Список литературы9.<span Times New Roman"">
Приложение А10.Приложение Б
<span Arial",«sans-serif»;mso-fareast-font-family: «Times New Roman»;mso-font-kerning:16.0pt;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">Введение
В последнее время исследования в областях, традиционноотносящихся к дискретной математике, занимают все более заметное место. Нарядус такими классическими разделами математики, как математический анализ,дифференциальные уравнения, в учебных планах специальности «Прикладнаяматематика» и многих других специальностей появились разделы поматематической логике, алгебре, комбинаторике и теории графов. Причины этогонетрудно понять, просто обозначив круг задач, решаемых на базе этогоматематического аппарата.
Историявозникновения теории графов.Родоначальником теории графов принято считатьматематика Леонарда Эйлера (1707-1783). Однако теория графов многократнопереоткрывалась разными авторами при решении различных прикладных задач.
1.<span Times New Roman"">
Задача о Кенигсбергских мостах.На рис. 1 представлен схематический план центральнойчасти города Кенигсберг (ныне Калининград), включающий два берега реки Перголя,два острова в ней и семь соединяющих мостов. Задача состоит в том, чтобы обойтивсе четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходнуюточку. Эта задача была решена (показано, что решение не существует) Эйлером в1736 году.<img src="/cache/referats/20858/image002.jpg" v:shapes="_x0000_i1026">
рис. 1
2.<span Times New Roman"">
Задача о трех домах и трех колодцах. Имеется три дома и три колодца, каким-то образомрасположенные на плоскости. Провести от каждого дома к каждому колодцу тропинкутак, чтобы тропинки не пересекались (рис. 2). Эта задача была решена (показано,что решение не существует) Куратовским в 1930 году.SHAPE * MERGEFORMAT <img src="/cache/referats/20858/image003.gif" v:shapes="_x0000_s1063 _x0000_s1062 _x0000_s1081 _x0000_s1069 _x0000_s1067 _x0000_s1065 _x0000_s1066 _x0000_s1068 _x0000_s1080 _x0000_s1082 _x0000_s1083 _x0000_s1084 _x0000_s1085 _x0000_s1086 _x0000_s1087 _x0000_s1088 _x0000_s1089 _x0000_s1090 _x0000_s1091 _x0000_s1092 _x0000_s1093 _x0000_s1094 _x0000_s1095 _x0000_s1096 _x0000_s1097 _x0000_s1098 _x0000_s1099 _x0000_s1102 _x0000_s1103">
рис. 2
3.<span Times New Roman"">
Задача о четырех красках.Разбиение на плоскости на непересекающиеся областиназывается картой. Области на карте называются соседними, если они имеют общуюграницу. Задача состоит в раскрашивании карты таким образом, чтобы никакие двесоседние области не были закрашены одним цветом (рис. 3). С конца позапрошлоговека известна гипотеза, что для этого достаточно четырех красок. В 1976 годуАппель и Хейкен опубликовали решение задачи о четырех красках, котороебазировалось на переборе вариантов с помощью компьютера. Решение этой задачи«программным путем» явилось прецедентом, породившим бурную дискуссию, котораяотнюдь не закончена. Суть опубликованного решения состоит в том, чтобыперебрать большое, но конечное число (около 2000) типов потенциальныхконтрпримеров к теореме о четырех красках и показать, что ни один случайконтрпримером не является. Этот перебор был выполнен программой примерно затысячу часов работы суперкомпьютера. Проверить «вручную» полученное решениеневозможно – объем перебора выходит далеко за рамки человеческих возможностей.Многие математики ставят вопрос: можно ли считать такое «программноедоказательство» действительным доказательством? Ведь в программе могут бытьошибки… Методы формального доказательства правильности программ не применимы кпрограммам такой сложности, как обсуждаемая. Тестирование не можетгарантировать отсутствие ошибок и в данном случае вообще невозможно. Такимобразом, остается уповать на программистскую квалификацию авторов и верить, чтоони сделали все правильно.1
2
2
3
4
<img src="/cache/referats/20858/image004.gif" align=«left» v:shapes="_x0000_s1105 _x0000_s1104 _x0000_s1111 _x0000_s1110 _x0000_s1106 _x0000_s1108 _x0000_s1107 _x0000_s1109">Рис. 3
Основныепонятия теории графов1)<span Times New Roman"">
ГрафомG(V,E) называется совокупность двух множеств – непустогомножества V(множества вершин) и множества Eдвухэлементных подмножеств множества V(E– множестворебер).2)<span Times New Roman"">
Ориентированнымназывается граф, в котором <img src="/cache/referats/20858/image006.gif" v:shapes="_x0000_i1028"> — множествоупорядоченных пар вершин вида (x,y), где xназываетсяначалом, а y– концом дуги. Дугу (x, y) частозаписывают как <img src="/cache/referats/20858/image008.gif" v:shapes="_x0000_i1029"><img src="/cache/referats/20858/image008.gif" v:shapes="_x0000_i1030">xквершине y, а вершина yсмежнаяс вершиной x.<img src="/cache/referats/20858/image011.gif" v:shapes="_x0000_i1031">3)<span Times New Roman"">
Если элементом множества Eможет быть пара одинаковых(не различных) элементов V, то такойэлемент множества Eназывается петлей, а граф называется графомс петлями (или псевдографом).4)<span Times New Roman"">
Если Eявляется немножеством, а набором, содержащимнесколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом.5)<span Times New Roman"">
Если элементами множества Eявляются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества Eназываются гипердугами,а граф называется гиперграфом.6)<span Times New Roman"">
Если задана функция F: V→ Mи/или F: E→ M, то множество Mназывается множеством пометок, а граф называется помеченным(или нагруженным). В качествемножества пометок обычно используются буквы или целые числа. Если функция Fинъективна, то есть разные вершины (ребра)имеют разные пометки, то графназывают нумерованным.7)<span Times New Roman"">
Подграфом называется граф G′(V′,E′), где <img src="/cache/referats/20858/image013.gif" v:shapes="_x0000_i1032"><img src="/cache/referats/20858/image015.gif" v:shapes="_x0000_i1033">a)<span Times New Roman"">
Если V′ = V, то G′называется остовным подграфом G.b)<span Times New Roman"">
Если <img src="/cache/referats/20858/image017.gif" v:shapes="_x0000_i1034">G′называется собственным подграфомграфа G.c)<span Times New Roman"">
Подграф G′(V′,E′) называется правильным подграфом графа G(V,E), если G′ содержитвсе возможные рёбра G.8)<span Times New Roman"">
Степень(валентность)вершины – этоколичество ребер, инцидентных этой вершине (количество смежных с ней вершин).9)<span Times New Roman"">
Маршрутом в графеназывается чередующаяся последовательность вершин и ребер <img src="/cache/referats/20858/image019.gif" v:shapes="_x0000_i1035">a)<span Times New Roman"">
Если <img src="/cache/referats/20858/image021.gif" v:shapes="_x0000_i1036">замкнут,иначе открыт.b)<span Times New Roman"">
Если все ребра различны, то маршрут называется цепью.c)<span Times New Roman"">
Если все вершины (а значит, и ребра) различны, томаршрут называется простой цепью.d)<span Times New Roman"">
Замкнутая цепь называется циклом.e)<span Times New Roman"">
Замкнутая простая цепь называется простымциклом.f)<span Times New Roman"">
Граф без циклов называется ациклическим.g)<span Times New Roman"">
Для орграфов цепь называется путем, а цикл – контуром.SHAPE * MERGEFORMAT
V1 V2
V3
V4 V5
<img src="/cache/referats/20858/image022.gif" v:shapes="_x0000_s1122 _x0000_s1123 _x0000_s1132 _x0000_s1124 _x0000_s1125 _x0000_s1126 _x0000_s1127 _x0000_s1128 _x0000_s1121 _x0000_s1129 _x0000_s1130 _x0000_s1131">рис. 4. Маршруты,цепи, циклы
Пример
В графе, диаграмма которогоприведена на рис.4:
1.<span Times New Roman"">
v1, v3, v1, v4– маршрут, но не цепь;2.<span Times New Roman"">
v1, v3, v5, v2, v3, v4– цепь, но не простая цепь;3.<span Times New Roman"">
v1, v4, v3, v2, v5– простая цепь;4.<span Times New Roman"">
v1, v3, v5, v2, v3, v4, v1– цикл, но не простой цикл;5.<span Times New Roman"">
v1, v3, v4, v1– простой цикл.10)<span Times New Roman"">
Если граф имеет цикл(не обязательно простой), содержащий все ребра графа по одному разу, то такойцикл называется эйлеровым циклом.11)<span Times New Roman"">
Если граф имеетпростой цикл, содержащий все вершины графа (по одному разу), то такой циклназывается гамильтоновым циклом.12)<span Times New Roman"">
Деревом называетсясвязный граф без циклов.13)<span Times New Roman"">
Остовомназывается дерево, содержащее все вершины графа.14)<span Times New Roman"">
Паросочетанием называетсямножество ребер, в котором никакие два не смежны.15)<span Times New Roman"">
Паросочетаниеназывается максимальным, если никакоеего надмножество не является независимым.16)<span Times New Roman"">
Две вершины вграфе связаны, если существуетсоединяющая их простая цепь.17)<span Times New Roman"">
Граф, в которомвсе вершины связаны, называется связным.18)<span Times New Roman"">
Граф, состоящийтолько из изолированных вершин, называется вполненесвязным.19)<span Times New Roman"">
Длиной маршрутаназывается количество ребер в нем (с повторениями).20)<span Times New Roman"">
Расстояниеммежду вершинами uи vназывается длина кратчайшей цепи <img src="/cache/referats/20858/image024.gif" v:shapes="_x0000_i1038">геодезической.21)<span Times New Roman"">
Диаметром графаGназывается длина длиннейшей геодезической.22)<span Times New Roman"">
Эксцентриситетомвершины vв связном графе G(V,E) называется максимальное расстояние от вершины vдо других вершин графа G.23)<span Times New Roman"">
Радиусом графаGназывается наименьший из эксцентриситетов вершин.24)<span Times New Roman"">
Вершина vназывается центральной,если ее эксцентриситет совпадает с радиусом графа.25)<span Times New Roman"">
Множество центральныхвершин называется центром графа.SHAPE * MERGEFORMAT
3
2 2
3 3
3
3<span Times New Roman"">
34 4
2
3 3
<img src="/cache/referats/20858/image025.gif" v:shapes="_x0000_s1135 _x0000_s1134 _x0000_s1162 _x0000_s1150 _x0000_s1137 _x0000_s1138 _x0000_s1139 _x0000_s1140 _x0000_s1142 _x0000_s1143 _x0000_s1144 _x0000_s1145 _x0000_s1146 _x0000_s1147 _x0000_s1148 _x0000_s1149 _x0000_s1153 _x0000_s1155 _x0000_s1156 _x0000_s1157 _x0000_s1158 _x0000_s1159 _x0000_s1160 _x0000_s1161">рис.5 Эксцентриситеты вершин и центры графов (выделены).
Основныетеоремы теории графовОпираясьна приведенные выше определения теории графов, приведем формулировки идоказательства теорем, которые затем найдут свои приложения при решении задач.
Теорема1. Удвоенная сумма степеней вершин любого графа равна числу его ребер.
Доказательство.Пусть А1, А2, А3,..., An—вершиныданного графа, ap(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вершин, не могут быть одновременно вершины степени0и (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φ3+4φ4+ 5φ5+…)или 3Г<2Р, но по условию, 2Р=20, а ЗГ=21;поэтому вывод, полученный при введенном нами предположении (граф плоский),противоречит условию. Отсюда заключаем, что полный граф с пятью вершинами неявляется плоским.
Теорема11. (Теорема Понтрягина-Куратовского) Граф является плоским тогда и только тогда, когда онне имеет в качестве подграфа полного графа с пятью вершинами.
В заключение этого параграфа, на нашвзгляд, следует упомянуть то, что в нем объяснялись только основные теоремытеории графов. Их практическое применение будет рассмотрено в следующихпараграфах реферата.
Способыпредставления графов в компьютереКонструирование структур данных для представления впрограмме объектов математической модели – это основа искусства практическогопрограммирования. Далее приводится четыре различных базовых представленияграфов. Выбор наилучшего представления определяется требованиями конкретнойзадачи. Более того, при решении конкретных задач используются, как правило,некоторые комбинации или модификации указанных представлений, общее числокоторых необозримо. Но все они так или иначе основаны на тех базовых идеях,которые описаны в этом разделе.
Требования кпредставлению графовИзвестны различные способы представления графов впамяти компьютера, которые различаются объемом занимаемой памяти и скоростьювыполнения операций над графами. Представление выбирается, исходя изпотребностей конкретной задачи. Далее приведены четыре наиболее частоиспользуемых представления с указанием характеристики n(p,q) – объема памяти для каждого представления. Здесь p– число вершин, а q– число ребер.
Матрица смежностиПредставление графа с помощью квадратной булевойматрицы M, отражающей смежность вершин, называется матрицей смежности, где
<img src="/cache/referats/20858/image027.gif" v:shapes="_x0000_i1039">
Для матрицы смежности n(p,q) = O(p2).
Замечание
Матрица смежности неориентированногографа симметрична относительно главной диагонали, поэтому достаточно хранитьтолько верхнюю (или нижнюю) треугольную матрицу.
Матрица инциденцийПредставление графа с помощью матрицы H, отражающей инцидентность вершин и ребер, называется матрицей инциденций, где длянеориентированного графа
<img src="/cache/referats/20858/image029.gif" v:shapes="_x0000_i1040">
а для орграфа
<img src="/cache/referats/20858/image031.gif" v:shapes="_x0000_i1041">
Для матрицы инциденций n(p,q) = O(pq).
Списки смежностиПредставление графа с помощью списочной структуры,отражающей смежность вершин и состоящей из массива указателей на списки смежныхвершин, где элемент списка представлен структурой
N: record v: 1..p; n :↑ N end record,
называетсясписком смежности. В случаепредставления неориентированных графов списками смежности n(p,q) = O(p+2q), а в случаеориентированных графов n(p,q) = O(p+q).
Массив дугПредставлениеграфа с помощью массива структур
E: array [1..q] of record b,e: 1..p endrecord,
отражающегосписок пар смежных вершин, называется массивомребер (или, для орграфов, массивомдуг). Для массива ребер (или дуг) n(p,q) = O(2q).
Обзорзадач теории графовРазвитиетеории графов в основном обязано большому числу всевозможных приложений.По-видимому, из всех математических объектов графы занимают одно из первых меств качестве формальных моделей реальных систем.
Графы нашли применение практически вовсех отраслях научных знаний: физике, биологии, химии, математике, истории,лингвистике, социальных науках, технике и т.п. Наибольшей популярностьютеоретико-графовые модели используются при исследовании коммуникационных сетей,систем информатики, химических и генетических структур, электрических цепей идругих систем сетевой структуры.
Далее перечислим некоторые типовые задачи теорииграфов и их приложения:
— Задача о кратчайшей цепи
SYMBOL183 f «Symbol» s 10 hзамена оборудования
SYMBOL183 f «Symbol» s 10 hсоставление расписания движения транспортных средств
SYMBOL183 f «Symbol» s 10 hразмещение пунктов скорой помощи
SYMBOL183 f «Symbol» s 10 hразмещение телефонных станций
— Задача о максимальном потоке
SYMBOL183 f «Symbol» s 10 hанализ пропускной способности коммуникационной сети
SYMBOL183 f «Symbol» s 10 hорганизация движения в динамической сети
SYMBOL183 f «Symbol» s 10 hоптимальный подбор интенсивностей выполнения работ
SYMBOL183 f «Symbol» s 10 hсинтез двухполюсной сети с заданной структурнойнадежностью
SYMBOL183 f «Symbol» s 10 hзадача о распределении работ
— Задача об упаковках и покрытиях
SYMBOL183 f «Symbol» s 10 hоптимизация структуры ПЗУ
SYMBOL183 f «Symbol» s 10 hразмещение диспетчерских пунктов городскойтранспортной сети
— Раскраска в графах
SYMBOL183 f «Symbol» s 10 hраспределение памяти в ЭВМ
SYMBOL183 f «Symbol» s 10 hпроектирование сетей телевизионного вещания
— Связность графов и сетей
SYMBOL183 f «Symbol» s 10 hпроектирование кратчайшей коммуникационной сети
SYMBOL183 f «Symbol» s 10 hсинтез структурно-надежной сети циркуляционной связи
SYMBOL183 f «Symbol» s 10 hанализ надежности стохастических сетей связи
— Изоморфизм графов и сетей
SYMBOL183 f «Symbol» s 10 hструктурный синтез линейных избирательных цепей
SYMBOL183 f «Symbol» s 10 hавтоматизация контроля при проектировании БИС
— Изоморфное вхождение и пересечение графов
SYMBOL183 f «Symbol» s 10 hлокализация неисправности с помощью алгоритмов поискаМИПГ
SYMBOL183 f «Symbol» s 10 hпокрытие схемы заданным набором типовых подсхем
— Автоморфизм графов
SYMBOL183 f «Symbol» s 10 hконструктивное перечисление структурных изомеров для
производных органических соединений
SYMBOL183 f «Symbol» s 10 hсинтез тестов цифровых устройств
ЗаключениеВ работе былирассмотрены задачи из теории графов, которые уже стали классическими. Особенночасто в практическом программировании возникают вопросы о построениикратчайшего остова графа и нахождении максимального паросочетания. Известнотакже, что задача о нахождении гамильтонова цикла принадлежит к числу NP-полных, т.е. эффективный алгоритм для ее решения ненайден – приведенная программа ищет цикл методом перебора. Все задачиреализованы на языке С++, листинги которых приводятся в приложении А, примерывходных и выходных данных – в приложении Б.
Списоклитературы1.<span Times New Roman"">
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы:построение и анализ. – М: МЦНМО, 20012.<span Times New Roman"">
Н. Кристофидес. Теория графов: алгоритмический подход,Мир, 1978.3.<span Times New Roman"">
Ф.А. Новиков. Дискретная математика для программистов,Питер, 2001.4.<span Times New Roman"">
В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999.<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">Приложение А
1. Гамильтоновым циклом в графеназывается цикл, проходящий через все вершины графа ровно один раз. Для данногографа найти гамильтонов цикл, если он существует.
<span Courier New";mso-ansi-language:EN-US">#include<iostream.h>
<span Courier New";mso-ansi-language:EN-US">#include<stdio.h>
<span Courier New";mso-ansi-language:EN-US">
<span Courier New";mso-ansi-langu