Лекции Русакова, страница 7

2.1. Полные графы.Определение.Рёбра у которых обе концевые точки совпадают L = (a, a ) называютсяпетлёй. Петля обычно считается не ориентированной.50Определение.Для каждого графа G существует обратный граф G*, получаемыйизменением ориентации каждого из рёбер G на противоположную.Определение.Граф называется плоским, если он может быть изображён на плоскоститак, что все пересечения рёбер являются вершинами G.Рис. 2.2 Плоский и не плоский граф.2.02. Планарные графы.Определение.Планарный граф — это граф, который может быть изображён наплоскости без пересечения рёбер.Теорема Понтрягина-Куратовского.Граф планарен тогда и только тогда, когда не содержит подграфов,гомеоморфных (топологически эквивалентных) K 5 и K 3,3 .51K 5 , полный граф с 5 вершинамиK 3,3 граф иллюстрирующий задачу отрёх колодцахКритерий непланарности:Достаточное условие — если граф содержит двудольный подграфK 3,3 или полный подграф K 5 ,то он является не планарным.Необходимое условие — если граф не планарный, то он долженсодержать больше четырёх (4) вершин, степень которых больше трёх (3) илибольше пяти (5) вершин степени больше двух (2).2.03.

Локальные степени графа. Части и подграфы.Определение.Пусть G — неориентированный граф. Число рёбер, инцидентныходной вершине а, будем обозначать ρ (a ) . Это число называется локальнойстепенью или просто степенью графа в вершине а.Так же существует понятие локальной степени и для ориентированногографа. Это обозначается, как ρ (a ) и ρ * (a ) числа рёбер, соответственновыходящих из вершины а и входящих в а.Теорема: В конечном графе число вершин нечётной степени чётно.Определение.52Граф Н называется частью графа G, H ⊂ G, если его множество вершинV (H ) содержится в множестве вершин V (G ) графа b, и все рёбра Н являютсярёбрами G.Нуль-граф считается частью каждого графа.Определение.Граф G1 = (V1 , E1 ) называют подграфом графа G = (V , E ) то естьG1 ⊆ G , если V1 ⊆ V и E1 ⊆ E .Определение.Для любой части Н графа G существует единственная дополнительнаячасть (дополнение) H , состоящая из всех рёбер графа G, которые непринадлежат Н, то есть H = G − H .2.04.

Бинарные отношения в теории графов.Определение.Бинарное отношение ρ определяется как соотношение aρb , котороевыполняется для некоторых пар элементов заданного множества V.Между бинарными отношениями и графами с однократными рёбрамисуществует взаимно однозначное соответствие.Так, например. Нуль — граф отвечает нулевому отношению a0b .Полный граф UКаждоеотвечает универсальному отношению aUb .отношениеρимеет дополнительное отношение,илиотрицание ρ , такое что a ρb тогда и только тогда, когда aρb невыполняется.53Определение.Граф()()GρявляетсядополнениемкГрафуG (ρ ) ,тоестьG ρ = U (V ) − G (R ) по отношению к полному графу U , определённому на V.Определение.Для любого отношения ρ существует обратное отношение ρ * , такоечто bρ * a тогда и только тогда, когда выполняется aρb .Определение.Отношение a ≥ b называется частичным упорядочением, если онообладает следующими свойствами:1.

