درخت (نظریه گراف)

در نظریهٔ گراف، درخت گرافی همبند و بدون دور است. درخت‌ها به‌طور گسترده در علوم رایانه و ساختار داده‌ها کاربرد دارند. مثل درخت‌های جستجوی دودویی، پشته‌ها[۱] درخت‌های هافمن[۲] برای فشرده‌سازی اطلاعات و غیره.

تعاریف

نمونه‌ای از یک درخت
در اینجا به دلیل وجود یک دور گراف درخت نمی‌باشد.

درخت یک گراف ساده بدون جهت است که در یکی ار شروط معادل زیر صدق کند:

  • G متصل است و دور ندارد.
  • G هیج مداری ندارد و اگر یک یال به آن اضافه شود یک مدار ساده در آن به وجود می‌آید.
  • G متصل است و اگر یک یال آن حذف شود دیگر متصل نیست.
  • هر دو رأس در G با یک مسیر سادهٔ یکتا به هم وصل می‌شوند.

اگر G تعداد متناهی رأس داشته باشد احکام بالا با شروط زیر نیز معادل اند:

  • G متصل است و n-1 یال دارد.
  • G مدار ساده ندارد و n-1 یال دارد.

گراف سادهٔ بدون جهت G را جنگل[۳] گوئیم اگر مسیر ساده نداشته باشد.

انواع درخت

  • یک درخت را ریشه‌دار[۵] گوییم اگر راسی داشته باشد که به ازای هر راس دیگر درخت، مسیری از آن به راس مذکور وجود داشته باشد. مرتبهٔ درخت[۶] یک مرتب‌سازی جزئی[۷] روی رئوس درخت است که اگر و فقط اگر یک مسیر یکتا از ریشه به v از u بگذرد. یک درخت که زیر گراف، گراف G است را درخت نرمال[۸] گوییم اگر انتهای هر یال G با این رتبه‌بندی قابل مقایسه باشد (Diestel 2005 ,p.15).

درخت ریشه‌دار یک ساختار داده کلیدی در علوم کامپیوتر است. در ضمن با توجه به این که فرض می‌شود درخت‌ها ریشه دارند یک درخت بدون ریشه را درخت آزاد[۹] گوییم.

  • درخت چندگانه[۱۰] درختی است که حداکثر یک مسیر بدون جهت بین هر دو رأسش دارد. یعنی درخت چندگانه یک گراف جهت دار بدون مدار است که مدار بدون جهت نیز ندارد.
  • درخت برچسب دار[۱۱] درختی است که در آن هر رأس برچسب یکتایی دارد. رئوس درختی با n رأس به‌طور نمونه با اعداد ۱و۲و۳و… وn برچسب گذاری می‌شوند. درخت بازگشتی[۱۲] یک درخت ریشه دار با برچسب است که برچسب رئوس باتوجه به مرتبهٔ درخت تعیین می‌شود. (اگر و u,v دو رأس درخت باشند برچسب u کوچکتر از برچسب v است)
  • درخت ساده نشدنی[۱۳] درختی است که رأسی با درجهٔ ۲ ندارد.
  • درخت مرتب[۱۴] درختی است که برای فرزندان هر رأس مرتبه‌ای تعیین شده باشد.
  • درخت n-تایی درختی است که هر رأس که برگ نیست حداکثر n فرزند دارد.

درخت نمایش داده شده در شکل بالا ۶ رأس، ۱–۶ = ۵ یال دارد. مسیر سادهٔ یکتا که رأس ۲ را به ۶ وصل می‌کند ۶-۵-۴-۲ است.

احکام

  • هر درخت یک گراف دو بخشی[۱۵] و یک گراف میانه[۱۶] است. هر درخت با تعداد شمارا رأس یک گراف مسطح است.
  • هر درخت با حداقل ۲ برگ (یا رأس با درجه ۱)دارد. حداقل تعداد برگ مربوط به گراف مسیر[۱۷] و حداکثر تعداد برگ (n-1) مربوط به گراف ستاره‌ای است.

کاربرد

خیابان‌ها و چهار راه‌ها:

تغییر نام خیابان‌ها و چهارراه‌ها ی عمومی یکی از سرگرمی‌های مطلوب انجمن‌های شهری در سراسر جهان است. فرض کنید مسئولین شهری بخواهند نسبت به نامگذاری خیابان‌های خود بسیار اصولی باشند. فرض کنید بخواهند هر خیابان به درازای یک بلوک و هم نام با یکی از چهارراه‌های دو انتهای خود باشد؛ پس به عنوان مثال، یکی از دو انتهای خیابان واشینگتن بایستی در چهار راه واشینگتن باشد. طبیعتاً می‌خواهیم مسئله خود را در زبان گراف‌ها در حالتی کلی عنوان کنیم. گراف همبندی داده شده‌است. تحت چه شرط‌هایی می‌توان به‌طور منحصربه‌فردی هر یال را با یکی از دو رأس انتهایی آن متناظر کرد؟ در ابتدا خاطر نشان می‌کنیم که اگر گرافمان درخت باشد، این امر ممکن است. برای این منظور به طریق زیر عمل می‌کنیم: پس از اینکه ریشه ای مانند a0 را در درختی مانند درخت شکل زیر

به دلخواه انتخاب کردیم، یال a1 a0 را متناظر با رأس a1 می‌گیریم، به همین ترتیب a0 a2 را متناظر با a2 و و a0 a3 را متناظر با a3، سپس a1 a11 را متناظر با a11 قرار می‌دهیم، و الی آخر؛ به‌طور کلی، هر یال را به انتهایی از آن که از a0 دور تر است، متناظر می‌کنیم. اکنون فرض کنید که گراف دارای مداری مثلاً c، باشد (شکل ۲) هر یال c باید متناظر با یکی از دو رأس انتهایی خود باشد، یعنی متناظر با رأسی از c. اگر به عنوان مثال یال a1 a2 متناظر با a2 باشد آنگاه یال a2 a3 بایستی متناظ با a3 باشد، و الی آخر؛ بنابراین هیچ یال نا متعلق به c نمی‌تواند با رأسی از c متناظر باشد. در نتیجه یالی مانند a1 b1 که در a1 مدار c را قطع می‌کند، بایستی با b1 متناظر باشد و یالی مانند b1 b2 با b2 و الی آخر.

چنان‌که ملاحظه می‌کنیم، قسمتی از گراف که به این ترتیب با عزیمت از a1 و حرکت در طول یال‌هایی مانند a1 b1 که با c در a1 مشترکند، پیموده می‌شود، بایستی درختی مانند T1 می‌توان هر یال را با انتهایی از آن که از a1 متناظرند، بنابراین از این تجزیه و تحلیل نتیجهٔ زیر به دست می‌آید: هر یال یک گراف همبند را می‌توان به‌طور منحصربه‌فردی با یکی از دو رأس آن یال متناظر کرد اگر و تنها اگر گراف نامبرده یک درخت باشد یا متشکل از مدار منحصربه‌فردی همراه با درخت‌هایی منشعب از رأس‌های آن مدار باشد (به شکل ۳ نگاه کنید)

بنا به قضیه (هر درخت با n رأس دارای n-1 یال است) تعداد رأس‌های یک درخت یکی بیش از تعداد یال‌های آن است . . تعداد یال‌های یک مدار یا مداری که درخت‌هایی از رأس‌های آن منشعب شده‌اند با تعداد رأس‌های آن مساوی است؛ بنابراین، در این موارد برقراری تناظری میان یال‌ها و رأس‌ها امکان دارد.

در ختی مانند درخت شکل (۱) یا گرافی مانند گراف شکل (۳)، فقط می‌توانند نقشهٔ خیابان‌های شهرهای خیلی کوچک باشند که فاقد بلوک‌های شهری واقعی اند، یا فقط یک بلوک مرکزی دارند که خیابان‌هایی از حومه به آن‌ها کشیده شده‌است. پس از اندکی تأمل دربارهٔ این موضوع، عضوهای انجمن شهر سرافرازانه متوجه این واقعیت می‌شوند که شهر آن‌ها بزرکتر از آن است که بتوان این روش را در آن به کار گرفت؛ بنابراین قرار می‌گذارند که به جای آن از قاعدهٔ زیر استفاده کنند: خیابان‌ها و چهارراه‌ها طوری نامگذاری شوند که در هر چهار راهی یکی از خیابان‌ها به نام همان چهارراه باشد؛ یعنی، به عنوان مثال، بایستی یکی از خیابان‌ها به نام همان چهار راه باشد؛ یعنی به عنوان مثال، بایستی یکی از خیابان‌های منتهی به چهارراه واشینگتن به نام واشینگتن باشد. به زبان نظریهٔ گراف‌ها، این کار به معنی متناظر کردن هر رأس با فقط یکی از یال‌های متصل به آن است. این کار در مواردی عملی نیست؛ به عنوان مثال همان‌طور که گفته شد، تعداد رأس‌های هر درخت از تعداد یال‌های آن یکی بیشتر است. گراف شکل (۱) را در نظر بگیرید. در این گراف می‌توان هر رأس را با یالی که از آن به سمت رأس a0 خارج می‌شود متناظر کرد. به این ترتیب، به جز ریشه، هر رأس با یالی متناظر می‌شود.

