فاصله در درخت و گراف¶

فاصله چیست؟¶

دو راس \(u,v\) در گراف را در نظر بگیرید. فاصله این دو راس طول (تعداد یال ها) کوتاه ترین مسیر بین این دو راس تعریف می شود.

نکته : اگر دو راس در دو مولفه همبندی جدا باشند فاصله آن ها بینهایت است.

فاصله دو راس \(u,v\) را به صورت \(d(u,v)\) نشان میدهند.

قطر¶

تعریف : قطر گراف برابر است با \(Max_{u,v} d(u,v)\) یا به عبارتی ماکسیمم فاصله دو به دو راس ها در گراف.

توجه کنید که قطر بلندترین مسیر نیست و در واقع بلند ترین فاصله است ولی در درخت بلندترین مسیر و قطر یکی است زیرا اگر دو سر بلندترین مسیر را بگیرید چون بین آن دو دقیقا یک مسیر وجود دارد و بلندترین مسیر , آن مسیر است در واقع طول بلندترین مسیر برابر فاصله آن دو راس است پس قطر برابر بلندترین مسیر است. تفاوت بلند ترین مسیر و قطر جایی به چشم می اید که در حالت کلی پیدا کردن قطر یک گراف از اوردر چند جمله ای حل میشود ولی پیدا کردن بلند ترین مسیر یک مسئله NP است.

خروج از مرکز¶

اگر نام راس را \(u\) در نظر بگیریم خروج از مرکز \(u\) برابر ماکسیمم \(d(u,v)\) به ازای همه \(v\) هاست.

گراف اگر درخت باشد و درخت را از \(u\) اویزان کنیم خروج از مرکز \(u\) میشود ارتفاع راسی که بیشترین ارتفاع را در درخت دارد.

خروج از مرکز راس \(u\) را با \(\varepsilon{(u)}\) نشان میدهند.

قضیه 2.2.1¶

صورت قضیه : در درخت خروج از مرکز یک راس برابر ماکسیمم فاصله آن از دو سر قطر است.

اثبات : برهان خلف میزنیم. فرض کنید راس ما \(a\) است و دو سر قطر هم راس های \(u , v\) هستند . و راسی که فاصله اش با \(a\) برابر \(\varepsilon(a)\) است \(b\) نام دارد . واضح هم است \(a\) اگر یکی از دو سر قطر بود حکم درست است پس فرض میکنیم هیج یک از دو سر قطر نیست.

درخت را از \(a\) آویزان میکنیم. فرض کنید راس \(mh\) راسی با بیشترین ارتفاع باشد که سه راس \(b,u,v\) داخل زیر درخت آن هستند. چون \(mh\) بیشترین ارتفاع از پدر های مشترک این سه راس دارد یعنی یا \(mh = b\) است یا بچه ای از \(mh\) که جد \(b\) است در زیر درختش حداقل یکی از دو راس \(u , v\) را ندارد.که یعنی \(mh = lca(u,b)\) or \(lca(v,b)\) .بدون از دست دادن کلیت مسئله فرض کنید \(mh = lca(u,b)\). حال ثابت میکنیم \(d(b,u)\) > \(d(u,v)\) با اثبات این بخش با تناقض بدست امده در طول قطر قضیه اثبات میشود.

• \(d(b,u)\) > \(d(u,v)\)
• \(mh = lca(b,u)\) \(\longrightarrow\) \(h(b)+h(u)-2×h(Mh)\) > \(d(u,v)\)
• اگر \(mh \neq lca(u,v)\) هم باشد باز جد مشترکشان است پس \(d(u,v)\) \(\leqslant\) \(h(u)+h(v)-2×h(mh)\)
• در نتیجه \(h(B) + h(u) - 2×h(mh) > h(u) + h(v) - 2×h(mh) \longrightarrow h(B) > h(u)\) که فرض سوال است پس عبارت درست است. با تناقض بدست امده قضیه اثبات شد.

شعاع و مرکز¶

به راسی که مینیمم خروج از مرکز را را در بین راس های گراف دارد مرکز گراف گوییم و به خروج از مرکز آن شعاع گراف.

قضیه 2.2.2¶

• الف) در درخت اگر قطر برابر \(Q\) باشد شعاع برابر \(\lceil{Q/2}\rceil\) است.
• ب) در درخت اگر \(Q\) فرد باشد دو راس وسط مسیر دو سر قطر مرکز هستند و اگر زوج باشد راس وسط قطر.

