درخت در گراف — به زبان ساده

۴۴۰۴ بازدید
آخرین به‌روزرسانی: ۱۲ اردیبهشت ۱۴۰۲
زمان مطالعه: ۵ دقیقه
درخت در گراف — به زبان ساده

در آموزش‌های قبلی مجله فرادرس درباره تعاریف و انواع گراف بحث شد. در این آموزش قصد داریم مفهوم درخت در گراف را بررسی کنیم. درخت یکی از مفاهیم اصلی در گراف است که در این آموزش مورد بررسی قرار می‌گیرد. اگر با برخی اصطلاحات این آموزش آشنا نیستید، به آموزش «گراف — تعاریف و انواع به زبان ساده» مراجعه کنید.

ابتدا یک قضیه اساسی در نظریه گراف را بیان می‌کنیم.

قضیه ۱

اگر $$G$$ یک گراف ساده با $$n$$ رأس و $$k$$‌ مولفه و $$m$$ یال باشد، گزاره زیر صحیح است:

$$n-k \leq m \leq (n-k) (n-k+1)/2 $$

تعریف پل در گراف

پل (Bridge) به یالی گفته می‌شود که در صورت حذف آن، گراف دقیقا به دو قسمت یا مولفه (Component) تبدیل می‌شود. در گراف همبند، قطع یالِ پل، باعث غیر همبند شدن گراف می‌شود.

تعریف درخت در گراف 

به گرافِ همبند (متصل) و بدون دور، درخت گفته می‌شود. برای مثال در شکل‌های زیر انواعی از درخت‌ها نشان داده شده است:

انواع درخت
شکل ۱: انواع درخت

همانطور که در آموزش‌های قبلی گفتیم، گرافِ بدیهی، گرافی است که تنها یک رأس دارد و هیچ یالی ندارد. درخت، ساده‌ترین نوع گراف غیر بدیهی است. این نوع گراف، خواص جالبی دارد. برای مثال، در درخت، هر دو رأس با یک مسیر مشخص به هم متصل هستند. برای اثبات قضایای مربوط به گراف، بعضی اوقات معمول است که آن‌ را برای درخت‌ها اثبات کنیم. در حقیقت، معلوم شده است بسیاری از حدس‌هایی که برای گراف‌های دلخواه ثابت نشده‌اند، برای درخت‌ها صحیح هستند.

به رئوس درخت با درجه یک،‌ برگ یا رئوس آویزان گفته می‌شود. بنابراین با این تعاریف، گراف ستاره یک درخت است. به یال‌های یک درخت، شاخه گفته می‌شود. هر رأسِ درخت، یک گره نام دارد. هر درخت حداقل دو رأس با درجه یک دارد.

قضیه زیر خواص ساده درخت‌ها را نشان می‌دهد:

قضیه ۲

اگر $$T$$ یک گراف با $$n$$ رأس باشد، گزاره‌های زیر معادل هستند:

  1. T یک درخت است.
  2. T یک گراف بدون دور است و $$n-1$$ یال دارد.
  3. T همبند است و $$n-1$$ یال دارد.
  4. T همبند است و هر یال، یک پل است.
  5. هر دو رأس T فقط با یک مسیر به یکدیگر متصل هستند.
  6. T بدون دور است، اما اضافه کردن یک یال جدید، دقیقا یک دور در گراف ایجاد می‌کند.

اثبات: اگر $$n=1$$ باشد، تمامی این شش گزاره بدیهی هستند. بنابراین فرض می‌شود که $$n \geq 2$$.

اثبات معادل بودن گزاره ‌های ۱ و ۲: از آنجا که $$T$$ هیچ دوری ندارد، حذف هر یال، موجب می‌شود گراف $$T$$ به دو گراف، تقسیم شود. هر یک از این دو گراف نیز درخت هستند. اگر به حذف یال‌ها همچنان ادامه دهیم به طوری که مولفه‌ها نیز درخت باقی بمانند، در نهایت به یک درخت با ۲ رأس و یک یال می‌رسیم. بنابراین طبق استقرا می‌توان گفت تعداد یال‌ها در هر یک از این درخت‌ها از تعداد راس‌ها یکی کمتر است. پس می‌توان نتیجه گرفت تعداد کل یال‌های درخت $$T$$ برابر $$n-1$$ است.

