Diqraflar üçün əlçatanlıq məsələləri və əlçatanlıq və əks əlçatanlıq matrislərinin tapılması üsulları nəzərdən keçirilir. Qrafikin hər hansı təpələri arasında yolların sayını tapmaq, eləcə də təpələr cütü arasındakı yola daxil olan təpələr çoxluğunu tapmaq üçün matris metodu nəzərdən keçirilir. Mühazirənin məqsədi: Əlçatanlıq və əks əlçatanlıq və onları necə tapmaq barədə fikir vermək

Əlçatanlıq və əks əlçatanlıq

Konsepsiyadan istifadə edilən tapşırıqlar əlçatanlıq, kifayət qədər.

Onlardan biri budur. Qrafik insanların təpələrlə təmsil olunduğu və qövslərin rabitə kanallarını şərh etdiyi bəzi təşkilatın modeli ola bilər. Belə bir modeli nəzərdən keçirərkən soruşmaq olar ki, bir şəxsdən i məlumatı başqa bir şəxsə j ötürülə bilərmi, yəni i təpələrindən j təpələrinə gedən yol varmı? Əgər belə bir yol varsa, onda biz təpələri j deyirik əldə edilə bilən təpələrdən i . j təpələrinin i təpələrindən yalnız uzunluqları verilmiş qiymətdən çox olmayan və ya uzunluğu qrafikdəki ən çox təpələrdən kiçik olan yollarda və s.

Qrafikdə əlçatanlıq R=, i, j=1, 2, ... n əldə edilə bilənlik matrisi ilə təsvir edilir, burada n qrafik təpələrinin sayıdır və hər bir element aşağıdakı kimi müəyyən edilir:

r ij =1, əgər j təpələrinə x i-dən çatmaq olarsa,

r ij =0, əks halda.

Verilmiş xi təpəsindən əldə edilə bilən G qrafikinin R(xi) təpələri çoxluğu elə xi elementlərindən ibarətdir ki, onlar üçün əlçatanlıq matrisindəki (i, j)-ci element 1-ə bərabərdir. Aydındır ki, bütün diaqonal elementlər R matrisində 1-ə bərabərdir, çünki hər bir təpəyə özündən 0 uzunluqlu bir yol ilə çatmaq olar. Birinci dərəcəli birbaşa xəritələmə G +1 (xi) xi-dən yollardan istifadə etməklə əldə edilə bilən xj təpələrinin çoxluğu olduğundan uzunluğu 1, onda Г + (Г +1 (xi)) = Г +2 (xi) çoxluğu 2 uzunluqlu yollardan istifadə etməklə xi-dən əldə edilə bilən təpələrdən ibarətdir. Eynilə, Γ+p (xi) təpələr çoxluğudur. p uzunluğundakı yollardan istifadə edərək xi-dən əldə edilə bilən.

X i-dən əldə edilə bilən hər hansı qrafik təpəsinə 0 və ya 1 və ya 2, ... və ya p uzunluğundakı yoldan (yaxud yollardan) istifadə etməklə çatmaq mümkün olduğundan, x i təpəsi üçün əldə edilə bilən təpələr dəsti kimi təmsil oluna bilər.

R (x i) = ( x i ) G +1 (x i) G +2 (x i) ... G + p (x i).

Gördüyünüz kimi, əldə edilə bilən təpələr dəsti R(x i) təpəsinin birbaşa keçid bağlanmasıdır x i , yəni R(x i) = T + (x i). Buna görə də, əlçatanlıq matrisini qurmaq üçün bütün x i X təpələri üçün əldə edilə bilən R(x i) çoxluqlarını tapırıq. X j R(x i) olarsa r ij =1, əks halda isə r ij =0 təyini.

düyü. 4.1. Qrafikdə əlçatanlıq: a - qrafik; b – bitişiklik matrisi; c – əlçatanlıq matrisi; r əks əlçatanlıq matrisidir.

Şəkildə göstərilən qrafik üçün. 4.1, a, əlçatan dəstlər aşağıdakı kimi yerləşir:

R (x 1) = ( x 1 ) ( x 2 , x 5 ) ( x 2 , x 4 , x 5 ) ( x 2 , x 4 , x 5 ) = ( x 1 , x 2 , x 4 , x 5 ) ),

R (x 2) = ( x 2 ) ( x 2 , x 4 ) ( x 2 , x 4 , x 5 ) ( x 2 , x 4 , x 5 ) = ( x 2 , x 4 , x 5 ),

R (x 3) = ( x 3 )( x 4 )( x 5 )( x 5 ) = ( x 3 , x 4 , x 5 ),

R (x 4) = ( x 4 )( x 5 )( x 5 ) = ( x 4 , x 5 ),

R (x 5) = ( x 5 )( x 5 ) = ( x 5 ),

R (x 6) = ( x 6 )( x 3 , x 7 )( x 4 , x 6 )( x 3 , x 5 , x 7 )( x 4 , x 5 , x 6 ) = ( x 3 , x 4, x 5, x 6, x 7),

R (x 7) = ( x 7 )( x 4 , x 6 )( x 3 , x 5 , x 7 )( x 4 , x 5 , x 6 ) = ( x 3 , x 4 , x 5 , x 6 , x 7).

Əlçatanlıq matrisi Şəkildə göstərildiyi kimi formaya malikdir. 4.1, c. Əlçatanlıq matrisi uyğun olaraq tikilə bilər bitişiklik matrisi(Şəkil 4.1b), hər bir x i təpəsi üçün T + (x i) dəstləri əmələ gətirir.

Qarşı əlçatanlıq matrisi Q = [ q ij ],i, j =1, 2, ... n, burada n qrafikin təpələrinin sayıdır, aşağıdakı kimi müəyyən edilir:

q ij =1, əgər x j təpəsindən x i təpəsinə çatmaq olarsa,

q ij =0, əks halda.

qarşısı alına bilən Q (x i) çoxluğu elə təpələr çoxluğudur ki, bu çoxluğun istənilən təpəsindən x i təpəsinə çatmaq mümkün olsun. Əlçatan R (x i) çoxluğunun qurulmasına bənzər şəkildə Q (x i) üçün ifadə yaza bilərik:

Q (x i) = ( x i ) Г -1 (x i) Г - 2(x i) ... Г -p (x i).

Beləliklə, aydın olur ki, Q (x i) x i təpəsinin tərs keçid bağlanmasından başqa bir şey deyil, yəni Q (x i) = T - (x i). Təriflərdən aydın olur ki, Q matrisinin xi sütunu (burada xj Q (xi) olduqda q ij =1, əks halda q ij =0) R matrisinin xi sətri ilə üst-üstə düşür, yəni Q = RT. , burada RT köçürülmüş matrisdir əlçatanlıq matrisi R.

Qarşı əlçatanlıq matrisiŞəkildə göstərilmişdir. 4.1, g.

Qeyd etmək lazımdır ki, R və Q matrislərinin bütün elementləri 1 və ya 0-a bərabər olduğundan, hər bir sətir ikili formada saxlanıla bilər, kompüter yaddaşı xərclərinə qənaət edilir. R və Q matrisləri kompüterdə işləmək üçün əlverişlidir, çünki hesablama baxımından əsas əməliyyatlar yüksək sürətli məntiqi əməliyyatlardır.

Yola daxil olan təpələr dəstinin tapılması

