پرش به محتوا

تجزیه انشعابی

از ویکی‌پدیا، دانشنامهٔ آزاد
تجزیه انشعابی یک گراف شبکه‌ای. جداسازی، تجزیه و نمودار همگی دارای عرض سه هستند.

در تئوری گراف، تجزیه انشعابی از یک گراف بدون جهت G یک خوشه‌بندی سلسله مراتبی از یال‌های G است که توسط یک درخت دودویی بدون ریشه T نشان داده می‌شود که یال‌های G به برگ‌های T نسبت داده‌شده‌اند. حذف هر یال از T، یال‌های G را به دو زیرگراف تقسیم می‌کند. عرض این تجزیه برابرست با حداکثر تعداد رئوس مشترک هر جفت زیرگراف است که به این ترتیب تشکیل شده‌است. عرض شاخه G حداقل عرض هر شاخه تجزیه G است.[۱]

منابع

[ویرایش]
  1. "Branch-decomposition". Wikipedia (به انگلیسی). 2021-04-08.