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

درختان
درختان
	درختی برچسب دار با 6 رأس و 5 لبه.
رگه ها	v
لبه ها	v − 1
عدد کروماتیک	2 اگر v > 1
	جدول نمودارها و پارامترها

در تئوری گراف ، درخت یک گراف بدون جهت است که در آن هر دو راس دقیقاً توسط یک مسیر یا به طور معادل یک گراف غیر چرخه ای متصل به هم متصل می شوند . ^[1] جنگل یک گراف بدون جهت است که در آن هر دو رأس حداکثر توسط یک مسیر یا به طور معادل یک گراف بدون جهت غیر چرخه‌ای یا به طور معادل یک اتحاد ناپیوسته از درختان به هم متصل می‌شوند. ^[2]

یک polytree ^[3] (یا درخت جهت دار ^[4] یا درخت جهت دار ^[5]^[6] یا شبکه متصل منفرد ^[7] ) یک گراف غیر چرخه ای جهت دار (DAG) است که گراف غیر جهت دار زیرین آن یک درخت است. یک جنگل چندگانه (یا جنگل هدایت‌شده یا جنگل جهت‌دار ) یک گراف غیر چرخه‌ای جهت‌دار است که نمودار غیر جهت‌دار زیرین آن یک جنگل است.

انواع مختلفی از ساختارهای داده که در علم کامپیوتر به آنها درخت گفته می شود، گراف های زیرینی دارند که در تئوری گراف درختی هستند، اگرچه چنین ساختارهای داده ای عموماً درختان ریشه دار هستند . یک درخت ریشه دار ممکن است جهت دهی شود، که درخت ریشه دار نامیده می شود ، ^[8]^[9] یا تمام لبه های آن را از ریشه دور کند - در این صورت درختکاری ^[4]^[10] یا بیرون درخت ^{[11 ] نامیده می شود.}^]^[12] - یا اینکه تمام لبه های آن به سمت ریشه باشد - در این صورت به آن ضد درختکاری ^[13] یا درون درخت می گویند.. ^[11]^[14] خود درخت ریشه دار توسط برخی نویسندگان به عنوان یک نمودار جهت دار تعریف شده است. ^[15]^[16]^[17] یک جنگل ریشه دار ، پیوندی ناپیوسته از درختان ریشه دار است. یک جنگل ریشه دار ممکن است جهت دهی شود، به نام جنگل ریشه دار ، که یا تمام لبه های آن را به سمت ریشه در هر درخت ریشه دار قرار می دهد - در این صورت به آن جنگل منشعب یا خارج از جنگل می گویند - یا تمام لبه های آن را به سمت ریشه می گویند. در هر درخت ریشه دار - در این صورت آن را ضد انشعاب یا درون جنگل می نامند .

اصطلاح درخت در سال 1857 توسط ریاضیدان بریتانیایی آرتور کیلی ابداع شد . ^[18]

تعاریف

درخت

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

G متصل و غیر حلقوی (شامل هیچ چرخه ای نیست).
G غیر چرخه ای است و اگر لبه ای به G اضافه شود یک چرخه ساده تشکیل می شود .
G متصل است، اما اگر یک لبه از G حذف شود، قطع می شود .
G متصل است و نمودار کامل 3 رأس K ₃جزئی از G نیست .
هر دو راس در G را می توان با یک مسیر ساده منحصر به فرد به هم متصل کرد .

اگر G دارای تعداد محدودی از رئوس باشد، n عدد از آنها را بگوییم، عبارات فوق نیز معادل هر یک از شرایط زیر هستند:

G متصل است و n − 1 لبه دارد.
G متصل است و هر زیرگراف G شامل حداقل یک راس با یال های صفر یا یک می باشد . (یعنی G متصل است و 1-دژنره می شود .)
G چرخه ساده ای ندارد و n − 1 یال دارد.

مانند جاهای دیگر در تئوری گراف، گراف مرتبه صفر (گراف بدون رئوس) به طور کلی درخت در نظر گرفته نمی شود: در حالی که به صورت خلاء به عنوان یک گراف متصل است (هر دو راس را می توان با یک مسیر به هم متصل کرد)، 0 نیست. -connected (یا حتی (-1)-connected) در توپولوژی جبری، بر خلاف درختان غیر خالی، و رابطه "یک راس بیشتر از یال ها" را نقض می کند. با این حال، ممکن است به عنوان یک جنگل متشکل از درختان صفر در نظر گرفته شود.

