انتخاب های اکسترمالی¶
در فصل های قبل دیدیم که چگونه می توان با انتخاب یک چیز که خاصیت بزرگترین یا کوچکترین بودن را دارد، می توان مسائل را به راحتی اثبات کرد. برای مثال بلند ترین مسیر یک انتخاب اکسترمالی متداول است که خاصیت های آن در حل مسائل به ما کمک می کند. در این بخش با انتخاب های اکسترمالی دیگر آشنا می شویم.
هر انتخاب اکسترمالی خواصی دارد که می تواند در حل مسائل به ما کمک کند. در ادامه صرفا خواص را ذکر می کنیم و اثبات این خواص (که عموما ساده است) به خواننده واگذار می شود.
کوتاه ترین مسیر بین دو راس¶
خواص¶
- هیچ راسی از خارج این مسیر به دو راس در این مسیر که ۳ یال یا بیشتر فاصله دارند یال ندارد
- در نتیجه گزاره بالا، هر راس از خارج به حداکثر ۳ راس درون این مسیر یال دارد
- زیر گراف القایی رئوس این مسیر خود این مسیر است و هیچ یال دیگری در آن وجود ندارد
بلند ترین مسیر گراف¶
خواص¶
- تمام رئوس مجاور راس های ابتدا و انتهای این مسیر، درون این مسیر هستند.
- هیچ دو راس متوالی همسایه مشترک خارج از مسیر ندارند.
- اگر سر و ته این مسیر به هم متصل باشند، این مسیر تمام رئوس مولفه اش را داراست.
کوچک ترین دور¶
خواص¶
- زیر گراف القایی رئوس این دور خود این دور است و هیچ یال دیگری در آن وجود ندارد
- اگر طول این دور از ۴ بیشتر باشد، هر راس از بیرون این دور حداکثر به یک راس از این دور یال دارد.
این کتاب توسط مشارکت کنندگان شاززز به وجود آمده است.
این کتاب عمومی است و تحت پروانه cc-by-sa در دسترس است.
آخرین به روز رسانی در ژوئن 09, 2022.
