Algoritma Kruskal - pembangunan kerangka optimal

Pada ilmu ukur awal abad ke-19 Jakob Steiner dari Berlin mengatur tugas bagaimana menghubungkan tiga desa sehingga panjangnya adalah terpendek. Kemudian, ia diringkas masalah: diperlukan untuk menemukan titik di pesawat, jarak dari ke n titik lainnya adalah yang terendah. Pada abad ke-20, terus bekerja pada topik ini. Diputuskan untuk mengambil beberapa poin dan menghubungkan mereka dalam sedemikian rupa sehingga jarak antara mereka adalah yang terpendek. Ini semua adalah kasus khusus dari masalah yang sedang dipelajari.

"Greedy" algoritma

Algoritma Kruskal mengacu pada "serakah" algoritma (juga disebut gradien). Inti dari mereka - kemenangan tertinggi di setiap langkah. Tidak selalu, "serakah" algoritma memberikan solusi terbaik untuk masalah ini. Ada teori, menunjukkan bahwa dalam aplikasi mereka untuk tugas-tugas khusus mereka memberikan solusi optimal. Ini adalah teori matroids. Algoritma Kruskal mengacu pada masalah tersebut.

Menemukan bobot karkas minimum

algoritma Dilihat membangun hitungan bingkai optimal. Masalah itu adalah sebagai berikut. Dan tidak diarahkan grafik tanpa tepi paralel dan loop, dan set tepi diberikan fungsi berat w, yang memberikan nomor untuk setiap sisi e - berat rusuk - w (e). Bobot masing-masing bagian dari pluralitas rusuk adalah jumlah bobot ujungnya. Diperlukan untuk menemukan kerangka berat badan kecil.

deskripsi

Algoritma Kruskal bekerja. Pertama, semua tepi grafik awal disusun dalam urutan menaik dari bobot. Awalnya, frame tidak mengandung tulang rusuk apapun tetapi mencakup semua simpul. Setelah langkah berikutnya dari algoritma ke bagian yang sudah dibangun dari bangkai, yang merupakan kawasan hutan yang membentang, salah satu ujung ditambahkan. Hal ini tidak dipilih secara sewenang-wenang. Semua tepi grafik, yang tidak termasuk frame, bisa disebut merah dan hijau. Bagian atas setiap tepi merah dalam komponen yang sama di bawah konektivitas hutan konstruksi, dan puncak hijau - yang berbeda. Oleh karena itu, jika Anda menambahkan ke tepi merah, ada siklus, dan jika hijau - seperti yang diterima setelah langkah ini komponen kayu yang terhubung akan kurang dari satu. Dengan demikian, konstruksi yang dihasilkan tidak dapat menambahkan tidak ada tepi merah, tetapi setiap tepi hijau dapat ditambahkan untuk mendapatkan hutan. Dan menambahkan tepi hijau dengan berat minimum. Hasilnya adalah kerangka berat minimum.

pelaksanaan

Menunjukkan hutan saat F. Ini membagi himpunan simpul di bidang konektivitas (bentuk serikat mereka F, dan mereka menguraikan). Pada kedua tepi simpul merah mereka berbohong dalam satu potong. Bagian (x) - fungsi yang untuk setiap titik x mengembalikan sebagian dari nama, itu milik x. Unite (x, y) - prosedur yang membangun partisi baru, yang terdiri dari menggabungkan bagian-bagian dari x dan y dan semua bagian lain. Biarkan n - jumlah tepi. Semua konsep ini termasuk dalam Algoritma Kruskal. pelaksanaan:

1. Mengatur semua tepi grafik dari 1 untuk bobot naik n-th. (Ai, bi - i dengan nomor tepi apex).

2. untuk i = 1 sampai n lakukan.

3. x: = Bagian (ai).

4. y: = Bagian (bi).

5. Jika x tidak y sama maka Unite (x, y), untuk menyertakan dengan jumlah tepi F i.

kebenaran

Mari T - bingkai grafik asli dibangun menggunakan algoritma Kruskal dan S - bingkai sewenang-wenang. Kita harus membuktikan bahwa w (T) tidak lebih besar dari w (S).

Mari M - pluralitas sirip S, P - pluralitas sirip T. Jika S tidak sama dengan T, maka ada bingkai tulang rusuk et T, tidak milik S. S. et adjoin siklus, hal itu disebut C. C menghapus dari setiap es tepi, milik S. Kami mendapatkan bingkai baru, karena tepi dan titik adalah sama. Bobotnya tidak lebih besar dari w (S), karena w (et) tidak lagi w (es) dalam algoritma listrik Kruskal. Operasi ini (pengganti T S tulang rusuk pada tulang rusuk) akan diulang selama menerima T. Berat setiap frame yang diterima berikutnya tidak lebih besar dari berat sebelumnya, yang menyiratkan bahwa w (T) tidak lebih besar dari w (S).

Kekokohan Algoritma Kruskal mengikuti dari teorema dari Rado-Edmonds di matroids.

Aplikasi Contoh algoritma Kruskal

Dan grafik dengan node a, b, c, d, e dan tulang rusuk (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). Bobot dari tepi ditunjukkan dalam tabel dan gambar. Awalnya, hutan konstruksi F berisi semua simpul dari grafik dan tidak mengandung tulang rusuk apapun. Algoritma Kruskal pertama kali menambahkan rusuk (a, e), karena berat memiliki terendah, dan simpul a dan e berada di komponen yang berbeda konektivitas kayu F (tulang rusuk (a, e) berwarna hijau), maka tulang rusuk (c, d), karena bahwa setidaknya ini berat tepi tepi grafik, tidak milik F, dan itu hijau, maka untuk alasan yang sama bertambah tepi (a, b). Tapi tepi (b, e) dilewatkan, meskipun ia dan berat minimum tepi tersisa, karena itu adalah merah: simpul b dan e milik komponen yang sama konektivitas hutan F, yaitu, jika kita menambah F tepi (b, e), terbentuk siklus. Kemudian ditambahkan tepi hijau (b, c) tepi merah, dilewatkan (c, e), dan kemudian d, e. Dengan demikian, tepi ditambahkan secara berurutan (a, e), (c, d), (a, b), (b, c). Dari nihera bingkai optimal dan terdiri dari grafik asli. Jadi dalam hal ini ia beroperasi algoritma Kruskal. Contoh ditunjukkan.

Angka ini menunjukkan grafik, yang terdiri dari dua komponen yang terhubung. Garis tebal menunjukkan rusuk bingkai optimal (hijau) dibangun menggunakan algoritma Kruskal.

Gambar atas menunjukkan grafik asli, dan bagian bawah - kerangka berat minimal, dibangun untuknya dengan menggunakan algoritma.

Urutan rusuk ditambahkan (1,6); (0,3), (2,6) atau (2,6), (0,3) - tidak penting; (3,4); (0,1), (1,6) atau (1,6), (0,1), juga peduli (5,6).

Algoritma Kruskal menemukan aplikasi praktis, misalnya, untuk mengoptimalkan komunikasi gasket, jalan di perumahan daerah baru di masing-masing negara, serta dalam kasus lain.