Минимальное остовное дерево

Минимальное остовное дерево (или минимальное покрывающее дерево) в (неориентированном) связном взвешенном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

Пример

Пример минимального остовного дерева в графе. Числа на ребрах обозначают вес ребер.

Задача о нахождении минимального остовного дерева часто встречается в подобной постановке: допустим, есть n городов, которые необходимо соединить дорогами так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Разрешается строить дороги между заданными парами городов и известна стоимость строительства каждой такой дороги. Требуется решить, какие именно дороги нужно строить, чтобы минимизировать общую стоимость строительства.

Эта задача может быть сформулирована в терминах теории графов как задача о нахождении минимального остовного дерева в графе, вершины которого представляют города, рёбра — это пары городов, между которыми можно проложить прямую дорогу, а вес ребра равен стоимости строительства соответствующей дороги.


Алгоритмы

Существует несколько алгоритмов для нахождения минимального остовного дерева. Некоторые наиболее известные из них перечислены ниже:

Родственные задачи

На задачу о нахождении минимального остовного дерева похожа задача о дереве Штейнера. В ней задано несколько точек на плоскости и требуется проложить между ними граф путей так, чтобы минимизировать сумму длин путей. Главное отличие от задачи о минимальном остовном дереве при этом заключается в том, что разрешается добавлять дополнительные точки ветвления с целью ещё сильнее уменьшить сумму длин рёбер. Задача о дереве Штейнера является NP-полной.

Литература

  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 23. Минимальные остовные деревья // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.

Read other articles:

Kappei Yamaguchi

Japanese actor This biography of a living person includes a list of general references, but it lacks sufficient corresponding inline citations. Contentious material about living persons that is unsourced or poorly sourced must be removed immediately, especially if potentially libelous or harmful. Please help to improve this article by introducing more precise citations. (October 2015) (Learn how and when to remove this template message) Kappei Yamaguchi山口 勝平Yamaguchi in 2016BornMitsuo...

 

No Land! No House! No Vote! (book)

Book by Symphony Way Pavement Dwellers No Land! No House! No Vote! Voices from Symphony Way AuthorSymphony Way Pavement DwellersCountrySouth AfricaLanguageEnglish, AfrikaansSubjectLand Rights, Civil Rights. CitizenshipGenreNon-fictionPublished1 March 2011 Pambazuka Press (first edition)Media typePaperbackPages160ISBN9781906387846 (pbk.)9780857490308 (ebook - pdf) No Land! No House! No Vote! Voices from Symphony Way is an anthology published in 2011 of 45 factual tales written and edited ...

 

Vulva

External genitalia of the female mammal For other uses, see Vulva (disambiguation). VulvaExamples of different human vulvasDetailsPrecursorGenital tubercle, urogenital folds, labioscrotal foldsSystemReproductive system, genitourinary systemArteryInternal pudendal artery, superficial external pudendal artery, deep external pudendal artery, labial arteries, clitoral arteriesVeinInternal pudendal veins, external pudendal veins, labial veins, clitoral veinsNervePudendal nerve, labial nerves, dors...

Pemberontakan Satsuma

Pemberontakan SatsumaTanggal29 Januari – 24 September 1877LokasiKyūshū, JepangHasil Kemenangan Kekaisaran JepangPihak terlibat  Kekaisaran Jepang Domain SatsumaTokoh dan pemimpin Emperor Meiji Arisugawa Taruhito Yamagata Aritomo Kuroda Kiyotaka Tani Tateki Saigō Takamori † Kirino Toshiaki † Beppu Shinsuke †Kekuatan 227,000 10 kapal perang 25,000Korban 15,000 tewas dan terluka[1] 21,000 tewas dan terluka[1][2] 4,000 ditangkap Pemberontaka...

 

1869 en France

Chronologies L'inauguration du canal de Suez le 17 novembre 1869. Édouard Riou. L’Album de l’Impératrice : Voyage pittoresque à travers l’isthme de Suez.Données clés 1866 1867 1868  1869  1870 1871 1872Décennies :1830 1840 1850  1860  1870 1880 1890Siècles :XVIIe XVIIIe  XIXe  XXe XXIeMillénaires :-Ier Ier  IIe  IIIe Chronologies géographiques Afrique Afrique du Sud, Algérie, Angola, Bénin, Botswana, Burkina Faso, B...

 

