Thuật toán Karger

Trong khoa học máy tính và lý thuyết đồ thị, thuật toán Karger là một thuật toán Monte Carlo để tìm lát cắt nhỏ nhất của một đồ thị vô hướng. Bài toán lát cắt nhỏ nhất yêu cầu tìm cách chia đồ thị làm hai phần sao cho số cạnh nối các đỉnh ở hai phần khác nhau là nhỏ nhất. Thuật toán được tìm ra bởi David Karger.

Thuật toán

Ý tưởng chính của thuật toán là sử dụng phép hợp nhất hai đầu của một cạnh $e$ trong đồ thị $G=(V,E)$ . Sau mỗi lần hợp nhất, số đỉnh của đồ thị giảm đi 1. Thuật toán sử dụng một chuỗi các phép hợp nhất các cạnh ngẫu nhiên của đồ thị. Xác suất chọn mỗi cạnh tỉ lệ với trọng số của nó. Thuật toán này là một thuật toán đệ quy. Trong mỗi tầng đệ quy, thuật toán hoạt động như sau. Thử hai lần độc lập nhau việc lặp đi lặp lại phép hợp nhất để giảm số đỉnh của $G$ xuống $\left\lceil n/{\sqrt {2}}+1\right\rceil$ và gọi đệ quy để tính lát cắt nhỏ nhất trong đồ thị thu được. Sau đó, chọn kết quả tốt hơn trong hai lần gọi đệ quy và trả về giá trị đó.

Phép hợp nhất

Trong mỗi lần thực hiện, phép toán này hợp nhất hai đỉnh x và y của một cung e thành một đỉnh mới $v_{e}$ kề với tất cả các đỉnh kề của x và y. Định nghĩa cụ thể là như sau.

Cho một đồ thị $G=\left(V,E\right)$ và $e=\lbrace x,y\rbrace \in E$ , kết quả phép hợp nhất hai đỉnh kề với cạnh $e$ (ký hiệu $G/e=\left(V',E'\right)$ ) là một đa đồ thị định nghĩa như sau:

V'=\left(V\setminus \lbrace x,y\rbrace \right)\cup \lbrace v_{e}\rbrace

và:

E'=\lbrace \lbrace v,w\rbrace \in E\mid \lbrace v,w\rbrace \cap \lbrace x,y\rbrace =\emptyset \rbrace \cup \lbrace \lbrace v_{e},w\rbrace \mid \lbrace x,w\rbrace \in E\setminus \lbrace e\rbrace

hoặc

\lbrace y,w\rbrace \in E\setminus \lbrace e\rbrace \rbrace

Có thể chứng minh phép toán này không làm giảm nhưng có thể làm tăng giá trị lát cắt nhỏ nhất.

Thời gian thực hiện

Thuật toán Karger là thuật toán ngẫu nhiên nhanh nhất hiện nay cho việc tìm lát cắt nhỏ nhất, với thời gian chạy O(|V|² log³|V|). Để chứng minh điều này, tác giả chỉ ra cách thực hiện chuỗi các phép hợp nhất để giảm kích thước $G$ xuống $\left\lceil n/{\sqrt {2}}+1\right\rceil$ đỉnh trong thời gian $O(n^{2})$ . Do đó thời gian chạy của thuật toán là $T(n)=2\left(n^{2}+T\left(\left\lceil n/{\sqrt {2}}+1\right\rceil \right)\right)$ . Phương trình này cho kết quả $T(n)=O(n^{2}log(n))$ . Sau mỗi lần thực hiện thuật toán, xác suất tìm ra lát cắt nhỏ nhất là $\Omega (1/log(n))$ . Nếu thực hiện thuật toán $O(log^{2}(n))$ lần thì xác suất không tìm ra lát cắt nhỏ nhất giảm xuống $O(1/ n 2)$ .

Tham khảo

David R. Karger (1993). “Global Min-cuts in RNC and Other Ramifications of a Simple Mincut Algorithm”. Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms.
Karger, David R.; Stein, Clifford (1996), “A New Approach to the Minimum Cut Problem”, Journal of the ACM, 43 (4): 601–640

Read other articles:

CNA (saluran berita)

CNADiluncurkan1 Maret 1999; 25 tahun lalu (1999-03-01)JaringanMediacorpSloganUnderstand AsiaNegaraSingapuraBahasaInggrisKantor pusatMediacorp Campus, SingapuraTelevisi InternetCNA Official (Internasional)Watch TVMediaCorp (Singapura)Toggle.SG CNA (singkatan nama sebelumnya, Channel NewsAsia)[1] adalah stasiun televisi berita yang berbasis di Singapura. Perusahaan ini didirikan pada tanggal 1 Maret 1999. Saluran ini menggunakan satelit Hot Bird. Di negara Malaysia, CNA dapat diper...

Ludwig Feuerbach