یک راس داخلی (یا راس داخلی یا راس شاخه ) یک راس با درجه حداقل 2 است. به طور مشابه، یک راس خارجی (یا راس بیرونی ، راس انتهایی یا برگ ) یک راس درجه 1 است.

درخت تقلیل‌ناپذیر (یا درخت کاهش‌یافته سری ) درختی است که در آن راس درجه ۲ وجود ندارد (شمرده‌شده در دنباله A000014 در OEIS ). ^[19]

جنگل

جنگل یک گراف بدون جهت است که در آن هر دو رأس حداکثر با یک مسیر به هم متصل می شوند. به طور معادل، جنگل یک گراف غیر چرخه ای بدون جهت است که همه اجزای متصل آن درخت هستند. به عبارت دیگر، نمودار از یک اتحادیه جدا از درختان تشکیل شده است. به عنوان موارد خاص، نمودار مرتبه صفر (جنگلی متشکل از درختان صفر)، یک درخت تک، و یک نمودار بدون لبه، نمونه‌هایی از جنگل‌ها هستند. از آنجایی که برای هر درخت V − E = 1 ، به راحتی می‌توانیم تعداد درخت‌هایی را که در یک جنگل قرار دارند، با کم کردن تفاوت بین رئوس کل و کل یال‌ها بشماریم. TV - TE = تعداد درختان در یک جنگل .

Polytree

یک polytree ^[3] (یا درخت جهت دار ^[4] یا درخت جهت دار ^[5]^[6] یا شبکه متصل منفرد ^[7] ) یک گراف غیر چرخه ای جهت دار (DAG) است که گراف غیر جهت دار زیرین آن یک درخت است. به عبارت دیگر، اگر لبه های جهت دار آن را با یال های غیر جهت دار جایگزین کنیم، نموداری بدون جهت به دست می آوریم که هم متصل و هم غیر چرخه ای است.

برخی از نویسندگان ^{[ چه کسی؟ ]} عبارت "درخت جهت دار" را به مواردی محدود کنید که لبه ها همه به سمت یک راس خاص هدایت شوند یا همه از یک راس خاص دور شوند (به درختکاری مراجعه کنید ).

چند جنگلی

یک جنگل چندگانه (یا جنگل هدایت‌شده یا جنگل جهت‌دار ) یک گراف غیر چرخه‌ای جهت‌دار است که نمودار غیر جهت‌دار زیرین آن یک جنگل است. به عبارت دیگر، اگر یال های جهت دار آن را با یال های غیر جهت دار جایگزین کنیم، نموداری بدون جهت به دست می آوریم که غیر چرخه ای است.

برخی از نویسندگان ^{[ چه کسی؟ ]} عبارت «جنگل هدایت‌شده» را به مواردی محدود می‌کند که لبه‌های هر جزء متصل همگی به سمت یک راس خاص یا همه به دور از یک راس خاص هدایت می‌شوند (به شاخه‌بندی مراجعه کنید ).

درخت ریشه دار

درخت ریشه دار درختی است که یک رأس آن ریشه تعیین شده باشد. ^[20] لبه های یک درخت ریشه دار را می توان یک جهت طبیعی، به دور یا به سمت ریشه، اختصاص داد، در این صورت ساختار به درخت ریشه دار جهت دار تبدیل می شود . هنگامی که یک درخت ریشه دار جهت گیری دور از ریشه داشته باشد، درخت درختی ^[4] یا بیرون درخت نامیده می شود . ^[11] هنگامی که جهت گیری به سمت ریشه داشته باشد، آن را ضد درختکاری یا درون درختی می نامند . ^[11] مرتبه درختی استترتیب جزئی در رئوس درخت با u < v اگر و فقط اگر مسیر منحصر به فرد ریشه به v از u عبور کند . درخت ریشه دار T که زیرگرافی از گراف G است یک درخت معمولی است اگر انتهای هر مسیر T در G در این ردیف درختی قابل مقایسه باشد ( Diestel 2005 , p. 15). درختان ریشه دار، اغلب با ساختار اضافی مانند ترتیب همسایگان در هر رأس، یک ساختار داده کلیدی در علوم کامپیوتر هستند. ساختار داده درختی را ببینید .

