گشت، گذر، مسیر، اکسترمال

تا کنون هر چه که از گراف دیدیم تفاوت خاصی با ساختار های معمول در ریاضیات مانند لیست ها و مجموعه ها نداشت. اما با تعاریف این بخش می توانیم قضایایی را ثابت کنیم که بدون استفاده از گراف، بسیار پیچیده به نظر می رسند.

گشت

به یک دنباله مانند دنباله \(v_1e_1v_2e_2...v_{k-1}e_{k-1}v_k\) گشت می گوییم اگر و تنها اگر v ها راس و e ها یال باشند و هر یال بین دو راس مربوط به خودش قرار گرفته باشد. اگر گراف را مانند یک شهر در نظر بگیریم که جاده های آن یال های گراف هستند، حرکت یک موجود در این شهر یک گشت است.

اگر راس سر و ته گشت یکی باشند (موجود به نقطه ابتدایی اش برگشته باشد) به این گشت یک گشت بسته می گوییم.

گذر

گذر گشتی است که یال تکراری نداشته باشد. به یک گذر که راس ابتدا و انتهای آن یکی باشد، مشابه قسمت قبل، یک گذر بسته می گوییم.

دور و مسیر

مسیر، گشتی است که راس تکراری نداشته باشد. واضح است که هر مسیری یک گذر نیز هست. طبق تعریف، مسیری که راس ابتدا و انتهای آن یکی باشد وجود ندارد. (به استثنای مسیر های یک راسی) اما اگر در گشتی، تنها راس ابتدا و انتها یکی بودند، به آن گشت یک دور می گوییم. گشت های یک راسی دور حساب نمی شوند.

چند مثال

تعاریف بالا اگر چه تعاریف ساده ای هستند اما در اثبات قضایای گراف کمک بسیاری به ما خواهند کرد. در زیر چند مثال با هم می بینیم.

اگر گشتی بین دو راس وجود داشته باشد، مسیری بین آن دو وجود دارد

منظور از گشت بین دو راس u و v ،گشتی است که راس ابتدای آن u و راس انتهای آن v باشد. برای اثبات گزاره، کافیست که بین تمام گشت های بین این دو، گشتی را در نظر بگیریم که کمترین یال را دارد. این گشت، یک مسیر است چون اگر راس تکراری داشته باشد، یعنی گشت به صورت

\[v_1e_1 .. e_{i-1} x e_i ... x e_j .... e_{k-1}v_k\]

باشد، گشتی با یال کمتر وجود دارد (گشت زیر)

\[v_1e_1 .. e_{i-1} x e_j .... e_{k-1}v_k\]

که با فرض ما در تناقض است.

اگر درجه تمام رئوس حداقل ۲ باشد، در گراف دور وجود دارد

گراف های بدون دور خواص جالبی دارند که آن ها را به طور گسترده در فصل ۲ بررسی خواهیم کرد. اما اکنون به این قضیه که در گراف بدون دور حتما راسی با درجه کمتر از ۲ وجود دارد، بسنده می کنیم.

برای اثبات، بلند ترین مسیر (یعنی مسیری که بیشترین یال ممکن را دارد) را در نظر می گیریم. توجه کنید که اگر در استدلال مان بلند ترین گشت را در نظر می گرفتیم، استدلال ما معتبر نبود و ممکن بود به نتایج نادرستی برسد زیرا بزرگترین گشت ممکن است وجود نداشته باشد. اما چون هر مسیر حداکثر n راس و بنابراین n-1 یال دارد، می توان بلند ترین مسیر موجود در گراف را در نظر گرفت.

راس ابتدای این مسیر، نمی تواند به راسی خارج از این مسیر یال داشته باشد چون در این صورت مسیری بزرگتر وجود داشت. پس تمام یال های این راس درون همین مسیر هستند. و چون درجه این راس حداقل ۲ است، به جز راس مجاورش در مسیر حتما به یک راس دیگر نیز یال دارد و این یعنی دور وجود دارد (نیازمند تصویر برای واضح شدن)

یال های هر گرافی که تمام درجاتش زوج باشد را می توان به دور ها افراز کرد

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