Diskretka

Diskretka.doc20.02.2014

81

Определение.

Полнымдвудольнымграфом

называетсяграфn+m

вершинбезпетель,кратныхипротивоположныхмидугориент( безразлична),у ция

которогомножестазбитове шиннаднепересекающихсяв подмножестваnm

вершинамитак,чтолюбыед шиныазличныхподмножествсоедине

ныдугойи

никакиедвершиныодногоподмножествасоединеныдугой.

Заполняемстрочкуеслиs:естьдугавsздругуювершинуграфаG,тоставим1,если

нет - 0Из.естьдугиs вx:(sx)вy:(sy)Поаналогиизаполняем. другиестроки.

Матрицаинцедентности:

строкисоответствуютвершинам,столбцыду

гам,приэтом

встолбце,соответдуге(x,y)ставитсястрокеующ1x, м

-1встрокеостальныеy,

элемерав0.нты

Рисунок3.1.13.

Diskretka.doc20.02.2014

82

4.

Определение.

Цепьюдлиныn

награфе(N,A)называетсяпоследовательность

дуг

такая,чтоулюбойдуги

однавершинаобщаясдугойf(i

-1),адругая

-

общаясдугойf(i+1).

Вершдугf(1),неявляющаясяинаобщейдугойf(2),называетсяначаломцепи,

вершдугиf(n),неявляющаясянаобщейдугойf(n

-1),называетсяконцомцепи.

Еслиначалоцепи

совпаданазываетсяееконцом,тоцепьциклом.

Определение.

Путемдлиныn

награфе(N,A)называетсяпоследовательность

дуг

такая,чтоулюбойдугиf:(i)(i=1началадугисовпадает..концомn)дугиf(i

-1),

аконецдугисовпадаетначаломдугиf(i+1).

Началодугиf(1)называетсяначаломпути,конецдугиf(n)называетсяконцомпути.

контуром.

Еслинача

лопутисовпадаетконцомпути,топутьназывают

Diskretka.doc20.02.2014

83

вершдостижима2 изна1:(1,2)

вершдостижима4 изна1:(1,2),(2,4)

вершинане3достижимаиз1.

Определение.

Грнафзывается

сильносвязным

,есдлиюбыхядвухеговершинxy,

существуетпутьсоединяющ

ийxy.

Diskretka.doc20.02.2014

84

Получимкомпоненты2 сильнойсвязностиграфаG2.

Определение.

ПустьданграфG=(N,A)(N=[V1,Матрицейдостижимостиграфа...,Vn]).

Gназываетсяквадр

атнаяматрица

порядкауn,которой

,есливершинаVj

достизVi,ижима

- впротивоположномслучае.

Определение.

Матрицейсильнойсвязн

остиграфаG=(N,A)называетсяматрица

порядка n,укоторой

,есливершинаVjдостижимаиз

Vi,и

- впротивоположном

случае.

Матрицасильнсвязности:пдиагоналийставимзаполняем1; строкуX1

- если

вершинадостижим

аизX1иX1достижимаизэтойвершины,тосоответствующемэтой

вершинестолбцеставим1,противслучае0;поналогиизаполняемомостальныестроки.

Замечание.

Поматрицесильнсвязностиможновыпийк мпонентысильнойать

связности.

Выпишемкомпонент

ысильнойсвязнодлярассграфатимотренного.

Diskretka.doc20.02.2014

85

РассмстрокуX1:вычеркнемтримстолбцы,которыхстоятединицыX1, X2, X3.

Теперьвычест:рX1,окикнемX2, X3.

ПрипересечениистолбцовX1,строкX1,2,получиласьX2,таблица3 X3

,т.е.

вершиныX1,сильноX2,связнымеждусобойX3иобразуюткомп

онентусильнойсвязности.

ВычеркивстрокеX4столбец,вкоторомаем

итединицаX4Теперьвычеркиваем.

строкуX4Припересечении. строкиX4столбцаX4получили

5. Операциинадграфамиобъединение( ,пересечение).

Определение.

Объединениемграфов

называетсяграф,у

которогообъе

