Cây (lý thuyết đồ thị)

Một cây có dán nhãn với 6 đỉnh và 5 cạnh

Cây là khái niệm quan trọng trong lý thuyết đồ thị, cấu trúc dữ liệugiải thuật. Cây là một đồ thị mà trong đó hai đỉnh bất kì đều được nối với nhau bằng đúng một đường đi. Nói cách khác, đồ thị liên thông bất kỳ không có chu trình là một cây. Rừnghợp (disjoint union) của các cây. Cây được sử dụng rộng rãi trong các cấu trúc dữ liệu của ngành khoa học máy tính như cây nhị phân, đống, trie, cây Huffman cho nén dữ liệu, v.v...

Cây tự do

Cây tự do là một đơn đồ thị, liên thông, không có chu trình.

Định lý sau cho biết các điều kiện tương đương với định nghĩa cây

Định lý - Các điều kiện cần và đủ để đồ thị là một cây

Cho đồ thị G=(V,E) có n đỉnh. Sáu mệnh đề sau là tương đương:

  1. G là một cây;
  2. G không có chu trình và có n-1 cạnh;
  3. G liên thông và có n-1 cạnh;
  4. G không có chu trình và nếu bổ sung vào một cạnh nối hai đỉnh không kề nhau thì xuất hiện một chu trình duy nhất;
  5. G liên thông và nếu bỏ đi một cạnh bất kỳ thì G mất tính liên thông;
  6. Mỗi cặp đỉnh trong G được nối với nhau bằng đường đi duy nhất.

Cây (có gốc)

Cây (có gốc) là cây trong đó có một đỉnh được chọn là gốc và mỗi cạnh được định hướng trùng với hướng đi của đường đi đơn duy nhất từ gốc tới mỗi đỉnh.

Trong một cây có gốc, nếu có một cạnh đi từ đỉnh x đến đỉnh y thì đỉnh x được gọi là cha của đỉnh y, y là con của x (xem đồ thị (toán học)).

Hai đỉnh cùng cha được gọi là đỉnh anh em, các đỉnh không có con tức nằm ngoài rìa cây được gọi là (đỉnh) hay đỉnh ngoài, các đỉnh còn lại gọi là đỉnh trong (kể cả đỉnh gốc).

Số cạnh trên đường đi từ gốc tới mỗi đỉnh được gọi là mức của đỉnh ấy.

Cây nhị phân và các biến thể của nó

Định nghĩa:

Cây mà mỗi đỉnh có không quá hai con được gọi là cây nhị phân (binary tree).

Biến thể: có 4 loại cơ bản

Về tên gọi tiếng Việt cho chúng: thực tế, các tài liệu Việt Nam không thống nhất cách gọi tên các cây, mỗi kiểu tài liệu lại ghi khác nhau, cách diễn giải định nghĩa cũng khác nhau,... nên chúng tôi khuyên bạn nên sử dụng tiếng Anh để gọi tên cây, trong bài này, tên của các cây được dịch theo giáo trình Toán học tổ hợp của Trường Đại học Khoa học Tự Nhiên - ĐHQG TP.HCM và định nghĩa cũng sẽ được ghi đơn giản nhất có thể

  • Cây nhị phân mà mỗi đỉnh chỉ có 0 hoặc 2 con được gọi là cây nhị phân đủ (full binary tree)
  • Cây nhị phân đầy đủ mà tất cả các lá có cùng một mức được gọi là cây nhị phân hoàn hảo (perfect binary tree).
  • Cây nhị phân mà từ mức 0 xuống mức h - 1cây nhị phân hoàn hảo, ở mức h thì các đỉnh được sắp từ trái sang phải được gọi là cây nhị phân hoàn thành (complete binary tree) (h là độ cao cây)
  • Cây nhị phân có mức lá là h hoặc h - 1 (h là độ cao cây) thì gọi là cây nhị phân cân bằng (hoặc cân đối).

Ứng dụng cây trong khoa học máy tính

Trong khoa học máy tính cây là một cấu trúc dữ liệu không tuyến tính.

Cấu trúc cây được ứng dụng trong các giải thuật tìm kiếm, giải thuật sắp xếp và nhiều bài toán khác

Cây dùng để biểu diễn bài toán quyết định (cây quyết định), biểu diễn quá trình tính toán các biểu thức đại số.

Các cây đặc biệt

Biểu diễn cây

Có thể biểu diễn cây bằng mảng hoặc bằng danh sách kề. Khi biểu diễn bằng danh sách kề, mọi cây có thể chuyển sang một cây nhị phân tương đương với nó.

Cây khung

Mọi đơn đồ thị liên thông G có ít nhất một đồ thị con là cây và chứa tất cả các đỉnh của G. Đồ thị con này được gọi là cây khung (hoặc cây bao trùm) của G (thuật ngữ cây khung được sử dụng phổ biến hơn). Đồ thị G có thể có nhiều cây khung. Nếu G có trọng số trên các cạnh thì cây khung có tổng trọng số trên các cạnh của nó là nhỏ nhất (hoặc lớn nhất) được gọi là cây khung nhỏ nhất (hoặc lớn nhất).

