خاصیت های مقدماتی
====================

در این فصل به بررسی درخت که یکی از مهمترین تعاریف گراف است و کاربرد زیادی در برنامه نویسی نیز دارد میپردازیم . 

در این بخش ویژگی ها و خاصیت های اصلی درخت را بیان و آن ها را اثبات میکنیم . در پایان این بخش انتظار میرود شهود خوبی روی شکل درخت و ویژگی های ابتدایی آن داشته باشید.

تعاریف مربوط به این بخش
--------------------------

- **درخت** : گراف ساده ای که همبند است و دور ندارد .
- **جنگل** : گراف ساده ای که دور ندارد .
- **برگ** : راسی در درخت که درجه اش 1 است .
- **درخت فراگیر یا درخت پوشا** : زیر گراف فراگیری که درخت است .

قضایا و لم های مورد استفاده در این بخش 
-----------------------------------------

لم 2.1.1
~~~~~~~~~~~~~~

**صورت لم :** یک گراف :math:`n` راسی و :math:`m` یالی حداقل max(1,n-m) مؤلفه همبندی دارد و اگر دقیقا n-m مؤلفه همبندی داشت دور ندارد و اگر نه دور دارد .

**اثبات لم :** 
ابتدا فرض میکنیم گراف هیچ یالی ندارد و یال های آن را به ترتیبی دلخواه اضافه میکنیم . 

حال اثبات میکنیم وقتی یک یال را به گراف اضافه میکنیم تعداد مؤلفه های همبندی حداکثر یکی کمتر میشود و اگر تعداد مؤلفه های ثابت ماند گراف دور خواهد داشت.
فرض کنید یالی که الان به گراف اضافه میکنیم بین دو راس i و j است. اگر i و j در یک مؤلفه همبندی بودند بعد اضافه کردن یال تعداد مولفه های همبندی تغییر نمیکند و چون بین i و j مسیر است یال جدید و مسیر بین i و j تشکیل دور میدهند.
اگر هم i و j در دو مؤلفه همبندی بودند بعد اضافه کردن یال مولفه های  i و j باهم یک مولفه همبندی میدهند یعنی تعداد مؤلفه های همبندی یکی کم میشود و چون مسیری بین i و j نبود با اضافه شدن یال دوری با این یال بوجود نمیاید.

وقتی هیچ یالی را هنوز اضافه نکردیم گراف n مؤلفه همبندی دارد و چون با اضافه کردن هر یال حداکثر تعداد مولفه ها یکی کم میشد پس در اخر حداقل n-m مولفه همبندی داریم.
پس اگر گراف در اخر دقیقا n-m مولفه همبندی داشت یعنی با اضافه کردن هر یال تعداد مولفه های همبندی دقیقا یکی کم میشد که ما ثابت کردیم وقتی تعداد مؤلفه های همبندی یکی کم شود دوری اظافه نمیشود 
پس در اخر گراف ما بدون دور است. و اگر بیشتر از n-m بود یعنی یالی بود که وقتی اضافه اش میکردیم تعداد مولفه های همبندی کم نمیشد پس دور بوجود می امد پس گراف ما دور دارد.

با توجه به لم 2.1.1 اگر بدانیم یک گراف دور ندارد و از تعداد یال ها , تعداد راس ها و تعداد مولفه های همبندی حداقل دو تایشان را بدانیم دیگری یکتا بدست می اید در واقع اگر گراف دور نداشت :

- n - m - Cc = 0
- n = تعداد راس ها
- m = تعداد یال ها
- Cc = تعداد مؤلفه های همبندی

قضیه 2.1.2
~~~~~~~~~~~~~

**صورت قضیه :** درخت n راسی دقیقا n-1 یال دارد.

**اثبات قضیه :** طبق لم 2.1.1 اگر یک گراف n راسی و m یالی دور نداشته باشد دقیقا n-m مولفه همبندی دارد و چون درخت یک مولفه همبندی دارد و دور ندارد پس در درخت n راسی n - m = 1 است پس m = n - 1.

قضیه 2.1.3
~~~~~~~~~~~~~

**صورت قضیه :** یک درخت n راسی که (n >= 2) حداقل 2 برگ دارد.

