Model matematik. Algoritma untuk mengekstrak komponen yang bersambung kuat

Biarkan G(V,X) ialah pseudograf dan biarkan bucu v dan w (v¹w) graf ini disambungkan dengan laluan. Maka semestinya terdapat laluan minimum yang menghubungkan bucu ini. Nyatakan panjang laluan ini d(v, w). Kami juga menetapkan d(v, v) =0 untuk sebarang bucu vнV; d(v, w) = ¥ jika tiada laluan antara v dan w.

Nilai d(v,w) ditakrifkan dengan cara ini untuk sebarang bucu v dan w graf G(V, X) dipanggil jarak antara v dan w.

Bilangan jarak dalam graf dengan n bucu adalah sama dengan bilangan gabungan C n 2 .

Biarkan graf G(V,X) disambungkan. Mari kita tentukan konsep berikut untuknya:

Diameter graf: d(G) = maxd(v, w).

Sipi (offset maksimum) bagi puncak: r(v) = maxd(v, w);

Jejari Graf: r(G) = min r(v);

Pusat Graf: mana-mana bucu vОV supaya r(v) = r(G).

Diameter graf, kesipian bucu, jejari graf, dan pusat graf dipanggil ciri metrik graf.

Contoh. Cari ciri metrik graf yang diberikan oleh rajah:

Mari kita cari semua jarak, dengan mengambil kira bahawa d(v, w) = d(w, v).

Bilangan jarak dalam graf yang diberi С 5 2 = 5!/3!2! = 10: d(v 1 , v 2) =1, d(v 1, v 3) = 2, d(v 1, v 4) = 2, d(v 1, v 5) = 3, d(v 2 , v 3) = 1, d(v 2 , v 4) = 1, d(v 2, v 5) = 2, d(v 3, v 4) = 1, d(v 3, v 5) = 2, d(v 4 , v 5) = 1.

Diameter graf d(G) =3.

Sipi bucu: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3.

Jejari graf r(G) = 2.

Pusat graf v 2 , v 3 , v 4 .

3. Laluan minimum dalam graf yang dimuatkan

Graf G(V, X) dipanggil dimuatkan jika pada set tepi graf terdapat fungsi yang dipanggil fungsi pemberat yang mengaitkan dengan setiap tepi x нX graf beberapa nombor l(x). Nilai l(x) dipanggil panjang lengkok.

Kuantiti l(x) boleh diberikan makna yang berbeza: kos pengangkutan, masa perjalanan, jarak antara titik, penggunaan petrol, dsb.

Jumlah panjang tepi yang termasuk dalam laluan dipanggil panjang laluan.

Ambil perhatian bahawa jika untuk semua x н X l(x) = 1, maka graf boleh dianggap sebagai dipunggah.

Satu laluan dalam graf G(V, X) dari bucu v ke bucu w (v¹w) dipanggil minimum jika ia mempunyai panjang minimum antara semua laluan dalam graf G(V, X) dari bucu v ke bucu w.

Kami mengehadkan diri kami kepada graf yang l(x)>0.

Apabila mencari laluan minimum dalam graf yang dimuatkan dengan l(x)>0

kami menggunakan pernyataan yang sama seperti untuk graf yang tidak dimuatkan, iaitu:

mana-mana laluan minimum ialah laluan yang mudah.

Pertimbangkan sekarang masalah mencari laluan minimum dalam graf yang dimuatkan.

Biarkan graf G(V,X) dimuatkan, bilangan bucu n ³ 2, adalah perlu untuk membina laluan minimum dari v 1 ke v n .

Mari kita berikan algoritma.

Langkah 1. Berikan indeks a(v i) kepada setiap bucu: a(v 1) = 0, a(v i) = ¥, i ¹ 1. Warnakan bucu v 1 dan tetapkan v = v 1 .

Langkah 2. Untuk setiap bucu tidak berwarna v j tukar indeks mengikut peraturan:

a(v j) = min (a(v j), a(v) + l(v, v j)).

Warnakan bucu yang a(v j) adalah terkecil.. warnakan juga tepi yang menuju ke nod yang dipilih. langkah ini puncak v j . Letakkan v = v j .

Langkah 3. Jika v = v j , selesaikan prosedur sejak laluan terpendek dari v 1 hingga v n . jika v ¹ v n , kemudian pergi ke langkah 2.

Komen. Langkah 2 adalah mustahil jika semua a(v j)= ¥. Dalam kes ini, bucu v n tidak boleh dicapai.

Mari kita gunakan algoritma di atas pada graf yang diberikan oleh rajah. Mari cari di dalamnya laluan terpendek dari v 1 hingga v 6 .

Langkah 1. Warnakan bucu v 1 . Tetapkan indeks pada bucu: a(v 1) =0, a(v 2) = a(v 3)=…= a(v n)=¥. Kami menetapkan v 1 = v.

a(v 2) = min(¥, 0+4) = 4,

a(v 3) = min(¥, 0+7) = 7,

a(v 4) = min(¥, 0+3) = 3,

a(v 5) = min (¥, 0+¥) = ¥,

a(v 6) = min (¥, 0+¥) = ¥.

Kami mewarnakan bucu v 4 dan tepi (v 1, v 4).

Langkah 3. Oleh kerana bucu v 6 tidak berwarna, kami melakukan langkah 2, menetapkan v = v 4 .

a(v 2) = min(4, 3+¥) = 4,

a(v 3) = min(7, 3+¥) = 7,

a(v 5) = min(¥, 3+3) = 6,

a(v 6) = min (¥, 3+¥) = ¥.

Kami mewarnakan bucu v 2 dan tepi (v 1, v 2).

Langkah 3. Oleh kerana bucu v 6 tidak berwarna, kami melakukan langkah 2, menetapkan v = v 2 .

a(v 3) = min(7, 4+3) = 7,

a(v 5) = min(6, 4+2) = 6,

a(v 6) = min (¥, 4+¥) = ¥.

Kami mewarnakan bucu v 5 dan tepi (v 4, v 5).

Langkah 3. Memandangkan bucu v 6 tidak berwarna, kami melakukan langkah 2, menetapkan v = v 5 .

a(v 3) = min(7, 6+¥) = 7,

a(v 6) = min (¥, 6+2) = 8.

Kami mewarnakan bucu v 3 dan tepi (v 1, v 3).

Langkah 3. Memandangkan bucu v 6 tidak berwarna, kami melakukan langkah 2, menetapkan v = v 3 .

a(v 6) = min(8, 7+2) = 8.

Kami mewarnakan bucu v 6 dan tepi (v 5 , v 6 ).

Memandangkan bucu v 6 berwarna, kami menghentikan kerja. Kami mendapat laluan minimum v 1 v 4 v 5 v 6 , yang panjangnya bersamaan dengan 8 .

Ambil perhatian bahawa ini adalah dalam kes ini bukan satu-satunya laluan minimum untuk bucu v 1 dan v 6, kerana dalam algoritma adalah mungkin untuk mewarna dan bukannya tepi (v 4, v 5) tepi (v 2, v 5), maka kita akan mendapat laluan lain yang sama panjang.