Bu yollara daxil olan qrafikin təpələri haqqında bilmək lazımdırsa, o zaman birbaşa və tərs keçid qapanmalarının təriflərini xatırlamalısınız. T + (xi) xi təpəsindən yolların olduğu təpələr çoxluğu olduğundan və T - (xj) xj-ə gedən yolların olduğu təpələr çoxluğu olduğundan, T + (xi) T - (xj) ) hər biri x i-dən x j-ə gedən ən azı bir yola aid olan təpələr çoxluğudur. Bu təpələr x i və x j son təpələrinə görə əsas və ya inteqral adlanır. Qrafikin bütün digər təpələri əhəmiyyətsiz və ya lazımsız adlanır, çünki onların çıxarılması x i-dən x j-ə qədər olan yollara təsir göstərmir.

düyü. 4.2. diqraf

Beləliklə, Şəkildəki qrafik üçün. 4.2 Yola daxil olan təpələri tapmaq, məsələn, x 2 təpəsindən 4 təpəsinə qədər, T + (x 2) \u003d ( x 2, x 3, x 4, x 5, x 6 ) tapmağa endirilir.

T - (x 4) \u003d ( x 1, x 2, x 3, x 4, x 5) və onların kəsişmələri T + (x 2) T - (x 4) \u003d ( x 2, x 3, x 4, x beş).

Qrafiklərdə yolların tapılması üçün matris üsulu

Qonşuluq matrisi qrafikin strukturunu tamamilə müəyyən edir. Qonşuluq matrisini riyaziyyat qaydalarına uyğun olaraq kvadratlaşdıraq. A 2 matrisinin hər bir elementi düsturla müəyyən edilir

a (2) ik = n j=1 a ij a jk

Düsturdakı termin 1-ə bərabərdir o halda və yalnız a ij və jk ədədlərinin hər ikisi 1-ə bərabərdirsə, əks halda 0-a bərabərdir. a ij = a jk = 1 bərabərliyi uzunluqlu yolun mövcudluğunu nəzərdə tutduğundan xi təpəsindən x j təpəsindən keçən k təpələrinə 2, onda A 2 matrisinin (i -ci,k-ci) elementi x i-dən k-ə gedən 2 uzunluqlu yolların sayına bərabərdir.

Cədvəl 4.1a Şəkildə göstərilən qrafikin bitişiklik matrisini göstərir. 4.2. Qonşuluq A 2 matrisinin kvadratlaşdırılmasının nəticəsi Cədvəl 4.1b-də göstərilmişdir.

Beləliklə, ikinci sıra ilə dördüncü sütunun kəsişməsində dayanan "1", x 2 təpəsindən 4 təpələrinə qədər uzunluğu 2 olan bir yolun mövcudluğunu göstərir. Doğrudan da, gördüyümüz kimi sütunşək. 4.2, belə bir yol var: a 6 , a 5 . A 2 matrisində "2" uzunluğu 2 olan iki yolun 3-cü təpələrdən 6-cı təpələrə qədər olduğunu göstərir: a 8, a 4 və 10, a 3.

Eynilə, üçüncü dərəcəli A 3-ə yüksəldilmiş qonşuluq matrisi üçün (Cədvəl 4.1c), a (3) ik x i-dən x k-ə gedən 3 uzunluqlu yolların sayına bərabərdir. A 3 matrisinin dördüncü cərgəsindən görünür ki, uzunluğu 3 olan yollar var: 4-də x 4-dən biri (a 9, a 8, a 5), ​​x 4-də biri.

x 5 (a 9, a 10, a 6) və 6-da x 4-dən iki yol (a 9, 10, 3 və 9, 8, 4). A 4 matrisi uzunluğu 4 olan yolların mövcudluğunu göstərir (Cədvəl 4.1d).

Beləliklə, əgər p ik A p matrisinin elementidirsə, onda p ik x i-dən x k-ə qədər p uzunluğunda olan yolların (mütləq və ya zəncir və ya sadə və ya zəncir deyil) sayına bərabərdir.

Əlçatanlıq Qrafiki

Qrafiklərin öyrənilməsində yaranan ilk suallardan biri verilmiş və ya bütün təpə cütləri arasında yolların mövcudluğu məsələsidir. Bu sualın cavabı yuxarıdakı G=(V,E) qrafasının təpələrində çata bilmə əlaqəsidir: əgər v = w olarsa, w təpəsinə v təpəsindən çatmaq olar və ya G-də v-dən w-ə qədər yol varsa. Başqa sözlə, əlçatanlıq əlaqəsi E münasibətinin refleksiv və keçidli bağlanmasıdır. İstiqamətsiz qrafiklər üçün bu əlaqə həm də simmetrikdir və buna görə də V təpə çoxluğunda ekvivalent münasibətdir. İstiqamətsiz qrafikdə əlçatanlıq ekvivalentlik sinifləri bağlı komponentlər adlanır. İstiqamətləndirilmiş qrafiklər üçün əlçatanlıq, ümumiyyətlə, simmetrik əlaqə olmamalıdır. Qarşılıqlı əlçatanlıq simmetrikdir.

Tərif 9.8.İstiqamətləndirilmiş G=(V,E) qrafikinin v və w təpələri, əgər G v-dən w-yə, w-dən v-ə qədər yola malikdirsə, qarşılıqlı olaraq əldə edilə bilən deyilir.

Aydındır ki, qarşılıqlı əlçatanlıq əlaqəsi refleksiv, simmetrik və keçid xarakterlidir və deməli, qrafikin təpə çoxluğunda ekvivalentdir. Qarşılıqlı əlçatanlığa görə ekvivalentlik siniflərinə güclü bağlı komponentlər və ya deyilir ikiqat əlaqəli komponentlər qrafik.

Əvvəlcə əlçatanlıq əlaqəsinin qurulması məsələsini nəzərdən keçirək. Gəlin hər bir qrafik üçün kənarları orijinal qrafikin yollarına uyğun gələn əlçatanlıq qrafikini (bəzən keçid qapanma qrafiki də adlandırırlar) müəyyən edək.

Tərif 9.9. G=(V,E) istiqamətləndirilmiş qrafik olsun. G üçün əlçatanlıq qrafiki G * =(V,E *) eyni V təpələri dəstinə və aşağıdakı kənarlar dəstinə malikdir E * =( (u, v) | G qrafikində, v təpəsinə təpədən çatmaq olar. u).

Misal 9.3. Nümunə 9.2-dən G qrafikini nəzərdən keçirək.

düyü. 9.2. Qraf G

Sonra G üçün əlçatanlıq qrafikinin G* belə göründüyünü yoxlaya bilərik (1-5 təpələrinin hər birində yeni döngə kənarları göstərilmir):

düyü. 9.3. Say G*

G qrafikindən G * qrafikini necə qurmaq olar? Bunun bir yolu, G qrafikinin hər bir təpə nöqtəsi üçün 0, 1, 2 və s. uzunluqlu yollarla ondan əldə edilə bilən təpələri ardıcıl olaraq əlavə etməklə ondan əldə edilə bilən təpələr çoxluğunu müəyyən etməkdir.

G qrafikinin A G bitişiklik matrisinin və Boolean əməliyyatlarının istifadəsinə əsaslanan başqa bir üsulu nəzərdən keçirəcəyik. Təpələr çoxluğu V=(v 1 , … , v n ) olsun. Onda A G matrisi n × n Boolean matrisidir.

Aşağıda, matrislər üzərində adi əməliyyatlarla oxşarlığı qorumaq üçün məntiqi əməliyyatlar üçün "arifmetik" qeyddən istifadə edəcəyik: disyunksiyanı +, birləşməni isə · ilə işarə edəcəyik.

n × n ölçülü eynilik matrisini E n ilə işarələyin. qoyaq . G * qurmaq üçün prosedurumuz aşağıdakı ifadəyə əsaslansın.

Lemma 9.2. Qoy olsun. Sonra

Sübut k üzərində induksiya ilə həyata keçirək.

Əsas. k=0 və k=1 üçün ifadə və tərifinə görə doğrudur.

