Model matematik. Ciri metrik graf tidak terarah

Kenyataan. Jika terdapat laluan untuk dua bucu yang menghubungkannya, maka mesti ada laluan minimum yang menghubungkan bucu ini. Mari kita nyatakan panjang laluan ini sebagaid(v,w).

Definisi. nilaid(v,w) (terhingga atau tidak terhingga) akan dipanggil jarak antara bucu v, w . Jarak ini memenuhi aksiom metrik:

1) d(v,w) 0, dand(v,w) = 0 jika dan hanya jikav=w;

2) d(v, w) = d(w, v);

3) d(v, w) d(v, u) + d(u, w).

Definisi. diameter bagi graf bersambung ialah jarak maksimum yang mungkin antara dua bucunya.

Definisi. Pusat Graf ialah bucu sedemikian jarak maksimum antara ia dan mana-mana puncak lain adalah yang terkecil daripada semua yang mungkin; jarak ini dipanggil jejari graf.

Contoh 82.

Untuk graf G ditunjukkan dalam rajah. 3.16, cari jejari, diameter dan pusat.

nasi. 3.16. Kira sebagai contoh 82

Keputusan.

Untuk menentukan pusat, jejari, diameter graf G, cari matriks D(g) jarak antara bucu graf, unsur dij yang akan menjadi jarak antara bucu v i dan vj. Untuk ini kami gunakan perwakilan grafik graf. Perhatikan bahawa matriks D(g) simetri mengenai pepenjuru utama.

Menggunakan matriks yang terhasil untuk setiap puncak graf G tentukan penyingkiran terbesar daripada ungkapan: untuk saya,j = 1, 2, …, 5. Hasilnya, kami mendapat: r(v1) = 3,r(v2) = 2,r(v3) = 2,r(v4) = 2,r(v5) = 3. Minimum nombor yang diperoleh ialah jejari graf G, maksimum ialah diameter graf G. Bermaksud, R(G) = 2 dan D(G) = 3, pusat adalah bucu v 2,v 3,v 4.

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.

Keputusan. 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:

. (12.2)

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. AT 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.

Keputusan. 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

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 antara faedahnya matriks segi empat sama di hadapan 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 tentang 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. AT 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 lain-lain.

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 yang terdiri daripada satu sahaja. 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 akan 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. AT matriks pelancongan$(i,j)$elemen ke- sama panjang laluan terpanjang (rantai terpanjang) dari puncak $i$-th ke $j$-th, dan jika tiada laluan sedemikian sama sekali, maka, mengikut takrifan jarak, $(i ,j)$-th elemen matriks traversal ditetapkan sama dengan sifar .

Pada 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.

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 lajur 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 letakkan 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 dalam kes ini 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.

Biarkan graf tidak bersambung yang bersambung. Oleh kerana mana-mana dua bucu graf dan disambungkan, wujud rantaian ringkas dengan hujung dan . Mungkin terdapat beberapa rantai sedemikian. Panjangnya ialah integer bukan negatif. Oleh itu, antara bucu dan ada mesti mudah rantai dengan panjang terpendek. Panjang rantai panjang terkecil yang menghubungkan bucu dan dilambangkan dengan simbol dan dipanggil jarak antara bucu dan . A-priory .

Adalah mudah untuk mengesahkan bahawa konsep jarak yang diperkenalkan dengan cara ini memenuhi aksiom metrik:

2. jika dan hanya jika ;

3. ;

4. ketaksamaan segi tiga adalah benar:

Untuk bucu tetap graf, jarak ke bucu yang paling jauh daripadanya: , dipanggil kesipian (maksimum mengeluarkan) gasing.

diameter graf itu dipanggil nombor, sama dengan jarak antara bucu graf yang paling jauh antara satu sama lain:

.

Rantai mudah yang panjangnya ialah , dipanggil berdiameter rantai. Adalah jelas bahawa diameter graf adalah sama dengan yang terbesar di antara semua kesipian bucu graf. Bahagian atas dipanggil persisian, jika .

Sipi terkecil bagi bucu graf yang disambungkan dipanggil jejari dan menandakan:

Oleh kerana diameter graf adalah sama dengan terbesar kesipian bucu, dan jejari adalah yang terkecil, jejari graf tidak boleh lebih besar daripada diameternya. Bahagian atas dipanggil pusat, jika . Set semua bucu pusat graf dipanggil pusat. Pusat graf boleh menjadi satu bucu atau beberapa bucu. Terdapat graf yang pusatnya bertepatan dengan set semua bucunya. Sebagai contoh, pusat rantaian ringkas terdiri daripada dua bucu untuk nombor genap bucunya dan satu untuk nombor ganjil, dan untuk mana-mana kitaran semua bucu adalah pusat.