**اثبات :** بلندترین مسیر در درخت را در نظر بگیرید. چون n > 1 پس قطعا بلندترین مسیر حداقل 2 راس دارد.حال 2 راس سر مسیر را در نظر بگیرید. حداکثر به یک راس در مسیر یال دارد زیرا اگر بیشتر داشته باشند دور بوجود می اید که با ویژگی درخت
تناقض دارد . و چون بلند ترین مسیر را گرفته ایم دو سر مسیر به راسی که داخل مسیر نیست یال ندارند پس ثابت شد دو سر بلند ترین مسیر در درخت برگ هستند.

قضیه 2.1.4
~~~~~~~~~~~~

**صورت لم :** اگر از درخت برگش را حذف کنیم گراف باقی مانده باز درخت است.

**اثبات :** باید ثابت کنیم گراف باقی مانده همبند است و دور ندارد. واضح است که یک گراف اگر دور نداشته باشد وقتی راسی از ان را نیز حذف کنیم باز دور ندارد.حال میخواهیم بگوییم همبند است. اگر برگ را حذف کنیم و گراف ناهمبند شود پس حداقل  2 مولفه همبندی دارد
و راسی که حذف کردیم هم باید به هر یک از این مولفه ها حداقل یک یال میداشت تا گراف بدون حذفش همبند باشد پس درجه اش حداقل 2 بود ولی درجه برگ 1 است. با تناقض بدست آمده ثابت شد گراف همبند نیز هست پس درخت است.

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

قضیه 2.1.5
~~~~~~~~~~~~~

ثابت کنید گرافی که ویژگی های یکی از موارد زیر را داشته باشد درخت است. 

- الف) گرافی که n-1 یال دارد و همبند است.
- ب) گرافی که دور ندارد و n-1 یال دارد.
- ج) بین هر دو راس گراف دقیقا یک مسیر وجود دارد.

**جواب :**

**الف)**  اگر ثابت کنیم گراف دور ندارد قضیه اثبات میشود. طبق لم 2.1.1 اگر گراف دور داشته باشد تعداد مولفه های همبندی بیشتر از n-m است ولی در این گراف برابر n-m است.
با تناقض بدست امده قضیه اثبات شد.

**ب)**  چون گراف دور ندارد طبق لم 2.1.1 : 

n - m - Cc = 0  -->  n - (n-1) = Cc  -->  Cc = 1 

پس گراف همبند است و دور ندارد پس درخت است .

**ج)** باید ثابت کنیم گراف همبند است و دور ندارد. واضح است گراف همبند است زیرا بین هر دو راس مسیر وجود دارد پس همه در یک مولفه همبندی هستند .حال باید بگوییم دور ندارد .این هم 
واضح است زیرا اگر دور داشته باشد بین هر دو راس از یک دور حداقل 2 مسیر وجود دارد .



قضیه 2.1.6
~~~~~~~~~~~~~~

**صورت قضیه :** هر گراف همبند یک درخت فراگیر دارد.

**اثبات :** تا زمانی تعداد یال های گراف n-1 نشده هر مرحله یک یال را از گراف حذف میکنیم و ثابت میکنیم گراف همچنان همبند است و طبق قضیه 2.1.5 گرافی که n-1 یال دارد و همبند است درخت است و قضیه اثبات میشود.

پس تا زمانی که تعداد یال ها n-1 نشده حرکت زیر را انجام میدهیم : چون تعداد یال ها بیشتر از n-1 است و گراف 1 مولفه همبندی دارد طبق لم 2.1.1 در گراف دور وجود دارد. یکی از دور ها را بگیرید و یک یال از ان را حذف کنید واضح است گراف همبند میماند 
زیرا دو سر این یال از طریق یال های دیگر این دور باز هم به هم مسیر دارند پس تا وقتی تعداد یال ها n-1 نشده میتوانیم هی یال حذف کنیم به طوری که گراف همبند بماند پس قضیه اثبات شد.


ریشه دار کردن درخت
--------------------

فرض کنید یال های درخت را طوری جهت دهی کردیم که هر راس به جز راس :math:`u` دقیقا یک ورودی دارد (دقیقا یک یال به آن وارد می شود) و راس :math:`u` هیچ ورودی ندارد.