Canton de Vigneux-sur-Seine

Canton de Vigneux-sur-Seine Situation du canton de Vigneux-sur-Seine dans le département de l'Essonne. Administration Pays France Région Île-de-France Département Essonne Arrondissement(s) Évry Bureau centralisateur Vigneux-sur-Seine Conseillersdépartementaux Mandat Samia CartierFrançois Durovray 2021-2028 Code canton 91 19 Histoire de la division Création 25 novembre 1975[1] Modification 22 mars 2015[2] Démographie Population 58 287 hab. (2021) Géographie Coordonnées 48...

Penknife

Small folding knife A simple penknife Canivetes A 16th century depiction of using a penknife on a quill Penknife, or pen knife, is a small folding knife.[1] Today penknife is also the common British English term for both a pocketknife, which can have single or multiple blades, and for multi-tools, with additional tools incorporated into the design.[2] History Originally, penknives were used for thinning and pointing quills (cf. penna, Latin for feather) to prepare them for use...

 

United Aircraft

Pour les articles homonymes, voir United Aircraft Corporation. United Aircraft Corporation Création 1934 Disparition 1975 Fondateurs Frederick Rentschler Personnages clés George J. Mead (en), ingénieur principal Siège social Hartford États-Unis Activité Industrie aéronautique Sociétés sœurs Pratt & Whitney, Sikorsky et Vought modifier - modifier le code - voir Wikidata  La United Aircraft Corporation est une entreprise américaine fondée en 1934, dans le secteur...

 

Komoro

Halaman ini berisi artikel tentang negara kepulauan di Afrika Timur. Untuk kepulauannya, lihat Kepulauan Komoro. Untuk kegunaan lain, lihat Komoro (disambiguasi). Perserikatan KomoroUnion des Comores (Prancis) Udzima wa Komori (Komoro)الاتحاد القمري Al-Ittiḥād al-Qumurī/Qamarī (Arab) Bendera Lambang Semboyan: وحدة، تضامن، تنمية (Arab) Unité – Solidarité – Développement (Prancis: Persatuan, Solidaritas, Pembangunan)Lagu kebangsaan:  Udzima wa ...

Royal Caribbean International

Royal Caribbean InternationalJenisPublicIndustriTransportasiDidirikan1968KantorpusatMiami, Amerika SerikatTokohkunciMichael Bayley (CEO)ProdukKapal pesiarIndukRoyal Caribbean GroupSitus webhttp://www.royalcaribbean.com/ U.S. headquarters in Miami, Florida. Royal Caribbean International (RCI) NYSE: RCL adalah sebuah perusahaan kapal pesiar Norwegia-Amerika Serikat yang berbasis di Miami, Florida. Perusahaan ini memiliki 20 kapal dalam pelayanan dan 1 dalam pembuatan. Semua nama kapalnya memili...

 

Solon

Pour les articles homonymes, voir Solon. Sauf précision contraire, les dates de cet article sont sous-entendues « avant l'ère commune » (AEC), c'est-à-dire « avant Jésus-Christ ». SolonFonctionArchonte éponyme594-593 av. J.-C.BiographieNaissance Vers 630 av. J.-C.AthènesDécès Vers 560 av. J.-C.ChypreNom dans la langue maternelle Σόλων ο ΑθηναίοςActivités Législateur, philosophe, écrivain, poète, élégistePériode d'activité VIIe siècle av....

 

Ouragan Gilbert

Ouragan Gilbert Ouragan Gilbert approchant la Jamaïque Apparition 8 septembre 1988 Dissipation 19 septembre 1988 Catégorie maximale Ouragan catégorie 5 Pression minimale 888 hPa Vent maximal(soutenu sur 1 min) 295 km/h Dommages confirmés 5,5 milliards $US (1 988)10 milliards $US (2 008) Morts confirmés 341 directs Blessés confirmés N/D Zones touchées   Îles du Vent (Antilles) Venezuela Haïti République dominicaine Jamaïque îles Caïmans Mexique États-Unis (Texas)...