اثبات معادل بودن گزاره‌های 2 و 3: اگر T ناهمبند باشد، هریک از مولفه‌های $$T$$ یک گراف همبند بدون دور است. بنابراین مثل حالت قبل، تعداد رئوس در هر یک از این مولفه‌ها از تعداد یال‌ها به اندازه ۱ عدد بزرگتر است. بنابراین کل رئوس از کل یال‌ها در گراف $$T$$، حداقل ۲ عدد بیشتر خواهد بود. این مسئله با این قانون که گراف $$T$$، $$n-1$$ یال دارد،‌ در تناقض است. برای مثال، شکل زیر را در نظر بگیرید.

گراف ناهمبند
Disconnected Graph

در این شکل فرض شده است یک گراف ناهمبند داریم که شامل دو گراف همبند غیر مدور است. همانطور که مشاهده می‌شود این گراف ۶ رأس و ۴ یال ($$n-2$$) دارد که با تعریف درخت تناقض دارد.

اثبات معادل بودن گزاره‌های ۳ و ۴: حذف هر یال باعث می‌شود گراف $$n$$‌ راس و $$n-2$$ یال داشته باشد. به این ترتیب طبق گزاره ۲، گراف ناهمبند می‌شود که با فرض اولیه در تناقض است.

اثبات معادل بودن گزاره‌های ۴ و ۵: از آنجا که $$T$$ یک گراف همبند است،‌ هر جفت رأس به وسیله حداقل یک یال یا مسیر به یکدیگر متصل شده‌اند. اگر یک جفت رأس با دو مسیر به هم وصل باشند، یک دور در گراف ایجاد می‌شود. این مورد با این قانون که هر یال یک پل است در تناقض است.

اثبات معادل بودن گزاره‌های ۵ و ۶: اگر $$T$$ شامل یک دور باشد، پس هر دو رأس در این دور با حداقل دو مسیر به یکدیگر متصل هستند که با گزاره ۵ در تناقض است. اگر یک یال $$e$$ به درخت $$T$$ اضافه شود، از آنجا که رئوسی که یال $$e$$ به آنها متصل است از قبل به هم وصل بوده‌اند، یک دور ایجاد می‌شود. پس فقط و فقط یک دور داریم.

اثبات معادل بودن گزاره‌های ۶ و ۱: فرض کنید که $$T$$ یک گراف ناهمبند باشد. اگر به $$T$$، یک یال اضافه کنیم که یک راس از یک مولفه را به یک راس از مولفه دیگر متصل کند، هیچ دوری ایجاد نمی‌شود. پس درخت، یک گراف همبند بدون دور است.

در ادامه به بیان چند مثال برای گراف‌ها می‌پردازیم.

مثال ۱

گراف نشان داده شده در شکل زیر یک درخت است، زیرا هیچ دوری ندارد و همبند است. این گراف، ۴ رأس و ۳ یال دارد که با تعریف سازگار است.

یک درخت با ۴ راس و سه یال
شکل ۳: یک درخت با ۴ راس و 3 یال

مثال ۲

شکل زیر را در نظر بگیرید. در این شکل، رئوس $$a$$ و $$d$$ از درجه یک هستند. دو رأس دیگر یعنی $$b$$ و $$c$$‌ نیز از درجه دو هستند. به این دلیل که در درخت دور وجود ندارد، بنابراین حداقل دو یال تکی در گراف وجود دارد. این دو یال به دو رأس از درجه یک متصل هستند.

یک درخت با برگ‌هایش
شکل ۴: یک درخت با برگ‌هایش

تعریف جنگل

جنگل به مجموعه‌ای از درخت‌ها گفته می‌شود که به هم متصل نیستند. بنابراین مجموعه‌ای از درخت‌های ناهمبند، جنگل نام دارد. در جنگل نیز مانند درخت، حلقه وجود ندارد. در تعریف کلی‌تر می‌توان گفت که یک گراف بدون دور، جنگل است.