در ابتدا یک مهره را روی راس :math:`v` قرار دهید و در هر مرحله مهره اگر در راس :math:`w` بودیم مهره را به راسی ببرید که به :math:`w` یال ورودی دارد. اگر :math:`w \neq u` باشد آنگاه این راس یکتا است.

اول از همه می توان نتیجه گرفت در هر مرحله یک راس جدید را می بینیم (زیرا در درخت دور نداریم و اگر راس تکراری ببینیم یک دور را طی کرده ایم) سپس می توان نتیجه گرفت مراحل متناهی است (زیرا در هر مرحله یک راس جدید را می بینیم و تعداد راس ها متناهی است) و در نهایت می توان گفت مهره به :math:`u` خواهد رسید.

به صورت شهودی می توانید تصور کنید درخت را از :math:`u` **آویزان** کرده اید و به ازای هر یال :math:`ab` اگر :math:`a` در ارتفاع بالاتری نسبت به :math:`b` بود یال را از :math:`a` به :math:`b` جهت دهی کرده ایم. در اینصورت جهت دهی مذکور همان جهت دهی خواهد بود که در بالا به آن اشاره کردیم. برای شهود بیشتر می توانید به اینصورت فکر کنید. در جهت دهی بالا راس :math:`u` ورودی ندارد پس تمام یال های مجاور :math:`u` باید از :math:`u` به خارج جهت دهی شوند. در اینصورت به راس های مجاور :math:`u` لایه اول می گوییم. حالا تمام لایه اول دقیقا یک ورودی دارند‌ (که آن ورودی :math:`u` است) پس تمام یال های مجاور دیگر آن ها باید از لایه اول به خارج جهت دهی شوند که به آن ها لایه دوم می گوییم. به همین شکل می توان لایه سوم را تعریف کرد. هر راس لایه دوم دقیقا یک ورودی دارد که در لایه اول قرار دارد. پس تمام مجاور های دیگر آن را در لایه سوم قرار می دهیم و یال ها را از لایه دوم و سوم جهت دهی می کنیم. به همین شکل می توانید جهت دهی کردن و لایه بندی را ادامه دهید. یال های لایه :math:`h` ام به :math:`h+1` ام را در نظر بگیرید و توجه کنید که تعداد یال های ورودی هر راس لایه :math:`h+1` ام باید دقیقا 1 باشد پس به هر راس در لایه :math:`h+1` ام دقیقا یک یال از لایه :math:`h` ام می رسد.در نهایت نتیجه می گیرید که جهت دهی که در ابتدا تصور کردیم همان جهت دهی است که با شهود **آویزان کردن** از راس :math:`u` به دست آوردیم.

.. figure:: /_static/dot/Simple_Rooted_Tree.svg
   :width: 50%
   :align: center
   :alt: اگه اینترنت یارو آشغال باشه این میاد


به این عمل آویزان کردن درخت از راس :math:`u`، ریشه دار کردن درخت از راس :math:`u` هم می گویند. در اینصورت به راس :math:`u` **ریشه** می گوییم. همچنین گفتیم در جهت دهی هر راس به جز :math:`u` تنها یک یال ورودی دارد.

به ازای راس :math:`b` اگر یال ورودی به آن :math:`ab` باشد به راس :math:`a` **پدر** راس :math:`b` می گوییم.

هر دو راسی که پدر مشترک داشته باشند را **برادر** می نامیم.

راس :math:`u` **جد** راس :math:`v` است اگر که یا :math:`u` پدر راس :math:`v` باشد یا اینکه :math:`u` جد پدر :math:`v` باشد. به عبارتی به مجموعه پدران یک راس جد های این راس می گوییم.

به فاصله بین :math:`u` و هر راس (تعداد یال های مسیر بین آن ها) **ارتفاع** آن راس می گوییم.

به ازای یک راس خاص مثل :math:`v` به مجموعه راس هایی که مسیرشان (که این مسیر یکتا است) به ریشه از :math:`v` می گذرد **زیردرخت** راس :math:`v` می گوییم. به طور شهودی وقتی درخت را از :math:`u` آویزان کردیم به مجموعه راس هایی که از :math:`v` آویزان شده اند زیردرخت :math:`v` می گوییم.


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