induksiya mərhələsi. Lemma k üçün etibarlı olsun. Göstərək ki, k + 1 üçün də etibarlı qalır. Tərifinə görə bizdə var:

Fərz edək ki, G qrafikində v i-dən v j-ə qədər k+1 uzunluğunda bir yol var. Bu yollardan ən qısasını nəzərdən keçirək. Əgər onun uzunluğu k olarsa, induksiya hipotezi ilə a_(ij)^((k))=1. Bundan əlavə, jj (1) =1. Buna görə də a ij (k) a jj (1) =1 və a ij (k+1) =1. Əgər v i-dən v j-ə qədər olan ən qısa yolun uzunluğu k+1-ə bərabərdirsə, onda v r onun sondan əvvəlki təpəsi olsun. Onda v i-dən v r-ə k uzunluğunda bir yol var və induksiya fərziyyəsinə görə ir (k) =1. Çünki (v r ,v j) E, onda a_(rj)^((1))=1. Buna görə də a ir (k) a rj (1) =1 və a ij (k+1) =1.

Əksinə, əgər a ij (k+1) =1, onda ən azı bir r üçün cəm a ir (k) a rj (1) 1-ə bərabərdir. Bu r=j olarsa, a ij (k) = 1 və induksiya fərziyyəsi ilə G-nin vi-dən vj-ə k uzunluğunda bir yolu var. Əgər r j olarsa, onda a ir (k) =1 və a rj (1) =1. Bu o deməkdir ki, G-nin v i-dən v r-ə k uzunluğunda yolu və kənarı (v r ,v j) E. Onları birləşdirərək, k+1 uzunluğunda v i-dən v j-ə qədər yol alırıq.

Lemmas 9.1 və 9.2-dən biz birbaşa əldə edirik

Nəticə 1. G=(V,E) n təpəsi olan istiqamətləndirilmiş qrafik və G * onun əlçatanlıq qrafiki olsun. Sonra A_(G*) =. Sübut. Lemma 5.1 nəzərdə tutur ki, əgər G-nin u-dan v u-ya qədər yolu varsa, onun da u-dan v-ə qədər n-1 uzunluğunda sadə yolu var. Və Lemma 5.2 ilə, bütün bu cür yollar matrisdə təmsil olunur.

Beləliklə, G üçün əlçatanlıq qrafikinin A G* bitişik matrisinin qurulması proseduru matrisi n-1-in gücünə yüksəltməyə qədər azaldılır. Bu proseduru sadələşdirmək üçün bəzi qeydlər edək.

burada k ən kiçik ədəddir ki, 2 k n.

belə r tapılır ki, a ir = 1 və a rj =1, onda bütün cəm a ij (2) =1 olur. Buna görə də, qalan şərtləri nəzərə almamaq olar.

Misal 9.3. Nümunə olaraq təqdim olunan G qrafiki üçün A G* əlçatanlıq qrafikinin matrisinin hesablanmasını nəzərdən keçirək. şək.9.2. Bu halda

G-nin 6 təpəsi olduğundan, onda . Bu matrisi hesablayaq:

və (son bərabərliyi yoxlamaq asandır). Bu cür,

Gördüyünüz kimi, bu matris həqiqətən göstərilən qrafiki müəyyənləşdirir şək.9.3.

Qarşılıqlı Əlçatanlıq, Güclü Əlaqəli Komponentlər və Qrafik Əsaslar

Əlçatanlıq qrafikinə bənzətməklə, biz güclü əlçatanlıq qrafikini təyin edirik.

Tərif 9.10. G=(V,E) istiqamətləndirilmiş qrafik olsun. G üçün güclü şəkildə əldə edilə bilən qrafik G * * =(V,E * *) eyni V təpələri dəstinə və aşağıdakı kənarlar dəstinə malikdir E * * =( (u, v) | G-də v və u təpələri qarşılıqlıdır. əlçatan).

Əlçatanlıq qrafikinin matrisindən güclü əlçatanlıq qrafikinin matrisini qurmaq asandır. Həqiqətən, əlçatanlığın və güclü əlçatanlığın təriflərindən birbaşa belə nəticə çıxır ki, bütün (i,j), 1 i,jn cütləri üçün elementin dəyəri yalnız və yalnız hər iki element AG* (i, j) olduqda, 1-ə bərabərdir. və AG* (j, i) 1-ə bərabərdir, yəni.

Matris əsasında G qrafikinin güclü bağlı komponentlərini aşağıdakı kimi ayırmaq olar.

K 1 komponentinə v 1 təpəsini və bütün v j təpələrini elə yerləşdirək ki, A_(G_*^*)(1,j) = 1 olsun.

Qoy K 1 , …, K i və v k komponentləri artıq qurulmuşdur - bu komponentlərə hələ daxil edilməmiş minimum sayda təpədir. Sonra K_(i+1) komponentinə v k təpəsini və bütün belə təpələri v j yerləşdiririk,

ki, A_(G_*^*)(k,j) = 1.

Bütün təpələr komponentlər arasında paylanana qədər (2) addımı təkrarlayın.

Bizim nümunəmizdə G qrafiki üçün şək.2 matris vasitəsilə biz güclü əlçatanlıq qrafikinin aşağıdakı matrisini alırıq

Yuxarıda təsvir edilən prosedurdan istifadə edərək, G qrafikinin təpələrinin 4 möhkəm bağlı komponentə bölündüyünü tapırıq: K 1 = (v 1 , v 2 , v 3 ), \ K 2 =( v 4 ), \ K 3 = ( v 5 ), \ K 4 =( v 6 ). Güclü əlaqəli komponentlər toplusunda biz həmçinin əlçatanlıq əlaqəsini müəyyənləşdiririk.

Tərif 9.11. K və K" qrafiki G-nin güclü bağlı komponentləri olsun. K komponenti -dan əldə edilə bilər komponentləri K^\prime əgər K= K" və ya iki u K və v K" təpələri var ki, u v-dən əldə edilə bilər. K -dən ciddi şəkildə əldə edilə bilər K^\prime əgər K K" və K K"-dən əldə edilə bilər. K komponenti adlanır minimum hər hansı bir komponentdən ciddi şəkildə əlçatan deyilsə.

Bir komponentin bütün təpələri qarşılıqlı şəkildə əldə oluna bildiyindən komponentlər üzrə əlçatanlıq və ciddi əlçatanlıq münasibətlərinin u K və v K təpələrinin seçimindən asılı olmadığını görmək asandır.

Tərifdən nəticə çıxarmaq asandır növbəti xüsusiyyət ciddi əlçatanlıq.

Lemma 9.3. Ciddi əlçatanlıq əlaqəsi qismən sifariş əlaqəsidir, yəni. antirefleksiv, antisimmetrik və keçidlidir.

Bu əlaqə təpələri komponentlər olan istiqamətləndirilmiş qrafik kimi göstərilə bilər və kənar (K, K) K-nin K-dən ciddi şəkildə əldə edilə biləcəyini bildirir. Üstündə düyü. 9.4 komponentlərin bu qrafiki yuxarıda nəzərdən keçirilən G qrafiki üçün göstərilmişdir.

düyü. 9.4.

Bu halda, bir minimal komponent K 2 var.

Bir çox tətbiqlərdə istiqamətləndirilmiş qrafik hansısa resursun paylama şəbəkəsidir: məhsul, məhsul, məlumat və s. Belə hallarda təbii olaraq problem bu resursun şəbəkənin istənilən nöqtəsinə çatdırıla biləcəyi belə nöqtələrin (təpələrin) minimum sayını tapmaqda yaranır.

