درخت (نظریه گراف): تفاوت میان نسخه‌ها

[[پرونده:Tree graph.svg|left]]

در [[نظریه گراف|نظریهٔ گراف]]، '''درخت''' گرافی همبند و بدون دور است. درخت‌ها به طور گسترده در [[علوم رایانه]] و [[ساختار داده‌ها]] کاربرد دارند. مثل [[درخت‌های جستجوی دودویی]]، [[پشته‌ها]]<ref>Heaps</ref>، درخت‌های هافمن<ref>Huffman trees</ref> برای [[فشرده‌سازی اطلاعات]] و غیره.

 

== تعاریف ==

 

[[پرونده:Tree3.JPG]]

 

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

 

[[رده:نظریه گراف]]