در شرایطی که درختان معمولاً ریشه دارند، درختی که هیچ ریشه مشخصی ندارد، درخت آزاد نامیده می شود .

درخت برچسب دار درختی است که در آن به هر رأس یک برچسب منحصر به فرد داده می شود. رئوس یک درخت برچسب دار روی n راس معمولاً برچسب های 1، 2، ...، n داده می شود. درخت بازگشتی یک درخت ریشه دار برچسب دار است که در آن برچسب های راس به ترتیب درخت احترام می گذارند (به عنوان مثال، اگر u < v برای دو راس u و v ، پس برچسب u کوچکتر از برچسب v است).

در یک درخت ریشه دار، والد یک راس v ، راس متصل به v در مسیر ریشه است. هر راس یک والد منحصر به فرد دارد به جز ریشه ای که والد ندارد. ^[20] فرزند یک راس v رأسی است که v والد آن است. ^[20] صعودی یک رأس v هر راسی است که یا والد v باشد یا (به صورت بازگشتی) صعودی از والد v باشد. نواده یک راس v هر رأسی است که یا فرزند v باشدیا (به صورت بازگشتی) از نوادگان هر یک از فرزندان v است. خواهر و برادر به رأس v هر رأس دیگری روی درخت است که والد یکسانی با v دارد. ^[20] برگ یک رأس بدون فرزند است. ^[20] رأس داخلی، رأسی است که برگ نباشد. ^[20]

ارتفاع یک راس در یک درخت ریشه دار طول طولانی ترین مسیر رو به پایین تا یک برگ از آن راس است . ارتفاع درخت ، ارتفاع ریشه است. عمق یک راس طول مسیر تا ریشه آن ( مسیر ریشه ) است . این معمولاً در دستکاری درختان مختلف خود متعادل کننده، به ویژه درختان AVL مورد نیاز است. عمق ریشه صفر، ارتفاع برگ ها صفر، و درختی که فقط یک راس دارد (از این رو هم ریشه و هم برگ) عمق و ارتفاع آن صفر است. به طور معمول، یک درخت خالی (درختی بدون رئوس، در صورت مجاز بودن) دارای عمق و ارتفاع -1 است.

درخت k-ary درختی ریشه دار است که هر رأس آن حداکثر k فرزند دارد. ^[21] درختان 2 تایی اغلب درختان دوتایی نامیده می شوند ، در حالی که درختان 3 تایی گاهی اوقات درختان سه تایی نامیده می شوند .

درخت سفارش داده شده

درخت مرتب شده (یا درخت چنار ) درختی ریشه دار است که در آن ترتیبی برای فرزندان هر رأس مشخص شده است. ^[20]^[22] این درخت چنار نامیده می شود زیرا ترتیب فرزندان معادل جاسازی درخت در صفحه است، به طوری که ریشه در بالا و فرزندان هر رأس پایین تر از آن راس است. با توجه به تعبیه یک درخت ریشه دار در هواپیما، اگر یک جهت بچه ها را مشخص کند، بگویید از چپ به راست، آنگاه تعبیه ترتیبی از بچه ها را می دهد. برعکس، با توجه به درخت مرتب شده، و رسم معمول ریشه در بالا، رئوس فرزند در یک درخت مرتب شده را می توان از چپ به راست ترسیم کرد، که اساساً یک جاسازی مسطح منحصر به فرد ایجاد می کند.

خواص