Định lý

  • Mọi đồ thị liên thông đều có chứa ít nhất một cây bao trùm.
  • Định lý Carley: Số cây khung của đồ thị

Các thuật toán tìm cây bao trùm

  • Thuật toán tìm cây bao trùm theo chiều rộng
  • Thuật toán tìm cây bao trùm theo chiều sâu
  • Thuật toán Prim
  • Thuật toán Kruskal

Các thuật toán khác

Xem thêm

Tham khảo

Read other articles:

I Married Adventure karya Osa Johnson Martin Elmer Johnson (9 Oktober 1884 – 13 Januari 1937) dan Osa Helen Johnson (née Leighty, 14 Maret 1894 – 7 Januari 1953) adalah sepasang pasutri asal Amerika Serikat yang menjadi petualang dan pembuat film dokumenter. Pada paruh pertama abad ke-20, pasutri tersebut membuat film-film dan buku-buku tentang petualangan di wilayah-wilayah eksotis. Daftar pustaka Johnson, Martin (1929). LION. New York - London: G.P. Putnam's...

 

42-й саміт G7 Тип саміт G7dКраїна  ЯпоніяРозташування Shima Kanko Hoteld 34°18′29″ пн. ш. 136°49′08″ сх. д. / 34.3083000000277778° пн. ш. 136.819000000027756414° сх. д. / 34.3083000000277778; 136.819000000027756414Координати: 34°18′29″ пн. ш. 136°49′08″ сх. д. / 34.3083000000277778° пн. ш....

 

Bagian belakang mesin CFM56 CFM International CFM56 adalah keluarga Prancis-Amerika Serikat dari mesin pesawat turbofan bypass tinggi yang dibuat oleh CFM International (CFMI), dengan kisaran daya dorong 18.500 hingga 34.000 lbf (82 hingga 150 kN). CFMI adalah 50-50 perusahaan milik bersama Safran Aircraft Engine (sebelumnya dikenal sebagai Snecma) dari Prancis, dan GE Aviation (GE) Amerika Serikat. Kedua perusahaan bertanggung jawab untuk memproduksi komponen dan masing-masing memi...

YanusRaja Yanus dan Ratu Charlotte di Katedral ChartresRaja SiprusBerkuasa9 September 1398 - 29 Juni 1432PendahuluJacques IPenerusJean IIInformasi pribadiKelahiran1375GenovaKematian29 Juni 1432NikosiaWangsaWangsa LusignanAyahJacques I dari SiprusIbuHelvis dari Brunswick-GrubenhagenPasanganAnglesia ViscontiCharlotte de BourbonAnakJean II dari SiprusAnne dari Siprus Yanus dari Siprus (1375 – 29 Juni 1432) merupakan seorang Raja dari Siprus dan tituler Raja Armenia Kilikia dan Yerusalem dari t...

 

Software feature removing online advertising in a web browser or application Adblock redirects here. For the extension by Eyeo GmbH, see Adblock Plus. For the extension by Michael Gundlach, see AdBlock. Part of a series onInternet marketing Search engine optimization Local search engine optimisation Social media marketing Email marketing Referral marketing Content marketing Native advertising Search engine marketing Pay-per-click Cost per impression Search analytics Web analytics Display adve...

 

Sampul Buku Pertempuran Terakhir Pertempuran Terakhir (The Last Battle) adalah buku ketujuh dan yang terakhir dari novel The Chronicles of Narnia, karya C. S. Lewis. Atas karya ini, C. S. Lewis mendapat penghargaan Carnegie Medal pada tahun 1956. Di dalam buku ini C. S. Lewis membawa cerita “The Chronicles of Narnia” sampai pada akhirnya. Buku ini bercerita tentang akhir zaman dari Narnia dan menyimpulkan cerita-cerita sebelumnya dengan pengalaman anak-anak manusia di Narnia dan di bumi. ...

Political party in Poland Szymon Hołownia's Poland 2050 Polska 2050 Szymona HołowniAbbreviationPL2050ChairmanSzymon Hołownia[1]Vice-ChairmanMichał KoboskoJacek Kozłowski [pl][1]FounderSzymon HołowniaFounded30 June 2020 (2020-06-30)Registered7 April 2021 (2021-04-07)Headquartersul. Warecka 8/67, 00-049 WarsawThink tankStrategy Institute 2050Youth wingGeneration 2050IdeologyChristian democracy[2][3]Environmentalism...

 

Dans ce nom chinois, le nom de famille, Zhang, précède le nom personnel. Pour les articles homonymes, voir Zhang. Cet article est une ébauche concernant un personnage de fiction. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Zhang HeBiographieNaissance 167Maozhou Town (en)Décès 231District de QinzhouPrénom social 儁乂Activité OfficierAutres informationsConflit Rébellion des Turbans jaunesmodifier...

 

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

