Реферат: Орграфы, теория и применение
Направленный граф — это
орграф, не имеющий симметричных пар ориентированных ребер.
Матрица смежностей
помеченного орграфа D определяется аналогично: Л =Л (D)—||а^-||, где а^=1, если
дуга v{V] принадлежит D, и ац=0 в противном случае. Из определения матрицы A
(D) следует, что матрицу смежностей данного графа можно также рассматривать как
матрицу смежностей симметрического орграфа. Если D — орграф с линейными
подграфами DI, » = 1, 2,. Любому графу G поставим в соответствие орграф D, в
котором вершины vt и V) соединены дугами vtVj и VjVt только в том случае, если
эти вершины смежны в G. Компоненты линейного подграфа графа G, являющиеся
отдельными ребрами, взаимно однозначно соответствуют 2-контурам линейного
подграфа орграфа D, а компоненты, являющиеся простыми циклами графа G,
соответствуют двум простым контурам орграфа D.
Далее, каждой дуге
орграфа D (F), скажем идущей из вершины fi в вершину fj, приписывается цвет,
связанный с элементом /71// группы F. Чтобы построить граф G, группа
(автоморфизмов) Г (G) которого изоморфна F, он заменяет каждую дугу fifj
орграфа D (F). Для р^г 4 не существует таких орграфов D, чтоГ(/})==А^. Для
орграфов нужно использовать редуцированную упорядоченную парную группу Sp2. По
определению группа 5р2 действует на множестве V^ как индуцированная группой Sp:
каждая подстановка а из Sp индуцирует такую подстановку а' из 5р2', что а' (i,
/) = (ai, а/) для (г,/) из 1^4 Применяя теорему Пойа к цикловому индексу группы
S[P2\ получаем многочлен dp(x), в котором коэффициент при х9 равен числу
орграфов с q ориентированными ребрами.
Свойства орграфов,
которые отличают их от графов. Сформулировав принцип ориентированной
двойственности, мы перейдем к изучению матриц, связанных с орграфами, и затем
приведем аналог матричной теоремы о деревьях в графах.
Орграфы и
соединимость
Орграф D состоит из
конечного множества V вершин и набора упорядоченных пар различных вершин. В
орграфе (ориентированным) маршрутом называется чередующаяся последовательность
вершин и дуг v9, хг, uit. Средние вершины совпадают; основной маршрут содержит
все вершины. Поскольку граф может быть либо связным, либо нет, то существуют
три различных способа определения связности орграфа и каждый из них имеет свою
собственную идиосинкразию). Ясно, что каждый сильный орграф — односторонний, а
каждый односторонний орграф — слабый, но обратные утверждения не верны.
Орграф называется
несвязным, если он даже не слабый. Заметим, что тривиальный орграф, состоящий
только из одной вершины, является (по определению) сильным, поскольку в нем нет
двух различных вершин. Сформулируем теперь необходимые и достаточные условия,
обеспечивающие орграфу одну из этих трех типов соединимости. Орграф сильный
тогда и только тогда, когда он имеет остовный замкнутый маршрут; односторонний
тогда и только тогда, когда он имеет основной маршрут; слабый тогда и только
тогда, когда он имеет основной полупуть. Для орграфа определены три типа
компонент (связности). Сильной компонентой орграфа называется максимальный
сильны л подграф, односторонней компонентой — максимальный односторонний
подграф и слабой компонентой — максимальный слабый подграф. Это, в частности,
демонстрирует способ построения по сильным компонентам орграфа D нового
орграфа, который хотя и проще D, но сохраняет некоторые его структурные
свойства. Конденсацией l) D* орграфа D называется орграф, множеством вершин
которого служит множество {Si, 52,. , Sn} всех сильных компонент орграфа D, а
дуга идет из St к Sj, если в орграфе D имеется по крайней мере одна дуга,
идущая из некоторой вершины компоненты St к вершине компоненты Sj.
Орграф и
его конденсация
Из максимальности сильных
компонент следует, что в конденсации D* любого орграфа D нет контуров.
Очевидно, что конденсация каждого сильного орграфа есть тривиальный орграф.
Можно показать, что орграф является односторонним тогда и только тогда, когда
его конденсация имеет единственный остовный путь.
Ориентированная
двойственность и бесконтурные орграфы
Орграф D', обратный к
данному орграфу D, имеет те же вершины, что и D, a дуга ии принадлежит D' тогда
и только тогда, когда дуга ии принадлежит D. Другими словами, орграф, обратный
к орграфу D, получается изменением ориентации каждой дуги орграфа D.
Для любой теоремы об
орграфах можно сформулировать соответствующую двойственную теорему, заменив
каждое понятие на обратное к нему. Бесконтурным орграфом называется орграф, не
содержащий контуров. Бесконтурный орграф содержит по крайней мере одну вершину
с нулевой полустепенью исхода. В соответствии с обозначением D' орграфа,
обратного к D, будем также отмечать штрихами двойственные результаты. Бесконтурный
орграф D содержит по крайней мере одну вершину с нулевой полустепенью захода.
Ранее было указано, что конденсация любого орграфа есть бесконтурный орграф, а
приведенные выше утверждения дают некоторую информацию о бесконтурных орграфах.
Дадим теперь несколько характеризаций орграфов. Следующие свойства орграфа D
эквивалентны: (1) D — бесконтурный орграф; (2) D* изоморфен D; (3) каждый
маршрут орграфа D есть путь; (4) вершины орграфа D можно упорядочить таким
образом, что матрица смежностей" A (D) будет верхней треугольной матрицей.
Особый интерес представляют два двойственных типа бесконтурных орграфов.
Источником в орграфе! Выходящее дерево *)—• это орграф с источником, не имеющий
полуконтуров; входящее дерево — двойственный ему орграф. Слабый орграф является
выходящим деревом тогда и только тогда, когда точно одна его вершина имеет
нулевую полустепень захода, а у всех остальных вершин полустепень захода равна
1. Слабый орграф является входящим деревом тогда и только тогда, когда точно
одна его вершина имеет нулевую полустепень исхода, а у всех остальных вершин
полустепень исхода равна 1. В функциональном орграфе каждая вершина имеет
полустепень исхода, равную 1; двойственный к нему орграф называется
контрафункциональным орграфом.
Слабый
функциональный орграф
Для слабого орграфаD
следующие утверждения эквивалентны: (1) D — функциональный орграф; (2) eD точно
один такой контур, что удаление его дуг приводит к орграфу, в котором каждая
слабая компонента является входящим деревом; (3) в D точно один такой контур,
что удаление любой его дуги приводит к образованию входящего дерева.
Минимальный набор вершин, из которого достижимы все вершины орграфа D,
называется вершинной базой орграфа. Каждый бесконтурный орграф имеет
единственную вершинную базу, состоящую из всех вершин с нулевыми полустепенями
захода. Каждый орграф имеет вершинную базу, но не каждый имеет 1-базу. Критерий
существования 1-базы у произвольного орграфа еще не найден. Каждый орграф, не
содержащий контуров нечетной длины, имеет 1-базу. Каждый бесконтурный орграф
имеет 1-базу.
Заключение
Теории графов применяют в
различных областях науки и техники:
Информация: двоичные
деревья играют весьма важную роль в теории информации. Предположим, что
определенное число сообщений требуется закодировать в виде конечных
последовательностей различной длины, состоящих из нулей и единиц. Если
вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя
длина слов минимальна по сравнению с прочими распределениями вероятности.
Задачу о построении такого оптимального кода позволяет решить алгоритм
Хаффмана.
Двоичные кодовые деревья
допускают интерпретацию в рамках теории поиска. Каждой вершине при этом
сопоставляется вопрос, ответить на который можно либо "да", либо
"нет". Утвердительному и отрицательному ответу соответствуют два
ребра, выходящие из вершины. "Опрос" завершается, когда удается
установить то, что требовалось.
Таким образом, если
кому-то понадобится взять интервью у различных людей, и ответ на очередной
вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то
план такого интервью можно представить в виде двоичного дерева.
Химия. Еще А. Кэли
рассмотрел задачу о возможных структурах насыщенных (или предельных)
углеводородов, молекулы которых задаются формулой: CnH2n+2
Все атомы углеводорода
четырехвалентны, все атомы водорода одновалентны. Молекула каждого предельного
углеводорода представляет собой дерево. Если удалить все атомы водорода, то
оставшиеся атомы углеводорода также будут образовывать дерево, каждая вершина
которого имеет степень не выше 4. Следовательно, число возможных структур
предельных углеводородов, т. е. число гомологов данного вещества, равно числу
деревьев с вершинами степени не больше четырех.
Таким образом, подсчет
числа гомологов предельных углеводородов также приводит к задаче о перечислении
деревьев определенного типа. Эту задачу и ее обобщения рассмотрел Д. Пойа.
Электротехника. Еще
недавно одной из наиболее сложных и утомительных задач для радиолюбителей было
конструирование печатных схем.
Печатной схемой называют
пластинку из какого-либо диэлектрика (изолирующего материала), на которой в
виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут
только в определенных точках, куда устанавливаются необходимые элементы (диоды,
триоды, резисторы и другие), их пересечение в других местах вызовет замыкание
электрической цепи.
Список
исследуемой литературы
1. Харари Ф. Теория графов. — М.:
УРСС, 2003. — 300 с.
2. О. Ойстин Теория графов. — М.:
УРСС, 2008. — 352 с. Альфред В. Ахо.
3. Моника С. Лам, Рави Сети, Джеффри
Д. Ульман Компиляторы: принципы, технологии и инструменты, 2 издание. — 2 изд.
— М.: «Вильямс», 2008.
4. http://ru.wikipedia.org/wiki/Орграф
5. http://dic.academic.ru
|