هر درخت یک نمودار دو بخشی است . یک گراف دو قسمتی است اگر و فقط در صورتی که فاقد چرخه هایی با طول فرد باشد. از آنجایی که یک درخت اصلاً چرخه ای ندارد، دو بخشی است.
هر درخت یک نمودار میانه است.
هر درختی که فقط رئوس آن قابل شمارش است یک نمودار مسطح است.
هر گراف متصل G یک درخت پوشا را می پذیرد که درختی است که هر رأس G را در بر می گیرد و یال های آن یال های G هستند.
هر گراف متصلی که فقط تعداد رئوس آن قابل شمارش است، یک درخت پوشا معمولی را می پذیرد ( Diestel 2005 ، Prop. 8.2.4).
نمودارهای متصل با رئوس غیرقابل شمارش وجود دارد که درخت پوشا معمولی را نمی پذیرد ( Diestel 2005 ، Prop. 8.5.2).
هر درخت متناهی با n راس، با n > 1 ، حداقل دو راس انتهایی (برگ) دارد. این حداقل تعداد برگ مشخصه نمودارهای مسیر است . حداکثر عدد، n - 1 ، تنها با نمودارهای ستاره ای به دست می آید . تعداد برگها حداقل حداکثر درجه راس است.
برای هر سه راس در یک درخت، سه مسیر بین آنها دقیقاً یک راس مشترک دارند (این راس را میانه این سه راس می نامند).
هر درخت دارای مرکزی است که از یک راس یا دو راس مجاور تشکیل شده است. مرکز، راس میانی یا دو راس میانی در طولانی‌ترین مسیر است. به طور مشابه، هر درخت n- راس دارای یک مرکز متشکل از یک راس یا دو راس مجاور است. در حالت اول، حذف راس درخت را به زیردرخت هایی با کمتر از n /2 راس تقسیم می کند. در حالت دوم، حذف لبه بین دو راس مرکز، درخت را به دو درخت فرعی با n /2 رأس تقسیم می‌کند.

شمارش

درختان دارای برچسب

فرمول Cayley بیان می کند که n ^{n- 2} درخت روی n راس برچسب دار وجود دارد. یک اثبات کلاسیک از دنباله‌های Prüfer استفاده می‌کند که طبیعتاً نتیجه قوی‌تری را نشان می‌دهد: تعداد درخت‌هایی با رئوس 1، 2، ...، n درجه d ₁ ، d ₂ ، ...، d _n به ترتیب ضریب چندجمله‌ای است .

{n-2 \choose d_{1}-1,d_{2}-1,\ldots,d_{n}-1}.

یک مشکل کلی تر، شمارش درختان پوشا در یک گراف بدون جهت است که با قضیه درخت ماتریس به آن پرداخته می شود . (فرمول کیلی حالت خاص پوشاندن درختان در یک نمودار کامل است.) مشکل مشابه شمارش همه زیردرخت ها بدون توجه به اندازه، در حالت کلی #P-complete است ( جروم (1994) ).

درختان بدون برچسب

شمارش تعداد درختان آزاد بدون برچسب مشکل سخت تری است. هیچ فرمول بسته ای برای عدد t ( n ) درختان با n رأس تا ایزومورفیسم گراف شناخته شده نیست. چند مقدار اول t ( n ) هستند

1، 1، 1، 1، 2، 3، 6، 11، 23، 47، 106، 235، 551، 1301، 3159، ... (توالی A000055 در OEIS ).

اوتر (1948) تخمین مجانبی را ثابت کرد

t(n)\sim C\alpha ^{n}n^{-5/2}\quad {\text{as }}n\to \infty ,

با مقادیر C و α که به ترتیب تقریباً 0.534949606... و 2.95576528565... شناخته شده است (توالی A051491 در OEIS ). (در اینجا، f ~ g به این معنی است که lim _n→∞ f / g = 1. ) این نتیجه تخمین مجانبی او برای تعداد r ( n ) درختان ریشه دار بدون برچسب با n راس است:

r(n)\sim D\alpha ^{n}n^{-3/2}\quad {\text{as }}n\to \infty ,

با D در حدود 0.43992401257... و همان α در بالا (ر.ک. Knuth (1997) ، فصل 2.3.4.4 و Flajolet & Sedgewick (2009) ، فصل VII.5، ص 475).

چند مقدار اول r ( n ) ^{[23] است.}

1، 1، 2، 4، 9، 20، 48، 115، 286، 719، 1842، 4766، 12486، 32973، ... (توالی A000081 در OEIS )

انواع درختان

