Árvore de extensão

Exemplo de uma árvore de dispersão (composta pelas arestas azuis)
Três exemplos em um grafo de grade quadrada 8x8

Uma árvore de extensão, árvore geradora ou árvore de dispersão (em inglês: spanning tree) é o subconjunto de arestas de um grafo que forma uma árvore contendo todos os vértices.

Uma árvore de extensão mínima, árvore geradora mínima ou árvore de extensão de custo mínimo (em inglês: minimum spanning tree) é o subconjunto de arestas de menor peso total em um grafo valorado que forma uma árvore contendo todos os nós.

Uma árvore de extensão apresenta as seguintes propriedades:

  • Define um subconjunto de arestas que mantém o grafo conectado em um único componente;
  • Em um grafo não-valorado qualquer árvore de dispersão é mínima;
  • Podem ser calculadas em tempo polinomial.

Os algoritmos usuais para a determinação de árvores de extensão são o algoritmo de Prim (1957) e o algoritmo de Kruskal (1956).

Aplicações

Vários algoritmos de busca de caminho, incluindo o algoritmo de Dijkstra e o algoritmo A*, desenvolvem internamente uma árvore de extensão como uma etapa intermediária para resolver o problema.

Para minimizar o custo de redes de energia, conexões cabeadas, tubulação, reconhecimento automático de fala, etc., as pessoas geralmente usam algoritmos que gradualmente constroem uma árvore de extensão (ou muitas dessas árvores) como passo intermediário no processo de encontrar a árvore de extensão mínima. [1]

A Internet e muitas outras redes de telecomunicações possuem links de transmissão que conectam nós em uma topologia de malha (mesh) que inclui alguns loops. Para evitar loops de ponte e de roteamento, muitos protocolos de roteamento projetados para essas redes -- incluindo o protocolo Spanning Tree, Open Shortest Path First, protocolo de roteamento de estado de link, roteamento com base em árvore aumentada, etc. -- exigem um roteador para lembrar a árvore de extensão.

Referências

  1. ↑ R. L. Graham and Pavol Hell. "On the History of the Minimum Spanning Tree Problem". 1985.

Read other articles:

Jean Baptiste Adoue