4. Tugas pada pokok

Graf dipanggil asiklik jika tiada kitaran.

Graf tanpa kitaran dipanggil hutan.

Pokok ialah graf asiklik bersambung.

Dalam bahagian terakhir, kami menekankan bahawa matriks bersebelahan $A$ yang diperkenalkan di sana, atau sebaliknya matriks bersebelahan bucu graf, memainkan peranan yang sangat penting. peranan penting dalam teori graf. Kami perhatikan sebagai kelebihan matriks ini - ia adalah segi empat sama tertib, sama dengan nombor baris matriks kejadian $B$, iaitu, sebagai peraturan, mengandungi bilangan yang lebih kecil elemen. Kedua, matriks ini menyimpan semua maklumat tentang tepi graf dan, untuk penomboran bucu tertentu, secara unik menerangkan graf. Matriks bersebelahan, seperti matriks kejadian graf, ialah matriks (0,1), i.e. unsur-unsurnya boleh dianggap sebagai unsur-unsur struktur algebra lain, dan bukan sahaja sebagai unsur-unsur set integer. Khususnya, kami ambil perhatian bahawa unsur-unsur matriks bersebelahan boleh dianggap sebagai unsur algebra Boolean, tertakluk kepada undang-undang aritmetik Boolean, tetapi tidak menerangkannya dengan betul. Sebelum mengisi jurang ini, kami menekankan kelebihan matriks bersebelahan, yang mengikuti dari segi empat samanya.

Untuk melakukan ini, kita ingat peraturan untuk pendaraban matriks. Biarkan matriks arbitrari dengan unsur berangka diberikan: matriks $A$ dimensi $n\kali m$ dengan unsur $a_(ik)$ dan matriks $B$ dimensi $m\kali q$ dengan unsur $b_(kj)$ . Matriks $C$ dimensi $n\kali q$ dipanggil hasil darab matriks $A$ dan $B$ (tertib adalah penting) jika unsur-unsurnya $c_(ij)$ ditakrifkan seperti berikut: $c_(ij) = \jumlah\had_( k = 1)^m (a_(ik) b_(kj))$. Hasil darab matriks ditulis dengan cara biasa $AB=C$. Seperti yang anda lihat, hasil darab matriks memerlukan ketekalan dalam saiz faktor pertama dan kedua (bilangan lajur matriks faktor pertama adalah sama dengan bilangan baris matriks faktor kedua). Keperluan ini hilang jika kita menganggap matriks segi empat sama susunan yang sama dan, oleh itu, kita boleh mempertimbangkan kuasa sewenang-wenangnya bagi matriks segi empat sama. Ini adalah salah satu kelebihan matriks segi empat sama berbanding matriks segi empat tepat. Kelebihan lain ialah kita boleh memberikan tafsiran graf kepada unsur darjah matriks bersebelahan.

Biarkan matriks bersebelahan $A$ dalam bentuk: $A = \left(((\begin(array)(*c) (a_(11) ) & (a_(12) ) & (...) & ( a_(1n ) ) \\ (a_(21) ) & (a_(22) ) & (...) & (a_(2n) ) \\ (...) & (...) & (.. .) & (...) \\ (a_(n1) ) & (a_(n2) ) & (...) & (a_(nn) ) \\ \end(array) )) \kanan)$, dan kuasa $ k$th — $A^k = \left(((\begin(array)(*c) (a_(11)^((k)) ) & (a_(12)^(k) ) ) & (...) & (a_(1n)^((k)) ) \\ (a_(21)^((k)) ) & (a_(22)^((k)) ) & ( .. .) & (a_(2n)^((k)) ) \\ (...) & (...) & (...) & (...) \\ (a_(n1)^ (( k)) ) & (a_(n2)^((k)) ) & (...) & (a_(nn)^((k)) ) \\ \end(array) )) \kanan) $, dengan $k = 2,3,...$ Jelas sekali bahawa $A^k$, seperti matriks $A$, akan menjadi matriks simetri.

Biarkan $k=2$. Kemudian $a_(ij)^((2)) = \sum\limits_(k = 1)^n (a_(il) a_(lj))$ ($i,j = 1,2,...,n $), dan setiap istilah $a_(il) a_(lj)$ adalah sama dengan $0$ atau $1$. Kes apabila $a_(il) a_(lj) = 1$ bermakna terdapat dua tepi dalam graf: tepi $\(i,l\)$ (sejak $a_(il) = 1)$ dan tepi $\( l,j\)$ (sejak $a_(lj) = 1$) dan dengan itu laluan $\(( \(i,l\), \(l,j\) )\)$ daripada $i $- th bucu hingga $j$-th panjang dua (laluan dua tepi). Di sini kita bercakap ia adalah mengenai laluan, bukan rantai, kerana arahnya ditunjukkan - dari dari puncak $i$-th ke $j$-th. Oleh itu, $a_(ij)^((2))$ memberi kita nombor semua laluan pada graf (dalam tafsiran geometri graf) dengan panjang 2 menuju dari puncak $i$ ke $j$th satu.

Jika $k=3$ maka $A^3 = A^2A = AA^2 = AAA$ dan $a_(ij)^((3)) = \sum\limits_(l_1 = 1)^n (a_( il_1 ) ) a_(l_1 j)^((2)) = $ $\sum\limits_(l_1 = 1)^n (a_(il_1 ) ) \left((\sum\limits_(l_2 = 1)^n ( a_ (l_1 l_2 ) a_(l_2 j) ) ) \kanan) =$ $\sum\limits_(l_1 = 1)^n (\sum\limits_(l_2 = 1)^n (a_(il_1 ) ) ) a_( l_1 l_2 ) a_(l_2 j) = \jumlah\had_(l_1 ,l_2 = 1)^n (a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) )$.

Istilah $a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) $, jika ia sama dengan 1, mentakrifkan laluan panjang 3 yang pergi dari bucu $i$-th ke bucu $j$-th dan melalui bucu $l_1$ dan $l_2$. Kemudian $a_(ij)^((3))$ memberi kita bilangan laluan panjang 3 yang menghubungkan bucu $i$th dan $j$th. DALAM kes am$a_(ij)^((k))$ menentukan bilangan laluan panjang $k$ yang menghubungkan bucu $i$th dan $j$th. Selain itu, $a_(ij)^((k)) = \sum\limits_(l_1 ,l_2 ,...,l_(k - 1) = 1)^n (a_(il_1 ) a_(l_1 l_2 ) .. .) a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j)$.

Jelaslah bahawa kuantiti $a_(ii)^((k)) $ memberi kita bilangan laluan tertutup panjang $k$ bermula dan berakhir pada bucu $i$. Oleh itu, laluan dengan panjang 2, $a_(il) a_(li)$, bermakna laluan yang melalui tepi $\( i,l \)$ dari bucu $i$ ke bucu $l$ dan belakang. Oleh itu $a_(ii)^((2)) = s_i$, i.e. unsur pepenjuru matriks $A^2$ adalah sama dengan kuasa bucu yang sepadan.

Pertimbangkan sekarang, bersama-sama dengan matriks $A$, matriks $\dot (A)$, yang berbeza daripada matriks $A$ sahaja kerana unsur-unsurnya (nombor 0 atau 1) dianggap sebagai unsur algebra Boolean. Oleh itu, tindakan dengan matriks sedemikian akan dijalankan mengikut peraturan algebra Boolean. Oleh kerana operasi penambahan dan pendaraban matriks dengan unsur Boolean dikurangkan kepada operasi penambahan dan pendaraban unsur matriks ini mengikut peraturan aritmetik Boolean, kami berharap ini tidak akan membawa kepada kesukaran. Matriks dengan unsur Boolean akan dipanggil matriks Boolean. Jelas sekali, operasi penambahan dan pendaraban matriks Boolean ditutup pada set matriks Boolean, i.e. hasil daripada operasi ini sekali lagi akan menjadi matriks boolean.

Jelas sekali, untuk penomboran bucu tertentu, terdapat padanan satu-dengan-satu antara matriks dan graf bersebelahan Boolean. Oleh itu, tafsiran graf tindakan penambahan dan peningkatan kepada kuasa matriks bersebelahan Boolean adalah menarik (dalam kes umum, hasil darab dua matriks simetri tertib yang sama tidak semestinya matriks simetri).

Hasil penambahan dua matriks simetri Boolean daripada susunan yang sama akan menjadi matriks simetri Boolean tertib yang sama dengan sifar di tempat yang kedua-dua sebutan mempunyai sifar dan satu di tempat yang sekurang-kurangnya satu sebutan mempunyai unit. Dalam tafsiran graf, operasi ini dipanggil operasi penambahan graf. Hasil tambah dua graf, diberikan pada set bucu yang sama dengan penomboran yang sama, dipanggil graf yang bucu i dan j adalah bukan bersebelahan jika mereka tidak bersebelahan untuk kedua-dua graf jumlah, dan bucu i dan j bersebelahan jika mereka bersebelahan sekurang-kurangnya. satu graf hasil tambah.

Mari kita sekarang mentafsir kuasa kedua matriks bersebelahan Boolean $\dot (A)^2$ dengan entri $\dot (a)_(ij)^((2)) = \sum\limits_(l = 1)^ n (\dot ( a)_(il) \dot (a)_(lj) )$. Adalah jelas bahawa $\dot (a)_(ij)^((2)) = 1$ jika sekurang-kurangnya satu sebutan $\dot (a)_(il) \dot (a)_(lj) $ adalah sama kepada 1 dan $\dot (a)_(ij)^((2)) = 0$ jika semua sebutan adalah sama dengan 0. Jika matriks $\dot (A)$ ialah matriks bersebelahan bagi sesetengah graf, i.e. ialah matriks simetri (0,1) dengan pepenjuru utama sifar, maka matriks $\dot (A)^2$, secara amnya, bukanlah matriks bersebelahan graf dalam erti kata yang telah kita pakai, kerana kesemuanya unsur pepenjuru adalah sama dengan 1 (jika graf tidak mempunyai bucu terpencil). Untuk melihat matriks seperti matriks bersebelahan, kita mesti, apabila mempertimbangkan sambungan antara bucu beberapa sistem bersambung yang mentakrifkan sistem ini sebagai graf, mengakui sambungan beberapa bucu dengan diri mereka sendiri. "Tepi" yang mentakrifkan sambungan puncak tertentu dengan dirinya dipanggil gelung. Kami akan meneruskan, seperti sebelum ini, dengan perkataan graf kami akan memahami graf tanpa gelung, dan mengenai graf dengan gelung, jika ini tidak jelas dari konteks, kami akan mengatakannya - graf dengan gelung.

Pertimbangkan jumlah $\dot (A)^() = \dot (A) + \dot (A)^2$. Matriks $\dot (A)^()$ memberi kita graf yang diperoleh daripada yang asal dengan "menepu" dengan sambungan tambahan yang sepadan dengan laluan panjang 2. Iaitu, bucu $i$ dan $j$ adalah bersebelahan dalam graf baharu jika ia bersebelahan dalam graf asal atau bucu ini disambungkan oleh beberapa laluan panjang 2, dan bucu $i$ dan $j$ adalah bukan bersebelahan jika ia tidak bersebelahan dalam graf asal dan terdapat tiada laluan panjang 2 yang menghubungkan bucu ini.

$\dot (A)^() = \dot (A) + \dot (A)^2 + \dot (A)^3$ ditakrifkan sama. Iaitu, dalam graf diberikan oleh matriks$\dot (A)^()$ bucu $i$ dan $j$ bersebelahan jika ia bersebelahan dalam graf $\dot (A)^()$ atau bucu ini disambungkan oleh beberapa laluan panjang 3 dalam graf asal, dan bucu $i$ dan $j$ adalah bukan bersebelahan jika mereka bukan bersebelahan dalam graf $\dot (A)^()$ dan tiada laluan panjang 3 yang menghubungkan bucu ini dalam graf asal . Dan sebagainya.

Secara amnya $\dot (A)^([k]) = \sum\limits_(i = 1)^k (\dot (A)^i) $. Adalah mudah untuk melihat bahawa semua $\dot (A)^([k])$ untuk $k \ge n - 1$, dengan $n$ ialah susunan matriks $\dot (A)$, adalah sama . Sesungguhnya, jika bucu $i$ dan $j$ disambungkan, maka terdapat laluan (rantai) yang menghubungkan bucu ini, dan, oleh itu, terdapat laluan mudah (rantai ringkas) yang menghubungkan bucu ini. Laluan ringkas maksimum yang mungkin dalam graf $n$-pucuk mempunyai panjang $n-1$ (laluan mudah yang menghubungkan semua bucu yang berbeza bagi graf). Oleh itu, jika dalam matriks $\dot (A)^()$ terdapat 1 di tempat $(i,j)$, maka di tempat yang sama dalam matriks $\dot (A)^([k])$ untuk $k \ge n - 1$ juga akan menjadi 1, kerana matriks $\dot (A)^()$ dimasukkan sebagai istilah Boolean dalam takrifan matriks $\dot (A)^([k] )$. Jika dalam matriks $\dot (A)^()$ terdapat 0 dan bukannya $(i,j)$, maka ini bermakna tiada rantai mudah dalam graf yang menghubungkan $i$-th dan $j$- bucu ke-, dan, oleh itu, tiada rantai sama sekali yang menghubungkan bucu-bucu ini. Oleh itu, dalam kes yang sedang dipertimbangkan dan dalam matriks $\dot (A)^([k])$ untuk $k \ge n - 1$, tempat ($i$,$j)$ ialah 0. Ini membuktikan penegasan kami tentang kesamaan semua matriks $\dot (A)^([k])$ untuk $k \ge n - 1$ kepada matriks $\dot (A)^()$ dan, oleh itu, untuk setiap lain.

