یک درخت پوشا حداقل یا درخت پوشا حداقل وزن زیرمجموعه ای از لبه های یک نمودار بدون جهت متصل و وزن لبه است که همه راس ها را بدون هیچ چرخه ای و با حداقل وزن کل یال ممکن به هم متصل می کند. یعنی درختی است که مجموع وزن های لبه اش تا حد امکان کوچک است.
با مثال حداقل درخت پوشا چیست؟
درخت پوشاى حداقل نوع خاصی از درخت است که طول (یا "وزن") لبه های درخت را به حداقل می رساند. یک مثال یک شرکت کابلی است که می خواهد برای چندین محله خط بکشد; با به حداقل رساندن میزان کابل کشیده شده، شرکت کابل در هزینه صرفه جویی خواهد کرد. یک درخت یک مسیر دارد که به هر دو رأس می پیوندد.
چگونه حداقل درخت پوشا را پیدا می کنید؟
نزدیکترین همسایه بدون رنگ به زیرگراف قرمز را بیابید (یعنی نزدیکترین راس به هر راس قرمز). آن و لبه اتصال راس به زیرگراف قرمز را با رنگ قرمز علامت بزنید. مرحله 2 را تکرار کنید تا تمام رئوس قرمز مشخص شوند. زیرگراف قرمز یک درخت پوشا حداقل است.
منظور شما از درخت پوشا و درخت پوشای حداقل چیست؟
یک درخت پوشا از یک گراف مجموعه ای از یال های متصل است که هر رأس در نمودار را شامل می شود، اما چرخه ای تشکیل نمی دهد. … حداقل درخت پوشا است که وزن لبه های تجمعی آن کمترین مقدار را دارد، اما.
تفاوت بین درخت پوشا و حداقل درخت پوشا چیست؟
اگر نمودار باشدبا وزن یال، می‌توانیم وزن یک درخت پوشا را به عنوان مجموع وزن تمام یال‌های آن تعریف کنیم. یک درخت پوشا حداقل درخت پوشاداری است که وزن آن در بین همه درختان پوشاننده ممکن کوچکترین باشد.