Untuk menggambarkan, mari kita lihat graf dalam Rajah. 4.29. Di sini

sebab tu

Bucu 2 ialah pusat graf, dan semua bucunya yang lain adalah persisian. Rantai 1, 2, 3 adalah salah satu rantai diametral.

Untuk digraf bersambung, jarak antara bucu dan ditakrifkan sebagai jarak antara bucu dan dalam pendua tidak berarah graf ini.

Masalah mencari bucu pusat graf sentiasa dihadapi dalam aktiviti amali. Biarkan, sebagai contoh, bucu graf sepadan dengan kampung kecil, dan tepinya sepadan dengan jalan di antara mereka. Ia diperlukan untuk meletakkan secara optimum pada ini penempatan katakan kedai. AT situasi yang serupa kriteria optimum biasanya terdiri daripada mengoptimumkan kes "terburuk", iaitu, meminimumkan jarak dari kedai ke kampung paling terpencil. Pendekatan untuk pengoptimuman ini melibatkan meletakkan stor dalam penempatan yang mewakili bucu pusat graf.

Laluan graf

Telah diperhatikan bahawa permulaan teori graf dikaitkan dengan masalah jambatan Königsberg. Masalah ini, yang terkenal pada zamannya, terdiri daripada perkara berikut. Tujuh jambatan bandar Koenigsberg (kini Kaliningrad) terletak di Sungai Pregel seperti yang ditunjukkan dalam Rajah. 4.30. Tugasnya adalah untuk meninggalkan rumah dan kembali, melalui sekali sahaja di setiap jambatan.

Memandangkan hanya lintasan di atas jambatan yang penting dalam masalah ini, pelan bandar boleh dikurangkan kepada graf (lebih tepat, multigraf) di mana tepi sepadan dengan jambatan, dan bucu sepadan dengan pelbagai bahagian bandar yang dibahagikan, yang ditunjukkan dengan huruf (Rajah 4.30, di sebelah kanan). Euler menunjukkan bahawa mustahil untuk melalui semua jambatan Königsberg sekali dan kembali. Dalam karyanya, yang diterbitkan pada tahun 1736, beliau merumuskan dan menyelesaikan perkara berikut masalah biasa teori graf: dalam keadaan apa graf bersambung mengandungi kitaran yang melalui setiap tepinya.

Kitaran dalam graf dipanggil Euler jika ia mengandungi semua tepi graf. Graf bersambung yang mempunyai kitaran Euler dipanggil Euler mengira. Graf sedemikian boleh dilukis tanpa mengangkat pensel dari kertas dan tanpa mengulangi garisan.

Sebagai contoh, graf yang ditunjukkan dalam Rajah. 4.31 ialah Euler kerana ia mengandungi kitaran Euler 1, 2, 3, 4, 5, 6, 4, 2, 6, 1. Terdapat kitaran Euler lain dalam graf ini. Adalah jelas bahawa mana-mana dua kitaran sedemikian berbeza antara satu sama lain hanya dalam susunan di mana tepi dilalui.

Teorem 4.7.(L. Euler, 1736 .) Graf bersambung ialah Euler jika dan hanya jika darjah semua bucunya adalah genap.

Rantai itu dipanggil Euler jika ia mengandungi semua tepi graf.

Teorem 4.8(L. Euler, 1736 .) Multigraf mempunyai rantai Euler jika dan hanya jika ia disambungkan dan bilangan bucu darjah ganjil ialah 0 atau 2.

Walaupun terdapat "kesamaan" dalam takrifan untuk kitaran Euler dan Hamiltonian, teori sepadan yang menetapkan kriteria kewujudan dan algoritma untuk mencari kitaran sedemikian mempunyai sedikit persamaan. Terem Euler (Teorem 4.7) memudahkan untuk menentukan sama ada graf adalah Euler. Algoritma telah dibangunkan yang menjadikannya agak mudah untuk mencari kitaran Euler bagi graf Euler. Setakat graf Hamiltonian, keadaan di sini pada asasnya berbeza. Sebagai peraturan, sangat sukar untuk menjawab soalan sama ada graf tertentu adalah Hamiltonian. Kriteria umum, yang serupa dengan kriteria Euler, tidak wujud di sini. Tetapi, ternyata, di antara set semua graf, terdapat sedikit graf Euler, tetapi terdapat banyak graf Hamiltonian.