تجزیه درختی

شرط سوم نیز برقرار است. بدین معنی که سبدهای حاویِ یک راس، تشکیل یک زیردرخت در تجزیه درختی می‌دهند (به‌طور مثال به راس G که با رنگ بنفش مشخص شده‌است، دقت کنید که در سه سبد موجود است و این سه سبد تشکیل یک مولفه هم‌بندی می‌دهند).

برقراری این سه شرط نشان می‌دهد که تجزیه درختی ارائه‌شده، یک تجزیه درختی معتبر است.
در نظریه گراف، یک تجزیه درختی یک نگاشت از یک گراف به یک درخت است که می‌تواند برای تعریف عرض درخت مورد استفاده قرار گیرد. بسیاری از مسائل ان‌پی-کامل در نظریه گرافها برای گراف‌هایِ با عرض درختی پایین، الگوریتم‌های بسیار سریعی دارند.

تحزیه درختی کارکردهای بسیاری در مشکلاتی مانند استنباط احتمالی، رضایت محدودیت و تجزیه ماتریس دارد.

این مفهوم در سال ۱۹۸۴ توسط نیل رابرتسون و پاول سیمور برای اولین به‌طور دقیق تعریف شد. pp.354–355

 تعریف 
به‌طور شهودی، تجزیه درختی نمایان‌گر میزان نزدیکی یک گراف به ساختار درخت است. هرچه یک گراف به یک درخت «نزدیک» تر باشد، عرض درختی آن کم‌تر است. به‌طور مثال، عرض درختی هر درخت برابر ۱ است.

 پانویس 

 منابع 
 .
 .
 .
 .
 .
 .
 .
 .
 .

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