با توجه به حکم کلی زیر درخت‌ها از این نظر مستثنی هستند

رأس‌های گراف همبند غیر درخت را می‌توان با یال‌های متصل به آن‌ها متناظر کرد. اثبات:هر گرافی که n رأس را به هم متصل می‌کند دارای حداقل n-1 یال است و با حذف برخی از یال‌ها قابل تبدیل به درخت است. فرض کنید a0b0 = e0 یکی از یال‌هایی باشد که با حذف آن‌ها گراف ما به یک درخت، مثلاً T، تبدیل می‌شود. a0 را به عنوان ریشهٔ T انتخاب کنید. در T هر أس به جز a0 را می‌توان با یالی متصل به آن متناظر کرد؛ یال اضافی e0 از گراف را نیز می‌توان با a0 متناظر کرد. به این ترتیب هر رأس گراف با یالی متصل به آن متناظر شده‌است.

با توجه به بحث پیشین، توجه به این نکته مفید است که همیشه می‌توان در گراف، ر أس‌ها را با یال‌های متصل به آن‌ها، یا یال‌ها را با رأس‌های متصل به آن‌ها متناظر کرد. می‌توانیم هر دو کار را انجام دهیم، اگر و تنها اگر تعداد رأس‌ها و یال‌های گراف مساوی باشند. چنین گرافی نمی‌تواند درخت باشد و بنابراین، نتیجه می‌گیریم که بایستی مانند گراف شکل (۳) فقط دارای یک مدار c باشد. در واقع تناظری وجود دراد که دو سویی عمل می‌کند، یال‌ها را با رأس‌ها متناظر می‌کند، و رأس‌ها را با یال‌ها. کافی است یال‌های c را با رأس‌های c، و هر رأس غیر متعلق به c را با نزدیکترین یال متصل به آن نسبت به c متناظر کرد.

منابع

  • .Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4
  • Otter, Richard (1948), “The Number of Trees”, Annals of Mathematics, Second Series 49 (3): 583–599
  • . گراف وکاربردهای آن، نویسنده:ایستین ایر

پانویس

  1. Heaps
  2. Huffman trees
  3. forest
  4. Directed tree
  5. Rooted tree
  6. tree-order
  7. partial ordering
  8. Normal tree
  9. Free tree
  10. Polytree
  11. Labeled tree
  12. Recursive tree
  13. irreducible tree
  14. Ordered tree
  15. bipartite graph
  16. Median graph
  17. Path graph

Read other articles:

Biblical figure who died from touching the Ark of the Covenant For the pre-Islamic goddess, see Al-Uzza. Not to be confused with Uzziah. The Chastisement of Uzzah by James Tissot Baroque painting of the death of Uzzah by Giulio Quaglio the Younger in a medallion in Ljubljana Cathedral (1704) According to the Tanakh, עזה, Uzzah or Uzza, meaning Her Strength, was an Israelite whose death is associated with touching the Ark of the Covenant. The account of Uzzah appears in two places in script...

 

American football player (born 1982) American football player Charlie WhitehurstWhitehurst with the Tennessee Titans in 2014No. 6, 12, 15Position:QuarterbackPersonal informationBorn: (1982-08-06) August 6, 1982 (age 41)Green Bay, Wisconsin, U.S.Height:6 ft 5 in (1.96 m)Weight:226 lb (103 kg)Career informationHigh school:Chattahoochee(Johns Creek, Georgia)College:Clemson (2001–2005)NFL Draft:2006 / Round: 3 / Pick: 81Career history San Diego ...

 

اضغط هنا للاطلاع على كيفية قراءة التصنيف ثعبة   المرتبة التصنيفية جنس[1]  التصنيف العلمي  فوق النطاق  حيويات مملكة عليا  حقيقيات النوى مملكة  حيوان عويلم  ثنائيات التناظر مملكة فرعية  ثانويات الفم شعبة  حبليات شعيبة  فقاريات شعبة فرعية  أشباه...

