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

لم 2.1.1¶

صورت لم : یک گراف \(n\) راسی و \(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 نشده میتوانیم هی یال حذف کنیم به طوری که گراف همبند بماند پس قضیه اثبات شد.