Корневой граф

В теории графов корневым графом называется граф, в котором есть одна помеченная вершина. Эту помеченную вершину называют корнем графа^[1]^[2]^:454.

Число корневых графов для 1, 2, 3, ... вершин равно 1, 2, 6, 20, 90, 544, ... (последовательность A000666 в OEIS).

Корневые графы можно комбинировать с помощью корневого произведения графов.

Корневые деревья

Корневое дерево — дерево, в котором выделена одна вершина (корень дерева). Формально корневое дерево определяется как конечное множество $T$ одного или более узлов со следующими свойствами:

существует один корень дерева $T$ ;
остальные узлы (за исключением корня) распределены среди $m\geq 0$ непересекающихся множеств $T_{1},...,T_{m}$ , и каждое из множеств является корневым деревом; деревья $T_{1},...,T_{m}$ называются поддеревьями данного корня $T$ .

Связанные определения

Уровень узла — длина пути от корня до узла. Можно определить рекурсивно:

уровень корня дерева $T$ равен 0;
уровень любого другого узла на единицу больше, чем уровень корня ближайшего поддерева дерева $T$ , содержащего данный узел.

Дерево с отмеченной вершиной называется корневым деревом.
- $m$ -й ярус дерева $T$ — множество узлов дерева, на уровне $m$ от корня дерева.
- частичный порядок на вершинах: $u\prec v$ , если вершины $u$ и $v$ различны и вершина $u$ лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной $v$ .
- корневое поддерево с корнем $v$ — подграф $\{v\}\cup \{w\mid v<w\}$ .
- В контексте, где дерево предполагается имеющим корень, дерево без выделенного корня называется свободным.

Примечания

↑ Daniel Zwillinger. CRC Standard Mathematical Tables and Formulae, 32nd Edition. — CRC Press, 2011. — ISBN 978-1-4398-3550-0.
↑ Frank Harary. The number of linear, directed, rooted, and connected graphs // Transactions of the American Mathematical Society. — 1955. — Вып. 78. — С. 445—463. — doi:10.1090/S0002-9947-1955-0068198-2.

Литература

C. D. Godsil, B. D. McKay. A new graph product and its spectrum // Bull. Austral. Math. Soc. — 1978. — Т. 18, вып. 1. — С. 21—28. — doi:10.1017/S0004972700007760.
Frank Harary. The number of linear, directed, rooted, and connected graphs // Transactions of the American Mathematical Society. — 1955. — Вып. 78. — С. 445—463. — doi:10.1090/S0002-9947-1955-0068198-2.

Внешние ссылки

Weisstein, Eric W. Rooted Graph (англ.) на сайте Wolfram MathWorld.

Для улучшения этой статьи желательно:

Проверить качество перевода с иностранного языка.

После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.

Read other articles:

Ello (jejaring sosial)

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Oktober 2022. ElloJenis situsJejaring sosialBahasaInggrisPenciptaPaul BudnitzSitus webwww.ello.coKomersialTidakDaftar akunDiperlukan untuk memposting, mengikuti, atau diikutiPengguna1 Juta +DiluncurkanMaret 2014 (2014-03)StatusAktif Portal InternetSunting ...

Alexander Löhr

Alexander LöhrLöhr tahun 1939Lahir(1885-05-20)20 Mei 1885Turnu-Severin, Mehedinți, Kerajaan RumaniaMeninggal26 Februari 1947(1947-02-26) (umur 61)Beograd, YugoslaviaPengabdian Austria-Hungaria (hingga 1918) Republik Austria Pertama (hingga 1938) Jerman NaziDinas/cabangAngkatan Darat Austria-HungariaAngkatan Bersenjata AustriaAngkatan Udara Austria (1927–38)Luftwaffe (1938–45)Lama dinas1906–45PangkatGeneraloberstKomandanLuftflotte 4Army Group EOB SüdostPerang...

Achmad Wibisono

Achmad Wibisono Asisten Perencanaan dan Anggaran KasalPetahanaMulai menjabat 21 Februari 2024 PendahuluEdwinPenggantiPetahanaPanglima Komando Armada IMasa jabatan17 Juli 2023 – 21 Februari 2024 PendahuluErwin S. AldedharmaPenggantiPetahanaKepala Staf Komando Gabungan Wilayah Pertahanan II ke-5Masa jabatan29 Maret 2023 – 17 Juli 2023 PendahuluAhmad Rizal RamdhaniPenggantiRudhi AviantaraKepala Staf Komando Gabungan Wilayah Pertahanan III ke-4Masa jabatan31 Janu...

American Airlines Penerbangan 965