Рефлексивность a ≥ a .2. Транзитивность. Из a ≥ b и b ≥ c , следует a ≥ c .3. Антисимметричность. Из a ≥ b и b ≥ a следует a = b .Соответствующий граф транзитивен, имеет петли, и любые двевершины в нём соединены не более чем одним ребром.Например:2.05. Матрицы смежности и инцидентности.Во многих задачах теории графов (особенно решаемых на ЭВМ) графыудобно описывать матрицами.54Определение.Пусть G ( X ,U , f ) — помеченный конечный граф с n вершинами и mдугами (дуги тоже занумерованы).Матрицей смежности графа G называется матрица A(G ) размераn × n , определённая следующим образом:( A(G ))i , j1, если существует дуга из i - ой вершины в j - ю=0, в противном случаеОпределение.Матрицей инцидентности графа называется матрица B (G ) размераn × m , определённая следующим образом:(B(G ))i , j1, если i - я дуга заканчивается в j - ой вершине; − 1, если i - я дуга начинается в j - ой вершине;=2, {уcловный знак петли}, если петля; 0, в противном случае.В случае неориентированного графа матрица B (G ) определяетсяследующим:(B(G ))i , j1, если i - я дуга инцидентна в j - ой вершине;=  2, {уcловный знак петли}, если петля; 0, в противном случае.Пример.Неориентированные и ориентированные графы G и G0 можнопредставить в аналитической форме, либо матрицей смежности A , либоматрицей инцидентности B .55v4v4v3v3e2e2v2v1e1v2e5e3v5e4v1e3e1e5v5e4e6e6а) Граф Gv101A(G ) = 000v210201v302001б) Граф G0v400000v501101v1v2v3v4v5v110B (G ) =  0000v2111v3011v4000100100000v50001 1 2 e1e2e3e4e5e6Матрица смежности ( A ) для неориентированного графа ( G ) всегдасимметрична.Фигурирующая в ней двойка (2) или любое другое обозначение внекоторых случаях может быть заменена на единицу(1).В матрице инцидентности сумма единиц по столбцам указываетстепень вершины vi .v100A(G0 ) = 000v21v30v40010010010000v50 1 0 0 1 v1v2v3v4v5v1 v 2 v 3 v 4 v50  1 −1 0 001100−1 B (G ) = 0 − 1 1 010 0−1 000 −1 01 0 0 Петля 0 056e1e2e3e4e5e6В общем случае матрица смежности для ориентированного графа ужене будет симметричной.В матрице инцидентности ставится 1, если дуга исходит из вершиныи − 1, если дуга заходит в неё.Иногда, особенно графов с большим количеством вершин и дуг, вместоматриц смежности и инцидентности используются списковые структурыхранения элементов на их основе.2.06.

Маршруты, цепи и простые цепи.Определение.Маршрутом в графе G называется такая конечная или бесконечнаяпоследовательность рёберS = ( , E 0 , E1 ,  , E n , ) , что каждые двасоседних ребра E i и E i +1 имеют общую концевую точку. То есть , E 0 = (a 0 , a1 ),  , E1 = (a1 , a 2 ),  , E n = (a n , a n +1 ),  .Замечания.1. Одно и тоже ребро E i может встречаться в маршруте несколько раз.2. Если нет рёбер, предшествующих E 0 , то a 0 называется начальнойвершиной S , а если нет рёбер, следующих за E n −1 , то a n называетсяконечной вершиной S .3. Любая вершина a i , принадлежащая двум соседним рёбрам E i и E i +1 ,называется внутренней или промежуточной вершиной.

Так как рёбра ивершины в маршруте могут повторяться, внутренняя вершина может такжеоказаться начальной или конечной вершиной.Определение.57Определение.Если маршрут имеет начальную вершину, но не имеет конечнойвершины или если он имеет конечную вершину, но не имеет начальной, то онназывается односторонне бесконечным.Определение.Если маршрут не имеет ни начальной, ни конечной вершины, то онназывается двусторонне-бесконечным.Определение.Маршрут называется цепью, а циклический маршрут — циклом, есликаждое его ребро встречается в нём не более одного раза, а вершины в цепимогут повторяться и несколько раз.Любой участок цепи есть цепь.Определение.Нециклическая цепь называется простой цепью, если в ней нетповторяющихся вершин.Определение.Цикл с концом a 0 называется простым циклом, если a 0 не является внём промежуточной вершиной и никакие другие вершины не повторяются.Участок простой цепи или простого цикла есть простая цепь.582.07.

Транспортные сетиТранспортной сетью называется орт граф D = (u , x )U = {υ1 , υ 2 ,..., υ n } для которого выполняются условия:1) ∃ одна и только одна вершина называется источником D −1 (υ1 ) = 0D −1 (υ1 ) множество дуг заходящих в точку υ2) ∃ -//- верш . υ называется истоком т.ч. D(υ n ) = 03) Каждой дуге x ∈ X сопоставляется число (целое и не отрицательное)т.ч.