مثلا شکل ۱، یک جنگل با ۴ مولفه را نشان می‌دهد. باید اشاره کرد که درخت و جنگل، گراف‌های ساده هستند. یعنی در آنها، حلقه و یال موازی وجود ندارد.

نکته

اگر G یک جنگل با $$n$$ راس و $$k$$ مولفه باشد، پس $$G$$ به اندازه $$n-k$$ یال دارد.

اثبات: هر یک از گزاره‌های قضیه ۲ را به هر یک از مولفه‌های گراف G اعمال کنید.

به راحتی می‌توان مشاهده کرد که اگر یک جنگل یک مولفه داشته باشد، به یک درخت تبدیل می‌شود و طبق تبصره بالا، $$n-1$$ یال دارد که یک گزاره صحیح است.

درخت پوشا

گراف همبند $$G$$ و یک دور از این گراف را در نظر بگیرید. تعدادی از یال‌های این دور از گراف را به گونه‌ای حذف می‌کنیم که گراف همچنان همبند باقی بماند. فرض کنید حذف دورها را آنقدر ادامه دهیم تا دیگر دوری باقی نماند. گرافی که باقی می‌ماند یک درخت است که در آن، تمامی رأس‌ها به هم متصل هستند. به این درخت، درخت پوشای گراف $$G$$ گفته می‌شود. تعریف ساده‌تر درخت پوشا به این صورت است:

اگر $$G$$ یک گراف همبند باشد، زیرگراف $$H$$ از $$G$$ یک درخت پوشا نامیده می‌شود، اگر:

  • $$H$$ یک درخت باشد.
  • $$H$$ شامل همه رئوس $$G$$ باشد.

در شکل زیر یک گراف و یکی از درخت‌های پوشای آن نشان داده شده است:

یک گراف و درخت پوشای آن
شکل ۵: یک گراف و درخت پوشای آن

همانطور که مشاهده مش‌کنیم، این درخت همه رئوس گراف اصلی را شامل می‌شود و تعداد یال‌های آن، یکی کمتر از تعداد رئوس آن است. پس این درخت،‌ یک درخت پوشای گراف $$G$$ است.

در نتیجه، یک درخت پوشا از گراف بدون جهت $$G$$، زیرگرافی است که همه رئوس $$G$$ را شامل می‌شود.

درجه مدار

فرض کنید $$G$$ یک گراف همبند با $$n$$ رأس و $$m$$ یال باشد. درخت پوشای $$T$$ از گراف $$G$$ شامل $$n-1$$ یال است. بنابراین تعداد یال‌هایی که لازم است از گراف $$G$$ حذف کنیم تا به یک درخت پوشای بدون حلقه برسیم عبارت است از : $$m-(n-1)$$. این عدد، درجه مداری گراف نامیده می‌شود.

مثال ۳

در یک گراف تعداد یال‌ها برابر ۷ و تعداد رئوس برابر با ۵ است. درجه مداری این گراف عبارت است از:

$$G=m-(n-1)=7-(5-1)=3$$

مثال ۴

اگر $$G$$ یک گراف همبند با ۶ رأس و درجه هر رأس ۳ باشد، درجه مداری $$G$$ را بیابید.

حل: با استفاده از قضیه مجموع مرتبه‌های رئوس خواهیم داشت:

$$\sum_{i=1}^n deg(V_i)= 2 |E|$$

$$6\times 3 = 2 |E| \to |E| = 9$$

$$Circuit \, Rank = |E| - (|V|-1)= 9- (6-1)=4$$

در صورتی که مباحث بیان شده برای شما مفید بوده و می‌خواهید درباره سایر موضوعات مربوط به ریاضیات مطالب بیشتری یاد بگیرید، آموزش‌های زیر به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۱۵ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
Introduction to Graph TheoryIntroduction to Graph Theory (2nd Edition)Toturialspoint
۱ دیدگاه برای «درخت در گراف — به زبان ساده»

سلام برای بدست آوردن تعداد مسیر های (مثلا سه تایی) در یک گراف درختی باید چیکار کرد!؟
ممنون میشم راهنمایی کنین🙏🙏🙏

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *