|
|
| Применение теории графов в информатике |
|
b>Теорема 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. (Теорема Понтрягина-Куратовского) Граф является плоским тогда и только тогда, когда он не имеет в качестве подграфа полного графа с пятью вершинами.1.4 Способы представления графов в компьютереКонструирование структур данных для представления в программе объектов математической модели - это основа искусства практического программирования. Далее приводится четыре различных базовых представления графов. Выбор наилучшего представления определяется требованиями конкретной задачи. Более того, при решении конкретных задач используются, как правило, некоторые комбинации или модификации указанных представлений, общее число которых необозримо. Но все они так или иначе основаны на тех базовых идеях, которые описаны в этом разделе.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 Язык программирования DelphiDelphi - язык и среда программирования, относящаяся к классу 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. Интерфейс программыВерхняя панель кнопок предназначена для редактирования графа.Кнопка «Загрузить» предназначена для загрузки ранее сохраненного графа из файла.Рис. 7. Кнопка «Загрузить» Кнопка «Сохранить» предназначена для сохранения графа в файл.Рис. 8. Кнопка «Сохранить»Кнопка «Переместить» предназначена для перемещения вершин графа.Рис. 9. Кнопка «Переместить»
Страницы: 1, 2, 3
|
|
|
|
© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент. |
|
|