Serbian insurance company Dunav osiguranjeOfficial logoNative nameДунав осигурањеTypeJoint-stock companyIndustryFinance and InsuranceFounded30 June 1963; 60 years ago (1963-06-30)HeadquartersMakedonska 4, Belgrade, SerbiaArea servedSerbiaKey peopleIvana Soković (CEO)ServicesNon-life insuranceLife insuranceRevenue €256.22 million (2020)[1]Net income €31.37 million (2020)[1]Total assets €553.60 million (202)[2]Total equity €147.45...

 

Prof. Dr.Seto MulyadiS.Psi., M.Si., Psikolog.Seto di acara Ini Talkshow pada tahun 2017LahirSeto Mulyadi28 Agustus 1951 (umur 72)Klaten, Jawa TengahKebangsaanIndonesiaNama lainKak Seto, Sang MentorPekerjaanPsikolog anakOrganisasiLembaga Perlindungan Anak Indonesia (LPAI)[1]Dikenal atasPencipta karakter Si KomoPendiri Homeschooling Kak SetoSuami/istriDevianaAnak Minuk Eka Putri Duta Sari Bimo Dwi Putra Utama Shelomita Kartika Putri Maharani Nindya Putri Catur Permatasari Prof...

 

1983 Egyptian filmThe BeggarDirected byAhmed Al-SabaawiWritten bySamir AbdelazimStarringAdel EmamRelease date1983Running time120 minutesCountryEgyptLanguageArabic The Beggar (Arabic: المتسول, translit. Al-Motasawel) is a 1983 Egyptian comedy film directed by Ahmed Al-Sabaawi and starring Adel Emam.[1] Plot Emam plays Hasanin, an uneducated man who leaves his small village to live with his uncle's family in the city. After having no luck keeping a job, he must return to his...

2004 Georgia Democratic presidential primary ← 2000 March 2, 2004 (2004-03-02) 2008 → ← CTMD →101 Democratic National Convention delegates (86 pledged, 15 unpledged)The number of pledged delegates received is determined by the popular vote   Candidate John Kerry John Edwards Al Sharpton Home state Massachusetts North Carolina New York Delegate count 46 41 0 Popular vote 293,225 259,361 39,123 Percentage 46.8% 41.4%...

 

Protein-coding gene in the species Homo sapiens CHRM5IdentifiersAliasesCHRM5, HM5, cholinergic receptor muscarinic 5External IDsOMIM: 118496 MGI: 109248 HomoloGene: 22697 GeneCards: CHRM5 Gene location (Human)Chr.Chromosome 15 (human)[1]Band15q14Start33,968,497 bp[1]End34,067,458 bp[1]Gene location (Mouse)Chr.Chromosome 2 (mouse)[2]Band2 E3|2 57.02 cMStart112,309,516 bp[2]End112,311,114 bp[2]RNA expression patternBgeeHumanMouse (ortholog)To...

 

Опис Цю фотографію було зроблено в рамках Вікіекспедиції Київ — Обухів — Гребінки. Копачівська сільська рада, Копачів, Обухівський район Джерело власна робота Час створення 24.07.2011 Автор зображення Amakuha Ліцензія див. нижче Увага: це зображення не може бути завантажене до ...

Shafa Asrama Hogwarts|Gryffindor Tiga Tokoh Sentral (Trio Emas) Harry Potter Ronald Weasley Hermione Granger Satu Angkatan Dengan Harry Clay Canicie anggota Laskar Dumbledore, Auror Neville Longbottom anggota Laskar Dumbledore, Guru Herbologi Hogwarts pada masa depan, suami Hannah Abbott Lavender Brown anggota Laskar Dumbledore, menghadiri pesta dansa Yule Ball bersama Seamus Finnigan, sempat menjadi pacar Ron Weasley di buku keenam Seamus Finnigan anggota Laskar Dumbledore Parvati Patil angg...

 

April 1896 poster for the Evening Telegraph The Philadelphia Evening Telegraph was a newspaper published in Philadelphia, Pennsylvania, from 1864 to 1918.[1] The paper was started on January 4, 1864, by James Barclay Harding and Charles Edward Warburton. Warburton served as publisher until 1896,[2] when he passed the newspaper and the publisher's job to Barclay Harding Warburton I. In 1911, Barclay Warburton sold the paper to Rodman Wanamaker,[3] who ran it until it cl...

 