یک گراف مسیر (یا نمودار خطی ) از n راس تشکیل شده است که در یک خط مرتب شده اند، به طوری که راس i و i +1 توسط یک یال برای i =1،...، n -1 به هم متصل می شوند.
یک درخت ستاره مانند از یک راس مرکزی به نام ریشه و چندین نمودار مسیر متصل به آن تشکیل شده است. به طور رسمی تر، اگر درختی دقیقاً یک راس درجه بزرگتر از 2 داشته باشد ستاره مانند است.
درخت ستاره درختی است که از یک راس داخلی (و n -1 برگ) تشکیل شده است. به عبارت دیگر، درخت ستاره ای از مرتبه n ، درختی از مرتبه n با بیشترین تعداد برگ ممکن است.
درخت کاترپیلار درختی است که در آن همه رئوس در فاصله 1 زیرگراف مسیر مرکزی قرار دارند.
درخت خرچنگ درختی است که در آن تمام رئوس در فاصله 2 زیرگراف مسیر مرکزی قرار دارند.
یک درخت منظم با درجه d درخت نامتناهی با d یال در هر رأس است. اینها به عنوان نمودارهای Cayley از گروههای آزاد و در تئوری ساختمانهای Tits بوجود می آیند .

همچنین ببینید

یادداشت ها

^ بندر و ویلیامسون 2010 ، ص. 171.
^ بندر و ویلیامسون 2010 ، ص. 172.
^ ^a ^b داسگوپتا (1999) را ببینید .
^ ^a ^b ^c ^d Deo 1974 , p. 206.
^ ^a ^b رجوع کنید به هری و سامنر (1980) .
^ ^a ^b به سیمیون (1991) مراجعه کنید .
کیم ^و ^{مروارید} (1983) را ببینید .
↑ استانلی گیل ویلیامسون (1985). ترکیبیات برای علوم کامپیوتر . انتشارات پیک دوور. پ. 288. شابک 978-0-486-42076-9.
↑ مهران مصباحی; مگنوس اگرستد (2010). روش‌های نظری نمودار در شبکه‌های چند عاملی . انتشارات دانشگاه پرینستون پ. 38. شابک 978-1-4008-3535-5.
^ Ding-Zhu Du; Ker-I Ko; Xiaodong Hu (2011). طراحی و تحلیل الگوریتم های تقریب . Springer Science & Business Media. پ. 108. شابک 978-1-4614-1701-9.
^ ^a ^b ^c ^d Deo 1974 , p. 207.
^ جاناتان ال. گراس; جی یلن؛ پینگ ژانگ (2013). کتاب تئوری گراف، ویرایش دوم . مطبوعات CRC. پ. 116. شابک 978-1-4398-8018-0.
^ برنهارد کورته ; ینس ویگن (2012). بهینه سازی ترکیبی: نظریه و الگوریتم ها (ویرایش پنجم). Springer Science & Business Media. پ. 28. شابک 978-3-642-24488-9.
^ کورت مهلهورن ; پیتر سندرز (2008). الگوریتم ها و ساختارهای داده: جعبه ابزار اصلی (PDF) . Springer Science & Business Media. پ. 52. شابک 978-3-540-77978-0.
↑ دیوید مکینسون (2012). مجموعه ها، منطق و ریاضیات برای محاسبات . Springer Science & Business Media. صص 167-168. شابک 978-1-4471-2499-3.
↑ کنت روزن (2011). ریاضیات گسسته و کاربردهای آن، ویرایش هفتم . علم مک گراو-هیل. پ. 747. شابک 978-0-07-338309-5.
↑ الکساندر شریور (2003). بهینه سازی ترکیبی: چندوجهی و کارایی . اسپرینگر. پ. 34. شابک 3-540-44389-4.
↑ کیلی (1857) "درباره نظریه اشکال تحلیلی به نام درخت"، مجله فلسفی ، سری چهارم، 13 : 172-176.
اما لازم به ذکر است که در سال 1847، KGC von Staudt ، در کتاب خود Geometrie der Lage (Nürnberg, (آلمان): Bauer und Raspe, 1847)، اثباتی از قضیه چندوجهی اویلر ارائه کرد که بر درختان در صفحات 20-21 متکی است . همچنین در سال 1847، فیزیکدان آلمانی گوستاو کیرشهوفمدارهای الکتریکی را بررسی کرد و رابطه ای بین تعداد (n) سیم/مقاومت (شاخه)، تعداد (m) اتصالات (راس) و تعداد (μ) حلقه ها (چهره ها) در مدار پیدا کرد. او این رابطه را از طریق استدلالی با تکیه بر درختان اثبات کرد. رجوع کنید به: Kirchhoff, GR (1847) "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird" (درباره حل معادلاتی که با بررسی توزیع خطی جریانوانی به آنها هدایت می شود. ), Annalen der Physik und Chemie , 72 (12): 497–508.
↑ هری و پرینس 1959 ، ص. 150.
^ ^a ^b ^c ^d ^e ^f ^g Bender & Williamson 2010 , p. 173.
↑ Black, Paul E. (4 مه 2007) را ببینید . "درخت k-ary" . موسسه ملی استاندارد و فناوری ایالات متحده . بازبینی شده در 8 فوریه 2015 .
↑ استانلی، ریچارد پی (2012)، ترکیبات شمارشی، جلد. I , Cambridge Studies in Advanced Mathematics, vol. 49، انتشارات دانشگاه کمبریج، ص. 573، شابک 9781107015425
لی (1996) را ببینید.

