Понятие изоморфизма для графов имеет наглядное толкование. Представим рёбра графов эластичными нитями, связывающими узлы – вершины. Тогда, изоморфизм можно представить как перемещение узлов и растяжение нитей.
Теорема 1.
Пусть задан граф G=(V;E),где V - множество вершин, E - множество рёбер, тогда 2[E]=?(V), т.е. удвоенное количество рёбер равно сумме степеней вершин.
Теорема 2. (Лемма о рукопожатиях)
В конечном графе число вершин нечетной степени чётно.
Теорема 3.
Граф связен тогда и только тогда, когда множество его вершин нельзя разбить на два непустых подмножества так, чтобы обе граничные точки каждого ребра находились в одном и том же множестве.
Расстоянием между двумя вершинами связного графа называется длина кратчайшей цепи, связывающей эти вершины (в количестве рёбер).
Свойства связных графов.
1. Связный граф остается связным после удаления ребра тогда и только тогда, когда это ребро содержится в цикле.
2. Связный граф , имеющий К вершин , содержит по крайней мере К-1 ребро.
3. В связном графе любые две простые цепи максимальной длины имеет по крайней мере одну общую вершину.
4. В графе с N вершинами и К компонентами связности число рёбер не превышает 1/2(N-K)(N-K+1).
5. Пусть у графа G есть N вершин . Пусть D(G)- минимальная из степеней вершин этого графа . Тогда D(G) > 1/2 (N-1).
Связный граф без циклов называется деревом.
Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярные генеалогические деревья. Пример(генеалогическое дерево): На рисунке показано библейское генеалогическое дерево.
Эквивалентные определения дерева.
1. Связный граф называется деревом, если он не имеет циклов.
2. Содержит N-1 ребро и не имеет циклов.
3. Связный и содержит N-1 ребро.
4. Связный и удаление одного любого ребра делает его несвязным.
5. Любая пара вершин соединяется единственной цепью.
6. Не имеет циклов и добавление одного ребра между любыми двумя вершинами приводит к появлению одного и только одного цикла.
1
Раскраска графов
Раскраской графа G = (V,E) называется отображение D: V( N . Раскраска называется правильной, если образы любых двух смежных вершин различны: D (U) ? D (V), если (U,V) ( I. Хроматическим числом графа называется минимальное количество красок, необходимое для правильной раскраски графа.
Теорема 5.
Граф является планарным тогда и только тогда, когда он не содержит подграфа, изоморфного одному из следующих (графы Понтрягина - Куратовского).
Граф К33
Граф К5
Свойство: В любом планарном графе существует вершина, степень которойявляется ориентированным графом, |V| = n, |E| = m. В целях упрощения изложения и избежания вырожденных случаев при оценке сложности алгоритмов будем исключать ситуации, при которых «большинство» вершин изолированные.
Будем также предполагать, что веса дуг запоминаются в массиве A[u, v], u, v ? V (A[u, v] содержит вес a (u, v)).
Кратчайшие пути от фиксированной вершины
Большинство известных алгоритмов нахождения расстояния между двумя фиксированными вершинами s и t опирается на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов дуг A[u, v], u, v ? V, вычисляются некоторые верхние ограничения D[v] на расстояния от s до всех вершин v ?V. Каждый раз, когда мы устанавливаем, что
D[u] + A[u, v] < D[v], оценку D[v] улучшаем: D[v] = D[u] + A[u, v].
Процесс прерывается, когда дальнейшее улучшение ни одного из ограничений невозможно.
Легко можно показать, что значение каждой из переменных D[v] равно тогда d (s, v) - расстоянию от s до v.
Заметим, что для того чтобы определить расстояние от s до t, мы вычисляем здесь расстояния от s до всех вершин графа.
Не известен ни один алгоритм нахождения расстояния между двумя фиксированными вершинами, который был бы существенным образом более эффективным, нежели известные алгоритмы определения расстояния от фиксированной вершины до всех остальных.
Описанная общая схема является неполной, так как она не определяет очередности, в которой выбираются вершины u и v для проверки условия минимальности расстояния. Эта очередности, как будет показано ниже, очень сильно влияет на эффективность алгоритма. Опишем теперь более детально методы нахождения расстояния от фиксированной вершины, называемой источником, его всегда будем обозначать через s, до всех остальных вершин графа.
Сначала представим алгоритм для общего случая, в котором предполагается только отсутствие контуров с отрицательной длиной. С эти алгоритмом обычно связывают имена Л.Р. Форда и Р.Е. Беллмана.
3. Программа определения кратчайшего пути в графе
1 3.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 3.2. Программа «Определение кратчайшего пути в графе»
Программа «Определение кратчайшего пути в графе» разработана в среде «Delphi», работает под ОС «Windows»-95,98,2000,NT.
Программа позволяет вводить, редактировать, сохранять графы в файл, загружать из файла. Также реализован алгоритм нахождения кратчайшего пути.
Интерфейс программы имеет следующий вид: [pic]
Верхняя панель кнопок предназначена для редактирования графа.
Кнопка «Загрузить» [pic] предназначена для загрузки ранее сохраненного графа из файла.
Кнопка «Сохранить» [pic] предназначена для сохранения графа в файл.
Кнопка «Переместить» [pic] предназначена для перемещения вершин графа.
Кнопка «Удалить» [pic] предназначена для удаления вершин графа.
При нажатии на кнопку «Новый» [pic] рабочее поле программы будет очищено и появится возможность ввода нового графа.
Кнопка «Помощь» [pic] вызывает помощь программы.
Для очистки результатов работы алгоритма определения кратчайшего пути в графе необходимо нажать кнопку «Обновить» [pic].
При нажатии на кнопку «Настройки» [pic] на экране появится окно, в котором можно настроить параметры сетки рабочего поля программы и цвета вводимого графа.
Окно настроек выглядит следующим образом:
[pic]
Нижняя панель кнопок предназначена для установки параметров ввода и запуска алгоритма определения кратчайшего пути в графе. Данная панель состоит из четырех кнопок:
При включенной кнопке «Показывать сетку» [pic] отображается сетка для удобства ввода вершин.
Для автоматического ввода длины ребра графа необходимо нажать кнопку [pic].
При включенной кнопке «Выравнивать по сетке» [pic] новые вершины будут автоматически выравниваться по координатной сетке.
Если выбрать две различные вершины (щелчком левой кнопки мыши) и нажать на кнопку [pic], то программа найдет кратчайший путь между вершинами.
Алгоритм определения кратчайшего пути между вершинами графа описан следующим модулем программы:
Страницы: 1, 2, 3, 4
