Algoritma Kruskal urang - pangwangunan hiji kerangka optimal

Dina geometer mimiti abad ka-19 Jakob Steiner ti Berlin ngeset tugas kumaha nyambungkeun tilu desa jadi nu panjang maranéhanana ieu shortest. Engké, anjeunna diringkeskeun masalah: eta anu diperlukeun pikeun manggihan hiji titik dina pesawat a, jarak ti ka n titik lianna nya éta panghandapna. Dina abad ka-20, terus pikeun berpungsi dina topik ieu. Ieu mutuskeun nyandak sababaraha titik tur sambungkeun aranjeunna dina cara sapertos yén jarak antara aranjeunna ieu shortest. Ieu kabeh mangrupakeun kasus husus masalah keur ditalungtik.

"Irakus" Algoritma

Algoritma Kruskal urang nujul kana "Irakus" Algoritma (disebut oge gradién). Hakekat jalma - anu win pangluhurna di unggal hambalan. Teu salawasna, "Irakus" algoritma nyadiakeun solusi pangalusna pikeun masalah. Aya teori, némbongkeun yén dina aplikasi maranéhna pikeun tugas husus aranjeunna masihan solusi optimum. Ieu téori matroids. Algoritma Kruskal urang nujul kana masalah sapertos.

Pananjung beurat tulang taleng minimum

Algoritma ditempo constructs hiji count pigura optimal. Masalah éta saperti kieu. Dan undirected grafik tanpa edges sajajar jeung puteran, sarta susunan edges dirumuskeun éta fungsi beurat w, anu nangtukeun jumlah ka unggal ujung e - beurat iga - w (e). Beurat unggal sawaréh tina pluralitas tulang rusuk ngarupakeun jumlah tina beurat tina edges na. Diperlukeun pikeun manggihan rorongkong of a beurat leutik.

gambaran

Algoritma Kruskal urang jalan. Kahiji, sadaya edges of grafik awal anu disusun dina naek urutan tina beurat. Dina awalna, pigura henteu ngandung tulang rusuk wae tapi ngawengku sakabéh hucu. Saatos lengkah saterusna tina algoritma jeung bagian geus diwangun tina tulang taleng, nu mangrupakeun leuweung Manjang, salah ujung ieu ditambahkeun. Ieu teu dipilih wenang. Kabéh edges of grafik, moal milik pigura, bisa disebut beureum jeung héjo. Luhureun unggal edges beureum nu dina komponén sarua handapeun konektipitas leuweung konstruksi, sarta tops héjo - béda. Ku alatan éta, lamun nambahan tepi beureum, aya siklus, sarta lamun nu héjo - sakumaha narima sanggeus hambalan ieu komponen kai disambungkeun bakal kirang ti hiji. Ku kituna, konstruksi hasilna moal bisa nambahkeun euweuh ujung beureum, tapi sagala ujung héjo bisa ditambahkeun kana meunang leuweung. Jeung nambihan tepi héjo kalawan beurat minimum. hasilna mangrupakeun kerangka beurat minimum.

palaksanaan

Denote leuweung ayeuna F. Ieu meulah susunan hucu dina widang konektipitas (bentuk rugbi maranéhna F, sarta aranjeunna disjoint). Dina duanana edges of hucu beureum maranéhna ngabohong dina hiji sapotong. Bagian (x) - fungsi nu keur unggal vertex x mulih nyangkokkeun sabagian nami, éta milik x. Ngahiji (x, y) - prosedur nu ngawangun hiji partisi anyar, nu diwangun ku ngagabungkeun bagéan x jeung y sarta sakabéh bagian séjén. Hayu n - Jumlah edges. Kabéh konsep ieu anu kaasup kana algoritma Kruskal urang. palaksanaan:

1. Ngatur sagala edges of grafik ti 1st kana timbangan naek n-th. (Ai, bi - i kalawan jumlah ujung Apex).

2. keur i = 1 nepi ka n do.

3. x: = Bagian (ai).

4. y: = Bagian (bi).

5. Lamun x henteu y sarua lajeng ngahiji (x, y), ngawengku kalawan jumlah ujung F i.

correctness

Hayu T - pigura tina grafik aslina diwangun ngagunakeun algoritma Kruskal jeung S - pigura sawenang na. Urang kudu ngabuktikeun yén w (T) teu leuwih gede ti w (S).

Hayu M - pluralitas fins S, P - a pluralitas fins T. Lamun S henteu sarua jeung T, teras aya hiji pigura iga et T, moal milik S. S. et adjoin daur, mangka disebut C. C piceun tina sagala es ujung, milik S. Urang ménta pigura anyar, sabab edges na hucu nyaeta sami. beurat na teu gede ti w (S), saprak w (et) euweuh w (es) dina algoritma kakuatan Kruskal. Operasi ieu (diganti T S iga on tulang rusuk) bakal terus-terusan salami nampi T. The beurat unggal pigura narima saterusna teu leuwih gede dibandingkeun beurat saméméhna, nu ngakibatkeun yen w (T) teu leuwih gede ti w (S).

Katahanan algoritma Kruskal urang kieu ti central of Rado-Edmonds on matroids.

Aplikasi Conto algoritma Kruskal

Dan grafik kalawan titik a, b, c, d, e jeung tulang rusuk (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). The beurat tina edges ditembrakkeun dina tabél jeung di angka. Dina awalna, leuweung konstruksi F ngandung sakabéh hucu grafik tur teu ngandung tulang rusuk nanaon. Algoritma Kruskal munggaran nambahkeun iga (a, e), saprak beurat kagungan panghandapna, jeung hucu a jeung e anu di komponén béda konektipitas kayu F (iga (a, e) anu héjo), lajeng iga nu (c, d), sabab yén sahenteuna ieu beurat ujung edges grafik, moal milik F, sarta éta héjo, teras kanggo alesan sarua nambahan ujung (a, b). Tapi ujung (b, e) anu kaliwat, sanajan anjeunna jeung beurat minimum edges sésana, sabab nyaeta beureum: anu hucu b jeung e milik komponén sarua konektipitas leuweung F, nyaeta, lamun urang tambahkeun ka F ujung (b, e), kabentuk siklus. Lajeng ditambahkeun ujung héjo (b, c) ujung beureum, disalurkeun (c, e), sarta lajeng d, e. Ku kituna, edges nu ditambahkeun sequentially (a, e), (c, d), (a, b), (b, c). Ti nihera pigura optimal sarta ngawengku grafik aslina. Sahingga dina hal ieu eta ngoperasikeun hiji algoritma Kruskal. Hiji conto anu ditémbongkeun.

inohong nembongkeun grafik nu diwangun ku dua komponén disambungkeun. The garis kandel nunjukkeun iga pigura optimal (héjo) diwangun ngagunakeun algoritma Kruskal.

Gambar luhur mintonkeun grafik aslina, sarta handap - a rorongkong tina beurat minimal, diwangun pikeun anjeunna ku maké algoritma nu.

Sekuen tina tulang rusuk ditambahkeun (1.6); (0,3), (2,6) atawa (2,6), (0,3) - teu penting; (3,4); (0,1), (1,6) atawa (1,6), (0,1), ogé jaga (5,6).

Algoritma Kruskal urang manggih aplikasi praktis, contona, pikeun ngaoptimalkeun komunikasi gasket, jalan di perkebunan perumahan lokalitas anyar dina tiap nagara, kitu ogé dina kasus séjén.