Ludwig Andreas von FeuerbachLudwig Andreas von FeuerbachLahir(1804-07-28)28 Juli 1804Landshut, BavariaMeninggal13 September 1872(1872-09-13) (umur 68)Rechenberg dekat Nürnberg, Kekaisaran JermanEraFilsafat abad ke-19KawasanFilsafat BaratAliranMaterialisme, HumanismeMinat utamaAgama, KekristenanGagasan pentingAgama sebagai proyeksi luar dari sifat batin manusia Dipengaruhi Hegel Memengaruhi Leconte de Lisle, Karl Marx, Friedrich Engels, Mikhail Bakunin, Max Stirner, Joseph Die...

Greeneville, Tennessee

Greeneville beralih ke halaman ini. Untuk Untuk kegunaan lain dari Greenville, lihat Greenville, lihat Greeneville (disambiguasi). Lokasi Greeneville Greeneville adalah sebuah kota di Greene County, Tennessee. Pada tahun 2000 Greeneville berpenduduk 15.198 jiwa, dengan luas wilayah 36,4 km². Kota ini adalah county seat Greene County. Tokoh Andrew Johnson, mantan Presiden Amerika Serikat pernah tinggal di Greeneville. Kota ini juga terkenal karena sebuah kapal selam kelas Los Angeles USS...

Gunpo

Gunpo 군포軍浦Municipal CityTranskripsi Korean • Hangul군포시 • Hanja軍浦市 • Revised RomanizationGunpo-si • McCune-ReischauerKunp'o-si Emblem of GunpoCountry South KoreaRegionSudogwonAdministrative divisions11 dongLuas • Total36,352005 km2 (14,035,588 sq mi)Populasi (2005) • Total313.413 • Kepadatan7.427,8/km2 (192,380/sq mi) • DialectSeoul Gunpo adalah...

Синелобый амазон

Синелобый амазон Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:ЗавропсидыКласс:Пт�...

1922–23 Illinois Fighting Illini men's basketball team

American college basketball season 1922–23 Illinois Fighting Illini men's basketballConferenceBig Ten ConferenceRecord9–6 (7–5 Big Ten)Head coachJ. Craig RubyAssistant coachDavid M. Bullock (Trainer)[1]CaptainNorton HellstromHome arenaKenney GymSeasons← 1921–221923–24 → 1922–23 Big Ten Conference men's basketball standings vte Conf Overall Team W L PCT W L PCT Iowa 11 – 1 .917 13 – 2 .867...

趙家驤

追晉陸軍二級上將趙家驤將軍个人资料出生1910年大清河南省衛輝府汲縣逝世1958年8月23日(1958歲—08—23)（47—48歲） † 中華民國福建省金門縣国籍中華民國政党中國國民黨获奖青天白日勳章（追贈）军事背景效忠中華民國服役國民革命軍中華民國陸軍服役时间1924年－1958年军衔二級上將（追晉）部队四十七師指挥東北剿匪總司令部參謀長陸軍�...

Operation Berlin (Atlantic)

German commerce raid during the naval battles of the Second World War This article is about the 1941 commerce raid. For the 1944 Arnhem rescue, see Operation Berlin (Arnhem). Operation Berlin (Atlantic)Part of the Battle of the Atlantic of the Second World WarThe German battleship Gneisenau in 1939; she served as the flagship for Operation BerlinDate22 January — 22 March 1941LocationAtlantic OceanResult German victoryBelligerents Germany United KingdomCommanders and leaders...

Johan Castberg

Norwegian jurist and politician (1862–1926) Johan CastbergCastberg in 1900.Member of the Norwegian ParliamentIn office1 January 1925 – 31 December 1927In office1 January 1913 – 31 December 1921In office1 January 1900 – 31 December 1909Minister of JusticeIn office19 March 1908 – 2 February 1910Prime MinisterGunnar KnudsenPreceded byJohan BredalSucceeded byHerman ScheelMinister of Social AffairsIn office1 July 1913 – 22 April 1914Prime Mi...

Rizal Day

Public holiday in the Philippines Rizal DayPresident Benigno Aquino III offering a wreath at the Rizal Monument in Manila on Rizal Day 2015Observed byPhilippinesTypeNationalSignificanceCommemoration of the life and works of José RizalDateDecember 30Next timeDecember 30, 2024 (2024-12-30)FrequencyAnnualFirst timeDecember 30, 1898 Rizal Day (Spanish: Día de Rizal, Filipino: Araw ni Rizal; Tagalog: [riˈsal]) is a Philippine national holiday commemorating life and w...

Katedral São Paulo (Yunani Melkit)

Katedral Katolik Yunani Melkit São PauloKatedral Bunda MariaKatedral Katolik Yunani Melkit São PauloLokasiSão PauloNegaraBrasilDenominasiGereja Katolik Roma(sui iuris: Gereja Katolik Yunani Melkit)ArsitekturStatusKatedralStatus fungsionalAktifAdministrasiKeuskupanEparki São Paulo (Yunani Melkit) Katedral Katolik Yunani Melkit São Paulo yang bernama resmi Katedral Bunda Maria (bahasa Portugis: Catedral de Nossa Senhora do Paraíso) adalah sebuah gereja katedral Katolik yang berlokasi ...

Liquid Paper