artikel ini perlu dirapikan agar memenuhi standar Wikipedia. Tidak ada alasan yang diberikan. Silakan kembangkan artikel ini semampu Anda. Merapikan artikel dapat dilakukan dengan wikifikasi atau membagi artikel ke paragraf-paragraf. Jika sudah dirapikan, silakan hapus templat ini. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) American Airlines Flight 965Sebuah Boeing 757-223 yang mirip dengan pesawat yang terlibat kecelakaanRingkasan accidentTanggalDecember 20, 1995Ring...

Bahasa Punan Merah

PemberitahuanTemplat ini mendeteksi bahwa artikel bahasa ini masih belum dinilai kualitasnya oleh ProyekWiki Bahasa dan ProyekWiki terkait dengan subjek. Perhatian: untuk penilai, halaman pembicaraan artikel ini telah diisi sehingga penilaian akan berkonflik dengan isi sebelumnya. Harap salin kode dibawah ini sebelum menilai. {{PW Bahasa|importance=|class=}} Terjadi [[false positive]]? Silakan laporkan kesalahan ini. 05.51, Sabtu, 30 Maret, 2024 (UTC) • hapus singgahan Seban...

السيدة زينب (ريف دمشق)

السيدة زينب السيدة زينب ضريح السيدة زينب اللقب الست زينب الإحداثيات 33°26′50″N 36°20′10″E / 33.44722°N 36.33611°E / 33.44722; 36.33611 تقسيم إداري دولة سوريا محافظة محافظة ريف دمشق منطقة مركز ريف دمشق عدد السكان (احصاء 2004[1]) المجموع 136,427 معلومات أخرى منطقة زمنية ...

Flunitrazepam

