بودجهٔ مرور پیشنهادی
ریاضیات گسسته دوازدهم / فصل ۲از شکل تا پاسخ، در سه ایستگاه
من راهنمای منطق رندو هستم. بیا هر شکل را اول با هم به فهرست رأسها، یالها و همسایگیها تبدیل کنیم تا حدس دیداری جای محاسبه را نگیرد.
نام رأسها را دنبال کن، هر یال را یک بار ثبت کن و نتیجه را با قضیهٔ دستدادن بیازما.
واژههای نزدیک را جدا نگه دار
گراف ساده، حلقه و یال موازی ندارد
گراف G=(V,E) از مجموعهٔ ناتهی رأسها و مجموعهٔ یالها ساخته میشود. در گراف ساده هر یال دو رأس متمایز را وصل میکند و میان یک جفت رأس بیش از یک یال نداریم.
مرتبه با اندازه فرق دارد
مرتبهٔ گراف تعداد رأسها و اندازهٔ آن تعداد یالهاست. اگر |V|=p و |E|=q، گراف مرتبهٔ p و اندازهٔ q دارد.
همسایگی بسته خود رأس را هم دارد
N(v) فقط همسایههای v را شامل میشود؛ N[v]=N(v)∪{v}. در مسئلهٔ احاطه معمولاً همسایگی بسته تعیینکننده است.
ریاضیات گسسته دوازدهم / فصل ۲هر یال دقیقاً دو بار دیده میشود
قضیهٔ دستدادن، کنترل اصلی است
هر یال به درجهٔ دو سر خود یک واحد میافزاید؛ بنابراین Σ deg(v)=۲|E|. جمع درجهها همیشه زوج است.
تعداد رأسهای فرد زوج است
در جمع درجهها، سهم رأسهای زوج اثری بر زوجوفردی ندارد. چون کل جمع زوج است، تعداد جملههای فرد نیز باید زوج باشد.
درجه در گراف ساده کران دارد
در گراف سادهٔ p رأسی، هر رأس حداکثر با p−۱ رأس دیگر مجاور است؛ پس ۰≤δ(G)≤Δ(G)≤p−۱.
رابطههایی که محاسبه را کوتاه میکنند
درجهٔ رأس در مکمل کاملکننده است
در گراف سادهٔ p رأسی، برای هر رأس v داریم degG(v)+degḠ(v)=p−۱.
اندازههای گراف و مکمل جمع میشوند
هر جفت رأس دقیقاً در یکی از G و Ḡ یال است؛ بنابراین |E(G)|+|E(Ḡ)|=p(p−۱)/۲.
زوجیت بهتنهایی وجود را ثابت نمیکند
اگر گراف سادهٔ r-منتظم و p رأسی باشد، هم ۰≤r≤p−۱ و هم pr=۲|E| لازم است. از زوجبودن pr بهتنهایی وجود گراف را نتیجه نگیر؛ مثلاً برای p=۳, r=۴ حاصلضرب زوج است، اما هر رأس فقط دو همسایهٔ ممکن دارد.
ریاضیات گسسته دوازدهم / فصل ۲گذر، مسیر و دور را با تکرارها تشخیص بده
گذر با مسیرِ کتاب یکی نیست
در این جزوه، دنبالهای از رأسهای پیاپیِ مجاور را «گذر» مینامیم؛ در گذر ممکن است رأس یا یال تکرار شود. در قرارداد کتاب، «مسیر» باید رأسهای دو به دو متمایز داشته باشد؛ پس دیدن هر رأس تکراری، مسیر بودن دنباله را رد میکند.
مسیر رأس تکراری ندارد
در قرارداد کتاب، هیچ رأسی در مسیر تکرار نمیشود. در گراف ساده، دور دنبالهای بسته با طول دستکم ۳ است که فقط رأس آغاز و پایان آن یکی است؛ هیچ رأس دیگری و هیچ یالی تکرار نمیشود. بنابراین دنبالهٔ u,v,u دور نیست، زیرا همان یک یال را دوبار میپیماید.
همبندی یعنی وجود مسیر برای هر جفت
گراف همبند است اگر میان هر دو رأس آن مسیری وجود داشته باشد. برای رد همبندی، کافی است دو رأس از مؤلفههای جدا پیدا کنی.
کمینه را با دو نیمهٔ اثبات بساز
احاطهگر همه را میپوشاند
مجموعهٔ D احاطهگر است اگر هر رأس بیرون D با دستکم یک رأس در D مجاور باشد. رأسهای داخل مجموعه خودبهخود پوشیدهاند.
مینیمال با مینیمم یکی نیست
احاطهگر مینیمال با حذف هر عضو خاصیتش را از دست میدهد؛ احاطهگر مینیمم کمترین اندازه را میان همهٔ احاطهگرها دارد. هر مینیمم، مینیمال است؛ عکس الزاماً درست نیست.
ستاره مثال نقض روشن میدهد
در K۱,۳، مجموعهٔ هر سه برگ احاطهگر مینیمال با اندازهٔ ۳ است؛ اما رأس مرکز بهتنهایی احاطهگر مینیمم با اندازهٔ ۱ است.
ریاضیات گسسته دوازدهم / فصل ۲پاسخ گرافی را به زبان مسئله برگردان
رأس و یال باید معنای صریح داشته باشند
پیش از حل بنویس هر رأس نمایندهٔ چه چیزی و هر یال نمایندهٔ کدام رابطه است. دو مدل با رأسهای یکسان و تعریف یال متفاوت، پاسخهای متفاوت میسازند.
قیدهای عددی را قبل از رسم حل کن
از Δ+۲δ=۱۷ و Δ−δ=۲ میگیریم δ=۵ و Δ=۷. پس مرتبه دستکم ۸ است؛ عبارت «کمترین مرتبه» برای محدودشدن مسئله ضروری است.
کمینه همیشه به کران و شاهد نیاز دارد
هر رأس انتخابی حداکثر خودش و Δ همسایه را میپوشاند؛ پس برای گراف p رأسی، γ(G)≥⌈p/(Δ+۱)⌉. اگر احاطهگری هماندازهٔ این کران پیدا شود، کمینه اثبات شده است؛ اگر پیدا نشود، برابری نتیجه نمیشود و به کران قویتر یا استدلال دیگری نیاز داریم.
- رأس و یال را معنا کردهام.
- جمع درجهها را کنترل کردهام.
- برای کمینه، هم کران و هم شاهد دارم.