اثبات : در ابتدا ثابت میکنیم راسی که در مسیر دو سر قطر نیست نمیتواند مرکز باشد. راسی مانند \(u\) را در نظر بگیرید که در مسیر دو سر قطر نیست و راس \(v\) را راسی از مسیر دو سر قطر در نظر بگیرید که فاصله اش با \(u\) مینیمم است با توجه به قضیه 2.2.1 میتوان فهمید \(\varepsilon{(u)} = \varepsilon{(v)} + d(u,v)\) پس \(u\) قطعا مرکز نیست. حال بیایبد راس های درون مسیر دو سر قطر را از یک سر قطر به ترتیب شماره گزاری کنید(یعنی از 0 تا \(Q\). طبق قضیه 2.2.1 میدانیم راس خروج از مرکز راس \(i\) ام در مسیر دو سر قطر برابر \(max(i,Q-i)\) است.میدانیم مینیمم عبارت بالا زمانی است که \(i , Q-i\) کمترین اختلاف را با هم داشته باشند پس

• اگر \(Q\) زوج باشد جواب میشود \(max(Q - Q/2 , Q/2)\) = \(Q/2\) پس شعاع برابر \(Q/2\) است و تنها مرکز هم راس وسط قطر است (راس \(Q/2\) مسیر دو سر قطر.
• اگر \(Q\) فرد باشد شعاع میشود \(max((Q-1)/2 , (Q+1)/2)\) = \((Q+1)/2\) و تنها راس هایی در مسیر در سر قطر که چنین ویژگی دارد راس های \((Q-1)/2,(Q+1)/2\) مسیر دو سر قطر هستند.

سنتروید¶

به راسی در گراف که مجموع فاصله هایش از دیگر راس ها مینیمم است سنتروید گراف میگویند . به مانند تعاریف بالا سنتروید در درخت نیز دارای ویژگی جالبی است که در قضیه زیر آمده.

قضیه 2.2.3¶

• الف) در درخت یک راس سنتروید است اگر و تنها اگر وقتی او را از درخت حذف کنیم سایز هر مولفه کمتر مساوی \(n/2\) باشد.
• ب) در درخت حداکثر دو سنتروید داریم و اگر دو تا باشند گراف زوج راسی است و ان دو به هم یال دارند .

اثبات : راس ها را شماره گزاری میکنیم و \(a_i\) برابر مجموع فاصله های راس \(i\) از دیگر راس های خواهد بود.حال ابتدا بخش اگر الف را اثبات میکنیم. فرض کنید سنتروید راس \(u\) باشد و وقتی ان را حذف کنیم مولفه همبندی با سایز بیشتر از \(n/2\) بوجود بیاید حال میگویم راسی که از ان مولفه با \(u\) همسایه است را در نظر بگیرید و نام آن را \(v\) بگزارید . فاصله \(v\) از راس های داخل این مولفه همبندی یکی کمتر از فاصله \(u\) از ان ها است و برای دیگر راس ها هم فاصله آن یکی بیشتر از فاصله \(u\) است پس \(a_v = a_u - sz + (n-sz)\) که \(sz\) برابر سایز آن مولفه همبندی است. و چون \(sz > n/2 \longrightarrow n - 2 \times sz < 0 \longrightarrow a_v > a_u\) با تناقض بدست امده اگر الف اثبات شد.