Matriks $\dot (A)^()$ dipanggil matriks penutupan transitif matriks$\dot (A)$, serta matriks bersebelahan penutupan transitif graf yang diberikan oleh matriks $\dot (A)$. Agak jelas bahawa matriks penutupan transitif graf bersambung ialah matriks bersebelahan graf lengkap, iaitu matriks segi empat sama, terdiri daripada satu unit. Pemerhatian ini juga memberi kita kaedah untuk menentukan ketersambungan graf: graf disambungkan jika dan hanya jika matriks penutupan transitif matriks bersebelahannya akan terdiri daripada satu sahaja (ia akan menjadi matriks graf lengkap).

Matriks penutupan transitif juga memungkinkan untuk menyelesaikan masalah pembahagian graf kepada komponen yang bersambung.

Sekarang mari kita tunjukkan bagaimana prosedur penutupan transitif membolehkan kita membina apa yang dipanggil "matriks jarak". Untuk melakukan ini, kami menentukan jarak antara bucu $i$ dan $j$. Jika bucu $i$ dan $j$ disambungkan, maka jarak di antara mereka kita akan menamakan panjang minimum (mengikut bilangan traversal tepi) laluan mudah yang menghubungkan bucu ini; jika bucu $i$ dan $j$ terputus sambungan, maka kami tetapkan jarak sama dengan sifar (sifar sebagai penolakan beberapa laluan yang menghubungkan bucu ini). Dengan takrifan jarak ini, jarak antara bucu dan dirinya adalah sama dengan 2 (panjang laluan di sepanjang tepi dan belakang). Jika terdapat gelung pada bucu, maka jarak antara bucu dan dirinya adalah sama dengan 1.

Untuk membina matriks jarak bagi graf $n$-pucuk dengan matriks bersebelahan $A$, yang akan menunjukkan jarak antara mana-mana dua bucu, kami memperkenalkan matriks $A^(\(k\)) = A^([ k]) - A^()$, dengan $k = 2,3,...,n - 1$ dan $A^(\(1\)) = A^() = A$. Ketiadaan titik di atas tatatanda matriks menunjukkan bahawa kita menganggap matriks $A^([k])$ ($k = 1,2,...,n - 1)$ sebagai matriks berangka (0,1), secara semula jadi diperoleh daripada matriks $\dot (A)^([k])$ (kami kini menganggap unsur Boolean 0 dan 1 sebagai nombor 0 dan 1). Ia berikutan daripada kaedah membina matriks $A^([k])$ bahawa $A^([k]) \ge A^()$ ($k = 2,3,...,n - 1$ ) dan, oleh itu $A^(\(k\))$ ($k = 1,2,...,n - 1$) ialah (0,1)-matriks. Selain itu, matriks $A^(\(2\))$ mengandungi 1 sahaja di tempat-tempat di mana bucu yang ditentukan oleh tempat ini (nombor baris dan nombor lajur) disambungkan oleh beberapa laluan panjang dua dan tidak disambungkan oleh yang lebih kecil. laluan. Begitu juga, $A^(\(3\))$ mengandungi 1 sahaja di tempat-tempat di mana bucu yang ditakrifkan oleh tempat ini disambungkan dengan laluan sepanjang tiga dan tidak disambungkan oleh mana-mana laluan yang lebih kecil, dan seterusnya. Oleh itu, matriks $D = \sum\limits_(k = 1)^(n - 1) (k \cdot A^(\(k\)))$ akan menjadi matriks jarak yang dikehendaki. Unsur $d_(ij)$ matriks ini ialah sama dengan jarak antara bucu $i$ dan $j$. Jarak antara bucu $u$ dan $v$ juga akan dilambangkan sebagai $d(u,v)$.

Komen. Hasil tambah tertentu $a_(il_1 ) a_(l_1 l_2 ) ...a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j) = 1$ unsur $a_(ij ) ^((k))$ $k$-kuasa ke atas matriks bersebelahan $A^k$ menentukan $(i,j)$-laluan $i\(i,l_1\)l_1 tertentu \(l_1 ,l_2 \ )l_2 ...l_(k - 2) \(l_(k - 2) ,l_(k - 1) \)l_(k - 1) \(l_(k - 1) ,j\)j$ daripada $ i$ -th bucu kepada $j$-th. Urutan bucu dan tepi bersebelahan yang menghubungkannya $i\(i,l_1 \)l_1 \(l_1 ,l_2 \)l_2 ...l_(k - 2) \(l_(k - 2) ,l_(k - 1) \ )l_(k - 1) \(l_(k - 1) ,j\)j$ juga dipanggil $(i,j)$-laluan. Laluan berbeza daripada rantai yang hanya terdiri daripada tepi bersebelahan yang berbeza dalam tepi yang sama dibenarkan dalam laluan itu. Laluan mudah terdiri daripada pelbagai bucu dan tepi bersebelahan, i.e. hampir sama dengan rantai mudah.

Agak jelas bahawa unsur $d_(ij) $ matriks jarak menentukan panjang rantai minimum yang menghubungkan puncak $i$-th dengan $j$-th.

Pertimbangkan contoh graf yang diberikan dalam Rajah 1 dan 2, matriks bersebelahan dan matriks jaraknya.

Rajah 1 (Graf $\Gamma _1$, matriks bersebelahan $A_1$, matriks jarak $D_1$).
$A_1 = \left(((\begin(array)(*c) 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \end(array) )) \right), $
$D_1 = \left(((\begin(array)(*c) 2 & 1 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 2 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 1 \\ 1 & 1 & 1 & 2 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 2 & 2 & 1 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 1 \\ 3 & 3 & 2 & 3 & 1 & 2 & 1 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 2 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 1 & 2 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 1 & 1 & 1 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 1 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 2 & 2 & 1 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 1 & 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 2 \\ \tamat(tatasusunan) )) \kanan) $

nasi. 2 (Graf $\Gamma _2$, matriks bersebelahan $A_2$, matriks jarak $D_2$).
$A_2 = \left(((\begin(array)(*c) 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \ \ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end(array) )) \kanan)$,
$D_2 = \left(((\begin(array)(*c) 2 & 1 & 2 & 3 & 4 & 5 & 6 & 4 & 4 & 5 \\ 1 & 2 & 1 & 2 & 3 & 4 & 5 & ​​​​3 & 3 & 4 \\ 2 & 1 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 3 & 2 & 1 & 2 & 1 & 2 & 3 & 1 & 1 & 2 \ \ 4 & 3 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 3 \\ 5 & 4 & 3 & 2 & 1 & 2 & 1 & 3 & 3 & 4 \\ 6 & 5 & 4 & 3 & 2 & 1 & 2 & 4 & 4 & 5 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 1 \\ 5 & 4 & 3 & 2 & 3 & 4 & 5 & 3 & 1 & 2 \\ \end(array) )) \kanan). $

Daripada matriks $D_1$ dan $D_2$ adalah mudah untuk ditentukan diameter$d_1$ graf $\Gamma _1$ dan $d_2$ graf $\Gamma _2$ sebagai nilai maksimum unsur-unsur matriks ini. Jadi $d_1 = 3$ dan $d_2 = 6$.