диненымножествовершинмножестводугграфов

.Обозначение

.

Пример1.

G1

Diskretka.doc20.02.2014

86

Определение.

Пересечениемграфов

граф,укоторого

пересеченымножествовершинмножестводугграфов

.Обозначение

.

Пример2.

Рассмотримграфы

изпримера1Построим. ихпересечение:выберем

одинаковыевершиныдуги.

Подграф

Подграфом графа G = <V, E> будемназыватьтакойпроизвольныйграф

G' = <V', E'>,

что V ʹ V и Uʹ U .

Вотечественнойлитературепотеорииграфов

G' называется

чаще частью графа,или

частичнымграфом,

подграфомжепонимаетсячастичныйграф,

удовлетворяющийдополнительномуусловию

x, yx, y V ʹ {x, y} E {x, y} Eʹ .

Diskretka.doc20.02.2014

87

ДЕРЕВЬЯ

Деревьяважнынетолькопотому,чтонаходятиприложенияв

различныхобластях

знан,ноиВиособогойлуположихвсамтеографовнияйрии.Последнеевызвано

предельнойпростстрдеревьтойения,поэтомуреившениикакойлибозадачиграфах

еесначаиссналдеа.дуютревьях

Однимизпростейшихклассомграфов

являютсядере.Графьядеревом, тсясли

онудовслетеоремедующейворяет.

Теорема. Дляграфа

G= <X,U>следующиеутвержденияэквивалентны:

1) G - дерево;

2)любыедвершиныграфе

G соединеныединственнойпростойцепью;

3)граф

G связениимеет

|X| - 1ребер;

4)граф

G несодержитцикловимеет|

X| - 1ребер;

5)граф

G несодержитциклов,нодобавлениеребрамеждулюбыдвумяи

несмежнымивершпркпоявлениюнамивододногоциклат;

6)граф

G связен,ноутрачиваетэтосвойпослеудалентво

иялюбогоребра.

Свободныедеревья

ациклическим,

или лесом.

Графбезцикловназывается

Связныйациклическийграф

называется (свободным)дерево.

Компонентамисвязностилесаявляютсядеревья.

Граф G, вкот

ором q(G)р(=

G)-1,называется

древовидным.

Вацикличграфеском

G

z(G) = 0.Пусть и,

v — несмежныевершиныграфа

G, х=и, (

v) E.Еслиграф

G+x имееттолькоодинпрцикл,стой

z(G+х)= 1 , тограф

G называется

субциклическим.

Пример

5 вершинами,

Нарис. показаны9.1диаграммывсехразличныхсвободных( )деревьев

анарис. 9.2

— диаграммывсехразличныхсвободных( )деревьев

6 вершинами.

Diskretka.doc20.02.2014

88

Рис. 8.2Свободные. деревьясвершинами6

Основныесвойстдеревьева

Следтеоремующстанавлива,чтодваизячетырсвойствех

—

связность,

ацикличность,древовидностьсубцикличность

— характеризуютгркакдеревоф.

Теорема

Пусть G(V,Е) — графс

р вершинами,

q ребрами,

k компонентамисвязности

z

простыциклами.Пустьдалее

х — ребро,соединялюбупарунесмювершинщежных

G.Тогдаследующиеутвержденияэквивалентны:

1.

G — дере,тосвязныйтьографбезциклов,

k(G) = 1&z(G) = 0;

2.

любыедвершинысоединеныв

G единственнойпростойцепью,

G — связныйграф

u, v ! u<, v .

3.

, илюбоерестьбромост,

4.

G — связныйидревовидный,

k(G) =1& e Ek(G − e) >1;

k(G) =1& q(G) = p(G) 1;

6.

G — ациклическийсубциклический,

7.

G — связный,субциклическийнеполный,

z(G) = 0 & z(G + x) =1;

k(G) =1& G ≠ K & p ≥ 3 & z(G+ x=) 1;

8.

G — древовидныйсубциклическийза(двумяисключениями),

U

q(G) =

−1& G ≠ K1

K3 & G ≠

+ =

;

Доказательство

p(G)

K 2 U K3 & z(G x)

