Árvore (grafo)

Nota: Para outros significados de Árvore, veja Árvore (desambiguação).

Na teoria dos grafos, uma árvore é um grafo conexo (existe caminho entre quaisquer dois de seus vértices) e acíclico (não possui ciclos)^[1]^[2]. Caso o grafo seja acíclico mas não conexo, ele é dito uma floresta. Uma floresta também é definida como uma união disjunta de árvores.

Toda árvore é um grafo, mas nem todo grafo é uma árvore. Toda árvore é um grafo bipartido e planar. Todo grafo conexo possui pelo menos uma árvore de extensão associada, composta de todos os seus vértices e algumas de suas arestas.

Propriedades

Seja G um grafo de n vértices. G é uma árvore se satisfaz as seguintes condições:

G é conexo, e há exatamente um caminho entre dois vértices quaisquer. Já em uma floresta, há no máximo um caminho entre dois vértices, devido à não-conectividade.
G é acíclico, e um simples ciclo é formado se qualquer aresta for adicionada a G.
G é conexo, e deixará de ser conexo se qualquer aresta for removida de G.
G é conexo, acíclico e tem n − 1 arestas.

Definições

Uma árvore é denominada enraizada se um vértice é escolhido como especial. Esse vértice é chamado raiz. Uma árvore que não é enraizada é denominada livre.
Um grafo G é uma árvore se e somente se existir um único caminho entre cada par de vértices de G^[2].

Referências

↑ BARBOSA, Ruy Madsen (1975). Combinatória e Grafos. 2. São Paulo: Livraria Nobel. p. 196
↑ ^a ^b SZWARCFITER, Jayme Luiz (1988). Grafos e algoritmos computacionais. Rio de Janeiro: Campus. p. 43-45. ISBN 85-7001-341-8

Este artigo sobre informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.

Read other articles:

Perang Yahudi