Sebagai tambahan kepada matriks jarak, teori graf juga mempertimbangkan matriks lain, unsur-unsurnya ditentukan dari segi panjang laluan. Seperti, sebagai contoh, adalah matriks lintasan. DALAM matriks pelancongan$(i,j)$elemen ke- sama panjang laluan terpanjang (rantai terpanjang) dari bucu $i$-th ke $j$-th, dan jika tiada langsung laluan sedemikian, maka, mengikut takrifan jarak, $(i ,j)$-th elemen matriks traversal ditetapkan sama dengan sifar .

Di penghujung bahagian, kami akan membuat nota tentang kaedah untuk menentukan rantai minimum dan maksimum menggunakan matriks jarak yang menghubungkan bucu $i$-th dan $j$-th dalam graf.

Dan kini kami memberikan beberapa lagi definisi teori graf yang berkaitan dengan jarak antara bucu dan yang mudah ditentukan daripada matriks jarak.

Sipi$e(v)$ daripada bucu $v$ dalam graf bersambung $\Gamma$ ditakrifkan sebagai maks $d(u,v)$ ke atas semua bucu $u$ dalam $\Gamma$. Jejari$r(\Gamma)$ ialah kesipian bucu terkecil. Perhatikan bahawa kesipian yang terbesar adalah sama dengan diameter graf. Bucu $v$ dipanggil bucu pusat graf $\Gamma$ jika $e(v) = r(\Gamma)$; pusat graf $\Gamma$ ialah set semua bucu pusat.

Jadi untuk graf $\Gamma _1$ daripada Rajah.1, kesipian bucu 13 akan bersamaan dengan 2 ($e(13) = 2$). Bucu 3, 5 dan 10 akan mempunyai kesipian yang sama ($e(3) = e(5) = e(10) = 2$). Kesipian bersamaan dengan 2 akan menjadi yang terkecil untuk graf $\Gamma _1$, i.e. $r(\Gamma _1) = 2$. Pusat graf $\Gamma _1$ akan terdiri daripada bucu 3, 5, 10 dan 13. Sipi terbesar akan bersamaan dengan 3 dan akan sama, seperti yang dinyatakan di atas, dengan diameter graf $\Gamma _1$ .

Untuk graf $\Gamma _2$ daripada Rajah. 2, satu-satunya bucu 4 akan mempunyai kesipian terkecil ($e(4) = r(\Gamma _2) = 3$). Oleh itu, pusat graf $\Gamma _2$ terdiri daripada satu bucu 4. Diameter graf $\Gamma _2$, seperti yang dinyatakan di atas, ialah 6.

Graf $\Gamma _2$ ialah pokok, dan struktur pusat mana-mana pokok diterangkan oleh teorem berikut.

Teorem Jordan-Sylvester. Setiap pokok mempunyai pusat yang terdiri daripada sama ada satu bucu atau dua bucu bersebelahan.

Bukti. Nyatakan dengan $K_1$ graf yang terdiri daripada satu bucu terpencil, dan dengan $K_2$ graf dua bucu yang disambungkan oleh tepi. Mengikut definisi, kami menetapkan $e(K_1) = r(K_1) = 0$. Kemudian penegasan teorem akan bertahan untuk $K_1$ dan $K_2$. Mari kita tunjukkan bahawa mana-mana pokok $T$ mempunyai bucu pusat yang sama dengan pokok $(T)"$ yang diperoleh daripada $T$ dengan mengeluarkan semua bucu yang tergantung. Jelaslah bahawa jarak dari bucu yang diberikan $u$ ke mana-mana bucu lain $v$ boleh sampai nilai yang paling besar hanya jika $v$ ialah bucu tergantung.

Oleh itu, kesipian setiap bucu pokok $(T)"$ betul-betul kurang satu daripada kesipian bucu yang sama dalam $T$. kesipian dalam $(T)"$, i.e. pusat pokok $T$ dan $(T)"$ bertepatan. Jika kita meneruskan proses mengeluarkan bucu yang tergantung, maka kita mendapat urutan pokok dengan pusat yang sama dengan $T$. Oleh kerana $T$ adalah terhingga, kita semestinya akan tiba pada sama ada $ K_1$, atau ke $K_2$ Dalam apa jua keadaan, semua bucu pokok yang diperoleh dengan cara ini membentuk pusat pokok, yang dengan itu terdiri sama ada daripada satu bucu atau dua bucu bersebelahan.

Sekarang mari kita tunjukkan bagaimana, menggunakan matriks jarak, seseorang boleh menentukan, sebagai contoh, laluan minimum yang menghubungkan bucu 4 dengan bucu 8 pada graf $\Gamma _1$. Dalam matriks $D_1$, unsur $d_(48) = 3$. Mari kita ambil lajur ke-8 matriks $D_1$ dan cari dalam lajur semua elemen lajur ini bersamaan dengan 1. Sekurang-kurangnya satu elemen sedemikian boleh ditemui kerana keterkaitan graf $D_1$. Malah, akan terdapat tiga unit sedemikian dalam lajur ke-8, dan ia terletak di baris ke-5, ke-6 dan ke-7. Sekarang mari kita ambil baris ke-4 dan pertimbangkan di dalamnya unsur-unsur yang terletak di lajur ke-5, ke-6 dan ke-7. Elemen ini masing-masing akan menjadi 2, 3 dan 3. Hanya elemen yang terletak dalam lajur ke-5 adalah bersamaan dengan 2 dan, bersama-sama dengan 1 yang terletak di tempat (5,8), memberikan hasil tambah 3. Oleh itu, bucu 5 termasuk dalam rantai $\( \(4, ?\), \(? ,5\),\(5,8\)\)$. Sekarang mari kita ambil lajur ke-5 matriks dan pertimbangkan 1 lajur ini. Ini akan menjadi elemen yang terletak di baris ke-3, ke-6, ke-7, ke-8, ke-10 dan ke-13. Kami kembali ke baris ke-4 sekali lagi dan melihat bahawa hanya di persimpangan lajur ketiga dan baris ke-4 ialah 1, yang, digabungkan dengan 1 di tempat (3,5), memberikan jumlah 2. Oleh itu, rantai yang dikehendaki akan jadilah $\( \ (4,3\),\(3,5\),\(5,8\)\)$. Melihat pada Rajah 1 sekarang, kami yakin dengan kesahihan penyelesaian yang ditemui.

Walaupun mengenai matriks pintasan buku teks moden mengatakan bahawa "tiada kaedah yang berkesan untuk mencari unsur-unsurnya", kita akan ingat bahawa menggunakan matriks kejadian kita boleh mencari semua rantai yang menyambungkan sepasang bucu dalam graf yang disambungkan, dan dengan itu rantai panjang maksimum.

biarlah G ialah graf n terhingga.

Laluan V G ialah jujukan tepi di mana setiap dua tepi bersebelahan mempunyai bucu sepunya:

Bilangan tepi dalam laluan dipanggilnya panjang.

Laluan M dipanggil laluan Pandangan umum rantai rantai mudah - jika bucunya tidak berulang,

Laluan di mana bucu mula dan tamat adalah sama, i.e. , dipanggil kitaran (tertutup ).

Laluan kitaran M dipanggil laluan umum , jika bucu dan tepi diulang, kitaran - jika tepinya tidak berulang, kitaran mudah – jika bucunya tidak berulang (kecuali permulaan dan akhir).

graf, tidak mengandungi kitaran dipanggil asiklik.

Puncak Dan dipanggil penghubung jika ada laluan bermula di dan berakhir pada .

Kenyataan: Hubungan ketersambungan puncak graf ialah hubungan kesetaraan dan mentakrifkan pembahagian set bucu graf kepada subset tidak bersilang .

Kiraan dipanggil bersambung jika untuk mana-mana dua bucu yang berbeza terdapat laluan yang menghubungkannya.

Jelas sekali, semua subgraf G(Vi) graf ini disambungkan dan dipanggil komponen graf yang disambungkan.

Jarak antara puncak a Dan b ialah panjang rantai ringkas minimum yang menghubungkannya. Jarak ditunjukkan d(a, b) .

Aksiom metrik:

1) d(a, b) =d(b,a);

2) d(a, b) ≥ 0, d(a, b) = 0 ↔ a = b;

3) d(a, b) ≤ d(a, c) + d(c, b)

Matriks jarak ialah matriks segi empat sama berdimensi , baris dan lajur yang sepadan dengan bucu graf, dan jarak antara bucu direkodkan pada persilangan baris dan lajur.

			…
			…
			…
…	…	…	…	…	…
			…

Lajur terakhir matriks mengandungi kesipian untuk setiap bucu: jarak dari bucu yang diberi ke bucu paling jauh.

. (7.1)

Diameter kira G – jarak maksimum antara bucu graf. Diameter didapati dengan formula:

.

Menggunakan kesipian yang ditemui bagi bucu, diameter boleh didapati dengan formula:

. (7.2)

Jejari kira G – nilai minimum kesipian. Jejari didapati dengan formula:

. (7.3)

Pusat kira G ialah puncak yang .

Komen. Pusat dalam graf mungkin bukan satu-satunya.

rantai diametral kira G diameter menyambungkan bucu graf yang paling jauh.

rantai jejari kira G ialah rantai ringkas, yang panjangnya sama dengan jejari, menghubungkan pusat dan puncak graf yang paling jauh daripadanya.

Contoh 7.1.

Untuk graf n yang ditunjukkan dalam Rajah 7.1, tulis 1) laluan umum, 2) litar bukan ringkas, 3) litar ringkas, 4) laluan kitaran umum, 5) kitaran bukan ringkas, 6) kitaran.

Penyelesaian:

1) Laluan umum ialah laluan di mana bucu mula dan tamat berbeza dan beberapa tepi diulang. M 1 = (1, 4 , 5, 1, 4 , 7, 3). Di sini tepi (1, 4) diulang.

2) Bukan rantai mudah - ini adalah laluan di mana tepi tidak berulang, tetapi bucu diulang. M 2 = (4, 3, 1 , 5, 6, 7 , 4, 1 ). Puncak 1 berulang di sini.

3) Rantaian ringkas ialah laluan di mana tiada bucu berulang. M 3 = (4, 3, 7, 5, 6).

4) Laluan kitaran umum ialah laluan di mana bucu mula dan tamat bertepatan dan beberapa tepi diulang. M 4 = (1, 5 , 1, 5 , 1 ). Di sini tepi (1, 5) diulang.

Rajah 7.1. Membina laluan

V graf tidak terarah

5) Kitaran bukan ringkas ialah laluan kitaran di mana tepi tidak berulang, tetapi bucu diulang. M 5 = (3, 4 , 5, 7, 4 , 13). Puncak 4 diulang di sini.

Catatan bahawa kitaran bukan mudah hanya berlaku dalam graf yang terdapat konfigurasi jam pasir.

6) Kitaran mudah ialah laluan kitaran di mana tiada bucu berulang. M 6 = (5, 4, 3, 2, 1, 5).

Contoh 7.2.

Untuk graf-n yang ditunjukkan dalam Rajah 7.1, bina matriks jarak. Tentukan diameter dan jejari graf. Nyatakan pusat graf. Catatkan rantaian diametrik dan jejari

Penyelesaian:

Untuk membina matriks jarak, mari kita bandingkan baris dan lajur dengan bucu. Di persimpangan baris dan lajur, kami menunjukkan jarak antara bucu yang sepadan.

d( a, b)	1	2	3	4	5	6	7
1	0	1	1	1	1	2	2	2
2	1	0	1	2	2	3	2	3
3	1	1	0	1	2	2	1	2
4	1	2	1	0	1	2	1	2
5	1	2	2	1	0	1	1	2
6	2	3	2	2	1	0	1	3
7	2	2	1	1	1	1	0	2

Kedudukan (1, 1) ialah 0, kerana laluan terpendek antara bucu 1 dan bucu 1 ialah laluan merosot (tanpa tepi) dengan panjang 0.

Kedudukan (1, 2) ialah 1, kerana laluan terpendek antara bucu 1 dan bucu 2 ialah satu-satunya tepi yang menghubungkan bucu ini.

Di tempat (1, 6) ialah 2, kerana laluan ringkas terpendek antara bucu 1 dan bucu 6 ialah rantai dua tepi (1, 5, 6). Jadi jarak antara bucu ini ialah 2.

Lajur terakhir jadual menunjukkan jarak dari bucu tertentu ke bucu yang paling jauh daripadanya - kesipian. Nilai mereka didapati dengan formula (7.1).

Nilai maksimum lajur terakhir ialah diameter graf. di mana d(G) = 3.

Nilai minimum lajur terakhir ialah jejari graf. di mana r(G) = 2.

Pusatnya ialah bucu: 1, 3, 4, 5, 7. Sipinya adalah sama dengan jejari graf.

Untuk membina rantaian diametrik, kami menggunakan matriks jarak untuk mengetahui bucu mana yang paling jauh antara satu sama lain. Oleh kerana jarak maksimum antara bucu adalah diameter graf, maka kita akan mencari bucu yang berada pada jarak yang sama dengan diameter. Ini ialah bucu 2 dan 6. Oleh itu, semua rantai diametrik dalam graf menyambungkan bucu ini. Terdapat dua litar sedemikian:

D 1 = (2, 1, 5, 6) dan D 2 = (2, 3, 7, 6).

Untuk membina rantai jejari, kami menggunakan matriks jarak untuk mengetahui bucu yang paling jauh dari pusat.

Bucu 6 dan 7 terletak pada jarak jejari 2 dari pusat 1. Ini bermakna rantai jejari boleh dilukis:

R 1 = (1, 5, 6) dan R 2 = (1, 4, 7).

