تجزیه درختی

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

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

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

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

پانویس

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

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