Tərif 9.12. G=(V,E) istiqamətləndirilmiş qrafik olsun. W V təpələrinin alt çoxluğu adlanır generativ, əgər W təpələrindən qrafikin istənilən təpəsinə çatmaq olarsa. W V təpələrinin alt çoxluğu yaradırsa, lakin öz alt çoxluqlarından heç biri yaratmırsa, qrafik bazası adlanır.

Aşağıdakı teorem qrafikin bütün əsaslarını səmərəli şəkildə tapmağa imkan verir.

Teorem 9.1. G=(V,E) istiqamətləndirilmiş qrafik olsun. W V təpələrinin alt çoxluğu o halda G-nin əsasıdır, o halda ki, o, G-nin hər bir minimal güclü bağlı komponentindən bir təpəni ehtiva edir və başqa təpələri ehtiva etmir.

SübutƏvvəlcə qeyd edin ki, qrafikin hər bir təpə nöqtəsi bəzi minimal komponentə aid olan təpədən əldə edilə bilər. Buna görə də, hər bir minimal komponentdən bir təpədən ibarət W təpələri çoxluğu yaranır və ondan hər hansı bir təpə çıxarıldıqda, o, belə olmaqdan çıxır, çünki müvafiq minimal komponentdən olan təpələr əlçatmaz olur. Beləliklə, W əsasdır.

Əksinə, əgər W əsasdırsa, onda hər bir minimal komponentdən ən azı bir təpə daxil edilməlidir, əks halda belə minimal komponentin təpələri əlçatmaz olacaqdır. W hər hansı digər təpələri ehtiva edə bilməz, çünki onların hər birinə artıq daxil edilmiş təpələrdən əldə etmək olar.

Bu teorem G qrafikinin bütün əsaslarını sadalamaq və ya qurmaq üçün aşağıdakı proseduru nəzərdə tutur.

G-nin bütün güclü əlaqəli komponentlərini tapın.

Onlardakı sıranı müəyyənləşdirin və bu sıraya görə minimal olan komponentləri seçin.

Hər minimum komponentdən bir təpə seçərək qrafikin bir və ya bütün əsaslarını yaradın.

Misal 9.5. Göstərilən istiqamətləndirilmiş G qrafikinin bütün əsaslarını təyin edirik şək.9.5.

düyü. 9.5. Qraf G

Birinci mərhələdə G-nin güclü əlaqəli komponentlərini tapırıq:

İkinci mərhələdə biz bu komponentlər üzərində ciddi əlçatanlıq qrafiki qururuq.

düyü. 9.6. G komponentləri üzrə əlçatanlıq əlaqəsi qrafiki

Minimum komponentləri müəyyən edirik: K 2 = ( b ), K 4 =( d, e, f, g) və K 7 = ( r).

Nəhayət, G-nin bütün dörd əsasını sadalayırıq: B 1 = ( b, d, r), B 2 = ( b, e, r), B 3 = ( b, f, r) və B 1 = ( b, g , r).

Tapşırıqlar

Problem 9.1.İxtiyari yönəldilmiş qrafikin bütün təpələrinin dərəcələrinin cəminin cüt olduğunu sübut edin.

Bu problemin məşhur şərhi var: ziyafətə gələn insanların əl sıxışmalarının ümumi sayının həmişə bərabər olduğunu sübut etmək.

Problem 9.2.Ən çox dörd təpəsi olan bütün qeyri-izomorf yönləndirilməmiş qrafikləri sadalayın.

Problem 9.3.İstiqamətsiz bağlı qrafikin bəzi kənarı çıxardıqdan sonra bağlı qaldığını sübut edin ↔ bu kənar hansısa dövrəyə aiddir.

Problem 9.4. Sübut edin ki, n təpəsi olan istiqamətlənməmiş əlaqəli qrafik

ən azı n-1 kənarları ehtiva edir,

əgər onun tərkibində n-1-dən çox kənar varsa, onda onun ən azı bir dövrü var.

Problem 9.5. Sübut edin ki, 6 nəfərlik hər hansı bir qrupda üç qoşa tanış və ya üç qoşa tanış var.

Problem 9.6.İstiqaməti olmayan G=(V,E) qrafikinin hər bir V= V 1 V 2 bölməsi üçün ↔ bağlı olduğunu sübut edin ki, boş olmayan V 1 və V 2 ilə V 1-i V 2 ilə birləşdirən kənar var.

Problem 9.7. Sübut edin ki, əgər istiqamətləndirilməmiş qrafikdə tək dərəcənin tam olaraq iki təpəsi varsa, deməli, onlar yol ilə bağlıdır.

Problem 9.8. G=(V,E) |E| ilə istiqamətsiz qrafik olsun< |V|-1. Докажите, что тогда G несвязный граф.

Problem 9.9. Birləşdirilmiş istiqamətsiz qrafikdə maksimum uzunluğa malik hər hansı iki sadə yolun ümumi təpəyə malik olduğunu sübut edin.

Məsələ 9.10. G=(V,E) döngələri olmayan istiqamətləndirilməmiş qrafikin k ədəd bağlı komponenti olsun. Onda bunu sübut et

Məsələ 9.11.Əlçatanlıq qrafikinin nə üçün olduğunu müəyyənləşdirin

n təpəsi və boş kənar dəsti olan qrafik;

n təpəsi olan qrafik: V= (v 1 ,… , v n ), kənarları dövrə təşkil edir:

Məsələ 9.12. Qrafik üçün Əlçatanlıq Qrafik Matrisini hesablayın

və müvafiq əlçatanlıq qrafikini qurun. G qrafikinin bütün əsaslarını tapın.

Məsələ 9.13. Verilən üçün tikin düyü. 9.7 istiqamətləndirilmiş qrafik G 1 =(V,E) onun bitişiklik matrisi A G1 , insident matrisi B G1 və bitişiklik siyahıları. A G1* əlçatanlıq matrisini hesablayın və müvafiq G 1 * əlçatanlıq qrafikini qurun.

düyü. 9.7.

İstiqamətsiz və yönləndirilmiş ağaclar

Ağaclar müxtəlif növ iyerarxik strukturları təmsil etmək üçün istifadə edilən ən maraqlı qrafik siniflərindən biridir.

Tərif 10.1.İstiqamətləndirilməmiş qrafik birləşdirilmişdirsə və dövrləri yoxdursa, ağac adlanır.

Tərif 10.2.İstiqamətləndirilmiş qrafik G=(V,E) əgər (yönləndirilmiş) ağac adlanır

Üstündə düyü. 10.1 istiqamətsiz ağac G 1 və istiqamətləndirilmiş ağac G 2 nümunələri göstərilmişdir. Qeyd edək ki, G 2 ağacı G 1-dən c təpəsini kök kimi seçməklə və bütün kənarları "kökdən uzaq" istiqamətə yönəltməklə əldə edilir.

düyü. 10.1.İstiqamətsiz və yönləndirilmiş ağaclar

Bu təsadüfi deyil. İstiqamətsiz və yönəldilmiş ağaclar arasındakı əlaqə haqqında aşağıdakı iddianı özünüzə sübut edin.

Lemma 10.1.Əgər hər hansı istiqamətləndirilməmiş ağacda G=(V,E) kök kimi ixtiyari v V təpəsini seçib bütün kənarları “kökdən” istiqamətə yönəldiriksə, yəni. v-ni ona düşən bütün kənarların başlanğıcı, v-yə bitişik təpələri - v-ə düşən hələ yönəldilməyən bütün kənarların başlanğıcı və s. edin, onda nəticədə yönəldilmiş G" qrafiki istiqamətləndirilmiş ağac olacaqdır.

İstiqamətsiz və yönləndirilmiş ağaclar bir çox ekvivalent xüsusiyyətlərə malikdir.

Teorem 10.1. G=(V,E) istiqamətsiz qrafik olsun. Sonra aşağıdakı şərtlər ekvivalentdir.