Bucu 5 dan 6 terletak pada jarak jejari dari pusat 3. Ini bermakna rantai jejari boleh dilukis:

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

Mengira jarak dan menentukan laluan dalam graf adalah salah satu masalah yang paling jelas dan praktikal yang timbul dalam teori graf. Mari kita perkenalkan beberapa definisi yang diperlukan.

Sipi bucu graf - jarak ke bucu yang paling jauh daripadanya. Untuk graf yang tidak ditakrifkan berat badan tepinya, jarak ditakrifkan sebagai bilangan tepi.

Jejari graf ialah kesipian minimum bucu, dan diameter graf ialah kesipian maksimum bucu.

Pusat bucu bentuk graf yang kesipiannya sama dengan jejari. Pusat graf boleh terdiri daripada satu, beberapa atau semua bucu graf.

persisian bucu mempunyai kesipian yang sama dengan diameter.

Rantaian ringkas dengan panjang sama dengan diameter graf dipanggil berdiameter .

Teorem 12.1.Dalam graf bersambung, diameter paling banyak adalah pangkat matriks bersebelahan.

Teorem 12.2.(Jordan) Setiap pokok mempunyai pusat yang terdiri daripada satu atau dua bucu bersebelahan.

Teorem 12.3.Jika diameter pokok itu genap, maka pokok itu mempunyai satu pusat, dan semua rantai diametrik melaluinya; jika diameternya ganjil, maka terdapat dua pusat dan semua rantai diametrik mengandungi tepi yang menghubungkannya.

Jelas sekali nilai praktikal pusat graf. Jika, sebagai contoh, kita bercakap tentang graf jalan dengan bucu-bandar, maka di pusat matematik adalah dinasihatkan untuk meletakkan pusat pentadbiran, gudang, dsb. Pendekatan yang sama boleh digunakan pada graf berwajaran, di mana jarak adalah berat tepi. Sebagai pemberat, anda boleh mengambil jarak Euclidean, masa atau kos pergerakan antara mata.

Contoh 12.5. Cari jejari, diameter dan pusat graf yang ditunjukkan dalam rajah. 12.1.

Penyelesaian. Dalam masalah ini, ia adalah mudah untuk digunakan matriks jarak S. Unsur matriks simetri segi empat sama ini adalah sama dengan jarak antara bucu i dan atas j. Untuk graf yang ditunjukkan dalam Rajah. 12.1, matriks jarak mempunyai pandangan seterusnya:

Mari kita hitung kesipian setiap bucu. Nilai ini boleh ditakrifkan sebagai elemen maksimum lajur yang sepadan bagi matriks jarak (atau baris, kerana matriks S simetri). Kita mendapatkan

Jejari Graf r ialah kesipian minimum bucu. Dalam kes ini r= 2. Bucu No. 2, No. 4, dan No. 5 mempunyai kesipian sedemikian. Bucu-bucu ini membentuk pusat graf. Diameter graf d ialah kesipian maksimum bucu. Dalam kes ini d= 3. Bucu No. 1 dan No. 3 mempunyai kesipian sedemikian, ini ialah pinggiran graf. Dalam graf yang dikaji, bucu ternyata sama ada tengah atau persisian. Terdapat bucu lain dalam graf tertib lebih tinggi.

Sipi bagi bucu graf kecil boleh dikira dengan mudah melalui pengiraan terus daripada rajah. Walau bagaimanapun, graf tidak selalu ditakrifkan oleh lukisannya. Di samping itu, graf mungkin mempunyai saiz besar. Oleh itu, cara lain untuk menyelesaikan masalah sebelum ini diperlukan. Teorem berikut diketahui.

Teorem 12.4. Biarkan matriks bersebelahan graf G tanpa gelung dan , di mana . Maka ia adalah sama dengan bilangan laluan panjang k dari bucu ke bucu .

Menyelesaikan masalah teori graf menggunakan pelbagai transformasi matriks bersebelahan dipanggil kaedah algebra .

Contoh 12.6. Cari matriks jarak bagi graf yang ditunjukkan dalam rajah. 12.1, dengan kaedah algebra.

Penyelesaian. Matriks bersebelahan graf ini ialah:

Kami akan mengisi matriks jarak dengan mempertimbangkan darjah matriks bersebelahan. Unit matriks bersebelahan menunjukkan pasangan bucu yang mempunyai jarak satu di antara mereka (iaitu, ia disambungkan oleh satu tepi).

Unsur pepenjuru bagi matriks jarak ialah sifar. Darabkan matriks bersebelahan dengan sendirinya:

Mengikut teorem antara bucu 2 dan 3, 1 dan 4, dsb. terdapat beberapa laluan panjang 2 (kerana darjah matriks adalah dua). Bilangan laluan tidak digunakan di sini, hakikat kewujudan laluan dan panjangnya adalah penting, yang ditunjukkan oleh unsur bukan sifar darjah matriks, yang tidak bertepatan dengan elemen yang dicatatkan semasa mengira laluan yang kurang panjang. Kami meletakkan 2 dalam elemen kosong matriks jarak dan dapatkan anggaran seterusnya:

Jarak antara bucu 1 dan 3 masih tidak diketahui. Kami akan mendarabkan matriks bersebelahan pada dirinya sehingga matriks elemen bukan nol tidak akan muncul . Kemudian elemen sepadan matriks jarak sama dengan darjat matriks bersebelahan: . Pada langkah seterusnya, kita dapat

oleh itu, , dan akhirnya

Matriks yang terhasil bertepatan dengan matriks jarak S(12.2) didapati dengan pengiraan terus daripada rajah.

1. Tugaskan hlm=1 (hlm ialah bilangan komponen yang disambungkan), .

2. Sertakan dalam set bucu V hlm komponen bersambung kuat D hlm bucu yang sepadan dengan unit baris pertama matriks S hlm . Sebagai matriks A(D hlm) ambil submatriks matriks A(D AV hlm .

3. Potong daripada S hlm baris dan lajur yang sepadan dengan bucu dari V hlm. Jika tiada baris (dan lajur) yang tinggal, maka hlm ialah bilangan komponen yang bersambung kuat. Jika tidak, kami menandakan matriks yang tinggal selepas pemadaman istilah dan lajur sebagai S hlm +1 , tugaskan hlm= hlm+1 dan pergi ke langkah 2.

Contoh

Mari kita pilih komponen bersambung bagi graf terarah yang ditunjukkan dalam Rajah. 1. Dalam masalah ini, bilangan bucu n= 5.

Jadi, untuk graf terarah yang diberikan, matriks bersebelahan akan mempunyai dimensi 5 × 5 dan akan kelihatan seperti ini

.

Mari cari matriks kebolehcapaian untuk graf terarah ini menggunakan formula 1) daripada Pernyataan 3:

,
,

,

Oleh itu,

.

Oleh itu, matriks bersambung kuat yang diperolehi oleh formula 2) pernyataan 3 adalah seperti berikut:

.