منابع

بندر، ادوارد آ. ویلیامسون، اس. گیل (2010)، فهرست ها، تصمیمات و نمودارها. با مقدمه ای بر احتمال
داسگوپتا، سانجوی (1999)، "یادگیری چند درختان"، در Proc. پانزدهمین کنفرانس عدم قطعیت در هوش مصنوعی (UAI 1999)، استکهلم، سوئد، ژوئیه تا آگوست 1999 (PDF) ، صفحات 134-141.
دیو، نارسینگ (1974)، نظریه گراف با کاربرد در مهندسی و علوم کامپیوتر (PDF) ، انگلوود، نیوجرسی: پرنتیس هال، شابک 0-13-363473-6
هری، فرانک ؛ پرینس، گیرت (1959)، "تعداد درختان همومورف غیر قابل تقلیل، و گونه های دیگر" ، Acta Mathematica ، 101 (1-2): 141-162، doi : 10.1007/BF02559543 ، ISSN 0001-596
هری، فرانک ؛ سامنر، دیوید (1980)، "عدد دو رنگی یک درخت جهت دار"، مجله ترکیبیات، علوم اطلاعات و سیستم ، 5 (3): 184-187، MR 0603363.
کیم، جین اچ. پرل، جودیا (1983)، "یک مدل محاسباتی برای استدلال علی و تشخیصی در موتورهای استنتاج"، در Proc. هشتمین کنفرانس بین المللی مشترک هوش مصنوعی (IJCAI 1983)، کارلسروهه، آلمان، آگوست 1983 (PDF) ، صفحات 190-193.
لی، گنگ (1996)، "نسل درختان ریشه دار و درختان آزاد"، پایان نامه کارشناسی ارشد، گروه علوم کامپیوتر، دانشگاه ویکتوریا، BC، کانادا (PDF) ، ص. 9.
سیمیون، رودیکا (1991)، "درختانی با 1-عامل و درختان جهت دار"، ریاضیات گسسته ، 88 (1): 93-104، doi : 10.1016/0012-365X(91)90061-6 ، MR 109927.

ادامه مطلب

دیستل، راینهارد (2005)، نظریه گراف (ویرایش سوم)، برلین، نیویورک: Springer-Verlag، ISBN 978-3-540-26183-4.
فلاژولت، فیلیپ؛ Sedgewick، Robert (2009)، ترکیبات تحلیلی ، انتشارات دانشگاه کمبریج، ISBN 978-0-521-89806-5
"درخت" ، دایره المعارف ریاضیات ، انتشارات EMS ، 2001 [1994]
کنوت، دونالد ای. (14 نوامبر 1997)، هنر برنامه نویسی کامپیوتر جلد 1: الگوریتم های بنیادی (ویرایش سوم)، ادیسون-وسلی حرفه ای
جروم، مارک (1994)، "شمارش درختان در نمودار #P-کامل است"، نامه‌های پردازش اطلاعات ، 51 (3): 111–116، doi : 10.1016/00085-0190(94)00085-9 ، ISSN 0020- 0190.
اوتر، ریچارد (1948)، "تعداد درختان"، سالنامه ریاضیات ، سری دوم، 49 (3): 583–599، doi : 10.2307/1969046 ، JSTOR 1969046.

[FOOTNOTEBenderWilliamson2010171-1] بندر و ویلیامسون 2010 ، ص. 171.

[FOOTNOTEBenderWilliamson2010172-2] بندر و ویلیامسون 2010 ، ص. 172.

[d99-3] داسگوپتا (1999) را ببینید .

[FOOTNOTEDeo1974206-4] Deo 1974 , p. 206.

