درخت ها (Trees)، در ریاضیات (Mathematics)
انواع گراف دو بخشی (Bipartite Graph) را در آموزش زیر شرح دادیم :
درخت ها (Trees) :
درخت ها (Trees) یکی از اساسی ترین و مهم ترین انواع گراف ها هستند که ویژگی دوبخشی بودن را دارند. یک درخت، یک گراف همبند (Connected) و بدون دور (Cycle) است . از آنجایی که هیچ دوری در درخت وجود ندارد، به طریق اولی هیچ دور فردی (Odd Cycle) ندارد. بنابراین، طبق قضیه اساسی گراف های دوبخشی، تمام درخت ها دو بخشی هستند .
این ویژگی را می توان به سادگی با یک رنگ آمیزی اثبات کرد. اگر یک رأس دلخواه را در نظر بگیریم و آن را یک رنگ بزنیم، سپس همسایه های آن را با رنگ دوم، و همسایه های همسایه ها را دوباره با رنگ اول و به همین ترتیب ادامه دهیم، به دلیل نبود دور، هیچگاه به تناقض برخورد نمی کنیم و یک رنگ آمیزی معتبر با دو رنگ به دست می آید. درخت ها به طور گسترده در علوم کامپیوتر برای ساختاردهی داده ها (مانند درخت دایرکتوری)، الگوریتم های جستجو و شبکه ها استفاده می شوند.