1

Рис.

8.3Кдоказатель. свойремыдеревьевствуах

[1 2] Отпротивного

.Пустьсуществуютдвец пи

<и,

v> (рис. 9слева.)3,Тогда.

w,

w2 — простойцикл.

и,

v !,следовательно,

k(G) =1.Далеепротивного.Пустьребро

х

[2 3Имеем.]:

— немост.Тогдав

G - х концыэтогоребрасвязаныцепью.Саморебро

х — втораяцепь.

[3 4Индукция.] по

р. База:

р= 1 q = 0.Пусть

q(G) = p(G) −1 длявсехвяз

анных

графов G счисломвершинменьше

р, укоторыхлюбоеребросутьмост.Тогдаудалимиз

G

ребро х (которявляетсямо)Получим.стомдвекомпоненты

G' и G", удовлетворяющие

индукционнпредпол.Имее: омжениюу

qʹ = pʹ −1, q=ʹʹ p−ʹʹ 1,=q +qʹ +qʹʹ =1 −pʹ 1+ p−ʹʹ 1+1 = p −1.

[4 5От.противного] .Пуестьцикл

п вершинами

п ребрами.Остальные

р - п

вершинимеютинцимрёбрадентные,которыесвязываютихцик,Следовательноом,

q ≥

р, чтопротивусловиюречит

q =р

- 1.

k;.

[5 1Граф.]безциклов,

следовательно,егок мпоненты

— деревья.Пустьих

Имеем:

Diskretka.doc20.02.2014

89

k

q=Σq i =У( pi-1)У= pi-k = p-k

Но q=p-1,следовательно,

i=1

k = 1.

5 1

2.Имеем :

u, v !

u<, v .Соединивдве

[5 6По.ранее] доказанному

несмежныевершины,получимединственныйпростойцикл.

[6 7При.]

р≥3

граф Кр содержитцикл,следовательно,

G ≠К р. Далеепротивного.

Пусть G несвязен,тогдаприсоединенииребрдвухком

понентсвязциклнеости

возникнет.

k(G) = 1,следовательно,

u, v ! u<, v

. Пустьцепнеединственная.

[7 2Имеем.]

Тогдасуществуетцикл

Z, причем Z =К 3,С= 3.Действительно,пусть

Z >С 3, тогда,соединив

двен смежные

вершэтогоци,пкланыдвалучимцикла.Но

G связени

G ≠К 3,

следовательно,существуетдругаявершина

w,смежная

Z =К 3 (см.рис. 9справа.)3,Если.

w

смежнаболеечемоднойвершиной

Z, тоимеембольшеодногоцикла.Если

2 U К3,

1 U К3.

w смежна

толькосоднвершинй

ой Z, тосоесдёинивругойвершиной,получимдвацикла.

[7 8Имеем.]

k(G) = 1,следовательно,

G

≠К

G

≠К

Имеемпо

доказанному:

7 2 3 4,тоесть

q =р - 1.

[8 5От.противного] .Пусть

G естьцикл

Z =С п. Если n > 3,тоесливнутри

Z уже

естьмежныевершины,имеемдвацикла.Если

Z нетсмежныхвершин,то,соединив

несмежныевер

шиныв

Z, получимдвацикСледовательно. ,

Z =К 3. Этотцикл

Z является

компонентойсвязности

G. Действительно,пустьэтонетак.Тогдасущ ршинаствует

W,

смежная

Z. Если W смежнаболеечемоднойвершиной

Z, тоимеембольшеодногоцикла.

Если W смежнатолькосоднвершиной

Z, то,соесдёинивругойвершиной,получимдва

цикла.Рассмотрим

G :=G - Z. Имеем:

рр='+ 3,

q = q' + 3.Но

q =р - 1,следовательно,

q'р'=