C( x ) = 0 называемое пропускной способностью дуги4)ВершиныотличныеотисточникаиистоканазываютсяпромежуточнымиОпределение.Функция ϕ( x ) определенная на множестве X граф D и принимающаяцелочисленные значения называется потоком транспортной сети D, если0 ≤ ϕ ( x) ≤ C ( x)1) для ∀ дуги x ∈ X2) для ∀ промежуточной дуги x2,5) для ∀ промежуточной вершины υ∑ ϕ(ω, υ) = ∑ ϕ(υ, ω)ω ∈ D −1 (υ) ω ∈ D(υ)Сколько вышло столько и вошло.∑ ϕ(υ , υ) = ∑ ϕ(υ , υ11n)=ϕυ ∈ D(υ1 ) υ ∈ D −1 (υ n )Определение.x ∈ X называется насыщенным, если поток по ней равен ее пропускнойспособности ϕ( x ) = C( x )Определение.59поток ϕ называется полным, если его путь из υ1 в υ n содержит хотябы одну насыщенную дугуОпределение.Поток называется максимальным, если ϕпринимает максимальноезначение по сравнению с другим допустимым потоком.Замечание.Максимальный поток является полным, но обратно не верно.Алгоритм построения полного потока1) ϕ( x ) = 0 x ∈ X2) из D′ удаляем дуги являющиеся насыщенными D′ → D′3) ищем в D′ простую цепьη : υ1 → υ n , если не находим, то конец.ϕ - искомый поток по определению4) Увеличим поток по всем дугам на одинаковую величину т.ч.

хотя быодна дуга из η является насыщенной, потоки по остальным не превышаютих пропускных способностей2.08. Связность. Компоненты связностиОпределение.Подграфом графа G называется граф, все вершины и ребра которогосодержатся среди вершин и ребер графа G. (Для орграфа то же).Определение.Подграф называется собственным, если он отличен от самого графа.60Определение.Говорят, что вершина w орграфа D (графа G) достижима из верш. v, еслилибо w=v, либо существует путь (маршрут) из v в w.Определение.Граф (орграф) называется связным (сильно связным), если для любыхдвух его вершин v, w существует маршрут (путь), соединяющий v и w.Определение.Орграф называется односторонне связным, если для любых двух еговершин по крайней мере одна достижима из другой.Определение.Псевдографом, ассоциированным с ориентированным псевдографомD=(V,X) наз. псевдограф G=(V,X0), в котором X0 получается из X заменойвсех упорядоченных пар (v,w) на неупорядоченные {v,w}.Определение.Орграф наз слабо связным, если связным является ассоциированный сним псевдограф.Определение.Если граф (орграф) не является связным (слабо связным), то он наз.несвязным.61Определение.Компонентой связности графа G (сильной связности орграфа D) наз.

егосвязный (сильно связный) подграф, не являющийся собственным подграфомникакого другого связного (сильно связного) подграфа графа G (орграфа D).Примеры.2.09. Матрицы достижимости и связностиПусть A(D) – матрица смежности ориентированного псевдографаD=(V,X) (или псевдо графа G=(V,X)), где V={v1,…, vn}. Обозначим черезAk=[a(k)ij] k-ю степень матрицы смежности A(D).Утверждение.Элемент a(k)ij матрицы Ak ориентированного псевдографа D=(V,X)(псевдографа G=(V,X)) равен числу всех путей (маршрутов) длины k из viв v j.ДоказательствоДля k=1 очевидно в силу построения матрицы A(D).Пусть это справедливо для n=k-1. Т.е. в матрице Ak-1 в i-той строке на lтом месте стоит число, означающее кол-во маршрутов из vi в vl длины k−1.Столбец под номером j матрицы A содержит числа, означающие кол-во дуг(ребер) из vl в vj (l-номер строки).