G ağacdır.

G-də hər hansı iki təpə üçün onları birləşdirən unikal yol var.

G bağlıdır, lakin E-dən hər hansı bir kənar çıxarıldıqda, onun bağlanması dayandırılır.

G bağlıdır və |E| = |V| -bir.

G asiklikdir və |E| = |V| -bir.

G asiklikdir, lakin E-yə hər hansı bir kənar əlavə etmək bir dövr yaradır.

Sübut(1) (2): Əgər G-də bəzi iki təpə iki yolla birləşdirilsəydi, onda G-də bir dövrə olacağı açıq-aydın olardı. Lakin bu, (1)-dəki ağacın tərifinə ziddir.

(2) (3): Əgər G birləşdirilirsə, lakin bəzi kənar (u,v) çıxarıldıqda E bağlı qalırsa, o zaman u və v arasında bu kənarı ehtiva etməyən bir yol var. Lakin sonra G-nin u və v-ni birləşdirən ən azı iki yolu var ki, bu da (2) şərtinə ziddir.

(3) (4): Oxucuya təqdim olunur (bax problem 9.4).

(4) (5): Əgər G dövrəni ehtiva edirsə və bağlıdırsa, onda dövrədən hər hansı kənarı çıxararkən əlaqə pozulmamalıdır, lakin kənarlar qalır |E|= V -2 və Məsələ 9.4(a) ), qoşulmuş qrafikin ən azı V -1 qabırğası olmalıdır. Yaranan ziddiyyət G-də dövrlərin olmadığını və (5) şərtinin təmin olunduğunu göstərir.

(5) (6): Fərz edək ki, E-yə kənarın (u,v) əlavə edilməsi dövrlə nəticələnmədi. Onda G-də u və v təpələri müxtəlif bağlı komponentlərdədir. |E|= V -1 olduğundan, bu komponentlərdən birində (V 1 ,E 1) olsun, kənarların sayı və təpələrin sayı eynidir: |E 1 |=|V 1 |. Lakin sonra o, G-nin asiklik olması faktına zidd olan bir dövrü ehtiva edir (bax. Məsələ 9.4(b)).

(6) (1): Əgər G əlaqəsi olmasaydı, onda müxtəlif bağlı komponentlərdən iki u və v təpəsi olardı. Sonra (u,v) kənarını E-yə əlavə etmək (6) ilə ziddiyyət təşkil edən dövrənin yaranmasına səbəb olmaz. Beləliklə, G birləşir və ağacdır.

İstiqamətləndirilmiş ağaclar üçün aşağıdakı induktiv tərifdən istifadə etmək çox vaxt rahatdır.

Tərif 10.3.İnduksiya ilə ağaclar adlanan istiqamətləndirilmiş qrafiklər sinfini təyin edirik. Eyni zamanda, onların hər biri üçün seçilmiş təpəni - kökü müəyyənləşdiririk.

düyü. 10.2 bu tərifi göstərir.

düyü. 10.2.İstiqamətləndirilmiş ağacların induktiv tərifi

Teorem 10.2. 10.2 və 10.3 istiqamətləndirilmiş ağacların tərifləri ekvivalentdir.

Sübut G=(V,E) qrafiki 10.2-ci tərifin şərtlərini ödəsin. Təpələrin sayında induksiya ilə göstərək ki, |V|.

Əgər |V|=1 olarsa, onda yeganə v V təpəsi (1) xassə görə ağacın köküdür, yəni. Bu qrafikdə kənarlar yoxdur: E = . Sonra .

Tutaq ki, 10.2 tərifini ödəyən n təpəsi olan istənilən qrafik . (n+1)-ci təpə ilə G=(V,E) qrafiki 10.2-ci tərifin şərtlərini ödəsin. (1) şərtinə görə onun kök təpəsi r 0 var. r 0-dan k kənar çıxsın və onlar r 1 , … , r k (k 1) təpələrinə aparsınlar. V i =( v V|v \textit( )ri ) təpələrini və onları birləşdirən E i E kənarlarını özündə birləşdirən qrafiki G i ,(i=1, …, k) ilə işarələyin. Bunu başa düşmək asandır. ki, G i tərifin şərtlərinə cavab verir 10.2. Həqiqətən, r i kənarları ehtiva etmir, yəni. bu təpə G i-nin köküdür. V i-dən olan digər təpələrin hər birinin G kimi bir kənarı var. Əgər v V i , onda G i qrafikinin tərifi ilə r i kökündən çatmaq olar. |V i | ildən n, sonra induktiv fərziyyə ilə . Sonra G qrafiki 10.3 tərifinin induktiv qaydası (2) ilə G 1 , …, G k ağaclarından alınır və buna görə də sinifə aiddir.

⇐ Əgər hansısa G=(V,E) qrafiki sinifinə aiddirsə, onun üçün 10.2-ci tərifin (1)-(3) şərtlərinin yerinə yetirilməsi 10.2-ci tərif üzrə induksiya ilə asanlıqla müəyyən edilə bilər. Bunu bir məşq kimi oxucunun ixtiyarına buraxırıq.

Orientasiyalı ağaclarla bağlı iki mənbədən gələn zəngin terminologiya var: botanika və ailə münasibətləri sahəsi.

Kök kənarları olmayan yeganə təpədir, yarpaqlar kənarları olmayan təpələrdir. Kökdən yarpağa gedən yola ağacın budağı deyilir. Ağacın hündürlüyü onun budaqlarının maksimum uzunluğudur. Təpənin dərinliyi kökdən həmin təpəyə gedən yolun uzunluğudur. v V təpəsi üçün T=(V,E) ağacının alt qrafası, v-dən çata bilən bütün təpələr və E-dən onları birləşdirən kənarlar daxil olmaqla, v kökü olan T ağacının T v alt ağacını təşkil edir (bax. Məsələ 10.3). . v hündürlüyü ağacın hündürlüyü T v . Bir neçə kəsişməyən ağacın birləşməsindən ibarət olan qrafikə meşə deyilir.

Əgər kənar v təpəsindən w təpəsinə keçirsə, onda v deyilir ata w və w - oğlum v (in Son vaxtlar ingilisdilli ədəbiyyatda aseksual cüt terminlərdən istifadə olunur: valideyn - uşaq). Ağacın tərifindən birbaşa belə nəticə çıxır ki, hər bir təpənin kökdən başqa özünəməxsus atası var. Əgər yol v təpəsindən w təpəsinə aparırsa, v təpəsinə w-nin əcdadı, w isə v-nin nəsli adlanır. Ümumi atası olan təpələr deyilir qardaşlar və ya bacılar.

İstiqamətləndirilmiş ağacları ümumiləşdirən daha bir qrafik sinfini - istiqamətləndirilmiş asiklikləri ayırırıq. Aşağıda Boolean funksiyalarını təmsil etmək üçün bu cür etiketlənmiş qrafiklərin iki növü istifadə olunacaq. Bu qrafiklərin bir neçə kökü ola bilər - kənarları daxil olmayan təpələr və hər bir təpənin ağaclar kimi bir deyil, bir neçə kənarı ola bilər.

kompüter texnologiya, xüsusilə proqram ... 2009 ilin İbtidai məktəb eksperimental saytdır haqqında Federal təqdimatı dövlət ...

M ONİTORİNQ MEDIA Peşə təhsilinin müasirləşdirilməsi Mart - Avqust 2011

Xülasə

Birləşmiş dövlət imtahanlar" haqqında seçim": məlumat kompütertexnologiya, biologiya və ədəbiyyat. Yeri gəlmişkən, bunda ilİSTİFADƏ EDİN... sual“İcranın nəticələri haqqında proqramlar milli inkişafı tədqiqat universitetləri in 2009 -2010 illər". ...