- 1. Отсюда z(С') = 0

,таккакодциуженестькл.След,ковательмпонентыо

G' — деревья.

Пустьих

k.Имеем:

k

q=Σq I =У( pi-1)У= pi-k = ṕ-k

но q' = p' -1, следовательно.

i=1

k = 1.тоестьдереодн.Есливэтомдеревесбединить

несмежныевершины,тополучимвторойцикл.Дваисключения:деревья,которыенеимеют

несмежныхвершин,

— это К1 и K2.

Diskretka.doc20.02.2014

90

Следствие1

Вл

юбомнетривиальномдеревеимеютсяпокрайнмерд исячией

вершины.

Доказательство

G(V,Е)

. Дерево — связныйграф,следовательно,

vi Vd (vi) ≥ 1.

Рассмотримдерево

Далеепротивного.Пусть

vi 1 pd>(vi)

1.Тогда

2q =У

d(vi) р> 2(

- 1) р+ 1 = 2 - 1.

Но q =р

- 1,тоесть

2q =р2

- 2.Имеемпротиворечие:

2р

- 2 р2 > 2

- 1.

Следствие2.

Каждаяневисячаявершинасвободндереваявляетсяочкойго

сочленения.

Доказательство

Пусть G(V,Е)

— дерево,

v V и d(v) > 1. Тогда и, w V(u,v) E& (u, w) E.Граф

G

связен,поэтомусущцествуетпь

(и,

w).Если

v <и,

w>, тоимеемцикл

v, <и,

w> ,v, что

противоречиттому,что

G — дерево.Следовательно,

и, w V <и,

w> v <u, w> ипо

теор8в.1е.мершина2

v — точкасочленения.

Центрдерева

Свободныедеревьявыделяютсяиздр

угихрафовтем,чтоихцентрсегдаопр вдывает

своёназвание.

Теорема

Центрсвободногодеревасостоитизоднойвершиныилииздвухсмежныхвершин:

Доказательство

Z(G) = 0&k(G) →=С( 1

G)К=

1 С( G)К=

2.

Длядеревьев

К1

и К2

утверждениетеоч.Пустьмывиднотеперь

G(V,Е)

—

некотороесвобдерев, днтличноеот

К1 и К2.Рассмотримграф

G'(V',Е') , полученныйиз

G удалвсехвисячихниемвершин.Заметим,что

G' — дерево,посколькуацикличность

еG(v) =

связностьприудалениивисяч х

ершинсохр.Да,еслинялеэксцентриситеттся

d(v,и) , то и — висячаявершинадереве

G (иначеможнобылпродолжитьцепьза«»

вершину и). Поэтому

v

V'е

G(v) е =

G'(v)+1

иприудалениивисячверших

н

эксценоставшумерисниьшаютсятетыхся

1.Следов,приудависячтлельнониих

вершинцентрнеменяется,

С( G)С(=

G'}. Посколькудерево

G конечно,тоудаляянакаждом

шагевсевисячиеверши,концезаыцовесколькошаговпридём

К1 или К2.

Ориентирован,упорядочбинарндеыеевьяные

Ориентиупо( р)деревьяядоченныеованныеявляютсяабстракциейиерархических

отношений,которыечаеньвстречокакпрактическойюжизни,таксявматематике

ипрограммировании.Деревоориентированное( )

иерархия — эторавнообъёмныепонятия.

Ориентирдеревованным

(или ордеревом,

или корневым деревом) называется орграф

соследующимисвойствами.

r,полустепезахк равторогоданьа

0, d+(r) = 0.Он

1Существует. единственныйузел

называется корнем ордерева.

1, v V \ { r } d+(r) = 1 == 1.

2Полуст. захвсестальныхдапеньузловравна

3Каждый. узелдостижимизкорня,

v V \ { r } <v, u >.

Пример

Нарис. приведены9.5диаграммывсехразличныхориентированныхдеревьевс 3

узл,анарис.мипоказаны9.6диаграммывсехразличныхориентированныхдеревьевс4

узлами.

Ордеревообладаетследующимисвойствами:

Теорема.

1. q =р

- 1;

2еслив. орде

ревезабытьориентациюдуг,тополучитсясвободндеревое

;

3ворд. нконтуровереве

4для.каждогоузласуществуетединспу,ведущийьэтотенныйузелизкорня;

5подг. ,опрафеделяемыймножеузл, оствизузлавомижимых

v,

является