Новиков Ф.А. Дискретная математика для программистов (860615), страница 47
Текст из файла (страница 47)
В цепи v0,ei,...,ek,Vk вершины vq И VKназываются концами цепи. Говорят, что цепь с концами uwv соединяет вершиныи и v. Цепь, соединяющая вершины и и г>, обозначается (и, v). Если нужно указатьграф G, которому принадлежит цепь, то добавляют индекс: (u,v)G. Нетруднопоказать, что если есть какая-либо цепь, соединяющая вершины и и v, то естьи простая цепь, соединяющая эти вершины. Замкнутая цепь называется циклом-,замкнутая простая цепь называется простым циклом.
Число циклов в графе Gобозначается z(G). Граф без циклов называется ациклическим.ЗАМЕЧАНИЕДля псевдографов обычно особо оговаривают, считаются ли петли циклами.Для орграфов цепь называется путем, а цикл — контуром. Путь в орграфе изузла и в узел v обозначают (и, v).ПримерВ графе, диаграмма которого приведена па рис. 7.8:1) VI, V3, Vl, V4 — маршрут, но не цепь;2) VI, V3, V5, V2> V3, V4 — цепь, но не простая цепь;3) VI, V4,V3,V2, V5 — простая4) VI, V3, V5,^з,цепь;i^i — цикл, но непростой цикл;5) Vl, V3, v4, Vl — простой цикл.Рис. 7.8.
Маршруты, цепи, циклы2497.2. Элементы графов7.2.4. СвязностьГоворят, что две вершины в графе связаны, если существует соединяющая их(простая) цепь. Граф, в котором все вершины связаны, называется связным.Нетрудно показать, что отношение связанности вершин является эквивалентностью. Классы эквивалентности по отношению связанности называются компонентами связности графа. Число компонентов связности графа G обозначается k(G).Граф G является связным тогда и только тогда, когда k(G) = 1.
Если k(G) > 1,то G — несвязный граф. Граф, состоящий только из изолированных вершин (вкотором k(G) = p(G) и r(G) = 0), называется вполне несвязным.7.2.5. Расстояние между вершинами, ярусыи диаметр графаДлиной маршрута называется количество рёбер в нём (с учётом повторений).Если маршрут М = vq, e\,v\,e2,v2, • • •,vk, то длина М равна к (обозначается\М\ — к). Расстоянием между вершинами и wv (обозначается d(u, v)) называетсядлина кратчайшей цепи (u,v), а сама кратчайшая цепь называется геодезической,d(u, г>)min l(n, гЛ1.{<«,«»Если для любых двух вершин графа существует единственная геодезическаяцепь, то граф называется геодезическим.ЗАМЕЧАНИЕЕсли -<3 ((u,v)), то по определению d(u,v) = f +oo.Множество вершин, находящихся на заданном расстоянии п от вершины v (обозначение D(v,n)), называется ярусом:D(v, п){и € V | d(v, и) —п} .Ясно, что множество вершин V всякого связного графа однозначно разбивается на ярусы относительно дайной вершины.
Диаметром графа G называетсядлиннейшая геодезическая. Длина диаметра обозначается D(G):D(G)max d(u,v).u,v(EV7.2.6. Эксцентриситет и центрЭксцентриситетом e(v) вершины v в связном графе G(V, Е) называется максимальное расстояние от вершины v до других вершин графа G:е(у) =f maxd(v, и).uGVЗаметим, что наиболее эксцентричные вершины — это концы диаметра. РадиусомR(G) графа G называется наименьший из эксцентриситетов вершин:R{G)D=mme(v).250Глава8.СвязностьВершина v называется центральной, если её эксцентриситет совпадает с радиусом графа, e(v) = R(G). Множество центральных вершин называется центромграфа и обозначается C(G):C(G) =f {v G V | e{v) = R{G)} .Пример На рис. 7.9 указаны эксцентриситеты вершин и центры двух графов.Вершины, составляющие центр, выделены жирными точками.33зРис.
7.9. Эксцентриситеты вершин и центры графов7.3. Виды графов и операции над графамиВ данном разделе рассматриваются различные частные случаи графов и вводятся операции над графами и их элементами. Заметим, что пе все используемые нами обозначения операций над графами являются традициониыми иобщепринятыми.7.3.1. Виды графовГраф, состоящий из одной вершины, называется тривиальным. Граф, состоящийиз простого цикла с к вершинами, обозначается С*,.ПримерСз — треугольник.Граф, в котором любые две вершины смежны, называется полным. Полный графс р вершинами обозначается К р , он имеет максимально возможное число рёбер:/ tv- \я\КР)=pfe - 1)2'Полный подграф (некоторого графа) называется кликой (этого графа).7.3.2.
Двудольные графыГраф G{V,E) называется двудольным (или биграфом, или чётным графом), еслимножество V может быть разбито па два непересекающихся множества V\ и V2(Vi uV2 = V,V1nV2 = 0), причём всякое ребро из Е инцидентно вершине из V\и вершине из У2 (то есть соединяет вершину из Vi с вершиной из V2). Множества7.3. Виды графов и операции над графами251Vi и V2 называются долями двудольного графа. Если двудольный граф содержитвсе рёбра, соединяющие множества V\ и V2, то он называется полным двудольнымграфом.
Если |Vi| = т и | V21 = п, то полный двудольный граф обозначается Кт^п.ПримерНа рис. 7.5 приведена диаграмма графа if 3 , 3 .Граф является двудольным тогда и только тогда, когда все его простыециклы имеют чётную длину.ТЕОРЕМАДОКАЗАТЕЛЬСТВО[ = • ] От противного. Пусть а У \ У 2 \ Е ) — двудольный граф и ы, v2,..., v2k+i,vi —простой цикл нечётной длины. Пусть v\ € Vi, тогда v2 е V2, V3 е Vi, V4 е V2,...,V2k+i € Vi. Имеем: vy,v2k+i € V\ и (vi,v2fc+i) € E, что противоречит двудольности.[ < = ] Не ограничивая общности, можно считать, что G — связный граф, поскольку каждый компонент связности можно рассматривать отдельно. Разобьём множество V на подмножества V\ и V2 с помощью следующей процедуры.Вход: граф G(V,E).Выход: Множества Vi и V2 — доли графа,select v е V { произвольная вершина }Vi: = v { в начале первая доля содержит v,...}V2 : = 0 { ...
а вторая пуста }for и е V - v doif d(v,u) — чётно thenVi: = Vi + и { помещаем вершину и в первую долю }elseV2: = V2 + u'{ помещаем вершину и во вторую долю }end ifend forДалее от противного. Пусть есть две вершины в одной доле, соединённые ребром. Пусть для определённости и, w е V2 и (и, w) е Е. Рассмотрим геодезические(v, и) и (t>, w) (здесь v — та произвольная вершина, которая использовалась в алгоритме построения долей графа). Тогда длины | (v, и) | и | (v, w) | нечётны. Этигеодезические имеют общие вершины (по крайней мере, вершину v). Рассмотрим наиболее удалённую от v общую вершину геодезических (v,u) и (v,w) иобозначим её v' (может оказаться так, что v = v').
Имеем: | (v',u) | + | (v',w) | == | (v, и) | -I- | (и, w) | - 2| (и, v') | — чётно и •?/,..., и, w,..., v' — простой циклнечётной длины, что противоречит условию. Если же и, w е Vi, то длины | (v, и) \и | (г>, w) | чётны, и аналогично имеем: v',..., и, w,..., v' — простой цикл нечётнойдлины.•СЛЕДСТВИЕАциклические графы двудольны.252Глава8.Связность7.3.3. Направленные орграфы и сетиЕсли в графе ориентировать все рёбра, то получится орграф, который называетсянаправленным, или антисимметричным. Направленный орграф, полученный изполпого графа, называется турниром.ЗАМЕЧАНИЕВ антисимметричном орграфе пе может быть «встречных» дуг (u,v) и (v,u), а в произвольном орграфе такое допустимо.ОТСТУПЛЕНИЕНазвание «турнир» имеет следующее происхождение.
Рассмотрим спортивное соревнование для пар участников (или пар команд), где не предусматриваются ничьи. Пометимвершины орграфа участниками и проведем дуги от победителей к побеждённым. В такомслучае турнир в смысле теории графов — это как раз результат однокругового турнирав спортивном смысле.Если в орграфе полустепень захода некоторого узла равна нулю (то есть d+(v) == 0), то такой узел называется источником, если же нулю равна полустепепьисхода (то есть d~(v) = 0), то узел называется стоком. Направленный слабосвязный (см. 8.5.1) орграф с одним источником и одним стоком называетсясетью.7.3.4. Операции над графамиВведем следующие операции над графами:1.
Дополнением графа G\{V\,E\)(обозначение — Gi(Vi,.Ei)) называется графG2(V2,E2),где V2 = Vi к Е2 = Ё[ = {е G Vi х Vi | е £ Ег}ПримерK i = К\.= V х V \Е.2. Объединением (дизъюнктным) графов GI(VI,E\)и G2(V2,E2)(обозначение —G\(VI, Ei)UG2(V2,Е2), при условии VifiV^ = 0 ) называется граф G(V,E), гдеу = vi U V2 k Е = Ei U Е2.ПримерК =Сз и Сз.3. Соединением графов GI(VI,EI)и G2(V2,E2)(обозначение — Gi(VI,EI)++ G2(V2,E2), при условии VI (1V2 = 0 ) называется граф G(V,E), где V == Vi U V2 к Е = EL U Е2 U {Е = {vi, v2) \ ы Е Vi к v2 Е V2} .Пример= Сз + С3.7.3.
Виды графов и операции над графами2534. Удаление вершины v из графа Gi(Vi,£i) (обозначение — G\{V\,E{)условии v б Vi) даёт граф G2(V2, Е2), где— v приV2 = Vi — v к Е2 = Ei \ {е = (г>1, v2) \ v\ = v V v2 = г>} .ПримерСз - v — К2.5. Удаление ребра е из графа Gi(Vi,Ei) (обозначение — G\(Vi, Е\) — е при условии е е Ег) даёт граф G2(V2, Е2), где V2 — V\ к Е2 = Е\ - е.ПримерК2 - е = ~К2.6. Добавление вершины v в граф G\(V\,E\) (обозначение — G\(V\,E\)условии v £ Vi) даёт граф G2(V2, Е2), где V2 = V\ + v к Е2 = Е\.Пример+ v приК2 + v = К2 и Ki.7. Добавление ребра е в граф Gi(Vi,Ei) (обозначение — Gi(Vi,Ei) + е при условии eg Ei) даёт граф £2(^2, Е2), где V2 = Vi к Е2 = Ei + е.8.
Стягивание (правильного) подграфа А графа G\(V\,E\) (обозначение —Gi(Vi,Ei)/Aпри условии А с Vi,v £ V\) даёт граф G2(V2,E2), гдеV2 = (Vi\A)+v,Е2 = Ei \ {е = (и, w) | и G А V w G A) U {е = (и, v) \ и G Г(Л) \ А} .ПримерК4/С3= К2.9. Размножение вершины v графа G\(Vi,Ei) (обозначение — Gi(Vi,Ei)условии v € Vi,v' g Vi) даёт граф G2(V2,E2), где| v приV2 = Vi +v' k E2 = £ i U { K i ) ' ) } u { e = {u,v') \ и <E Г + (г;)} .ПримерK2 j v = C3.Некоторые из примеров, приведённых в определениях операций, нетрудно обобщить. В частности, легко показать, что имеют место следующие соотношения:Введённые операции обладают рядом простых свойств, которые легко вывестииз определений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