STRATEJİ İNKİŞAF PROQRAMI Tver 2011

Proqram

IN 2009 il. 2010-cu ildə görülən struktur dəyişiklikləri ilhaqqında doğru 2009 , ... Peşəkar olaraq – yönümlü xarici dil”, “Müasir təhsil texnologiya". Hər birində proqram qabaqcıl təlim modulu " dövlət ...

Əlçatanlıq qrafikinə bənzətməklə, biz güclü əlçatanlıq qrafikini təyin edirik.

Tərif: İstiqamətləndirilmiş qrafik olsun. Güclü Əlçatanlıq Qrafiki
üçün həm də çoxlu təpələr var və növbəti kənarlar dəsti
sütunda zirvələri Və qarşılıqlı əlçatandır.

Əlçatanlıq Qrafik Matrisi ilə
matris qurmaq asandır
güclü əlçatanlıq qrafiki. Həqiqətən, bütün cütlər üçün əlçatanlıq və güclü əlçatanlıq təriflərindən birbaşa irəli gəlir
,
, element dəyəri
yalnız və yalnız hər iki element olduqda 1-ə bərabərdir
Və
1-ə bərabərdir, yəni.

Matrislə
qrafikin güclü bağlı komponentlərini ayırmaq olar aşağıdakı şəkildə:

Bütün təpələr komponentlər arasında paylanana qədər ikinci addımı təkrarlayın.

Qrafik üçün nümunəmizdə misal 14.1. matrislə
güclü əlçatanlıq qrafikinin aşağıdakı matrisini alırıq

Yuxarıda təsvir edilən prosedurdan istifadə edərək, qrafikin təpələrini tapırıq 4 güclü əlaqəli komponentə bölünür:
,
,
,
. Güclü əlaqəli komponentlər toplusunda biz həmçinin əlçatanlıq əlaqəsini müəyyənləşdiririk.

Tərif: Qoy olsun
Və
qrafikin güclü bağlı komponentləridir . Komponent
əldə edilə bilən komponentdən
, əgər
ya da iki belə təpə var
Və
, nə -dan əldə edilə bilər .
-dən ciddi şəkildə əldə edilə bilər
, əgər
Və
-dan əldə edilə bilər
. Komponent
hər hansı komponentdən ciddi şəkildə əlçatan deyilsə, minimal adlanır.

Bir komponentin bütün təpələri qarşılıqlı şəkildə əldə oluna bildiyi üçün komponentlər üzrə əlçatanlıq və ciddi əlçatanlıq münasibətlərinin təpələrin seçimindən asılı olmadığını başa düşmək asandır.
Və
.

Ciddi əlçatanlığın aşağıdakı xarakteristikasını tərifdən asanlıqla çıxarmaq olar.

Lemma: Ciddi əlçatanlıq əlaqəsi qismən sifariş əlaqəsidir, yəni. antirefleksiv, antisimmetrik və keçidlidir.

Bu əlaqə təpələri komponentləri və kənarı olan istiqamətlənmiş qrafik kimi göstərilə bilər.
bunun mənası
-dən ciddi şəkildə əldə edilə bilər
. Misal 14.1 üçün komponent qrafiki aşağıda göstərilmişdir.

Bu vəziyyətdə bir minimum komponent var
.

Bir çox tətbiqlərdə istiqamətləndirilmiş qrafik hansısa resursun paylama şəbəkəsidir: məhsul, məhsul, məlumat və s. Belə hallarda təbii olaraq problem bu resursun şəbəkənin istənilən nöqtəsinə çatdırıla biləcəyi belə nöqtələrin (təpələrin) minimum sayını tapmaqda yaranır.

Tərif: Qoy olsun
istiqamətlənmiş qrafikdir. Təpələrin alt çoxluğu
çağırdı generativəgər təpələrdən
qrafikin istənilən təpəsinə çatmaq olar. Təpələrin alt çoxluğu
generasiya edirsə, qrafikin əsası adlanır, lakin onun heç bir müvafiq alt çoxluğu yaranmır.

Aşağıdakı teorem qrafikin bütün əsaslarını səmərəli şəkildə tapmağa imkan verir.

Teorem: Qoy olsun
istiqamətlənmiş qrafikdir. Təpələrin alt çoxluğu
əsasdır minimum güclü bağlı komponentlərin hər birindən bir təpəni ehtiva edərsə və yalnız və heç bir başqa təpələri ehtiva etmir.

Sübut: əvvəlcə qeyd edin ki, qrafikin hər bir təpə nöqtəsi bəzi minimal komponentə aid olan təpədən əldə edilə bilər. Buna görə də təpələr dəsti
Hər bir minimal komponentdən bir təpə olan , yaradır və ondan hər hansı bir təpə çıxarıldıqda o, belə olmaqdan çıxır, çünki müvafiq minimal komponentdən olan təpələr əlçatmaz olur. Buna görə də
əsasdır.

Əksinə, əgər
əsasdır, onda hər bir minimal komponentdən ən azı bir təpəni daxil etməlidir, əks halda belə minimal komponentin təpələri əlçatmaz olacaq. Başqa zirvələr yoxdur
ehtiva edə bilməz, çünki onların hər birinə artıq daxil edilmiş təpələrdən əldə etmək olar.

Bu teorem bir qrafikin qurulması və ya bütün əsaslarının sadalanması üçün aşağıdakı proseduru nəzərdə tutur :

Misal 14.3: İstiqamətləndirilmiş qrafikin bütün əsaslarını təyin edin .

Birinci mərhələdə biz güclü bağlı komponentləri tapırıq :

İkinci mərhələdə biz bu komponentlər üzərində ciddi əlçatanlıq qrafiki qururuq.

Minimum komponentləri müəyyənləşdiririk:
,
Və
.

Nəhayət, bütün dörd əsasları sadalayın :
,
,
Və
.

QRAFİKALARDA ƏLAÇILABİLƏNLİK VƏ ƏLAQƏLİLİK Mühazirənin xülasəsi: Zəncirin yolları və dövrələr. Qrafik əlaqə və əlaqə komponentləri. Diametri, radiusu və qrafikin mərkəzi.

Sosial şəbəkələrdə işi paylaşın

Əgər bu iş sizə uyğun gəlmirsə, səhifənin aşağı hissəsində oxşar işlərin siyahısı var. Axtarış düyməsini də istifadə edə bilərsiniz

Baranov Viktor Pavloviç Diskret Riyaziyyat. Bölmə 3Qrafiklər, şəbəkələr, kodlar.

Mühazirə 8

Mühazirə 8 QRRAFLARDA ƏLAÇILABİLƏNLİK VƏ BAĞLILIK

Mühazirə planı:

1. Marşrutlar, zəncirlər və dövrələr.
2. Qrafik əlaqə və əlaqə komponentləri.
3. Diametri, radiusu və qrafikin mərkəzi.
4. Əlçatanlıq və əks əlçatanlıq matrisləri.

1. Marşrutlar, dövrələr və döngələr

İstiqamətləndirilmiş marşrut(və ya tərəfindən ) diqrafın sonuncudan başqa hər hansı qövsün son təpəsinin növbəti qövsün başlanğıc təpəsi olduğu qövslər ardıcıllığıdır. Əncirdə. 1 qövs ardıcıllığı

, (1)

, (2)

(3)

yollardır.

düyü. bir.

yönümlü zəncir(və ya orepio ) hər bir qövsün keçdiyi yol və adlanır-dan bir dəfədən çox istifadə olunmur. Beləliklə, məsələn, (2) və (3) yollar zəncirdir, lakin yol (1) deyil, çünki qövs iki dəfə istifadə olunur.