[Harary_1980-5] رجوع کنید به هری و سامنر (1980) .

[s91-6] به سیمیون (1991) مراجعه کنید .

[kp83-7] کیم ^و ^{مروارید} (1983) را ببینید .

[Williamson1985-8] استانلی گیل ویلیامسون (1985). ترکیبیات برای علوم کامپیوتر . انتشارات پیک دوور. پ. 288. شابک 978-0-486-42076-9.

[multi-9] مهران مصباحی; مگنوس اگرستد (2010). روش‌های نظری نمودار در شبکه‌های چند عاملی . انتشارات دانشگاه پرینستون پ. 38. شابک 978-1-4008-3535-5.

[DuKo2011-10] Ding-Zhu Du; Ker-I Ko; Xiaodong Hu (2011). طراحی و تحلیل الگوریتم های تقریب . Springer Science & Business Media. پ. 108. شابک 978-1-4614-1701-9.

[FOOTNOTEDeo1974207-11] Deo 1974 , p. 207.

[GrossYellen2013-12] جاناتان ال. گراس; جی یلن؛ پینگ ژانگ (2013). کتاب تئوری گراف، ویرایش دوم . مطبوعات CRC. پ. 116. شابک 978-1-4398-8018-0.

[KorteVygen2012b-13] برنهارد کورته ; ینس ویگن (2012). بهینه سازی ترکیبی: نظریه و الگوریتم ها (ویرایش پنجم). Springer Science & Business Media. پ. 28. شابک 978-3-642-24488-9.

[MehlhornSanders2008-14] کورت مهلهورن ; پیتر سندرز (2008). الگوریتم ها و ساختارهای داده: جعبه ابزار اصلی (PDF) . Springer Science & Business Media. پ. 52. شابک 978-3-540-77978-0.

[Makinson2012-15] دیوید مکینسون (2012). مجموعه ها، منطق و ریاضیات برای محاسبات . Springer Science & Business Media. صص 167-168. شابک 978-1-4471-2499-3.

[16] کنت روزن (2011). ریاضیات گسسته و کاربردهای آن، ویرایش هفتم . علم مک گراو-هیل. پ. 747. شابک 978-0-07-338309-5.

[Schrijver2003-17] الکساندر شریور (2003). بهینه سازی ترکیبی: چندوجهی و کارایی . اسپرینگر. پ. 34. شابک 3-540-44389-4.

[18] کیلی (1857) "درباره نظریه اشکال تحلیلی به نام درخت"، مجله فلسفی ، سری چهارم، 13 : 172-176.
اما لازم به ذکر است که در سال 1847، KGC von Staudt ، در کتاب خود Geometrie der Lage (Nürnberg, (آلمان): Bauer und Raspe, 1847)، اثباتی از قضیه چندوجهی اویلر ارائه کرد که بر درختان در صفحات 20-21 متکی است . همچنین در سال 1847، فیزیکدان آلمانی گوستاو کیرشهوفمدارهای الکتریکی را بررسی کرد و رابطه ای بین تعداد (n) سیم/مقاومت (شاخه)، تعداد (m) اتصالات (راس) و تعداد (μ) حلقه ها (چهره ها) در مدار پیدا کرد. او این رابطه را از طریق استدلالی با تکیه بر درختان اثبات کرد. رجوع کنید به: Kirchhoff, GR (1847) "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird" (درباره حل معادلاتی که با بررسی توزیع خطی جریانوانی به آنها هدایت می شود. ), Annalen der Physik und Chemie , 72 (12): 497–508.

[FOOTNOTEHararyPrins1959150-19] هری و پرینس 1959 ، ص. 150.

[FOOTNOTEBenderWilliamson2010173-20] ^ ^a ^b ^c ^d ^e ^f ^g Bender & Williamson 2010 , p. 173.

[21] Black, Paul E. (4 مه 2007) را ببینید . "درخت k-ary" . موسسه ملی استاندارد و فناوری ایالات متحده . بازبینی شده در 8 فوریه 2015 .

[22] استانلی، ریچارد پی (2012)، ترکیبات شمارشی، جلد. I , Cambridge Studies in Advanced Mathematics, vol. 49، انتشارات دانشگاه کمبریج، ص. 573، شابک 9781107015425

[23] لی (1996) را ببینید.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11 ] نامیده می شود.

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23] است.