در نظریه گراف، یک تجزیه درختی یک نگاشت از یک گراف به یک درخت است که می تواند برای تعریف عرض درخت مورد استفاده قرار گیرد. بسیاری از مسائل ان پی - کامل در نظریه گرافها برای گراف هایِ با عرض درختی پایین، الگوریتم های بسیار سریعی دارند.
تحزیه درختی کارکردهای بسیاری در مشکلاتی مانند استنباط احتمالی، رضایت محدودیت و تجزیه ماتریس دارد.
این مفهوم در سال ۱۹۸۴ توسط نیل رابرتسون و پاول سیمور برای اولین به طور دقیق تعریف شد. [ ۱]
به طور شهودی، تجزیه درختی نمایان گر میزان نزدیکی یک گراف به ساختار درخت است. هرچه یک گراف به یک درخت «نزدیک» تر باشد، عرض درختی آن کم تر است. به طور مثال، عرض درختی هر درخت برابر ۱ است.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفتحزیه درختی کارکردهای بسیاری در مشکلاتی مانند استنباط احتمالی، رضایت محدودیت و تجزیه ماتریس دارد.
این مفهوم در سال ۱۹۸۴ توسط نیل رابرتسون و پاول سیمور برای اولین به طور دقیق تعریف شد. [ ۱]
به طور شهودی، تجزیه درختی نمایان گر میزان نزدیکی یک گراف به ساختار درخت است. هرچه یک گراف به یک درخت «نزدیک» تر باشد، عرض درختی آن کم تر است. به طور مثال، عرض درختی هر درخت برابر ۱ است.
wiki: تجزیه درختی