1980 British filmLittle Lord FauntleroyDVD coverDirected byJack GoldWritten byFrances Hodgson Burnett (novel)Blanche Hanalis (teleplay)Produced byNorman RosemontStarringRick SchroderAlec GuinnessEric PorterColin BlakelyConnie BoothCinematographyArthur IbbetsonEdited byKeith PalmerMusic byAllyn FergusonRelease date December 1980 (1980-12) Running time103 minutesCountryUnited KingdomLanguageEnglish Little Lord Fauntleroy is a 1980 British family film directed by Jack Gold and starring...

This article is about the district. For its eponymous headquarters, see Faridkot, Punjab. District of Punjab in IndiaFaridkot districtDistrict of PunjabBrijendra College in FaridkotLocation in PunjabCountry IndiaStatePunjabHeadquartersFaridkotFounded byRaja MokalsiNamed forSheikh Fariduddin GanjshakarGovernment • Deputy CommissionerVineet Kumar, IASArea • Total1,458 km2 (563 sq mi)Elevation196 m (643 ft)Population (2011) • ...

 

Scottish jazz saxophonist, composer, and educator This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) A major contributor to this article appears to have a close connection with its subject. It may require cleanup to comply with Wikipedia's content policies, particularly neutral point of view. Please discuss further on the talk page. (November 2018) (Learn how and when to remove this template...

 

Elisabethenburg PalaceSchloss ElisabethenburgElisabethenburg PalaceShow map of ThuringiaElisabethenburg PalaceShow map of GermanyGeneral informationArchitectural styleoriginally Baroquesome later additionsTown or cityMeiningenCountryGermanyCoordinates50°34′12″N 10°24′47″E / 50.570°N 10.413°E / 50.570; 10.413Construction started1682Completed1692ClientBernhard I, Duke of Saxe-Meiningen Elisabethenburg Palace (German: Schloss Elisabethenburg) is a Baroque pala...

Japanese politician Takeshi Hayashida (林田 彪, Hayashida Takeshi, born 1944) is a Japanese politician of the Liberal Democratic Party (LDP) and a former member of the House of Representatives in the Diet (national legislature). A native of Nagasu, Kumamoto and graduate of Tokyo University of Agriculture and Technology he joined the Ministry of Construction in 1967. Leaving the ministry, he was elected to the House of Representatives for the first time in 1996. He represented the 2nd Distr...

 

British film critic (1929–1989) Leslie HalliwellBornRobert James Leslie Halliwell23 February 1929Bolton, Lancashire, EnglandDied21 January 1989(1989-01-21) (aged 59)Esher, Surrey, EnglandOccupation(s)Film critic, encyclopaedistYears active1952−1987 Robert James Leslie Halliwell[1] (23 February 1929 – 21 January 1989) was a British film critic, encyclopaedist and television rights buyer for ITV, the British commercial network, and Channel 4. He is best known for his ref...

 

Titeuf - Il filmManù, Titeuf e Hugo in una scena del filmTitolo originaleTiteuf, le film Paese di produzioneFrancia, Svizzera Anno2011 Durata87 min Genereanimazione, commedia, avventura RegiaPhilippe Chappuis SoggettoTiteuf di Philippe Chappuis SceneggiaturaPhilippe Chappuis Casa di produzioneMoonScoop, Pathé, France 3 Cinéma, RTS Distribuzione in italianoCloud Movie MusicheMoïse Albert, Thierry Blanchard, Nicolas Neidhardt, Philippe Chappuis Doppiatori originali Donald Reigno...

British Army officer and politician Brigadier-GeneralSir William Bromley-DavenportKCB CMG CBE DSO TD JP DLFinancial Secretary to the War OfficeIn office12 October 1903 – 4 December 1905MonarchEdward VIIPrime MinisterArthur BalfourPreceded byLord StanleySucceeded byThomas Buchanan Personal detailsBorn21 January 1862 (1862-01-21)Belgravia, LondonDied6 February 1949 (1949-02-07) (aged 87)Capesthorne Hall, Cheshire, EnglandNationalityBritishPoliti...

 

Véase también: Temporada 2021 del fútbol colombiano Liga Profesional Femenina 2021 Liga Femenina BetPlay Dimayor Datos generalesSede Colombia ColombiaCategoría Liga Profesional FemeninaFecha 10 de julio - 12 de septiembreTV oficial Win SportsWin Sports+PalmarésPrimero Deportivo CaliSegundo Santa FeDatos estadísticosParticipantes 11 equipos[1]​Partidos 56Goles 158 (2.68 por partido)Mayor anotadora Catalina Usme (12 goles) Cronología Liga Femenina 2020 Liga Profesional Femenin...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!