تجزیه درختی

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

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

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

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

تعریف

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

منابع

• Arnborg, S.; Corneil, D.; Proskurowski, A. (1987), "Complexity of finding embeddings in a k-tree", SIAM Journal on Matrix Analysis and Applications, 8 (2): 277–284, doi:10.1137/0608024.
• Arnborg, S.; Proskurowski, A. (1989), "Linear time algorithms for NP-hard problems restricted to partial k-trees", Discrete Applied Mathematics, 23 (1): 11–24, doi:10.1016/0166-218X(89)90031-0.
• Bern, M. W.; Lawler, E. L.; Wong, A. L. (1987), "Linear-time computation of optimal subgraphs of decomposable graphs", Journal of Algorithms, 8 (2): 216–235, doi:10.1016/0196-6774(87)90039-3.
• Bertelé, Umberto; Brioschi, Francesco (1972), Nonserial Dynamic Programming, Academic Press, ISBN 0-12-093450-7.
• Bodlaender, Hans L. (1988), "Dynamic programming on graphs with bounded treewidth", Proc. 15th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 317, Springer-Verlag, pp. 105–118, doi:10.1007/3-540-19488-6_110.
• Bodlaender, Hans L. (1996), "A linear time algorithm for finding tree-decompositions of small treewidth", SIAM Journal on Computing, 25 (6): 1305–1317, CiteSeerX 10.1.1.113.4539, doi:10.1137/S0097539793251219.
• Diestel, Reinhard (2005), Graph Theory (3rd ed.), اشپرینگر ساینس+بیزینس مدیا, ISBN 3-540-26182-6.
• Halin, Rudolf (1976), "S-functions for graphs", Journal of Geometry, 8: 171–186, doi:10.1007/BF01917434.
• Robertson, Neil; Seymour, Paul D. (1984), "Graph minors III: Planar tree-width", Journal of Combinatorial Theory, Series B, 36 (1): 49–64, doi:10.1016/0095-8956(84)90013-3.