قضایایی در ارتباط با درخت های پوشای کمینه

در زندگی روزمره با درخت های پوشای کمينه ی زيادی مواجه می شويم: در خانه، خيابان، محل کار، … ولی اکثر ما بدون هيچ گونه تاملی درباره ی آن ها به سادگی از کنار آن ها رد می شويم، بدون آگاهی از اينکه اين درخت ها دارای خواص خوشگل زيادی هستند. در اين نوشته سعی دارم به بررسی بعضی از آن ها بپردازم!

خاصیت 1: به ازای هر دور موجود C در گراف G، اگر وزن يال X از اين دور بزرگتر از يال های ديگر دور باشد، اين يال عضو هيچ درخت پوشای کمينه ای نيست.

اثبات: فرض کنيم درخت پوشای T دارای يال X باشد. اگر اين يال را از درخت حذف کنيم، درخت به دو مولفه ی A و B تقسيم می شود. چون دو سر يال X (گره های u و v) در دور C قرار دارند، پس C – X نيز مسيری بين اين دو گره است. اگر از گره u شروع کنيم و در اين مسير حرکت کنيم، چون v در مولفه B قرار دارد، بالاخره بايد از گرهی که در مولفه ی A قرار دارد، به گرهی در مولفه ی B نقل مکان کنيم. پس يالی در دور C وجود دارد که دارای وزن کمتری از X می باشد و مولفه ی A و B را به هم وصل می کند. با جايگزين کردن X با اين يال، درخت پوشايي با وزن کمتر به دست می آوريم.

خاصیت 2: دنباله ی وزنی دو درخت پوشای کمينه ی متفاوت در يک گراف، يکی است.

اثبات:

S: درخت پوشای کمينه ی اول

T: درخت پوشای کمينه ی دوم

s: يالی از S که در T وجود ندارد.

اگر يال s را از S حذف کنيم، درخت به مولفه ی A و B تقسيم می شود. دو راس دلخواه x و y را به طوری که x عضو A و y عضو B باشد را در نظر بگيريد. چون T يک درخت پوشا می باشد، بنابراين حتما مسيری از x به y در T وجود دارد. اگر در روی اين مسير حرکت کنيم، بالاخره در يکی از گام ها توسط يالی از T از مولفه ی A به مولفه ی B خواهيم رفت. اين يال را t می ناميم. اين يال طبق فرض، مخالف s است (چون s يالی از S است که در T نيست، ولی t در T است)، و اين يال در S موجود نمی باشد (چون اگر موجود بود، دور به وجود می آمد. درخت که دور ندارد)

اگر يال s را از S حذف کنيم، و به جای آن t را قرار دهيم، يک درخت پوشای جديد بدست می آوريم. که وزن آن برابر با S – s + t است. چون S درخت پوشای کمينه است، w(S) – w(s) + w(t) >= w(S) و بنابراين w(t) >= w(s) (1).

اگر يال t را از T حذف کنيم، و به جای آن s را قرار دهيم، يک درخت پوشای جديد بدست می آوريم. که وزن آن برابر با T – t + s است. چون T درخت پوشای کمينه است، w(T) – w(t) + w(s) >= w(T) و بنابراين w(s) >= w(t) (2).

از (1) و (2) به دست می آوريم که وزن s و t برابر است. پس برای s يال متناظر هموزن در T پيدا کرديم. حال از آن جا که يال های عضو S ای که رئوس آن در مولفه ی A قرار دارد، درخت پوشای کمينه ای را برای اين مولفه تشکيل می دهند، و يال های عضو S ای که رئوس آن در مولفه ی B قرار دارد، درخت پوشای کمينه ای را برای اين مولفه تشکيل می دهند، می توانيم به صورت بازگشتی همين رويه را برای اين مولفه ها انجام دهيم و برای هر کدام از يال های S يال متناظر هموزن در T پيدا کنيم.

خاصيت 3: اگر يال های يک گراف دارای وزن های دو به دو متفاوتی باشند، تنها يک درخت پوشای کمينه برای اين گراف وجود دارد.

اثبات: نتيجه ی خاصيت 2.

خاصیت 4: اگر A دنباله ی وزنی مرتب شده ی يک درخت پوشای کمينه ی يک گراف باشد، و B دنباله ی وزنی مرتب شده ی يک درخت پوشای غير کمينه برای همان گراف باشد، به ازای هر i، داريم [A[i] ⇐ B[i.

اثبات:: مشابه اثبات خاصيت 2.