Brand of correction fluid Liquid Paper products at The Women's Museum in Dallas, Texas Liquid Paper is an American brand of the Newell Brands company marketed internationally that sells correction fluid, correction pens, and correction tape. Mainly used to correct typewriting in the past, correction products now mostly cover handwriting mistakes. Product history Liquid Paper In 1956, Bette Nesmith Graham (mother of future Monkees guitarist Michael Nesmith) invented the first correction fluid ...

Alexander Kolchak

Russian admiral and polar explorer (1874–1920) In this name that follows Eastern Slavic naming customs, the patronymic is Vasilyevich and the family name is Kolchak. Alexander KolchakАлександр КолчакKolchak in 1919Supreme Ruler of Russia[a]In office18 November 1918 – 7 February 1920Preceded byPosition established(Nikolai Avksentiev as Chairman of the Provisional All-Russian Government)Succeeded byAnton Denikin(de facto) Personal detailsBorn16 November ...

Навчальний центр Національної гвардії України

Навчальний центр НГ України Нарукавний знак центруКраїна УкраїнаНалежність Національна гвардіяБазування Львівська область,м.ЗолочівОборонець Василь ВишиванийВійни/битви Російська збройна агресія проти України Війна на сході УкраїниКомандуванняПоточнийк...

Johnson County, Iowa

County in Iowa, United States County in IowaJohnson CountyCountyJohnson County Courthouse SealLocation within the U.S. state of IowaIowa's location within the U.S.Coordinates: 41°40′00″N 91°35′00″W / 41.666666666667°N 91.583333333333°W / 41.666666666667; -91.583333333333Country United StatesState IowaFoundedDecember 21, 1837Named forRichard Mentor Johnson (1837–2020) Lulu Johnson (since 2020)SeatIowa CityLargest cityIowa CityArea • T...

Eragrostis dielsii

Eragrostis dielsii TaksonomiDivisiTracheophytaSubdivisiSpermatophytesKladAngiospermaeKladmonocotsKladcommelinidsOrdoPoalesFamiliPoaceaeSubfamiliChloridoideaeTribusEragrostideaeGenusEragrostisSpesiesEragrostis dielsii Pilg. lbs Eragrostis dielsii, atau yang lebih dikenal dengan sebutan mallee lovegrass, adalah sebuah spesies tumbuhan yang merupakan endemik di Australia. Spesies tersebut mula-mula dipublikasikan pada 1904 oleh Robert Knud Friedrich Pilger[1] Referensi ^ Eragrostis diels...

Bleacher Report

Sports-related website Bleacher ReportOwnerTNT SportsFounder(s)David FinocchioAlexander FreundBryan GoldbergDave NemetzParentTNT Sports InteractiveSubsidiariesHouse of HighlightsURLbleacherreport.comRegistrationOptionalLaunched2005; 19 years ago (2005) Bleacher Report (often abbreviated as B/R) is a website that focuses on sport and sports culture. Its headquarters are in San Francisco, with offices in New York City and London.[1][2][3] Bleacher Repor...

RN01-SS

RN01-SS adalah peluru kendali antikapal dan peluru kendali serangan darat yang dikembangkan oleh Kementerian Pertahanan dan beberapa perusahaan. RN01-SS merupakan singkatan dari Rudal Nasional 01 - Surface to Surface. RN01-SS mempunyai kecepatan subsonik dan mempunyai kemiripan dengan rudal C-705.[1] Grafik 3D Rudal Pengembangan Pengembangan dilakukan oleh Kementrian Pertahanan dan BPPT bersama dengan konsorsium perusahaan yang terdiri dari PT Dirgantara Indonesia, PT Pindad, PT Dahan...

Doyle spiral

Circle packing arranged in spirals A Doyle spiral of type (8,16) printed in 1911 in Popular Science as an illustration of phyllotaxis.[1] One of its spiral arms is shaded. In the mathematics of circle packing, a Doyle spiral is a pattern of non-crossing circles in the plane in which each circle is surrounded by a ring of six tangent circles. These patterns contain spiral arms formed by circles linked through opposite points of tangency, with their centers on logarithmic spirals of th...

Tashi delek

Tashi delek Tashi delek (Tibet: བཀྲ་ཤིས་བདེ་ལེགས།།)[1] adalah kata sapaan atau salam tradisional Tibet kepada teman dan juga orang asing, untuk menyampaikan harapan penuh berkah, kesehatan yang baik, dan keberuntungan. Dianggap sebagai sapaan umum saat ini, Tashi delek terutama umum dan cocok digunakan pada saat Tahun Baru Tibet, yang disebut Losar.[2] Tashi delek juga digunakan di Bhutan dengan makna yang lebih kurang sama, dengan arti Semo...

الملفات الغامضة: أريد أن أصدق

Mazmur 51

Ben-Zion Meir Hai Uziel

Haruna Kojima

Andrew Miller (politician)

Tia Maria

Madrid Forum

Results of the 2007 New South Wales state election (Legislative Council)

Pathibhara Devi Temple

International Union of History and Philosophy of Science

Calcio nel mondo

Irish cuisine