Histoire de la mécanique

L'histoire de la mécanique débute réellement avec Galilée. Mais cette science prend ses racines dans des savoirs bien plus anciens, notamment avec les réflexions d'Archimède ou d'Aristote. Jusqu'au XIXe siècle, la notion de mécanique englobait aussi bien l'étude scientifique des corps en mouvement que la théorie des machines. Étymologie du mot mécanique Si le mot apparaît à la Renaissance dans son sens moderne[1], cette science plonge cependant ses racines en des temps beau...

 

Lijiang

Peta letak Lijiang Untuk Situs Warisan Dunia UNESCO, lihat Kota Tua Lijiang. Kota Lijiang merupakan salah satu kota di Tiongkok. Letaknya di bagian selatan. Tepatnya di provinsi Yunnan. Pada tahun 2005, kota ini memiliki jumlah penduduk sekitar 1.100.000 jiwa. Lijiang biasanya dijuluki sebagai kota tua. Kota tua ini didirikan pada tahun 811. Kota ini pernah hancur akibat gempa pada tahun 1996. Pranala luar Wikimedia Commons memiliki media mengenai 丽江. Lijiang DIY Diarsipkan 2019-12-02 di ...

 

American lager

Pale lager produced in the United States This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: American lager – news · newspapers · books · scholar · JSTOR (June 2010) (Learn how and when to remove this message) Budweiser, an American lager American lager or North American lager is pale lager that is produced in t...

1946 NCAA basketball championship game

See also: 1946 NCAA basketball tournament 1946 NCAA Tournament Championship GameNational championship game North Carolina Tar Heels Oklahoma A&M Aggies SoCon MVC (29-4) (30-2) 40 43 Head coach:Ben Carnevale Head coach:Henry Iba 1st half2nd half Total North Carolina Tar Heels 1723 40 Oklahoma A&M Aggies 2320 43 DateMarch 26, 1946VenueMadison Square Garden, New York City, New YorkMVPBob Kurland, Oklahoma A&M[1]FavoriteOklahoma A&M by 8 ½[2]RefereesJocko Collins...

 

Abortion in North Dakota

Overview of the legality and prevalence of abortions in the U.S. state of North Dakota Abortion in North Dakota is illegal.[1] The state's sole abortion clinic relocated to Minnesota.[2] Following the United States Supreme Court's ruling to overturn Roe v. Wade on June 24, 2022, the state's trigger law, HB 1466, has been blocked by a district court since July.[3][4] Under the trigger law, performance of an abortion is a Class C felony subject to a maximum penal...

 

Diana Cage

Diana CageBorn (1979-07-16) July 16, 1979 (age 44)San Diego, CaliforniaOccupationAuthorNationalityAmericanWebsitewww.dianacage.com Diana Cage (born July 16, 1979) is an American feminist author, editor, cultural critic and radio personality. Her work examines sexuality, feminism, and LGBT culture. Career Cage began writing about sex and culture while interning under editor Lisa Palac at the San Francisco-based magazine Future Sex. In 2000, Cage's editorial work and extensive writing on s...

العلاقات الألمانية الجورجية

العلاقات الألمانية الجورجية ألمانيا جورجيا   ألمانيا   جورجيا تعديل مصدري - تعديل   العلاقات الألمانية الجورجية هي العلاقات الثنائية التي تجمع بين ألمانيا وجورجيا.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارن...

 

Serie C 2017-2018

Serie C 2017-2018 Competizione Serie C Sport Calcio Edizione 4ª Organizzatore Lega Italiana Calcio Professionistico Date dal 26 agosto 2017al 6 maggio 2018 Luogo Italia Partecipanti 56[1] Formula girone unico, play-off e play-out Risultati Vincitore Livorno (2º titolo)Padova (2º titolo)Lecce (3º titolo) Altre promozioni Cosenza Retrocessioni GavorranoPratoSantarcangeloModenaRacing FondiAkragas Statistiche Miglior marcatore Simone Guerra Daniele Vantaggiato (19) Incon...