本條目存在以下問題,請協助改善本條目或在討論頁針對議題發表看法。 此條目需要編修,以確保文法、用詞、语气、格式、標點等使用恰当。 (2013年8月6日)請按照校對指引,幫助编辑這個條目。(幫助、討論) 此條目剧情、虛構用語或人物介紹过长过细,需清理无关故事主轴的细节、用語和角色介紹。 (2020年10月6日)劇情、用語和人物介紹都只是用於了解故事主軸,輔助�...

 

HEC ParisMotoApprendre à oserMoto dalam bahasa InggrisTomorrow is our businessJenisGrandes école (awam)Didirikan1881Jumlah mahasiswa4,500LokasiParis, PerancisSitus webwww.hec.edu HEC Paris adalah sebuah sekolah bisnis Eropa yang memiliki kampus di Paris, Jouy-en-Josas dan Doha.[1] Sekolah ini didirikan pada tahun 1881. HEC berada di peringkat ke-2 di antara Sekolah-Sekolah Bisnis Eropa pada tahun 2015 menurut the Financial Times.[2] Untuk jurusan Executive MBA (Magister...

 

Legendary Spartan warrior For the character in the Iliad who had the patronymic Othryades, see Panthous. OthryadesOthryades depicted in an 1810 sculptureNative nameὈθρυάδης and ὈθρυάδαςAllegianceSpartaBattles/warsBattle of the 300 Champions Othryades (Ancient Greek: Ὀθρυάδης) and Othryadas (Ancient Greek: Ὀθρυάδας)[1] was the last surviving Spartan of the 300 Spartans selected to fight against 300 Argives in the Battle of the 300 Champions. Ashamed ...

معهد باريس للموسيقى   معلومات المؤسس برنارد ساريت  التأسيس 1795 الموقع الجغرافي إحداثيات 48°53′20″N 2°23′27″E / 48.888888888889°N 2.3908333333333°E / 48.888888888889; 2.3908333333333   المدينة باريس البلد  فرنسا إحصاءات عدد الطلاب 1339 (2020)[1]  عدد الموظفين 388 مدرس (2020)[1]180 administrative...

 

Mobil salju Russian snowmobile dengan kabin panas Mobil salju merupakan sebuah kendaraan yang digunakan di atas salju pada saat musim dingin tiba. Diciptakan oleh Joseph-Armand Bombardier dari Valcourt, Quebec. Mobil salju sekarang ini sudah menjadi bagian dari berbagai komunitas di Swedia, Greenland, dan Kanada. Mobil ini biasanya dikenal sebagai snowmachine di Alaska. Lihat pula Merek Alpina Snowmobiles Bombardier Polaris Industries Arctic Cat Yamaha Logan Machine Company Thiokol BRP Lynx P...

 

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

American non-profit association American Alliance of MuseumsAbbreviationAAMFounded1906Founded atWashington, D.C., U.S.TypeNon-profit associationTax ID no. 53-0205889[1]FocusMuseums, including professionals and volunteersLocation2451 Crystal Drive, Suite 1005, Arlington County, Virginia 22202Websiteaam-us.orgFormerly calledAmerican Association of MuseumsThe initial AAM headquarters in Washington, D.C.; it is now headquartered in Arlington County, Virginia The American Alliance of Museu...

 

Former theater in New York City For a later Park Theatre in Manhattan (aka Herald Square Theatre), see New Park Theatre. Park TheatreNew Theatre (1798-99)The theatre and surrounding neighborhood c. 1830.Address23 Park Row, New York, NYCoordinates40°42′41″N 74°00′27″W / 40.711512°N 74.007600°W / 40.711512; -74.007600Owner John Jacob Astor & John Beekman William B. Astor Sr. TypeBroadwayCapacity2,000Current useDemolishedConstructionOpenedJanuary 1798...

 

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (ديسمبر 2018) ← 1917 1916 1915 1918 في روسيا → 1919 1920 1921 عقود: طالع أيضاً:أحداث أخرى 1918تاريخ روسيا • جدول زمني • قائِمة فيما يلي �...

マルグリット・ド・フランスMarguerite de France サヴォイア公妃 在位 1559年 - 1574年別称号 ベリー女公出生 (1523-06-05) 1523年6月5日 フランス王国サン=ジェルマン=アン=レー死去 (1574-09-15) 1574年9月15日(51歳没) サヴォイア公国トリノ埋葬 フランス王国オートコンブ修道院結婚 1559年7月9日 フランス王国パリサン=ポール=デ=シャン教会配偶者 サヴォイア公エマヌエーレ�...

 

Questa voce o sezione sull'argomento biografie è priva o carente di note e riferimenti bibliografici puntuali. Sebbene vi siano una bibliografia e/o dei collegamenti esterni, manca la contestualizzazione delle fonti con note a piè di pagina o altri riferimenti precisi che indichino puntualmente la provenienza delle informazioni. Puoi migliorare questa voce citando le fonti più precisamente. Segui i suggerimenti del progetto di riferimento. Luigi Comencini Luigi Comencini (Salò, 8 gi...