American politician Jean Baptiste Adoue, Jr. (November 4, 1884 – November 17, 1956) was the mayor of Dallas, Texas from 1951 to 1953. Early career He is born in Dallas County, Texas, as one of four children of Jean Baptiste Adoue, Sr. and Mittie Neosha Simpson Adoue. In 1906, he graduated in law from the University of Texas at Austin and returned to his home town to practice law for the following year before working with Adoue Sr. at the National Bank of Commerce (formerly known as Flippen,...

 

Mohammad Said Keruak

Ini adalah nama Melayu; nama Keruak merupakan patronimik, bukan nama keluarga, dan tokoh ini dipanggil menggunakan nama depannya, Mohammad Said. Yang Amat Berbahagia TunMohammad Said KeruakSMN PMN Yang di-Pertua Negeri Sabah ke-7Masa jabatan1 Januari 1987 – 31 Desember 1994PendahuluMohamad Adnan RobertPenggantiSakaran DandaiKetua Menteri Sabah ke-4Masa jabatan1 November 1975 – 18 April 1976PendahuluMustapha HarunPenggantiFuad Stephens Informasi pribadiLahirMohammad S...

 

Pieter Corneliszoon Hooft

Dutch historian and writer (1581–1647) For the Dutch ocean liner, see MV Pieter Corneliszoon Hooft. 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: Pieter Corneliszoon Hooft – news · newspapers · books · scholar · JSTOR (February 2014) (Learn how and when to remove this template message) P.C. Hooft Pieter ...

Западный округ (Краснодар)

У этого термина существуют и другие значения, см. Западный округ. Западный внутригородской округ город Краснодар Дата основания 1936 год Дата упразднения 1994 Прежние имена Кагановичский, Ленинский районы Микрорайоны Дубинка, Черёмушки, Покровка Площадь 22[1]  км² Насе...

 

2016年美國總統選舉

2016年美國總統選舉 ← 2012 2016年11月8日 2020 → 538個選舉人團席位獲勝需270票民意調查投票率55.7%[1][2] ▲ 0.8 %   获提名人 唐納·川普 希拉莉·克林頓 政党 共和黨 民主党 家鄉州 紐約州 紐約州 竞选搭档 迈克·彭斯 蒂姆·凱恩 选举人票 304[3][4][註 1] 227[5] 胜出州/省 30 + 緬-2 20 + DC 民選得票 62,984,828[6] 65,853,514[6]...

 

فولغا

  لمعانٍ أخرى، طالع فولغا (توضيح). فولغا     المنطقة البلد روسيا[1]  الخصائص الطول 3700 كم المجرى المنبع الرئيسي تلال فالداي (256 متر)  المصب بحر قزوين مساحة الحوض 1360000 كيلومتر مربع[2]  الروافد نهر كاما،  ونهر أوكا،  ونهر سورا،  وسامارا،  ونهر سفي�...

Barmah

For the village in Iran, see Barmah, Iran. Town in Victoria, AustraliaBarmahVictoriaMurray River crossing at BarmahBarmahCoordinates36°01′03″S 144°57′55″E / 36.01750°S 144.96528°E / -36.01750; 144.96528Population282 (2016 census)[1]Postcode(s)3639Location 265 km (165 mi) N of Melbourne 63 km (39 mi) NW of Shepparton 34 km (21 mi) SW of Echuca 27 km (17 mi) W of Nathalia 16 km (10 mi) W of Picola...

 

哈萨克斯坦总统

此条目序言章节没有充分总结全文内容要点。 (2019年3月21日)请考虑扩充序言，清晰概述条目所有重點。请在条目的讨论页讨论此问题。 哈萨克斯坦總統哈薩克總統旗現任Қасым-Жомарт Кемелұлы Тоқаев卡瑟姆若马尔特·托卡耶夫自2019年3月20日在任任期7年首任努尔苏丹·纳扎尔巴耶夫设立1990年4月24日（哈薩克蘇維埃社會主義共和國總統） 哈萨克斯坦 哈萨克斯坦政府...

 

The Exorcist: Believer

2023 film by David Gordon Green The Exorcist: BelieverTheatrical release posterDirected byDavid Gordon GreenScreenplay by Peter Sattler David Gordon Green Story by Scott Teems Danny McBride David Gordon Green Based onCharactersby William Peter BlattyProduced by Jason Blum David C. Robinson James G. Robinson Starring Leslie Odom Jr. Lidya Jewett Olivia O’Neill Jennifer Nettles Norbert Leo Butz Ann Dowd Ellen Burstyn CinematographyMichael SimmondsEdited byTim AlversonMusic by David Wingo Amma...

2009 Copa Libertadores finals

Football match2009 Copa Libertadores finalsPlayers of Estudiantes celebrating the victoryEvent2009 Copa Libertadores Estudiantes LP Cruzeiro 2 1 on pointsFirst leg Estudiantes LP Cruzeiro 0 0 Date8 July 2009VenueEstadio Único, La PlataMan of the MatchFábioRefereeJorge Larrionda (Uruguay)Second leg Cruzeiro Estudiantes LP 1 2 Date15 July 2009VenueMineirão, Belo HorizonteMan of the MatchJuan Sebastián VerónRefereeCarlos Chandía (Chile)← 2008 2010 → The 2009 Copa Libertadores f...

 

Saitama Prefecture

Prefecture of Japan Not to be confused with the main character of the popular anime One Punch Man, Saitama.Prefecture in Kantō, JapanSaitama Prefecture 埼玉県PrefectureJapanese transcription(s) • Japanese埼玉県 • RōmajiSaitama-ken FlagSymbolAnthem: Saitama kenkaCoordinates: 35°57′N 139°33′E / 35.950°N 139.550°E / 35.950; 139.550CountryJapanRegionKantōIslandHonshuCapitalSaitamaSubdivisionsDistricts: 8, Municipalities: 63Gove...

 

Alexander S. Clay

American politician For other people named Alexander Clay, see Alexander Clay (disambiguation). Alexander S. ClayUnited States Senatorfrom GeorgiaIn officeMarch 4, 1897 – November 13, 1910Preceded byJohn B. GordonSucceeded byJoseph M. TerrellMember of the Georgia House of RepresentativesIn office1884-18871889-1890 Personal detailsBornAlexander Stephens Clay(1853-09-25)September 25, 1853Powder Springs, GeorgiaDiedNovember 13, 1910(1910-11-13) (aged 57)Atlanta, GeorgiaPolitical ...

乔冠华

乔冠华 中华人民共和国外交部部长 中国人民对外友好协会顾问 任期1974年11月—1976年12月总理周恩来 → 华国锋前任姬鹏飞继任黄华 个人资料性别男出生(1913-03-28)1913年3月28日 中華民國江蘇省盐城县逝世1983年9月22日(1983歲—09—22)（70歲） 中华人民共和国北京市籍贯江蘇鹽城国籍 中华人民共和国政党 中国共产党配偶明仁（1940年病逝） 龚澎（1970年病逝） 章含�...

 

Integrasi vertikal

Dalam konteks ekonomi mikro dan manajemen, integrasi vertikal adalah sebuah keadaan dimana seluruh tahap dalam rantai suplai dimiliki oleh sebuah perusahaan. Integrasi ini berbeda dengan Integrasi Horizontal, dimana sebuah perusahaan akan mengintegrasikan produksi beberapa produk yang masih dalam satu tahap dalam rantai suplai. Andrew Carnegie adalah salah satu pengusaha pertama yang menggunakan metode integrasi ini dalam memproduksi baja,[1] Integrasi vertikal dapat menjadi strategi ...

 

Jerry Garcia

American guitarist and singer (1942–1995) Jerry GarciaGarcia performing in 1977, Fox Theatre, Atlanta, GeorgiaBornJerome John Garcia(1942-08-01)August 1, 1942San Francisco, California, U.S.DiedAugust 9, 1995(1995-08-09) (aged 53)Forest Knolls, California, U.S.OccupationsGuitaristsingersongwriterYears active1960–1995Spouses Sara Ruppenthal ​ ​(m. 1963; div. 1967)​ Carolyn Adams ​ ​(m. 1981; div. ...

بطولة العالم للسيكلو كروس 2021

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (نوفمبر 2022) هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحس...

 

2020 Taça de Portugal final

Football match2020 Taça de Portugal finalEstádio Cidade de CoimbraEvent2019–20 Taça de Portugal Benfica Porto 1 2 Date1 August 2020VenueEstádio Cidade de Coimbra, CoimbraMan of the MatchChancel Mbemba (Porto)[1]Fair Player of the MatchDanilo Pereira (Porto)[1]RefereeArtur Soares DiasAttendance0[note 1]← 2019 2021 → The 2020 Taça de Portugal final was the final match of the 2019–20 Taça de Portugal, which decided the winner of the 80th season of th...

 

Zombia

Genus of palm endemic to Hispaniola Not to be confused with Zambia. Zombia Zombia antillarum at Marie Selby Botanical Gardens, Sarasota, Florida, United States Conservation status Vulnerable  (IUCN 3.1)[1] Scientific classification Kingdom: Plantae Clade: Tracheophytes Clade: Angiosperms Clade: Monocots Clade: Commelinids Order: Arecales Family: Arecaceae Subfamily: Coryphoideae Tribe: Cryosophileae Genus: ZombiaL.H. Bailey Species: Z. antillarum Binomial name Zombia antilla...

Убийство Самюэля Пати

Убийство Самюэля Пати Государство  Франция Административно-территориальная единица Конфлан-Сент-Онорин Часовой пояс центральноевропейское летнее время Местонахождение Конфлан-Сент-Онорин Момент времени 16 октября 2020 Число раненых 0 Число погибших 1 чел.[1] Чи�...

 

Різдвяні пісні

У Вікіпедії є статті про інші значення цього терміна: Різдвяна пісня (значення). Різдвяна пісня (англ. Christmas carol, фр. Chant de Noël) — пісня (керол, ноель, колядка, щедрівка тощо) або гімн на тему Різдва Христового, яка традиційно виконується перед, під час або після цього свята. Р...