Sadə hər təpənin ən çox birinin istifadə olunduğu zəncir adlanır haqqında dəfə. Məsələn, orchain (3) sadədir, lakin orchain (2) sadə deyil.

Marşrut yolun yönləndirilməyən əkizidir, yəni hər bir kənarın, birinci və sonuncu istisna olmaqla, kənarları və kənarları ilə son təpələri ilə birləşdirildiyi kənarların ardıcıllığıdır. Qövs simvolunun üzərindəki çubuq onun kənar kimi qəbul edildiyini bildirir.

Biz zəncirləri və sadə zəncirləri təyin etdiyimiz kimi, zəncirləri və sadə zəncirləri də müəyyən edə bilərik.

Yol və ya marşrut həm də təpələrin ardıcıllığı ilə təmsil oluna bilər. Misal üçün Və ölçülər, yol (1) belə yazıla bilər: .

Yol qapalı adlanır , onun içindəki qövsün ilkin təpəsi atla üst-üstə düşərsə h qövsün zirvəsi. Qapalı zəncirlər (zəncirlər) adlanır və ya velosipedlər (dövrlər ). Orsikllər də adlanır konturlar . Qapalı sadə zəncirlər (zəncirlər) adlanır s sadə və ya velosipedlər(dövrlər). bağlı marşrutistiqamətsizdir n qapalı ikiqat Səndə.

1. Qrafik Əlaqə və Əlaqə Komponentləri

Diqrafdakı təpənin zirvədən əldə edilə biləcəyi deyilir, əgər yol varsa. Bundan əlavə, buradan əldə edilə bilərsə, bu təpələrin qarşılıqlı olaraq əldə edilə biləcəyi deyilir.

Diqrafa güclü bağlı və ya güclü deyilir , onda hər hansı iki təpə varsa Amma imo əldə edilə bilər. Güclü diqrafın nümunəsi Şəkildə göstərilmişdir. 2 a. Sütunda olduğundan e bütün təpələri özündə cəmləşdirən orcycle verilir, onda onlardan hər ikisi alınır lakin əldə edilə bilər.

° ° °

° ° ° ° ° °

° ° ° ° ° °

a B C

düyü. 2.

Diqraf deyilirbir şəkildə bağlıdır və ya birtərəfli onun təpələrinin hər hansı bir cütündə ən azı birinə digərindən çatmaq olarsa. Birtərəfli qrafikin nümunəsi Şəkildə göstərilmişdir. 2 b. Bu qrafikdə dörd qarşılıqlı əldə edilə bilən təpədən ibarət bir dövrə var. Təpənin sıfıra daxil olma dərəcəsi var, yəni bu təpəyə aparan yollar yoxdur. Üstəlik, digər dörd təpədən hər hansı biri ondan əldə edilə bilər.

Diqraf deyilir zəif bağlıdır və ya zəifdir , hər hansı iki təpəni ehtiva edərsə təxminən yarısı birləşdi . Yarım yol, yoldan fərqli olaraq, əks istiqamətə malik ola bilər. in tənbəl qövslər. Zəif bir diqrafın nümunəsi Şəkildə göstərilmişdir. 2 in. Qrafikdə olmadığı aydındır saat və təpələri arasında ty, lakin əks n-dən ibarət yarım yol var Amma idarə olunan qövslər və.

Bəzi təpələr cütü üçün onları birləşdirən marşrut yoxdursa, onda t Amma hansı diqraf adlanır uyğunsuz.

Diqraf üçün üç növ bağlı komponent müəyyən edilmişdir:güclü komponent– ma k ən güclü subqraf,birtərəfli komponent- maksimum tək haqqında ronny subqraf vəzəif komponentən zəif subqrafdır.

Güclü komponent anlayışı Şəkildə göstərilmişdir. 3.

° ° ° ° ° °

° ° ° °

° ° ° ° ° °

° ° ° ° ° °

° ° °

° ° ° ° °

düyü. 3

Bir istiqamətli bağlı olan bir qrafik altı güclüdən ibarətdir d yalnız və güclü komponentləri olan qrafiklər n tami. Birtərəfli komponent anlayışı oxşar şəkildə təsvir edilmişdir. Bu qeyddə e Yenidən birtərəfli komponent qrafikin özü ilə eynidir. Orientasiyanı dəyişdirsək Amma arc, məsələn, əks birinə, onda iki birtərəfli zəif bir qrafik alırıq haqqında frontal komponentlərdən biri təpələrdən, digəri isə ve r təkərlər.

İstiqamətsiz qrafik üçün onun təpələri çoxluğunda zibil qutusunu təyin edirik R bağlı bir zəncirin olub olmadığını fərz etməklə. Bu əlaqə Amma refleksivlik, simmetriya və keçidlilik xassələrini verir, yəni haqqındadır T ekvivalent geyinmək. O, təpələr dəstini kəsişməyən siniflərə bölür: . Eyni sinifdən olan iki təpə ekvivalentdir, yəni qrafikdə onları birləşdirən zəncir var, müxtəlif siniflərdən olan təpələr üçün belə zəncir yoxdur. Sonlarından bəri Yu Əgər kənarlar əlaqədədirsə, onda qrafikin kənarlar çoxluğu da kəsişməyən siniflərə bölünəcək: , burada ucları aid olan bütün kənarların çoxluğu ilə işarələnir.

Qrafiklər birləşdirilir və bir qrafikə əlavə olunur. Bu qrafiklər adlanırəlaqə komponentləriqrafik. Ədəd qrafikin başqa bir ədədi xarakteristikasıdır. Bağlı bir qrafik üçün, əgər qrafik ayrılıbsa, o zaman.

Əgər verilmiş qrafik bağlı deyilsə və bir neçə komponentə bölünürsə, bu qrafiklə bağlı istənilən sualın həlli, bir qayda olaraq, birləşdirilən ayrı-ayrı komponentlərin öyrənilməsinə qədər azaldıla bilər. Buna görə də, əksər hallarda verilmiş qrafikin bağlı olduğunu güman etmək məntiqlidir.

1. Diametr, radius və qrafik mərkəzi

Bağlı bir qrafik üçün müəyyən edirik məsafə onun iki təpəsi arasında və bu təpələri birləşdirən ən qısa zəncirin uzunluğu kimi və ilə işarələnir. Zəncirin uzunluğu zənciri təşkil edən kənarların sayıdır. Daxil olduğunuzu yoxlamaq asandır n Bu məsafə metrikanın aksiomlarına cavab verir:

2) ;

3) .

Qrafikin hər təpəsindən ondan ən uzaq təpəyə qədər olan məsafəni təyin edin

hansı adlanırekssentriklik. Aydındır ki, tam qrafikdə bütün təpələr üçün ekssentriklik birə bərabərdir və sadə dövrənin təpələri üçün - .

Maksimum ekssentriklik deyilir Diametr qrafik və minimum - radius qrafik. Tam qrafikdə bizdə və sadə dövrədə - .

Əgər təpəyə mərkəzi deyilir. Qrafikdə bir neçə ola bilər b belə təpələr, bəzi qrafiklərdə isə bütün təpələr mərkəzidir. Sadə bir zəncirdə, tək sayda təpələri olan, yalnız biri mərkəzi və cüt sayı ilə-dan iki belə təpə var. Tam bir qrafikdə və sadə bir dövr üçün bütün təpələr mərkəzidir. Mərkəzi təpələr dəsti deyilir qrafikin mərkəzi.

Misal 1 Şəkildə göstərilən qrafikin diametrini, radiusunu və mərkəzini tapın. 4.

° °

° ° °

° °

° °

düyü. 4.