Benzodiazepine sedative FlunitrazepamClinical dataPronunciation/ˌfluːnɪˈtræzɪpæm/ Trade namesRohypnolPregnancycategory AU: C AddictionliabilityModerateRoutes ofadministrationOralDrug classBenzodiazepineATC codeN05CD03 (WHO) Legal statusLegal status AU: S8 (Controlled drug) BR: Class B1 (Psychoactive drugs)[1] CA: Schedule I DE: Anlage III (Special prescription form required) UK: Class C US: Schedule IV (Schedule I trafficking pe...

Claire Keim

Claire KeimKeim di Festival Film Cannes 2014Lahir08 Juli 1975 (umur 48)Senlis, Oise, Picardy, PrancisPekerjaanAktris, penyanyiTahun aktif1994–sekarangPasanganBixente Lizarazu (2006-sekarang)Situs webhttp://www.clairekeim.fr/ Claire Keim (nee Claire Lefebvre lahir 8 Juli 1975) adalah seorang aktris dan penyanyi Perancis. Keim lahir di Senlis, Oise dari seorang arsitek dan dokter gigi.[1] Dia menjalin hubungan dengan pesepakbola Prancis Bixente Lizarazu, dan tinggal di Sain...

Transesterifikasi

Transesterifikasi: alkohol + ester → alkohol yang berbeda + ester yang berbeda. Dalam kimia organik, transesterifikasi (/ˌtrænzˌɛstərɪfɪˈkeɪʃən/) adalah proses pertukaran gugus organik R″ pada suatu ester dengan gugus organik R′ dari alkohol. Reaksi ini terkadang dikatalisis oleh penambahan katalis asam atau basa.[1] Reaksi ini juga dapat dicapai dengan bantuan enzim (biokatalis) terutama lipase (E.C.3.1.1.3).[2][3] Asam kuat mengkatalisis reaksi denga...

Lachin District

District of Azerbaijan 39°38′0″N 46°33′0″E / 39.63333°N 46.55000°E / 39.63333; 46.55000 District in East Zangezur, AzerbaijanLachin DistrictDistrictMap of Azerbaijan showing Lachin DistrictCountry AzerbaijanRegionEast ZangezurEstablished8 August 1930CapitalLachinSettlements[1]127Government • GovernorAgil NazarliArea • Total1,840 km2 (710 sq mi)Population (2020)[2] • Total78,600...

Telefe Internacional

Telefe InternacionalCaractéristiquesCréation 7 juin 1998Propriétaire TelefeParamount Networks Americas(Paramount Global)Slogan Siempre Juntos (Toujours ensemble)Langue EspagnolPays ArgentineStatut Généraliste internationale privéeSiège social Buenos AiresSite web http://www.telefeinternacional.com.ar/DiffusionSatellite Intelsat 34 (Amerique et Europe)modifier - modifier le code - modifier Wikidata Telefe Internacional est une chaîne de télévision argentine. Lancée le 7 juin 1998, e...

Pembantaian Babrra

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Februari 2023. Koordinat: 34°08′58″N 71°44′34″W / 34.1494°N 71.7428°W / 34.1494; -71.7428 Pembantaian Babrra terjadi pada 12 Agustus 1948 di Distrik Charsadda, Provinsi Frontier Barat Laut (sekarang Khyber Pukhtunkhwa), Pakistan, ...

Milan Puskar Stadium

American football stadium in West Virginia, US Mountaineer Field redirects here. For the original stadium bearing the name, see Mountaineer Field (1924). Mountaineer Field at Milan Puskar StadiumPanorama view inside of the stadium during a game in 2011Milan Puskar StadiumLocation in West VirginiaShow map of West VirginiaMilan Puskar StadiumLocation in the United StatesShow map of the United StatesFormer namesMountaineer Field (1980–2004)Location900 Willowdale RoadMorgantown, West Virginia 2...

18th Brigade (Australia)

Infantry brigade of the Australian Army during WWII 18th Brigade2/9th Battalion, part of the 18th Brigade, during the fighting at Shaggy Ridge, January 1944Active1939–1946Country AustraliaBranchAustralian ArmyTypeBrigadeSize~3,500 personnelPart of7th DivisionEngagementsSecond World War Siege of Tobruk Syria–Lebanon campaign New Guinea campaign Borneo campaign CommandersNotablecommandersLeslie MorsheadInsigniaHeadquarters unit colour patchMilitary unit The 18th Brigade was an inf...

Xerox Sigma 9

Xerox Sigma 9Living Computer Museum - Xerox Sigma 9DeveloperXeroxProduct familyXerox SigmaRelease date1970 Front of the Xerox Sigma 9. On display at the Living Computer Museum in Seattle, Washington. The Xerox Sigma 9, also known as the XDS Sigma 9, was a high-speed, general purpose computer. Xerox first became interested in office automation through computers in 1969 and purchased Scientific Data Systems or SDS. They then renamed the division Xerox Data Systems or XDS; they saw limited succe...

路易十四

此條目的语调或风格或許不合百科全書。 (2014年8月2日)請根據指南協助改善这篇条目，並在讨论页討論問題所在，加以改善。此條目可参照英語維基百科、日語維基百科和法語維基百科相應條目来扩充。 (2019年8月21日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明...

Peter Pace

Peter Pace Jenderal Peter Margaret Pace (lahir 5 November 1945) adalah Ketua Kepala Staf Gabungan yang sekarang dan Marinir AS pertama yang diangkat untuk jabatan ini. Dalam kapasitasnya ini ia menjabat sebagai perwira militer dengan kedudukan tertinggi di Amerika di bawah Presiden. Ia menjabat sebagai Wakil Ketua dari Kepala Staf Gabungan dari 1 Oktober 2001 hingga 12 Agustus 2005. Jenderal Pace adalah perwira ke-16, dan juga Marinir pertama, yang memegang posisi ini. Pada 30 September 2005,...

2008年夏季奥林匹克运动会匈牙利代表团

2008年夏季奥林匹克运动会匈牙利代表團匈牙利国旗IOC編碼HUNNOC匈牙利奧林匹克委員會網站olimpia.hu（匈牙利文）2008年夏季奥林匹克运动会（北京）2008年8月8日至8月24日運動員171參賽項目18个大项獎牌榜排名第20 金牌銀牌銅牌總計 3 6 2 11 历届奥林匹克运动会参赛记录（总结）夏季奥林匹克运动会18961900190419081912192019241928193219361948195219561960196419681972197619801984198819921996200020042008201...

Taro Daniel

Japanese tennis player This biography of a living person needs additional citations for verification. Please help by adding reliable sources. Contentious material about living persons that is unsourced or poorly sourced must be removed immediately from the article and its talk page, especially if potentially libelous.Find sources: Taro Daniel – news · newspapers · books · scholar · JSTOR (August 2014) (Learn how and when to remove this message) Taro Da...

Alysa Liu

American former figure skater Alysa LiuLiu at 2019 JGP United StatesBorn (2005-08-08) August 8, 2005 (age 18)Clovis, CaliforniaEducationUniversity of California, Los AngelesHeight158 cm (5 ft 2 in)Figure skating careerCountry United StatesDisciplineWomen's singlesCoachPhillip DiGuglielmo, Massimo ScaliSkating clubSt. Moritz ISCBegan skating2010Highest WS2nd (2021-2022)Medal record Event World Championships 0 0 1 World Junior Championships 0 0 1 Junior Grand Prix Final...

PROFILPELAJAR.COM