گشت، گذر، مسیر، اکسترمال¶
تا کنون هر چه که از گراف دیدیم تفاوت خاصی با ساختار های معمول در ریاضیات مانند لیست ها و مجموعه ها نداشت. اما با تعاریف این بخش می توانیم قضایایی را ثابت کنیم که بدون استفاده از گراف، بسیار پیچیده به نظر می رسند.
گشت¶
به یک دنباله مانند دنباله \(v_1e_1v_2e_2...v_{k-1}e_{k-1}v_k\) گشت می گوییم اگر و تنها اگر v ها راس و e ها یال باشند و هر یال بین دو راس مربوط به خودش قرار گرفته باشد. اگر گراف را مانند یک شهر در نظر بگیریم که جاده های آن یال های گراف هستند، حرکت یک موجود در این شهر یک گشت است.
اگر راس سر و ته گشت یکی باشند (موجود به نقطه ابتدایی اش برگشته باشد) به این گشت یک گشت بسته می گوییم.
در گراف بالا، \(a1b4d6d\) و \(b1a1b2a1b3c\) و \(a1b4d5c3b4d4b2a\) مثال هایی از گشت هستند. گشت آخر، یک گشت بسته است. طول یک گشت را تعداد یال های آن تعریف می کنیم. گشت های بالا به ترتیب به طول ۳ و ۵ و ۷ می باشند. اگر گراف ساده بود، ذکر دنباله رئوس کافی بود و نیازی نبود یال ها را نام گذاری کنیم و آن ها را درون گشت معین کنیم.
گذر¶
گذر گشتی است که یال تکراری نداشته باشد. به یک گذر که راس ابتدا و انتهای آن یکی باشد، مشابه قسمت قبل، یک گذر بسته می گوییم.
در گراف بالا، \(a1b4d6d\) و \(a1b4d5c3b2a\) مثال هایی از گذر هستند. گذر آخر، یک گذر بسته است.
دور و مسیر¶
مسیر، گشتی است که راس تکراری نداشته باشد. واضح است که هر مسیری یک گذر نیز هست. طبق تعریف، مسیری که راس ابتدا و انتهای آن یکی باشد وجود ندارد. (به استثنای مسیر های یک راسی یا به طول صفر) اما اگر در گشتی، تنها راس ابتدا و انتها یکی بودند، به آن گشت یک دور می گوییم. گشت های یک راسی (صفر یالی یا به طول صفر) دور حساب نمی شوند. اگر یک گراف ساده باشد، دور به طول یک و دو نیز ندارد.
در گراف بالا، \(a1b3c5d\) یک مسیر و \(a1b2a\) و \(d6d\) و \(b3c5d4b\) دور های این گراف هستند.
چند مثال¶
تعاریف بالا اگر چه تعاریف ساده ای هستند اما در اثبات قضایای گراف کمک بسیاری به ما خواهند کرد. در زیر چند مثال با هم می بینیم.
اگر گشتی بین دو راس وجود داشته باشد، مسیری بین آن دو وجود دارد¶
منظور از گشت بین دو راس u و v ،گشتی است که راس ابتدای آن u و راس انتهای آن v باشد. برای اثبات گزاره، کافیست که بین تمام گشت های بین این دو، گشتی را در نظر بگیریم که کمترین یال را دارد. این گشت، یک مسیر است چون اگر راس تکراری داشته باشد، یعنی گشت به صورت
باشد، گشتی با یال کمتر وجود دارد (گشت زیر)
که با فرض ما در تناقض است.
اگر درجه تمام رئوس حداقل ۲ باشد، در گراف دور وجود دارد¶
گراف های بدون دور خواص جالبی دارند که آن ها را به طور گسترده در فصل ۲ بررسی خواهیم کرد. اما اکنون به این قضیه که در گراف بدون دور حتما راسی با درجه کمتر از ۲ وجود دارد، بسنده می کنیم.
برای اثبات، بلند ترین مسیر (یعنی مسیری که بیشترین یال ممکن را دارد) را در نظر می گیریم. توجه کنید که اگر در استدلال مان بلند ترین گشت را در نظر می گرفتیم، استدلال ما معتبر نبود و ممکن بود به نتایج نادرستی برسد زیرا بلند ترین گشت ممکن است وجود نداشته باشد. اما چون هر مسیر حداکثر n راس و بنابراین n-1 یال دارد، می توان بلند ترین مسیر موجود در گراف را در نظر گرفت.
راس ابتدای این مسیر، نمی تواند به راسی خارج از این مسیر (مثلا راس قرمز) یال داشته باشد چون در این صورت مسیری بزرگتر وجود داشت. پس تمام یال های این راس درون همین مسیر هستند. و چون درجه این راس حداقل ۲ است، به جز راس مجاورش در مسیر حتما به یک راس دیگر نیز یال دارد (یال خط چین) و این یعنی دور وجود دارد.
یال های هر گرافی که تمام درجاتش زوج باشد را می توان به دور ها افراز کرد¶
اگر گراف بدون یال باشد که حکم اثبات شده است. در غیر این صورت، اگر راس های درجه صفر را در نظر نگیریم طبق گزاره بالا در گراف یک دور وجود دارد. آن دور را به عنوان یک مجموعه از افراز در نظر می گیریم و آن را حذف می کنیم. از درجه رئوس داخل دور دقیقا دو واحد کم می شود و بنابراین درجه های گراف حاصل نیز هم چنان زوج می ماند. آن قدر این کار را ادامه می دهیم تا گراف خالی از یال شود و به این ترتیب افراز مورد نظر به دست آمده است.
چند تعریف دیگر¶
طول یک گشت: به تعداد یال های یک گشت، همانطور که اشاره شد، طول آن گشت می گوییم. این تعریف به گذر و مسیر نیز تعمیم داده می شود. مثلا همانطور که خواندیم \(P_n\) گراف مسیر است. طول این مسیر، \(n-1\) است.
فاصله بین دو راس: طول کوتاه ترین مسیر بین دو راس را فاصله بین آن دو می گویند. اگر مسیری وجود نداشته باشد، فاصله را بی نهایت تعریف می کنیم.
کمر گراف: کوتاه ترین دور گراف که بیش از ۲ راس داشته باشد. اگر گراف دور نداشته باشد، کمر آن را بی نهایت تعریف می کنیم.
مسیر و دور همیلتونی: منظور مسیر یا دوری است که تمام رئوس گراف را شامل شود.
این کتاب توسط مشارکت کنندگان شاززز به وجود آمده است.
این کتاب عمومی است و تحت پروانه cc-by-sa در دسترس است.
آخرین به روز رسانی در ژوئن 09, 2022.
