درختها و ساختارهای پوشا
درخت یک گراف همبند بدون دور است و ساختارهای پوشا، اسکلتهای همبند حداقلی را از گرافهای بزرگتر استخراج میکنند.
Definition
درخت یک گراف همبند بدون دور است؛ یک درخت پوشا از یک گراف همبند، زیرگرافی است که یک درخت است و شامل تمام رئوس گراف میشود.
Scope
این موضوع به بررسی مشخصههای معادل درختها، درختهای ریشهدار و برچسبدار، درختها و جنگلهای پوشا، و شمارش آنها از طریق فرمول کیلی و قضیه ماتریس-درخت میپردازد. همچنین درختهای پوشای مینیمم را به عنوان یک مسئله بهینهسازی معرفی میکند که نظریه گراف را به طراحی الگوریتم و شمارش ترکیبیاتی پیوند میزند.
Core questions
- چه شرایط معادل یک گراف را به عنوان یک درخت مشخص میکند؟
- چند درخت برچسبدار با تعداد معینی از رئوس وجود دارد؟
- یک گراف معین شامل چند درخت پوشا است؟
- چگونه میتوان یک درخت پوشا با حداقل وزن کل را به طور کارآمد یافت؟
Key concepts
- گرافهای همبند بدون دور
- درختهای ریشهدار و برچسبدار
- درختها و جنگلهای پوشا
- دنبالههای پروفر
- فرمول کیلی
- درخت پوشای مینیمم
Key theories
- فرمول کیلی
- دقیقاً n^(n-2) درخت برچسبدار متمایز بر روی n رأس وجود دارد، که یک نتیجه کلاسیک شمارشی است و میتوان آن را با دنبالههای پروفر، قضیه ماتریس-درخت، یا چندین تناظر دوسویه ظریف اثبات کرد.
- قضیه ماتریس-درخت
- تعداد درختهای پوشای یک گراف برابر با هر همعامل (کوفاکتور) ماتریس لاپلاسین آن است، که شمارش ترکیبیاتی درختهای پوشا را به جبر خطی و دترمینانها پیوند میدهد.
Clinical relevance
درختهای پوشا زیربنای طراحی شبکه و مسیریابی پخش هستند، درختهای پوشای مینیمم مسائل اتصال با کمترین هزینه را حل میکنند، و ساختارهای درختی دادهها و سلسلهمراتب را در سراسر علوم کامپیوتر سازماندهی میکنند.
History
مطالعه شبکههای الکتریکی توسط کیرشهف در قرن نوزدهم منجر به قضیه ماتریس-درخت شد، در حالی که شمارش درختهای برچسبدار توسط کیلی در سال 1889 به یکی از مشهورترین فرمولها در نظریه گراف شمارشی تبدیل گشت.
Key figures
- Arthur Cayley
- Gustav Kirchhoff
- Heinz Prufer
Related topics
Seminal works
- diestel2017
- stanley2011
Frequently asked questions
- چرا یک درخت با n رأس دقیقاً n-1 یال دارد؟
- یک درخت همبند است که حداقل n-1 یال را ایجاب میکند، و بدون دور است که بیش از آن را منع میکند؛ این دو شرط با هم تعداد یالها را دقیقاً n-1 تعیین میکنند.
- یک درخت پوشا برای چه کاری استفاده میشود؟
- یک درخت پوشا حداقل مجموعهای از اتصالات را فراهم میکند که یک شبکه را همبند نگه میدارد، که اساس پخش کارآمد و طراحی شبکه با کمترین هزینه است.