Bu problemi həll etmək üçün əvvəlcədən hesablama aparmaq rahatdırməsafə matrisi zirvələr arasında sayıram. Bu halda, təpədən təpəyə qədər olan məsafənin yerləşdiyi ölçülü bir matris olacaq:

Matrisin hər sətri üçün ən böyük elementi tapırıq və onu yazırıq Amma tiredən wa. Bu ədədlərin ən böyüyü qrafikin diametrinə bərabərdir, ən kiçiyi isə p-dir Amma qrafikin diusu. Qrafikin mərkəzi mərkəzi təpələri və ilə formalaşır.

Qrafikin mərkəzi təpəsi və mərkəzi anlayışları optimizm problemləri ilə əlaqədar meydana çıxdı. Və xəstəxanalar, yanğınsöndürmə idarələri, ictimai asayişi təmin edən məntəqələr və s. kimi ictimai xidmət məntəqələrinin kiçik yerləşməsi, minimuma endirilməsi vacibdir. Və bəzi şəbəkənin istənilən nöqtəsindən ən yaxın xidmət nöqtəsinə qədər daha böyük məsafə bir niya.

1. Əlçatanlıq və əks əlçatanlıq matrisləri

Əlçatanlıq matrisiaşağıdakı kimi müəyyən edilir:

Verilmiş təpədən əldə edilə bilən qrafik təpələri dəsti matrisdəki 1-ci elementin 1-ə bərabər olduğu elementlərdən ibarətdir. Bu çoxluq aşağıdakı kimi göstərilə bilər.

Qarşı əlçatanlıq matrisi (tərs əlçatanlıq) müəyyənləşdirmək aşağıdakı kimidir:

Əlçatan dəstin qurulmasına bənzər şəkildə, bir dəst təşkil edilə bilər haqqında aşağıdakı ifadədən istifadə edərək jest:

Təriflərdən belə çıxır ki, matrisin --ci sütunu ma-nın -ci sətri ilə üst-üstə düşür. T , yəni matrisə köçürülmüş matris haradadır.

Misal 2 Qrafik üçün əlçatanlıq və əks əlçatanlıq matrislərini tapın və s. Və Şəkildə göstərilmişdir. beş.

düyü. beş.

Qrafik təpələri üçün əlçatanlıq dəstlərini müəyyən edək:

Beləliklə, əlçatanlıq və əlçatanlıq matrisləri aşağıdakı formaya malikdir:

Hər biri ən azı bir yola aid olan bu cür təpələrin çoxluğundan-a gedən olduğundan, bu çoxluğun təpələri adlanır. vacibdir və ya ayrılmazdır son təpələrə görə və. Bütün digər təpələr deyilirəhəmiyyətsiz və ya lazımsız , çünki onların aradan qaldırılması yollara təsir etmir.

Siz həmçinin matrisləri təyin edə bilərsiniz məhduddur əlçatanlıq və əks əlçatanlıq Və körpülər, əgər biz tələb etsək ki, yolların uzunluqları verilmiş bəzi rəqəmləri aşmasın. Sonra icazə verilən yolların uzunluğunun yuxarı həddi olacaq.

Qrafikin keçidli olduğu deyilir əgər qövslərin və izlərin mövcudluğundan saat qövsün varlığı var.keçid bağlanmasıqrafik bir qrafikdir, burada qrafikin keçidli olması üçün lazım olan minimum mümkün qövslər dəstidir. Aydındır ki, matrisdə əsas diaqonalın üzərinə vahidlər qoysaq, qrafikin əlçatanlıq matrisi qrafikin bitişiklik matrisi ilə üst-üstə düşür.

Döngələri olan, lakin çoxsaylı qövsləri olmayan G(V,X) V çoxluğunda X ikili münasibətini təyin edir. Tam qrafik universal əlaqəyə uyğundur. İstiqamətsiz qrafik simmetrik əlaqəyə uyğundur. Qrafikin tamamlayıcısı münasibətin tamamlayıcısına uyğun gəlir. Qövslərin istiqamətinin dəyişdirilməsi əks əlaqəyə uyğundur.

Diqraflar və binar əlaqələr müxtəlif vasitələrlə təsvir edilən eyni obyektlər sinfidir. Binar münasibətlər, funksiyalar böyük əksəriyyətin qurulması üçün əsas alətlərdir riyazi modellər praktiki məsələləri həll etmək üçün istifadə olunur və qrafiklər diaqram şəklində əyani təsvir etməyə imkan verir. Bu, kodlaşdırma və dizaynda müxtəlif növ diaqramların geniş istifadəsini izah edir.

Diqrafın (qrafik) b təpəsi G adlanır əldə edilə bilən U-dan yalnız və yalnız U=V olduqda və ya U-nu V ilə birləşdirən yol (marşrut) olduqda (U ilkin təpədir, V son təpədir). Beləliklə, diqrafın (qrafik) təpələri çoxluğunda təkcə A bitişiklik əlaqəsi deyil, həm də əldə olma münasibəti T müəyyən edilir.

Əlçatanlıq matrisi T diqrafik (qrafik) G T 2 n×n adlanır, onun elementləri şərtdən tapılır: 1, əgər ondan əldə etmək olarsa; 0-dan əldə etmək mümkün deyilsə.

Diqrafın əlçatanlıq matrisinin qonşuluq əlaqəsinin refleksiv və keçidli qapanma matrisi kimi müəyyən edilməsi.

G(V,X) qrafikinin təpələrində təqdim edilmiş əlçatanlıq əlaqəsi: əgər v təpəsindən w təpəsinə çatmaq olar, əgər v = w olarsa və ya G-də v-dən w-ə qədər yol varsa. Başqa sözlə, əlçatanlıq qonşuluq əlaqəsinin refleksiv və keçidlə bağlanmasıdır.

Qonşuluq matrisini, keçid və refleksiv qapanmanı tapın.

Qrafiklərdə əlaqə. Diqraflarda zəif, birtərəfli və güclü əlaqə. Bağlantı və güclü əlaqə matrisi. Bağlantı komponentləri. Əlçatanlıq matrisinə əsaslanan güclü əlaqə matrisinin tərifi.

G(V,X) adlanır əlaqədar onun təpələrindən hər hansı digərinə hər hansı digər təpədən çatmaq olarsa.

G(V,X) diqrafı adlanır bir şəkildə bağlıdır, əgər onun hər iki təpəsi üçün ən azı birinə digərindən çatmaq olarsa.

G(V,X) diqrafı adlanır möhkəm bağlıdırəgər onun təpələrindən hər hansı biri digərindən əlçatandırsa.

G(V,X) diqrafı adlanır sərbəst bağlanır, əgər qövslərin oriyentasiyasının silinməsi nəticəsində ona uyğun gələn qeyri-diqraf bağlanırsa.

Zəif bağlı olmayan diqraf deyilir uyğunsuz.

Güclü bağ komponenti diqrafının G(V,X) təpələrinin baş vermə sayına görə maksimal adlanır, bu diqrafın güclü bağlı yarımqrafı. Qeyri-diqrafın əlaqəli komponenti oxşar şəkildə müəyyən edilir.

Güclü əlaqə matrisi (bağlantı) diqrafının (qrafik) G(V,Х) elementləri şərtdən tapılan S n×n adlanır: 1-dən və ondan çatmaq olarsa; 0-dan əldə etmək mümkün deyilsə və ondan əldə etmək mümkün deyilsə.

(diqraf) güclü bağlı və ya əlaqəli olduqda, matrisdə 0-ın mövcudluğunu müəyyən etmək kifayətdir, əgər

0 yoxdur, onda qrafik (diqraf) bağlıdır (güclü bağlıdır), əks halda deyil.

Güclü əlaqəli matris, düsturla əldə edilə bilənlik matrisindən qurula bilər