Орграфы, теория и применение

Федеральноеагентство по образованию РФ
Государственноеобразовательное учреждение высшего профессионального образования«Санкт-Петербургский Государственный инженерно-экономический университет»
Филиал вг. Чебоксары

Факультетфинансов и бухгалтерского учета
 
Кафедрыфинансов и банковского дела
 
Реферат
подисциплине «Математика»
На тему: «Орграфы,теория и применение»

Выполнила:
Студентка группы 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
### 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
v2v5
Из вершин v2, v4, v5дуги не выходят (листья графа), v1 являетсяпредком v5, v5 является потомком v1 и прямым потомком v3 ит.д.
Существует тесная связь междуациклическими графами и частично упорядоченными отношениями. Частичные порядкибудут основаны скорее на отношении
Утверждения:
а) Пусть G=(V,E) — а–иклическийорграф и отношение
б) Пусть отношение
ОРИЕНТИРОВАННОЕ ДЕРЕВО T=(V,E) — э–оациклический орграф, в котором одна вершина vr in V не имеет предков и называется КОРНЕМ, а каждая другаявершина имеет ровно одного непосредственного предка. Корень соединяется с любойдругой вершиной единственным маршрутом. БИНАРНОЕ ДЕРЕВО — э–о ориентированноедерево, в котором каждая вершина имеет не более двух непосредственных потомков,т.е. delta+(v)
УРОВЕНЬ ВЕРШИНЫ — м–ксимальнаядлина маршрута от этой вершины до листа дерева.
ГЛУБИНА ВЕРШИНЫ — д–инапути от корня до этой вершины.
ГЛУБИНА ОРДЕРЕВА — д–инасамого длинного пути в Т.
Утверждение. Для полного k-арного ордерева, в котором все l листьев имеют одинаковую глубину d, справедливо следующее:
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 +
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 (полустепень захода);
Для орграфов справедливоутверждение:
Сумма полустепеней исходавсех вершин орграфа равна сумме полустепеней захода и равна числу его дуг:
SUMdelta+(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-базу.

Заключение
Теории графов применяют вразличных областях науки и техники:
Информация: двоичныедеревья играют весьма важную роль в теории информации. Предположим, чтоопределенное число сообщений требуется закодировать в виде конечныхпоследовательностей различной длины, состоящих из нулей и единиц. Есливероятности кодовых слов заданы, то наилучшим считается код, в котором средняядлина слов минимальна по сравнению с прочими распределениями вероятности.Задачу о построении такого оптимального кода позволяет решить алгоритмХаффмана.
Двоичные кодовые деревьядопускают интерпретацию в рамках теории поиска. Каждой вершине при этомсопоставляется вопрос, ответить на который можно либо «да», либо«нет». Утвердительному и отрицательному ответу соответствуют дваребра, выходящие из вершины. «Опрос» завершается, когда удаетсяустановить то, что требовалось.
Таким образом, есликому-то понадобится взять интервью у различных людей, и ответ на очереднойвопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, топлан такого интервью можно представить в виде двоичного дерева.
Химия. Еще А. Кэлирассмотрел задачу о возможных структурах насыщенных (или предельных)углеводородов, молекулы которых задаются формулой: CnH2n+2
Все атомы углеводородачетырехвалентны, все атомы водорода одновалентны. Молекула каждого предельногоуглеводорода представляет собой дерево. Если удалить все атомы водорода, тооставшиеся атомы углеводорода также будут образовывать дерево, каждая вершинакоторого имеет степень не выше 4. Следовательно, число возможных структурпредельных углеводородов, т. е. число гомологов данного вещества, равно числудеревьев с вершинами степени не больше четырех.
Таким образом, подсчетчисла гомологов предельных углеводородов также приводит к задаче о перечислениидеревьев определенного типа. Эту задачу и ее обобщения рассмотрел Д. Пойа.
Электротехника. Ещенедавно одной из наиболее сложных и утомительных задач для радиолюбителей былоконструирование печатных схем.
Печатной схемой называютпластинку из какого-либо диэлектрика (изолирующего материала), на которой ввиде металлических полосок вытравлены дорожки. Пересекаться дорожки могуттолько в определенных точках, куда устанавливаются необходимые элементы (диоды,триоды, резисторы и другие), их пересечение в других местах вызовет замыканиеэлектрической цепи.

Списокисследуемой литературы
1. Харари Ф. Теория графов. — М.:УРСС, 2003. — 300 с.
2. О. Ойстин Теория графов. — М.:УРСС, 2008. — 352 с. Альфред В. Ахо.
3. Моника С. Лам, Рави Сети, ДжеффриД. Ульман Компиляторы: принципы, технологии и инструменты, 2 издание. — 2 изд.— М.: «Вильямс», 2008.
4. ru.wikipedia.org/wiki/Орграф
5. dic.academic.ru