حال ثابت میکنم هر دو راسی مانند \(i , j\) که ویژگی اگر بخش الف را دارند در ان ها \(a_i = a_j\) و چون میدانیم سنتروید ما ویژگی اگر الف را دارد پس همه راس ها با ویژگی اگر الف سنتروید هستند. درخت را از راس \(i\) اویزان میکنیم.حال یک متغیر به نام \(A\) داریم که وقتی روی راس \(z\) هستیم \(A = a_z\) و اول کار \(A = a_i\) حال از راس ریشه یعنی \(i\) به سمت راس \(j\) حرکت میکنیم (یعنی در واقع مسیر بین این دو راس را با شروع از \(i\) طی میکنیم) حال زمانی که از یک راس به بچه اش میرویم \(A\) به اندازه سایز زیر درخت بچه اش کم میشود و به اندازه تعداد راس های منهای سایز زیر درخت بچه اش به \(A\) اضافه میشود. ما میدانیم سایز زیر درخت \(j\) بیشترمساوی از \(n/2\) است زیرا وقتی \(j\) را از درخت حذف کنیم سایز مولفه همبندی که پدرش در آن قرار دارد طبق فرض کمتر مساوی \(n/2\) است پس تعداد راس های که در این مولفه نیستند(با احتساب \(j\)) بیشتر مساوی \(n/2\) است. پس سایز زیر درخت تمام جد های \(j\) که ما طی کردیم هم این بیشتر مساوی بیشتر مساوی \(n/2\) است پس میتوان نتیجه گرفت مقدار \(A\) همیشه یا کمتر میشود یا تغییر نمیکند. پس \(a_i \geq a_j\) . اگر ما درخت را از \(j\) هم اویزان کنیم و مسیر بین ان دو را طی کنیم به نتیجه \(a_j \geq a_i\) میرسیم که در نتیجه \(a_i = a_j\) است.

حال به اثبات بخش ب میرویم فرض کنید دو راس \(i,j\) سنتروید هستند و درخت را از \(i\) اویزان کردیم و داریم الگوریتم بالا را طی میکنیم حال میگوییم وقتی از یک راس به بچه اش میرویم \(A\) در صورتی تغییر نمیکند که سایز زیر درخت بچه دقیقا برابر \(n/2\) باشد و چون سایز زیر درخت \(j\) بیشتر مساوی از \(\lceil{n/2}\rceil\) است پس باید برای آن که \(A\) در کل مسیر تغییر نکند \(j\) بچه \(i\) باشد و سایز زیر درختش دقیقا \(n/2\) باشد . پس درخت زوج راسی است زیرا سایز زیر درخت \(j\) بیشتر مساوی \(\lceil{n/2}\rceil\) است و سایز زیر درخت بچه های \(i\) باید کمتر مساوی \(\lfloor{n/2}\rfloor\) باشد پس باید \(\lfloor{n/2}\rfloor = \lceil{n/2}\rceil \) زوج است. همچنین فهمیدیم در بالا هر دو سنتروید با هم همسایه اند پس واضح است که حداکثر میتوانیم دو سمنترید داشته باشیم و اگر نه دور داریم.

مجموع فاصله ها¶

فرض کنید در مسئله ای هدف مینیمم یا ماکسیمم کردن مجموع فاصله بین هر دو راس است فرض کنید به این مجموع چگالی گراف بگوییم. به صورت شهودی هر چه چگالی گراف کمتر باشد گراف جمع و جور تر و هر چه چگالی گراف بیشتر باشد گراف پهن و پخش تر است.

در ضمن برای اینکه فاصله تعریف شده باشد فرض کنید موضوع بحث ما گراف های همبند می باشد.

کمینه کردن چگالی گراف¶

فاصله بین دو راس حداقل 1 است. و در گراف \(K_n\) فاصله بین هر دو راس دقیقا 1 است. پس کمترین چگالی ممکن در گراف \(K_n\) به دست می آید که برابر با \(n \choose 2\) می باشد.

حالا اگر دامنه بحث را به درخت ها محدود کنیم مسئله کمی سخت تر می شود. اما همچنان می توان اینگونه استنتاج کرد.

• دقیقا \(n-1\) جفت از راس ها هستند که فاصله اشان دقیقا 1 است. زیرا درخت \(n-1\) یال دارد.
• هر جفتی از راس ها که به همدیگر یال ندارند دارای فاصله حداقل 2 هستند.

در نتیجه کمترین چگالی ممکن حداقل \(2 \times {n \choose 2} - (n-1)\) می باشد و تنها مثالی که در حالت این کران صدق می کند حالتی است که فاصله بین هر دو راس حداکثر برابر با 2 است. تنها درختی که این ویژگی را دارد ستاره می باشد (همانطور که در عکس می بینید). زیرا که اگر در این گراف دو برگ باشند که پدر مشترک نداشته باشند در اینصورت فاصله آنها حداقل 3 خواهد بود.

درخت پشتیبانی¶

فرض کنید یک شبکه ارتباطی داریم که \(n\) شهر را به هم وصل می کنند. برای اطمینان یک شبکه ارتباطی پشتیبانی هم آماده کرده ایم که در صورت ایجاد اختلال در شبکه اصلی از شبکه پشتیبانی استفاده کنیم تا ارتباط قطع نشود.

به زبان گراف دو درخت \(n\) راسی \(T\) و \(T ^ {\prime}\) داریم. می خواهیم ثابت کنیم در صورتیکه یکی از یال های \(T\) مثل \(uv\) قطع شوند می توان یکی از یال های \(T ^ {\prime}\) مثل \(u^{\prime}v^{\prime}\) را به درخت \(T\) اضافه کرد که ساختار همچنان همبند باقی بماند.

پس فرض کنید \(uv\) را از \(T\) حذف کردیم در اینصورت درخت ما دارای دو مولفه همبندی خواهد شد یکی از مولفه ها را آبی و دیگری را قرمز در نظر بگیرید. حالا می توان در درخت \(T^{\prime}\) مسیری بین \(u,v\) یافت. در این مسیر یالی وجود خواهد داشت که یک سر آن آبی و یک سر آن قرمز باشد (چرا؟). حالا اگر این یال \(u^{\prime}v^{\prime}\) باشد می توانیم این یال را به \(T\) اضافه کنیم و دوباره آن را همبند کنیم!

افراز درخت به مسیر ها¶

درخت \(T\) را در نظر بگیرید. در این قسمت هدف ما این است که یال های این درخت را به کمترین تعداد تعدادی مسیر افراز کنیم. برای شهود بهتر فرض کنید یال های مسیر ها را یکی یکی از درخت حدف می کنیم تا به گرافی بدون یال برسیم.

اول از همه توجه کنید که بعد از حذف هر مسیر تنها زوجیت درجه دو سر مسیر تغییر می کند همچنین در انتها درجه تمام راس ها زوج (صفر) خواهد بود. پس یک راس درجه فرد باید فرد بار و یک راس درجه زوج باید زوج بار به عنوان یک سر مسیر انتخاب شود. پس اگر تعداد راس های درجه فرد درخت \(X\) باشد آنگاه حداقل \(\frac X 2\) مسیر نیاز داریم. (می دانیم که تعداد راس های درجه فرد هر گرافی زوج است پس \(X\) زوج است).

حالا اگر در هر مرحله مسیر بین دو راس درجه فرد را حذف کنیم می توانیم به حالت بهینه برسیم! فقط باید توجه داشته باشیم که دو راس درجه فرد ما مربوط به یک مولفه همبندی باشد.

حالا سوالی که پیش می آید این است که درخت بودن طی این فرایند به ما چه کمکی کرد؟

در نهایت ما از این موضوع استفاده کردیم که اگر درختی راس درجه فرد نداشته باشد یالی ندارد (اما این قضیه در گراف به صورت کلی برقرار نیست). چرا که اگر تعداد راس های گراف حداقل دو باشد در اینصورت برگی خواهد داشت که درجه آن 1 (و فرد) است.

پوشاندن یال های درخت با مسیر ها¶

در ابن قسمت می خواهیم کمترین تعداد مسیر را پیدا کنیم که اجتماع آن ها کل یال های \(T\) را شامل شود. این مسئله مشابه حالت قبل است با این تفاوت که در حالت قبل یال ها را به مسیر ها افراز می کردیم یعنی هر یال متعلق به یک مسیر بود. در اینجا این آزادی را داریم که یک مسیر چند بار یالی را بپوشاند. می توان نتیجه گرفت که جواب این مسئله کمتر از مسئله قبل است.

در نگاه اول متوجه می شوید که چون طولانی کردن مسیر ها ضرری با ما نمی زند پس حالت بهینه ای وجود دارد که دو سر هر مسیر برگ باشد!

از طرف دیگر به ازای هر برگ یالی که از این برگ به راس مجاورش می رود را در نظر بگیرید. هر مسیر حداکثر 2 تا از این یال ها را می پوشاند. پس اگر \(X\) تا برگ داشته باشیم حداقل \(\frac X 2\) تا مسیر نیاز داریم حالا تلاش می کنیم تا این کران را بر آورده کنیم. یعنی اگر \(X\) زوج باشد با \(\frac X 2\) مسیر و اگر \(X\) فرد بود با \(\frac {X+1} 2\) مسیر یال های درخت را بپوشانیم.

