Орграфы, теория и применение
Федеральное агентство по образованию РФ
Государственное образовательное учреждение высшего профессионального образования «Санкт-Петербургский Государственный инженерно-экономический университет»
Филиал в г. Чебоксары
Факультет финансов и бухгалтерского учета
Кафедры финансов и банковского дела
Реферат
по дисциплине «Математика»
На тему: «Орграфы, теория и применение»
Выполнила:
Студентка группы 32-08
Рассанова Мария
Научный руководитель:
Качевский
Дмитрий Николаевич
Чебоксары 2009
Содержание
Введение
Глава 1. Граф. Общее представление
Связность
Дополнительные определения
Применение орграфов
Глава 2. Теория графов
Определения
Способы задания графов
Связность
Планарность
Матричное представление графов
Орграфы и соединимость
Орграф и его конденсация
Ориентированная двойственность и бесконтурные орграфы
Слабый функциональный орграф
Заключение
Список исследуемой литературы
ВВЕДЕНИЕ
Актуальность темы. Теория графов предоставляет эффективные средства формализации задач из самых различных областей: экономики, физики, химии, планово-производственной практики, управления производством, сетевого и календарного планирования, информационных систем, и многих других. Одним из таких средств является ориентированный граф. Существует большое количество задач, решаемых на орграфах. Чаще всего рассматриваются задачи о достижимости (т.е. о существовании пути, связывающем две заданные вершины), о нахождении путей, обладающих какой-либо экстремальной характеристикой (например, кратчайший, или наиболее надежный путь), о случайных блужданиях, потоковая задача. Все они хорошо изучены и разработаны эффективные алгоритмы их решения. При этом предполагается, что все пути на графе являются допустимыми, т.е. не накладывается никаких ограничений на достижимость.
Наиболее известные работы в этой области принадлежат Кристофидесу Н., Басакеру Р.Д., Харари Ф., Бержу К., Дейкстре Э., Флойду Р., Замбицкому Д.К., Оре О., Саати Т., Фалкерсону Д.Р., Форду Л.Р.
В отличие от классического подхода, Басанговой Е.О. и Ерусалимским Я.М. было введено понятие ориентированных графов с нестандартной достижимостью, т.е. орграфов, в которых на допустимые пути накладываются какие-либо ограничения. В обычном ориентированном графе, для того чтобы одна вершина была достижима из другой, необходимо существование пути, связывающего две эти вершины. В случае же орграфов с нестандартной достижимостью требуется, кроме того, чтобы этот путь удовлетворял некоторому условию (ограничению). Понятно, что в этом случае классические алгоритмы решения задач на графах непосредственно неприменимы.
В работах Ерусалимского Я.М., Басанговой Е.О., Логвинова С.Ю., Скороходова В.А., Петросяна А.Г. описаны различные виды ограничений на достижимость. Так, Ерусалимским Я.М. и Басанговой Е.О. рассмотрено несколько видов достижимости на частично-ориентированных графах, на которых присутствуют ориентированные и неориентированные ребра. Введено понятие смешанной цепи, на дуги и звенья которой накладываются различные условия, в зависимости от вида ограничений. Например, рассмотрены случаи, когда в смешанной цепи два неориентированных ребра не могут следовать непосредственно друг за другом, или дуги и звенья строго чередуются.
В работах Скороходова В.А.
рассмотрены орграфы с накоплением
неубывающей магнитности
- го уровня. На таких графах допустимым
является магнитно-накопительный путь
порядка
с неубывающей магнитностью, т.е. такой
путь, что если на
- м шаге величина накопленной магнитности
не меньше
и среди выходящих дуг есть хотя бы одна
магнитная, то
- я дуга пути должна быть магнитной.
Другой вид достижимости –
вентильно-накопительная. В этом случае
множество дуг графа представляется в
виде
.
В допустимом пути прохождение по дуге
множества
делает доступными для прохождения дуги
множества
.
Также рассмотрены условия накопления
- исчезания и возрастания-убывания
магнитности, вентильная достижимость
с возрастанием-убыванием доступа и
энергии на пути, механическая достижимость.
Петросяном А.Г. определена
барьерная достижимость, при которой
множество дуг разбивается на три попарно
непересекающихся подмножества: дуг,
увеличивающих барьерный показатель,
дуг барьерного перехода и нейтральных
дуг. С каждым отрезком пути связана
числовая характеристика – барьерный
показатель частицы. Путь допускает
барьерный переход уровня
,
если к некоторому шагу он накопил
величину барьерного показателя, не
меньшую
.
Еще один вид ограничений – биполярная
магнитность. В этом случае определяется
величина накопления биполярной
магнитности. Путь считается допустимым,
если он удовлетворяет условию биполярной
магнитности уровня
.
Общим подходом к решению задач на орграфах с ограничениями на достижимость является построение вспомогательного графа, имеющего большее количество вершин, и обладающего следующим свойством: допустимому пути на исходном графе с ограничениями соответствует некоторый путь на вспомогательном графе, а недопустимому пути не соответствует ни один путь. Алгоритм построения такого графа зависит от вида вводимых ограничений. На вспомогательном графе, таким образом, все пути являются допустимыми, а дуги – равноправными, и его можно рассматривать как обычный ориентированный граф. Для графов с нестандартными достижимостями описанных видов рассмотрены классические задачи о кратчайшем пути из вершины в вершину, о максимальном потоке в сети с нестандартной достижимостью и о случайных блужданиях на таких графах. Наибольшую сложность вызывают две последние задачи, так как при построении вспомогательного графа увеличивается не только количество вершин, но и количество дуг. При этом необходимо правильно распорядится весами дуг, по которым строится несколько дуг на вспомогательном графе. Серьезного осмысления каждый раз требует и перенос соответствующего результата с вспомогательного графа на основной граф.
Цели и задачи работы. Цель состоит в изучении графов с нестандартными достижимостями, разработке алгоритмов решения задач на таких графах, описании нового класса динамических графов, программной реализации полученных алгоритмов.
Глава 1. Граф. Общее представление
В математической теории графов и информатике граф — это совокупность объектов со связями между ними.
Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами.
Неориентированный граф с шестью вершинами и семью рёбрами
Граф или неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:
V это множество вершин или узлов, E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами. V (а значит и E) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становятся ложными в случае бесконечных множеств.
Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | — порядком, число рёбер | E | — размером графа.
Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.
Два ребра называются смежными, если они имеют общую концевую вершину.
Два ребра называются кратными, если множества их концевых вершин совпадают.
Ребро называется петлёй, если его концы совпадают, то есть e = {v,v}.
Степенью degV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).
Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.
Ориентированный граф (сокращённо орграф) G — это упорядоченная пара G: = (V,A), для которой выполнены следующие условия:
V это множество вершин или узлов,
A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.
Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v w ведёт от вершины v к вершине w.
Формально, орграф D=(V, E) есть
множество E упорядоченных пар вершин
.
Дуга {u, v} инцидентна вершинам u и v. При этом говорят, что u — начальная вершина дуги, а v — конечная вершина.
Орграф, полученный из простого графа (Простой граф — граф, в котором нет кратных рёбер и петель.) ориентацией ребер называется направленным. В отличие от последнего, в произвольном простом орграфе две вершины могут соединяться двумя разнонаправленными дугами.
Направленный полный граф называется турниром. Полный граф — простой граф, в котором каждая пара различных вершин смежна. Полный граф с n вершинами имеет n(n − 1) / 2 рёбер и обозначается Kn. Является регулярным графом степени n − 1.
Связность
Маршрутом в орграфе называют чередующуюся последовательность вершин и дуг, вида v0{v0,v1}v1{v1,v2}v2…vn (вершины могут повторяться). Длина маршрута — количество дуг в нем.
Путь есть маршрут в орграфе без повторяющихся дуг, простой путь — без повторяющихся вершин. Если существует путь из одной вершины в другую, то вторая вершина достижима из первой.
Контур есть замкнутый путь.
Для полумаршрута снимается ограничение на направление дуг, аналогично определяются полупуть и полуконтур.
Орграф сильно связный, или просто сильный если все его вершины взаимно достижимы; односторонне связный, или просто односторонний если для любых двух вершин, по крайней мере одна достижима из другой; слабо связный, или просто слабый, если при игнорировании направления дуг получается связный (мульти)граф;
Максимальный сильный подграф (Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и все рёбра, инцидентные данному подмножеству. (ср. Суграф-частичный граф исходного графа — граф, содержащий все вершины исходного графа и подмножество его рёбер)) называется сильной компонентой; (Орграф называется сильно связным (strongly connected), если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Сильно связными компонентами орграфа называются его максимально сильно связные подграфы). Односторонняя компонента и слабая компонента определяются аналогично.
Конденсацией орграфа D называют орграф D*, вершинами которого служат сильные компоненты D, а дуга в D* показывает наличие хотя бы одной дуги между вершинами, входящими в соответствующие компоненты.
Дополнительные определения
Направленный ациклический граф или гамак есть бесконтурный орграф. (Направленный ациклический граф — случай направленного графа, в котором отсутствуют направленные циклы, то есть пути, начинающиеся и кончающиеся в одной и той же вершине. Направленный ациклический граф является обобщением дерева (точнее, их объединения — леса)).
Ориентированный граф, полученный из заданного сменой направления ребер на противоположное, называется обратным.
Изображение и свойства всех орграфов с тремя узлами. Легенда: С – слабый, ОС – односторонний, СС – сильный, Н – является направленным графом, Г – является гамаком, Т – является турниром.
|
0 дуг |
1 дуга |
2 дуги |
3 дуги |
4 дуги |
5 дуг |
6 дуг |
|
пустой, Н, Г |
Н, Г |
|
ОС |
CC |
CC |
полный, CC |
|
ОС, Н, Г |
CC, Н, Т |
CC |
||||
|
C, Н, Г |
ОС, Н, Г, Т |
ОС |
||||
|
C, Н, Г |
ОС |
ОС |
Применение орграфов
Орграфы широко применяются в программировании как способ описания систем со сложными связями. К примеру, одна из основных структур, используемых при разработке компиляторов и вообще для представления компьютерных программ — граф потоков данных.
Бинарные отношения
Бинарное отношение над конечным носителем может быть представлено в виде орграфа. Простым орграфом представимы антирефлексивные отношения, в общем случае требуется орграф с петлями. Если отношение симметрично, то его можно представить неориентированным графом, а орграф отношения делимости. Если антисимметрично, то направленным графом. (В математике бинарным отношением называется любое множество упорядоченных пар).
Глава 2. ТЕОРИЯ ГРАФОВ
Граф G – совокупность двух множеств: вершин V и ребер E, между которыми определено отношение инцидентности. Каждое ребро e из E инцидентно ровно двум вершинам v', v'', которые оно соединяет. При этом вершина v' и ребро e называются инцидентными друг другу, а вершины v' и v'' называются смежными. Часто пишут v', v'' из G и e из G. Если |V(G)|=n, |E(G)|=m, то граф G есть (n,m) граф, где n – порядок графа, m – размер графа.
Определения
Ребро (v',v'') может быть ориентированным и иметь начало (v') и конец (v'') (дуга в орграфе).
Ребро (v,v) называется петлей (концевые вершины совпадают).
Граф, содержащий ориентированные ребра (дуги), называется орграфом.
Граф, не содержащий ориентированные ребра (дуги), называется неографом.
Ребра, инцидентные одной паре вершин, называются параллельными или кратными.
Граф с кратными ребрами называется мультиграфом.
Граф, содержащий петли (и кратные ребра), называется псевдографом.
Конечный граф – число вершин и ребер конечно.
Пустой граф – множество ребер пусто (число вершин может быть произвольным).
Полный граф – граф без петель и кратных ребер, каждая пара вершин соединена ребром. Обозначение для полного графа с n вершинами – Kn.
Граф называется двудольным, если существует такое разбиение множества его вершин на две части, что концы каждого ребра принадлежат разным частям (долям).
Если любые две вершины двудольного графа, входящие в разные доли, смежны, то граф называется полным двудольным . Обозначение для полного двудольного графа с n и m вершинами – Kn,m.
Локальная степень вершины – число ребер ей инцидентных. В неографе сумма степеней всех вершин равна удвоенному числу ребер (лемма о рукопожатиях). Петля дает вклад, равный 2 в степень вершины.
Следствие 1 из леммы о рукопожатиях. Произвольный граф имеет четное число вершин нечетной степени.
Следствие 2 из леммы о рукопожатиях. Число ребер в полном графе n(n-1)/2.
В орграфе две локальных степени вершины v: deg(v)+ и deg(v) – (число ребер с началом и концом в v)
Графы равны, если множества вершин и инцидентных им ребер совпадают.
Графы, отличающиеся только нумерацией вершин и ребер, называются изоморфными.
Граф называется регулярным (однородным), если степени всех его вершин равны.
Способы задания графов
Матрица инцидентности A. По вертикали указываются вершины, по горизонтали – ребра. Aij=1 если вершина i инцидентна ребру j, в противном случае aij=0. Для орграфа aij=-1 если из вершины i исходит ребро j, aij=1 если в вершину i входит ребро j. Если ребро – петля, то aij=2. Список ребер. В первом столбце ребра, во втором вершины им инцидентные. Матрица смежности – квадратная симметричная матрица. По горизонтали и вертикали – все вершины. Dij= число ребер, соединяющее вершины i,j. Матрица Кирхгофа: bij=-1, если вершины i и j смежны, bij=0 если вершины i и j не смежны, bii=deg(i). Сумма элементов в каждой строке и каждом столбце матрицы Кирхгофа равна 0.
Связность
Отношение вершин графа «существует маршрут, связывающий вершины» является отношением эквивалентности, задающее разбиение графа на компоненты связности. Индекс разбиения – k.
МАРШРУТЫ, ЦЕПИ, ЦИКЛЫ
Чередующаяся последовательность v1, e1, v2, e2, … , en, vn+1 вершин и ребер графа такая, что ei =vivi+1 (i=1, n ), называется маршрутом, соединяющим вершины 1 и vn+1 (или (v1vn+1)-маршрутом). Очевидно, что для задания маршрута в графе достаточно задать последовательность v1, v2, …, vn+1. его вершин, либо последовательность e1, e2,… , en его ребер.
Вершина v называется достижимой из вершины u, если существует (u, v)-маршрут. Любая вершина считается достижимой из себя самой.
Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины, кроме, возможно, крайних, различны. Маршрут (1) называется циклическим, если v1=vn+1. Циклическая цепь называется циклом, а циклическая простая цепь – простым циклом. Число ребер в маршруте называется его длиной. Цикл длины 3 часто называют треугольником. Длина всякого цикла не менее трех, если речь идет о простом графе, поскольку в таком графе нет петель и кратных ребер. Минимальная из длин циклов графа называется его обхватом.
Маршрут – последовательность ребер, в которых каждые два соседних ребра имеют общую вершину.
Маршрут, в котором начало и конец совпадают – циклический.
Маршрут в неографе, в котором все ребра разные – цепь.
Маршрут в орграфе, в котором все дуги разные – путь.
Путь, в котором начало и конец совпадают – контур.
Цепь с неповторяющимися вершинами – простая.
Циклический маршрут называется циклом, если он цепь и простым циклом, если эта цепь простая.
Вершины связанные, если существует маршрут из одной вершины в другую.
Связанный граф – если все его вершины связаны. Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Очевидно, что для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины u и каждой другой вершины v существовал (u, v)-маршрут.
Свойства маршрутов, цепей и циклов:
1) Всякий незамкнутый (u, v)-маршрут, содержит в себе простую (u, v)-цепь. В частности, любая (u, v)-цепь, содержит в себе простую (u, v)-цепь. Причем, если (u, v)-маршрут содержит в себе вершину w (w?u и w?v), то в общем случае, простая (u, v)-цепь может не содержать в себе вершину w.
2) Всякий непростой цикл можно разбить на два или более простых. Причем для замкнутого маршрута такое утверждение не верно.
3) Всякая непростая (u, v)-цепь, может быть разбита на простую (u, v)-цепь и один или более простых циклов. Причем для незамкнутого маршрута такое утверждение не верно.
4) Для любых трех вершин u, w, v из существования (u, w)-цепи их и (w, v)-цепи, следует существование (u, v)-цепи. Причем может не существовать (u, v)-цепи, содержащей вершину w.
5) Объединение двух несовпадающих простых (u, v)-цепей содержит простой цикл.
6) Если граф содержит 2 несовпадающих цикла с общим ребром e, то после удаления этого ребра граф по-прежнему содержит цикл.
Если два графа изоморфны:
1) то они одного порядка;
2) у них одинаковое количество ребер;
3) для произвольного i,0?i?n-1, (n – порядок графов) количество вершин степени i, у обоих графов одинаковое;
4) у них совпадают обхваты;
5) у них одинаковое количество простых циклов минимальной длины (по количеству ребер).
Число ребер маршрута – его длина. Эйлеров цикл – цикл графа, содержащий все его ребра. Эйлеров граф – граф, имеющий Эйлеров цикл.
Теорема. Мультиграф обладает эйлеровой цепью тогда и только тогда, когда он связен и число вершин нечетной степени равно 0 или 2. Гамильтонов цикл – простой цикл, проходящий через все вершины.
ОРИЕНТИРОВАННЫЙ МАРШРУТ ДЛИНЫ k в орграфе из v в w в орграфе G=(V,E) – последовательность дуг вида (v,w1), (w1,w2), (w2,w3), …, (wk-1,w), т.е. конец каждой дуги, кроме последней, совпадает с началом следующей. Для упрощения маршрут удобно представлять последовательностью вершин, которые его представляют, однако следует помнить об одинаковом направлении дуг, входящих в маршрут: v, w1, w2, w3, …, wk-1,w.
ОРИЕНТИРОВАННАЯ ЦЕПЬ (ПУТЬ) – это ориентированный маршрут, в котором все дуги различны.
Маршрут называется ЦИКЛИЧЕСКИМ, если его начало и конец совпадают.
Циклический путь называется КОНТУРОМ.
Вершина w ДОСТИЖИМА из v, если существует (v,w) – путь. Орграф называется связным, если существуют пути для всех пар различных вершин графа. Матрица связи, связности, достижимости C=A(R*) определяется аналогично графам. Заметим, однако, что для орграфов отношение R* НЕ ЯВЛЯЕТСЯ ОТНОШЕНИЕМ ЭКВИВАЛЕНТНОСТИ на V и, следовательно, не осуществляет разбиения V!
Пусть «D – множество всех орграфов, а «G – множество всех графов.
Мы можем определить отображение «F: «D «G следующим образом.
Пусть G=(V,E) in «D. Тогда множество вершин F(G) in «G совпадает с V, а множество дуг F(G) определяется применением следующих операций на E:
a) удаляются все петли из Е;
б) (v,w) заменяются на [v,w] для всех (v,w) in E.
Тогда F(G) является графом, СВЯЗАННЫМ с орграфом G.
Для орграфов понятие связности является более содержательным, чем для графов. Различают три важных типа связности орграфа:
а) G СИЛЬНО СВЯЗНЫЙ, если для каждой пары различных вершин v,w in V существует маршрут из v в w и обратно.
Б) G ОДНОСТОРОННЕ СВЯЗНЫЙ, если для каждой пары различных вершин v, w in V существует маршрут из v в w или обратно.
В) G СЛАБО СВЯЗНЫЙ, если граф F(G) связный;
Очевидно, что справедливо следование:
G сильно связный G односторонне связный G слабо связный.
В)+v2+ б)+v2+ а)+v2+
v1 v3 v1 v3 v1--- v3
В терминах матрицы связности C=A(R*) орграф G сильно связный тогда и только тогда, когда Cij=1 для всех I,j in Nn; G односторонне связный тогда и только тогда, когда Cij=1 или Cji=1 для всех I,j in Nn.
Утверждение
Орграф является сильносвязным тогда и только тогда, когда в нем есть остовный циклический маршрут.
Если G=(V,E) – орграф, то можно разбить V путем определения отношения эквивалентности RO следующим образом: vROw, если v=w или существуют маршруты из v в w и обратно. Если {Vi: I in Np} – разбиение V и {Ei: I in Np, а Ei=(Vi*Vi) П E} являются соответствующими множествами дуг, то подграфы Gi=(Vi,Ei), I in Np называются СИЛЬНО СВЯЗНЫМИ КОМПОНЕНТАМИ G.
Очевидно, что RO<=R* и A(RO) может быть определено из A(R*) как A(RO)ij=A(R*)ij & A(R*)ji (& - символ операции конъюнкции); граф G связный тогда и только тогда, когда G имеет только одну сильно связную компоненту, т.е. если p=1.
### v1-----v2 |1 1 1 1| |1 0 0 0|
| | |0 1 1 0| |0 1 0 0|
| | A(R*)=|0 0 1 0| A(RO)=|0 0 1 0|
v v |0 0 1 1| |0 0 0 1|
v4-----v3 p=4
Таким образом, Gi=({vi}, Ф), I in N4, являются сильно связными компонентами заданного графа.
Путь (ориентированная цепь), содержащий все дуги орграфа, называется эйлеровым. Связный орграф называется ЭЙЛЕРОВЫМ, если в нем есть замкнутый эйлеров путь.
Теорема. Связный орграф G содержит открытый эйлеров путь тогда и только тогда, когда в нем есть две такие вершины v1, v2, что
delta+(v1)=delta-(v1)+1, delta+(v2)=delta-(v2)-1, и
delta+(v)=delta-(v) для любой вершины v, отличной от v1 и v2.
Контур (замкнутый путь) орграфа G называется ГАМИЛЬТОНОВЫМ, если он содержит все вершины орграфа G. ГАМИЛЬТОНОВ ГРАФ – это орграф, имеющий гамильтонов контур.
Распознавание гамильтоновости орграфов и построение гамильтоновых контуров так же сложны, как и для неориентированных графов. Рассмотрим одно из достаточных условий гамильтоновости орграфа.
Теорема (Мейниэл, 1973). Пусть G – сильносвязный орграф порядка n>1 без петель и параллельных дуг. Если для любой пары v и w его несовпадающих несмежных вершин справедливо неравенство
delta(v)+delta(w)>=2*n-1,
то в G есть гамильтонов контур.
Пусть G=(V,E) – АЦИКЛИЧЕСКИЙ ОРГРАФ. Вершину v in V называют ЛИСТОМ, если delta+(v)=0. Если (v,w) in E, то v является НЕПОСРЕДСТВЕННЫМ ПРЕДКОМ w, а w – НЕПОСРЕДСТВЕННЫМ ПОТОМКОМ v. Если существует маршрут из v в w, то говорят, что v является ПРЕДКОМ w, а w – ПОТОМКОМ v. Эти понятия не имеют смысла для графов, имеющих циклы, так как в этом случае вершины в цикле являлись бы потомками и предками самих себя!
+------v1-----+ v4
v2<-----------------v3----------->v5<---------v6
Из вершин v2, v4, v5 дуги не выходят (листья графа), v1 является предком v5, v5 является потомком v1 и прямым потомком v3 и т.д.
Существует тесная связь между ациклическими графами и частично упорядоченными отношениями. Частичные порядки будут основаны скорее на отношении <, чем на отношении <=, и, следовательно, являются нерефлексивными и транзитивными.
Утверждения:
а) Пусть G=(V,E) - а–иклический орграф и отношение < определяется следующим образом: v<w, если v является предком w. Тогда отношение < является частичным отношением порядка на V.
б) Пусть отношение < является частичным отношением порядка на конечном множестве V. Тогда, если E={(v,w): v<w}, то пара G=(V,E) является ациклическим графом.
ОРИЕНТИРОВАННОЕ ДЕРЕВО T=(V,E) - э–о ациклический орграф, в котором одна вершина vr in V не имеет предков и называется КОРНЕМ, а каждая другая вершина имеет ровно одного непосредственного предка. Корень соединяется с любой другой вершиной единственным маршрутом. БИНАРНОЕ ДЕРЕВО - э–о ориентированное дерево, в котором каждая вершина имеет не более двух непосредственных потомков, т.е. delta+(v)<=2 для всех v in V. Бинарное дерево является ПОЛНЫМ, если каждая вершина, не являющаяся листом дерева, имеет ровно 2 непосредственных потомка. Очевидно обобщение на k-арное дерево.
УРОВЕНЬ ВЕРШИНЫ - м–ксимальная длина маршрута от этой вершины до листа дерева.
ГЛУБИНА ВЕРШИНЫ - д–ина пути от корня до этой вершины.
ГЛУБИНА ОРДЕРЕВА - д–ина самого длинного пути в Т.
Утверждение. Для полного k-арного ордерева, в котором все l листьев имеют одинаковую глубину d, справедливо следующее:
l<=k^d; d=log(k) l.
Планарность
Плоский граф - г–аф с вершинами, расположенными на плоскости и непересекающимися ребрами. Планарный граф изоморфен плоскому. Всякий подграф планарного графа планарен. Задача о трех домах и трех колодцах. Провести от каждого из трех домов дорожки ко всем трем колодцам так, чтобы дорожки не пересекались. Граф этой задачи не является планарным. Грань графа - м–ожество всех точек плоскости, каждая пара которых может быть соединена жордановой кривой. Граница грани - м–ожество вершин и ребер, принадлежащих грани. Всякий плоский граф имеет одну, и притом единственную, неограниченную грань. Эта грань является внешней гранью графа, остальные - в–утренние.
Теорема Эйлера. Для всякого связного плоского графа n-m+f=2, где n - ч–сло вершин,m - ч–сло ребер, f - ч–сло граней. Подразбиение ребра - у–аление ребра и добавление двух новых, инцидентных вершинам удаленного ребра и соединенных между собой новой вершиной. Два графа называются гомеоморфными, если оба они могут быть получены из одного и того же графа подразбиением его ребер.
Теорема Понтрягина-Куратовского. Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных K5 и K3,3. Деревья и лес. Дерево - с–язный граф без циклов. Лес (или ациклический граф) - н–ограф без циклов (может быть и несвязным).
Теорема. Для неографа G с n вершинами без петель следующие условия эквивалентны:
G - д–рево;
G - с–язный граф, содержащий n-1 ребро;
G - а–иклический граф, содержащий n-1 ребро;
Любые две несовпадающие вершины графа G соединяет единственная цепь.
G - а–иклический граф, такой, что если в него добавить одно ребро, то в нем появится ровно один цикл.
Остов (каркас) связного графа - д–рево, содержащее все вершины графа. Определяется неоднозначно. Редукция графа - о–тов с наибольшим числом ребер. Цикломатическое (или циклический ранг) число графа ν=m-n+c, где n - ч–сло вершин,m - ч–сло ребер, c - ч–сло компонент связности графа. Коциклический ранг (или коранг) ν*=n-c.
Теорема. Число ребер неографа, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно цикломатическому числу графа.
Неограф G является лесом тогда и только тогда, когда ν(G)=0. Неограф G имеет единственный цикл тогда и только тогда, когда ν(G)=1. Остов неографа имеет ν* ребер. Ребра графа, не входящие в остов, называются хордами. Цикл, получающийся при добавлении к остову графа его хорды, называется фундаментальным относительно этой хорды.
Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Очевидно, что для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины u и каждой другой вершины v существовал (u, v)- маршрут.
Теорема. Граф G=(V,E) связен тогда и только тогда, когда множество го вершин нельзя разбить на два непустых подмножества V1 и V2 так, чтобы бе граничные точки каждого ребра находились в одном и том же множестве. Всякий максимальный связный подграф графа G называется связной компонентой (или компонентой) графа G. Слово "ма«симальный" о»начает максимальный относительно включения, т.е. не содержащийся в связном подграфе с большим числом элементов. Множество вершин связной компоненты называется областью связности. Для ориентированного графа вводится понятие ориентированного маршрута – это последовательность вида (1), в которой ei=(vi,vi+1). Аналогом цепи в этой итуации служить путь (ориентированная цепь). Аналогом цикла служит контур ориентированный цикл).
Орграф называется сильносвязным, если любые две его вершины достижимы руг из друга. Орграф называется одностороннесвязным, если для любой пары его вершин по меньшей мере одна достижима из другой. Орграф называется слабосвязным, если любые две вершины его основания соединены маршрутом. Орграф называется несвязным, если его основание несвязный псевдограф.
Теорема. Орграф является сильносвязным тогда и только тогда, когда в нем есть основной циклический маршрут.
Необходимость. Пусть G – сильносвязный орграф и T=(v0, x1, v1, ..., xn, v0) – его циклический маршрут, проходящий через максимально возможное число вершин. Если этот маршрут не является остовным, то возьмем вне его вершину v. Так как G – сильносвязный орграф, то существуют маршруты T1=(v0, y1, ..., v), T2=(v, z1, ..., v0). Но тогда циклический маршрут T’=(v0, x1, v1, ..., xn, v0, y1, ..., v, z1, ..., v0) содержит большее число вершин, чем T, что противоречит выбору маршрута T. Следовательно, T – остовной маршрут.
Достаточность. Пусть u и v – две произвольные вершины орграфа G, а T=(v0, x, ..., v, y, ..., u, z, ..., v0) – циклический маршрут. Тогда u достижима из v с помощью маршрута (v, y, ..., u) – части маршрута T, – а v из u – с помощью маршрута (u, z, ..., v0, x, ..., v).3
Теорема. Орграф является одностороннесвязным тогда и только тогда, когда в нем есть остовной маршрут.
Теорема. Орграф является слабосвязным тогда и только тогда, когда в его основание есть связный псевдограф.
Сильносвязной компонентой орграфа называется его максимальный относительно включения сильносвязный подграф.
Матричное представление графов
Орграфы и матрицы. Матрицей сложностей A (D) орграфа D называется (рхр)-матрица \\аи\\> У которой ai}=\, если vfl,— дуга орграфа D, и atj~Q в противном случае. Сумма по столбцу легко проверить, что суммы элементов по строкам матрицы A (D) равны полустепеням исхода вершин орграфа D, а суммы элементов по столбцам — полустепеням захода. Как и в случае графов, степени матрицы смежностей. А орграфа дают полную информацию о числе маршрутов, идущих из одной вершины в другую. Есть еще три матрицы, связанные с орграфом D — матрица достижимостей, матрица расстояний и матрица обходов. Матрицу достижимостей орграфа можно использовать для нахождения его сильных компонент. Формула для числа остовных входящих деревьев данного орграфа была найдена BOTTOM и Мейберри, а доказана Таттом. Чтобы сформулировать этот результат, известный как матричная теорема о деревьях для орграфов, введем еще матрицы, связанные с D. Для каждого помеченного орграфа D алгебраическое дополнение любого элемента 1-й строки матрицы Mod равно числу остовных входящих деревьев, у которых вершина vt является стоком. Для каждого помеченного орграфа D алгебраическое дополнение любого элемента j-го столбца матрицы Mid равно числу остовных выходящих деревьев, у которых вершина Vj является источником. Эйлеров контур в орграфе D — это замкнутый остовный маршрут, в котором каждая дуга орграфа D встречается по одному разу. Орграф называется эйлеровым, если в нем есть эйлеров контур. Для графов, можно легко показать, что слабый орграф D эйлеров тогда и только тогда, когда у каждой его вершины полустепень захода равна полустепени исхода. Сформулируем теперь теорему, в которой дается формула для числа эйлеровых контуров в эйлеровых орграфах. Эту теорему можно доказать очень изящно с помощью матричной теоремы о деревьях для орграфов; В эйлеровом орграфе число эйлеровых контуров равно с \\ (d,-—1)! Заметим, что для эйлерова орграфа МоА=М\А и все суммы и по строкам, и по столбцам равны нулю, так что все алгебраические дополнения равны между собой. Первый орграф с тремя вершинами называется транзитивной тройкой, второй — циклической тройкой.
Орграф называется строго слабым, если он слабый и не односторонний; строго односторонним, если он односторонний и не сильный. Пусть С0— класс всех несвязных орграфов, GI— класс всех строго слабых орграфов, С2— класс всех строго односторонних орграфов и Ся— класс всех сильных орграфов. Тогда максимум и минимум числа q дуг среди всех орграфов с р вершинами, относящихся по соединимости к категории С;, i=0, 1, 2, 3,. Орграф, являющийся декартовым произведением DjXZ^ двух орграфов, имеет VjX У2 в качестве множества вершин, и вершина («j, и2) смежна к вершине (уь у2) тогда и только тогда, когда или [ui=0i и u, adj гл2], или \u. Если орграф D относительно соединимости находится в категории С„, то будем писать c(D)=n. Ни один строго слабый орграф не содержит вершину, удаление которой приводит к сильному орграфу.
Реберный орграф L(D) имеет множество всех дуг данного орграфа D в качестве множества вершин, и две его вершины х и у смежны тогда и только тогда, когда дуги х к у порождают маршрут в орграфе D. Выразить число вершин и число дуг орграфа L(D) через соответствующие величины орграфа D. Реберный орграф L (D) слабого орграфа D изоморфен самому орграфу D тогда и только тогда, когда D или D' — функциональный орграф. Если D — несвязный орграф, то утверждение, содержащееся в предыдущем упражнении, не верно. Пусть S и Т — непересекающиеся множества вершин орграфа D, а X (S, Т) — множество всех дуг, идущих из S в Т. Орграф D реберный тогда и только тогда, когда не существует множеств 5 и Т, имеющих по две вершины и таких, что \Х (S,T)|=3. Число эйлеровых путей орграфа D равно числу гамильтоновых контуров реберного орграфа L(D]. Пусть орграф 7\ состоит из одной вершины с двумя ориентированными петлями. Пусть T2=L(T1) — реберный орграф (здесь, если быть более точным, нужно использовать термин «псевдоорграф») орграфа Тг, определенный естественным образом; рекурсивно определяется Tn=L(Tn,l). (Такие орграфы Т„ известны под названием «телетайпных диаграмм».) Тогда число эйлеровых путей в орграфе Т„ равно 22""1-1. Каждый орграф, у которого id (v)^p/2, od (v)^p/2 для любой вершины v, гамильтонов.
Рассмотрим орграфы, у которых для любой вершины и сумма ^d(u, v) расстояний от этой вершины до всех остальных постоянна. Найти среди этих орграфов орграф, не являющийся вершинно-симметрическим. Орграф D, его дополнение D и обратный к нему D' имеют одну и ту же группу (автоморфизмов). Пусть А—матрица смежностей реберного орграфа полного симметрического орграфа.
Два орграфа называются коспектральными, если их матрицы смежностей имеют один и тот же характеристический многочлен. Существуют в точности три различных коспектральных сильных орграфа с четырьмя вершинами.
Орграф, называемый конъюнкцией D=Dl/\D2 двух орграфов Z)j и D2, имеет в качестве множества вершин K=V1XV2, и вершина u=(u1, ы2) смежна к вершине v=(v-L,v2) тогда и только тогда, когда %adj г,^ в орграфе Dl и ы2 adj v.
Матрица смежностей А конъюнкции D=Dl/\D2 есть тензорное произведение матриц смежностей орграфов D1 и D2. Пусть Dl и D2— два орграфа, a d,-— наибольший общий делитель длин всех простых контуров орграфа D,-, t=l,2. Конъюнкция Dlf\D^ является сильным орграфом тогда и только тогда, когда Ог и D2 — сильные орграфы, a d1 и d2 взаимно просты.
Орграф называется примитивным, если какая-нибудь степень его матрицы смежностей целиком состоит из положительных чисел. Орграф примитивен тогда и только тогда, когда длины его простых контуров имеют наибольший общий делитель, равный 1. Пусть D — примитивный орграф. Аналогично для вершин и и v орграфа из и в v. Исключение составляют (3,3)-орграф и (4,6)-орграф. П2, составленной Обершельпом , приведены числа орграфов с р вершинами, Эти числа вычислены с помощью соотношения (15. L(D) реберный орграф орграфа D.
ОРИЕНТИРОВАННЫЙ ГРАФ (ОРГРАФ) G есть пара G=(V,E), где V - к–нечное множество вершин, а E - п–оизвольное подмножество V*V – множество ориентированных (направленных) ребер (дуг). Предложения.
а) Ориентированный граф G=(V,E) определяет отношение на V.
б) Пусть V - к–нечное множество. Тогда отношение на V определяет ориентированный граф, у которого множество вершин - V–
Доказательство.
а) Как и в случае неориентированных графов, определим R(E) следующим образом: vR(E)w тогда и только тогда, когда (v,w) in E. Очевидно, что R(E) - о–ношение.
б) Если R - о–ношение на V, то ориентированный граф G=(V,E), определяемый R, имеет множество дуг Е, где (v,w) in E тогда и только тогда, когда vRw.
Направление дуги обозначают порядком в V*V; если (v,w) in E, то говорят, что дуга выходит из v и входит в w. На диаграмме в этом случае для указания направления используют стрелки.
Матрицу смежности A для орграфа определим следующим образом:
Aij=1, если дуга (vi,vj) in E, 0 в противном случае.
### Пусть G=({v1, v2, v3},{(v1,v2), (v2,v3), (v3,v1)}). Тогда матрица смежности и изображение орграфа имеют вид:
\ | /-------->+
1 1 1 +<---------v1<--------+ |
0 0 1 | | /
1 0 0 v2------------------->v3
Поскольку реберное отношение для орграфа не обязательно нерефлексивно или симметрично, то вообще говоря, не обязательно, чтобы А=А^T или Aii=0. Дуги типа (v,v) называют ПЕТЛЕЙ.
СТЕПЕНЬ ВЕРШИНЫ v in V, может быть записана в виде суммы
delta(v)=delta+(v)+delta-(v),
где delta+(v) - чис–о дуг, выходящих из v (полустепень исхода);
delta-(v) - чис–о дуг, входящих в v (полустепень захода);
Для орграфов справедливо утверждение:
Сумма полустепеней исхода всех вершин орграфа равна сумме полустепеней захода и равна числу его дуг:
SUM delta+(v)=SUM delta-(v)=|E|.
v in V v in V
Определим матрицу инцидентности I орграфа. Пусть G=(V,E) - орг–аф, |V|=n, |E|=m. Если перенумеровать некоторым образом дуги, то матрица инцидентности - бин–рная n*m матрица вида:
| 1, если вершина vk является началом дуги el;
Ikl=| -1, если вершина vk является концом дуги el;
| 0, если вершина vk и дуга el не инцидентны.
Орграфы изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга последовательностью одинаковых перестановок строк и столбцов.
Пусть G –помеченный граф порядка n, VG={1, 2, ... , n}. Определим бинарную n×n- матрицу A=A(G), положив
1, {i, k } ∈ EG
Aik = .
0, {i, k } ∉ EG
A(G) называется матрицей смежности графа G. Это симметричная матрица с нулями на диагонали. Число единиц в строке равно степени соответствующей вершины. Очевидно, что соответствие G→A(G) определяет биекцию множества помеченных графов порядка n на множество бинарных симметричных n×n- матриц с нулевой диагональю. Аналогично определяются матрицы смежности A мульти- и псевдографов: Aik равно числу ребер, соединяющих вершины i и k (при этом петля означает два ребра). Также определяется матрица смежности A(G) ориентированного графа.
Очевидно, что если A(G) – матрица смежности орграфа G порядка n, то
n n
∑ Aik = d + ( i ) , ∑A i =1
k =1 ik = d − (i ),
I.е. число единиц в i-й строке матрицы A(G) равно полустепени исхода i-й вершины, а число единиц в k-м столбце равно полустепени захода k-й вершины.
Теорема. Графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одинаковыми перестановками строк и столбцов.
Теорема верна также для мультиграфов, псевдографов и орграфов.
Пусть G – (n, m)-граф, VG={1, 2, ... , n} EG={e1, e2, ... , em}. Определим бинарную n×m- матрицу I=I(G) условиями
1, если вершина k и ребро ei инцидентны I ki =
0, если вершина k и ребро ei не инцидентны
Матрица I называется матрицей инцидентности графа G. В каждом её столбце ровно две единицы, равных столбцов нет. Как и выше, соответствие G→I(G) является биекцией множества помеченных (n, m)-графов с занумерованными ребрами на множество n×m- матриц, удовлетворяющих описанным условиям.
Матрица инцидентности I для орграфа:
1 − если вершина k является началом дуги
I ki = −1 − если вершина k является концом дуги
0 − если вершины k и i не смежны
Теорема. Графы изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга произвольными перестановками строк и столбцов.
Теорема верна также для мультиграфов, псевдографов и орграфов.
Свойства матриц смежности и инцидентности:
1) Сумма элементов матрицы A(G), где G=(V, E) – мультиграф, V={v1, v2, ..., vn}, по i-й строке (или по i-му столбцу) равна δ(vi).
2) Сумма элементов матрицы A(G), где G=(V, E) – ориентированный псевдограф,
V={v1, v2, ... , vn}, по i-й строке и по i-му столбцу соответственно равны δ+(vi), δ– (vi).
3) Пусть G – ориентированный мультиграф с непустым множеством дуг. Тогда:
а) сумма строк матрицы I(G) является нулевой строкой;
б) любая строка матрицы I(G) является линейной комбинацией остальных строк;
в) ранг матрицы I(G) не превосходит n–1;
г) для любого контура матрицы G сумма столбцов матрицы I(G), соответствующих дугам, входящим в этот контур, равна нулевому столбцу.
4) Пусть G – мультиграф с непустым множеством ребер. Тогда при покоординатном сложении по модулю 2:
а) сумма строк матрицы I(G) является нулевой строкой;
б) любая строка матрицы I(G) является суммой остальных строк;
в) для любого цикла в G сумма столбцов матрицы I(G), соответствующих ребрам, входящим в этот цикл, равна нулевому столбцу.
Для того чтобы подсчитать все варианты, которые могли бы здесь возникнуть, заметим, что можно рассматривать или граф G, или ориентированный граф (орграф) D, в котором разделяются. Сеть N можно определить как граф или орграф, рассматриваемый вместе с функцией, приписывающей каждому ребру некоторое положительное действительное число. Если G — произвольный планарный (р, орграф и р^З, то а^Зр — 6. Ориентированный граф, или орграф, D состоит из конечного непустого множества V вершин и заданного набора X упорядоченных пар различных вершин.
Направленный граф — это орграф, не имеющий симметричных пар ориентированных ребер.
Матрица смежностей помеченного орграфа 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-базу.
Заключение
Теории графов применяют в различных областях науки и техники:
Информация: двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.
Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось.
Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.
Химия. Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой: CnH3n+2
Все атомы углеводорода четырехвалентны, все атомы водорода одновалентны. Молекула каждого предельного углеводорода представляет собой дерево. Если удалить все атомы водорода, то оставшиеся атомы углеводорода также будут образовывать дерево, каждая вершина которого имеет степень не выше 4. Следовательно, число возможных структур предельных углеводородов, т. е. число гомологов данного вещества, равно числу деревьев с вершинами степени не больше четырех.
Таким образом, подсчет числа гомологов предельных углеводородов также приводит к задаче о перечислении деревьев определенного типа. Эту задачу и ее обобщения рассмотрел Д. Пойа.
Электротехника. Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.
Печатной схемой называют пластинку из какого-либо диэлектрика (изолирующего материала), на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы и другие), их пересечение в других местах вызовет замыкание электрической цепи.
Список исследуемой литературы
1. Харари Ф. Теория графов. — М.: УРСС, 2003. — 300 с.
2. О. Ойстин Теория графов. — М.: УРСС, 2008. — 352 с. Альфред В. Ахо.
3. Моника С. Лам, Рави Сети, Джеффри Д. Ульман Компиляторы: принципы, технологии и инструменты, 2 издание. — 2 изд. — М.: «Вильямс», 2008.
4. http://ru.wikipedia.org/wiki/Орграф
5. http://dic.academic.ru