Perang Yahudi Edisi bahasa Ibrani-Latin Perang Yahudi (Basle, 1559)PengarangFlavius YosefusJudul asliBuku-buku Flavius Yosefus mengenai Sejarah Perang Yahudi melawan RomawiNegaraKekaisaran RomawiBahasabahasa Aram (hilang), bahasa YunaniGenreSejarahTanggal terbit~75 MDiikuti olehAntiquitates Iudaicae (Sejarah Kuno Orang Yahudi) Perang Yahudi (Inggris: The Jewish Warcode: en is deprecated atau Judean War atau The Wars of the Jews[1][2][3] (lengkapnya...

Yakovlev Yak-53

Yakovlev Yak-53 adalah sebuah pesawat pelatih aerobatic yang diproduksi di Uni Soviet selama tahun 1981/2. Hanya prototipe yang diproduksi. Prototipe Yak-53 berasal dari Yak-52, berbeda dalam menjadi single seater dirancang sebagai pelatih aerobatic. Referensi Wikimedia Commons memiliki media mengenai Yakovlev aircraft. Gordon, Yefim (2005). OKB Yakovlev: A History of the Design Bureau and its Aircraft. Hinkley: Midland. hlm. 289–90. Gunston, Bill. Yakovlev Aircraft since 1924. L...

Francisco Vásquez de Coronado

Nama ini menggunakan cara penamaan Spanyol: nama keluarga pertama atau paternalnya adalah Vázquez de Coronado dan nama keluarga kedua atau maternalnya adalah Luján. Francisco Vázquez de Coronado y Luján (1510 – 22 September 1554) adalah seorang conquistador Spanyol, yang mengunjungi New Mexico dan bagian lainnya yang sekarang merupakan bagian barat daya Amerika Serikat antara 1540 dan 1542. Coronado berharap untuk menaklukan Tujuh Kota Emas dalam mitos. Namanya sering dianglikanisa...

Brampton GO Station

Railway station in Ontario, Canada BramptonGeneral informationLocation27/31 Church Street WestBrampton, OntarioCanadaCoordinates43°41′13″N 79°45′53″W / 43.68694°N 79.76472°W / 43.68694; -79.76472Owned byMetrolinx (station) Canadian National Railway (tracks)Platforms2 side platformsTracks2Connections Downtown Brampton TerminalConstructionStructure typeUnstaffed stationParking962 spacesAccessibleYesOther informationStation codeGO Transit: BRFare zone33His...

Mark Bunn

Mark Bunn Bunn pemanasan sebelum menghadapi LiverpoolInformasi pribadiNama lengkap Mark John Bunn[1]Tanggal lahir 16 November 1984 (umur 39)Tempat lahir Southgate, InggrisTinggi 6 ft 0 in (1,83 m)[2]Posisi bermain Penjaga gawangKarier junior1998–2000 Tottenham Hotspur2000–2001 Northampton TownKarier senior*Tahun Tim Tampil (Gol)2001–2008 Northampton Town 90 (0)2004 → Kettering Town (pinjaman) 17 (0)2008–2012 Blackburn Rovers 6 (0)2009 → Leicest...

Russian destroyer Udaloy

Udaloy-class destroyer of the Russian Navy Udaloy in 1983 History Russia Name Udaloy (Удалой) NamesakeUdaloy BuilderYantar Shipyard, Kaliningrad Laid down23 July 1977 Launched5 February 1980 Commissioned31 December 1980 Decommissioned1996 HomeportSeveromorsk IdentificationPennant number: 444, 480, 612, 637, 658, 695 FateScrapped 2006 General characteristics Class and typeUdaloy-class destroyer 7,570 tons full load[1] Length163 m (535 ft) Beam19.3 m (63 ft) Dr...

rio Dniepre

Rio DniepreDanáprisRio Danápris em QuieveNomes locais (be) Дняпро(uk) Дніпро(ru) ДнепрLocalizaçãoContinente EuropaPaís Rússia Bielorrússia UcrâniaLocalização Oblast de ZaporíjiaOblast de KhersonVoblast de ViciebskVoblast de MahilouVoblast de HomielOblast de DnipropetrovskOblast de PoltavaOblast de KirovogradoOblast de TcherkássiOblast de TchernihivOblast de KievKievOblast de SmolenskCoordenadas 55° 52′ 20″ N, 33° 43′ 26″ LD...

Todd Haberkorn

Todd HaberkornHaberkorn pada tahun 2015LahirTodd Michael Haberkorn16 Agustus 1982 (umur 41)Arlington, Texas, Amerika SerikatTempat tinggalLos Angeles, California, Amerika Serikat[1][2]Nama lainTodd StoneAlmamaterSouthern Methodist University (BFA)PekerjaanPengisi suara, ADR voice directorTahun aktif1994 - sekarangAgenThe Horne AgencyVOX Inc.Anak1[1][3]Situs webwww.thehabertat.com Todd Michael Haberkorn (lahir 16 Agustus 1982 di Arlington, Texas,...

Tetrataenite

Native metal TetrataeniteSilvery-bright tetrataenite crystalsGeneralCategoryNative element mineralsFormula(repeating unit)FeNiIMA symbolTtae[1]Strunz classification1.AE.10Crystal systemTetragonalCrystal classDomatic (m) (same H-M symbol)Space groupPmUnit cell22.92 Å³IdentificationFormula mass57.27 gmColorgray white, silver whiteCrystal habitGranular – Common texture observed in granite and other igneous rockCleavagenoneFracturemalleableMohs scale hardness3.5LustermetallicStreakgra...

Lehigh Mountain Hawks

Athletic teams of Lehigh University Lehigh Mountain HawksUniversityLehigh UniversityConferencePatriot League (primary)EIWA (wrestling)MARC (men's rowing)NCAADivision I (FCS)Athletic directorJoe SterrettLocationBethlehem, Pennsylvania, U.S.Varsity teams23Football stadiumGoodman StadiumBasketball arenaStabler ArenaBaseball stadiumJ. David Walker Field at Legacy ParkSoftball stadiumLeadership ParkSoccer stadiumUlrich Sports ComplexOther venuesFrank Banko FieldGoodman Campus Cross Country CourseG...

Wenzhou World Trade Center

Supertall skyscraper in Wenzhou, Zhejiang, China Wenzhou World Trade CenterGeneral informationStatusCompletedTypeMixed-useLocationWenzhou, Zhejiang, ChinaCoordinates28°00′25″N 120°39′54″E / 28.006896°N 120.664993°E / 28.006896; 120.664993Construction startedJune 9, 2003CompletedApril 18, 2010OpeningOctober 20, 2010HeightArchitectural321.9 m (1,056 ft)[1]Technical detailsFloor count68[1]Floor area174,361 m2 (1,876,806 sq&#...

Міністерство оборони України

Міністерство оборони України (Міноборони) Емблема Міністерства оборони та Прапор Міністерства оборони Будівля Міністерства оборони у КиєвіЗагальна інформаціяКраїна УкраїнаДата створення 24 серпня 1991Попередні відомства Міністерство оборони СРСР Народний комісарі...

هنود

هنودمعلومات عامةنسبة التسمية الهند التعداد الكليالتعداد قرابة 1.21 مليار[1][2]تعداد الهند عام 2011ق. 1.32 مليار[3]تقديرات عام 2017ق. 30.8 مليون[4]مناطق الوجود المميزةبلد الأصل الهند البلد الهند الهند نيبال 4,000,000[5] الولايات المتحدة 3,982,398[6] الإمار...

قائمة الممتلكات الثقافية ذات الأهمية الوطنية في الإمارات العربية المتحدة

تسرد هذه القائمة الممتلكات الثقافية ذات الأهمية الوطنية في الإمارات العربية المتحدة. أبوظبي المنطقة الوسطى #. الاسم النوع الموقع الوصف الإحداثيات صورة AD-1 حصن المقطع أبو ظبي 24°25′16″N 54°29′19″E / 24.421148°N 54.488491°E / 24.421148; 54.488491 (AD-1) AD-2 برج المقطع أبو ظبي 24°25′12″N 54°...

Richard E. Grant

Untuk aktor Amerika, lihat Richard Gant. Richard E. GrantGrant pada upacara British Academy Television Awards 2007LahirRichard Grant Esterhuysen5 Mei 1957 (umur 67)Mbabane, EswatiniTempat tinggalLondon, InggrisKebangsaanInggris dan Swazi[1]Nama lainRichard GrantPekerjaanAktor dan pembawa acaraTahun aktif1987 - sekarangSuami/istriJoan Washington (1986 - sekarang)Anak2Situs webwww.richardegrant.com Richard E. Grant (nama asli Richard Grant Esterhuysen; lahir 5 Mei 1957) a...

غريغوري الرابع

غريغوري الرابع معلومات شخصية الميلاد سنة 795 روما الوفاة 25 يناير 844 (48–49 سنة)[1][2] روما مكان الدفن كاتدرائية القديس بطرس مواطنة الدولة البابوية مناصب بابا الفاتيكان[3] (101 ) في المنصبأكتوبر 827 – 25 يناير 844 البابا فالنتين سر�...

سفارة كوريا الجنوبية في بلجيكا

سفارة كوريا الجنوبية في بلجيكا كوريا الجنوبية بلجيكا الإحداثيات 50°47′45″N 4°24′09″E / 50.7957°N 4.4026°E / 50.7957; 4.4026 البلد بلجيكا المكان بروكسل الاختصاص بلجيكا، ولوكسمبورغ[1] تعديل مصدري - تعديل سفارة كوريا الجنوبية في بلجيكا هي أرفع تمثيل دبلوماسي&#...

Comissão de Direitos Humanos e Minorias da Câmara dos Deputados do Brasil

A Comissão de Direitos Humanos e Minorias é uma das comissões permanentes da Câmara dos Deputados do Brasil, que analisa os assuntos e propostas legislativas a ela pertinentes[1]. Histórico A primeira tentativa de criação de uma comissão de direitos humanos na Câmara dos Deputados ocorreu em 1987, por iniciativa da deputada federal Benedita da Silva.[2] Em 1991, através do Projeto de Resolução nº 43, de 1991,[3] a deputada voltou a apresentar o mesmo projeto, o qual foi novamente...

Sexual Healing

1982 single by Marvin Gaye For the therapeutic concept, see Sex therapy. For the South Park episode, see Sexual Healing (South Park). Sexual HealingSingle by Marvin Gayefrom the album Midnight Love B-sideSexual Healing (instrumental version)ReleasedOctober 1982StudioStudio Katy, Ohain, BelgiumGenre Post-disco soul funk Length 3:59 (album version) 4:05 (single version) 4:39 (alternate vocal) LabelColumbia/CBS RecordsSongwriter(s)Marvin GayeOdell BrownDavid RitzProducer(s)GayeMarvin Gaye single...

Electric potential energy

Potential energy that results from conservative Coulomb forces Not to be confused with Electric potential or Electric power. This article is about the physical magnitude Electric Potential Energy. For electrical energy, see Electrical energy. For energy sources, see Energy development. For electricity generation, see Electricity generation. Electric potential energyCommon symbolsUESI unitjoule (J)Derivations fromother quantitiesUE = C · V2 / 2 Articles aboutElectromagnetism Electricity ...