Kami menugaskan hlm=1
dan karang set bucu komponen pertama yang bersambung kuat D 1: ini ialah bucu yang sepadan dengan bucu dalam baris pertama matriks S(D). Oleh itu, komponen pertama yang bersambung kuat terdiri daripada satu bucu
.

Padam daripada matriks S 1 (D) baris dan lajur yang sepadan dengan bahagian atas v 1 untuk mendapatkan matriks S 2 (D):

.

Kami menugaskan hlm=2. Set bucu komponen bersambung kedua ialah bucu yang sepadan dengan bucu dalam baris pertama matriks S 2 (D), itu dia
. Menyusun Matriks Bersebelahan untuk Komponen Bersambung Kuat
graf asal D − dalam kualitinya kita mengambil submatriks matriks A(D) yang terdiri daripada unsur matriks A terletak di persimpangan baris dan lajur yang sepadan dengan bucu dari V 2:

.

Padam daripada matriks S 2 (D) baris dan lajur yang sepadan dengan bucu dari V 2 untuk mendapatkan matriks S 3 (D), yang terdiri daripada satu elemen:

dan tugaskan hlm=3. Oleh itu, komponen ketiga bersambung kuat graf asal, seperti yang pertama, terdiri daripada satu bucu
.

Oleh itu, 3 komponen bersambung kuat bagi graf berarah dikenal pasti D:

Tugasan 2. Jarak dalam graf terarah

Gunakan algoritma muka gelombang untuk mencari jarak dalam graf terarahD: diameter, jejari dan pusat.

biarlah
graf berarah dengan n³2 bucu dan v,w (v¹ w) – diberi bucu daripada V.

Algoritma untuk Mencari Laluan Minimum daripada B dalam Graf Berarah

(algoritma hadapan gelombang).

Jika tidak, kami meneruskan:

Jika tidak, kami telah menemui laluan minimum dari V
dan panjangnya ialah k. Urutan puncak

terdapat laluan minimum ini. Kerja sedang disiapkan.

Kenyataan

Untuk mencari jarak dalam graf terarah, anda perlu membuat matriks jarak minimum R(D) di antara bucunya. Ini ialah matriks segi empat sama dimensi
, yang unsur pepenjuru utamanya adalah sama dengan sifar (
,i=1,..,n).

Pertama, kami mencipta matriks bersebelahan. Kemudian kami memindahkan unit dari matriks bersebelahan ke matriks jarak minimum (
, Jika
). Seterusnya, kami mengisi matriks baris demi baris seperti berikut.

Kami menganggap baris pertama, yang mempunyai unit. Biarkan rentetan ini − i-thay dan di persimpangan dengan j-lajur ke- adalah satu (iaitu.
). Ini bermakna bahawa dari atas anda boleh sampai ke puncak dalam satu langkah. Kami sedang mempertimbangkan j-istilah ke- (rentetan harus dipertimbangkan jika ia mengandungi sekurang-kurangnya satu unit). Biarkan elemen
. Kemudian dari atas ke atas boleh dicapai dalam dua langkah. Oleh itu, seseorang boleh menulis
. Perlu diingatkan bahawa jika terdapat dua atau lebih baris dalam baris yang sedang dipertimbangkan, maka semua pilihan yang mungkin untuk pergi dari satu bucu ke bucu yang lain harus diusahakan, menulis panjang terpendeknya ke dalam matriks.

Catatan: Dalam ujian, cari laluan terpanjang menggunakan algoritma hadapan gelombang.

Contoh

Cari jarak dalam graf terarah D ditunjukkan dalam rajah. 2. Dalam masalah ini, bilangan bucu n= 7, maka matriks bersebelahan dan jarak minimum antara bucu graf berarah D akan mempunyai dimensi 7×7.

Matriks bersebelahan:

.

Mula mengisi matriks R(D) jarak minimum: mula-mula kita letakkan sifar di sepanjang pepenjuru utama Dan r ij =a ij, Jika a ij=1, (iaitu, kami memindahkan unit daripada matriks bersebelahan). Mari kita lihat baris pertama. Terdapat dua unit di sini, iaitu, dari puncak pertama dalam satu langkah anda boleh sampai ke yang kedua dan keenam. Dari puncak kedua adalah mungkin untuk sampai ke yang ketiga dalam satu langkah (kami tidak berminat dengan laluan ke puncak pertama), oleh itu, kita boleh menulis
. Dari puncak keenam kita boleh masuk dalam satu langkah ke kelima dan ketujuh, yang bermaksud
,
. Sekarang kita sedang mencari laluan yang berasal dari puncak pertama, terdiri daripada 3 langkah: dalam 2 langkah kita pergi ke puncak ketiga, dari sana kita sampai ke keempat dalam satu langkah, oleh itu
. Akibatnya, kami mendapat matriks berikut:

Oleh itu, diameter graf terarah yang dikaji ialah
.

Bagi setiap bucu graf berarah yang diberikan, kita dapati jarak maksimum (kesipian) dalam graf G dari bucunya mengikut formula yang diberikan di atas.
:r(v i) ialah maksimum jarak dalam i-baris ke-. Oleh itu,

r(v 1)=3, r(v 2)=3, r(v 3)=5, r(v 4)=4, r(v 5)=2, r(v 6)=2, r(v 7)=3.

Jadi jejari kira G kehendak

Sehubungan itu, pusat graf G akan ada puncaknya v 5 dan v 6, kerana nilai kesipiannya bertepatan dengan nilai jejari
.

Sekarang mari kita terangkan mencari laluan minimum dari puncak v 3 ke atas v 6 mengikut algoritma hadapan gelombang. Nyatakan bucu v 3 sebagai V 0 , dan bahagian atas v 6 - bagaimana W(Lihat Rajah 3). Set bucu kepunyaan imej V 0 , terdiri daripada satu elemen - ini adalah bahagian atas v 4 , yang, mengikut algoritma, ditandakan sebagai V 1: FW 1 (v 3)={v 4). Memandangkan puncak yang diingini bukan kepunyaan hadapan gelombang tahap pertama
, kami meneruskan algoritma. Kami membina hadapan gelombang tahap kedua - ini ialah set bucu kepunyaan imej bucu V 1: FW 2 (v 3)={v 7 ), menandakan v 7 ≡V 2. Dalam imej bahagian atas V 2 termasuk dua bucu - v 5 dan v 4 , tetapi sejak v 4 telah pun ditandakan sebagai V 0 , maka hadapan gelombang tahap ketiga terdiri daripada satu elemen: FW 3 (v 3)={v 5 }, v 5 ≡V 3 . Daripada bucu tidak berlabel kepada imej bucu V 3 disertakan v 1 dan v 2, masing-masing, FW 4 (v 3)={v 1 , v 2 }, v 1 ≡V 4 , v 2 ≡V 4 . Kini semua bucu dilabel kecuali v 6 , yang disertakan dalam imej puncak
, itu dia FW 5 (v 3)={v 6 ≡W), algoritma selesai. Laluan minimum (5 langkah) dari atas v 3 ke atas v 6 kelihatan seperti ini: v 3 v 4 v 7 v 5 v 1 v 6 .