پس سعی می کنیم در هر مرحله پس از انتخاب مسیر درختمان را به درختی تبدیل کنیم که تعداد برگ هایش دو تا کمتر است(البته در حالتی که \(X\) فرد باشد مرحله آخر نمی توانیم اینکار را بکنیم). اگر بتوانیم این کار را بکنیم تعداد مسیر هایی که انتخاب کردیم نصف تعداد برگ ها خواهد بود همانطور که می خواستیم.

دو برگ دلخواه مثل \(u,v\) را در نظر بگیرید و درخت را از این مسیر آویزان کنید. ابتدا این مسیر را انتخاب کنید (که یال های بین \(u,v\) را بپوشاند). فرض کنید راس های مسیر ما \(a_1,...,a_k\) باشد حالا درختی می سازیم که به جای \(a_1,...,a_k\) یک راس دارد! بین این راس و یک راس مثل \(w\) یال است اگر و تنها اگر بین \(w\) و یکی از \(a_1,...,a_k\) یال باشد.‌ (به صورت شهودی مثل این است که کل راس های مسیر را فشرده کردیم و به یک راس تبدیل کردیم). حالا هر مسیر در گراف جدیدمان معادل با یک مسیر در گراف اولیه است و الان تنها کافیست کل یال ها در درخت جدید را با مسیر ها بپوشانیم!

پس در هر مرحله یک مسیر که دو سر آن برگ است را فشرده می کنیم و به صورت یک راس در می آوریم. در هر مرحله تعداد برگ های گراف جدیدمان دو تا کم می شود مگر اینکه راسی که جدید اضافه کردیم (راس فشرده) برگ باشد. در صورتی این اتفاق می افتد که راس های مسیر بین \(u,v\) همه درجه 2 باشند به جز یکی از آنها که باید درجه 3 باشد. به \(u,v\) که مسیر بین آن چنین خاصیتی داشته باشد یک زوج ناسازگار می گوییم.

پس اگر بتوانیم در هر مرحله دو برگ \(u,v\) را طوری انتخاب کنیم که زوج ناسازگار نباشند این کار را می کنیم (‌که پس از فشرده سازی از تعداد برگ ها 2 تا کم می کند). اگر نتوانستیم اینکار را بکنیم چه؟ در اینصورت ادعا می کنیم تنها یک راس درجه 3 داریم و باقی راس ها دارای درجه 1 یا 2 هستند (چرا؟). در اینصورت همانطور که در شکل می بینید درخت ما دقیقا 3 برگ خواهد داشت و می توانیم آن را با 2 مسیر بپوشانیم.

درخت چپانی¶

فرض کنید درختی \(n\) راسی به نام \(T\) داریم. همچنین گرافی مثل \(G\) داریم که \(\delta(G) \geq n-1\). می خواهیم ثابت کنیم زیرمجموعه ای از یال های \(G\) وجود دارد که \(T\) را بسازد. (به صورت شهودی یک درخت \(T\) در گراف \(G\) بتوان پیدا کرد).

یک برگ دلخواه مثل \(u\) که تنها مجاور آن \(v\) است را در نظر بگیرید و \(u\) را از درخت حذف کنید! سپس به صورت استقرایی درخت \(T-u\) را در \(G\) پیدا کنید. حالا می خواهیم یال \(uv\) را به درختمان اضافه کنیم. فرض کنید راس \(v\) در گراف \(G\) متناظر با \(v^{\prime}\) شده باشد. حالا کافیست از بین مجاور های \(v^{\prime}\) راسی را انتخاب کنید که قبلا با هیچ راس درخت متناظر نشده است. سپس می توان این راس را متناظر با \(u\) قرار داد که فرض استقرای ما را ثابت می کند.

برای یافتن چنین راسی کافیست از فرض \(\delta(G) \geq n-1\) استفاده کنیم. پس \(v^{\prime}\) حداقل \(n-1\) مجاور دارد و حداکثر \(n-2\) تا از آن ها قبلا به راس های درخت متناظر شده اند. پس یکی از مجاور های \(v\) تا حالا به راس های درخت متناظر نشده که حالا می توانیم همانطور که گفتیم \(u\) را به آن متناظر کنیم.

این مسئله به منظور آشنایی شما با ساختار استقرا پذیر درخت مطرح شد. دیدید که چطور می توان یک برگ از درخت را حذف کرد و فرض استقرا را برای درخت باقی مانده به کار برد.