گراف و مدل‌سازی (ریاضیات گسسته)

گراف در زندگی واقعی

گراف مدلی ریاضی برای ارتباطات است. هر بار که چیزی به چیز دیگری وصل است، می‌توان آن را با گراف مدل کرد.

مفاهیم پایه

تعریف: گراف $G = (V, E)$ ادامهٔ فرمول را افقی ببین شامل مجموعهٔ رئوس $V(G)$ ادامهٔ فرمول را افقی ببین (هرگز خالی نیست) و مجموعهٔ یال‌ها $E(G)$ ادامهٔ فرمول را افقی ببین (می‌تواند خالی باشد) است. هر یال $e \in E$ ادامهٔ فرمول را افقی ببین یک زوج نامرتب $\{u, v\}$ ادامهٔ فرمول را افقی ببین از رئوس است.

مرتبه و اندازه و درجه: $p(G)=|V(G)|$ ادامهٔ فرمول را افقی ببین مرتبه، $q(G)=|E(G)|$ ادامهٔ فرمول را افقی ببین اندازه، $\deg(v)$ ادامهٔ فرمول را افقی ببین تعداد یال‌های متصل به $v$ ادامهٔ فرمول را افقی ببین، و $\Delta(G)$ ادامهٔ فرمول را افقی ببین و $\delta(G)$ ادامهٔ فرمول را افقی ببین به ترتیب ماکزیمم و مینیمم درجه‌اند. رأس با درجهٔ صفر ایزوله و با درجهٔ یک برگ نام دارد.

قضیهٔ اساسی مجموع درجات (دست‌دادن)

قضیه: در هر گراف $G$ ادامهٔ فرمول را افقی ببین با $p$ ادامهٔ فرمول را افقی ببین رأس و $q$ ادامهٔ فرمول را افقی ببین یال:
$\sum_{v \in V(G)} \deg(v) = 2q$

اثبات: هر یال $\{u,v\}$ ادامهٔ فرمول را افقی ببین یک‌بار در $\deg(u)$ ادامهٔ فرمول را افقی ببین و یک‌بار در $\deg(v)$ ادامهٔ فرمول را افقی ببین شمرده می‌شود، پس هر یال دقیقاً دو بار محاسبه می‌شود.

نتیجهٔ طلایی: تعداد رئوس فرد در هر گراف، عددی زوج است.

این نتیجه ابزار اصلی رد کردن سناریوهای ناممکن است: اگر شمارش رئوس فرد به عددی فرد برسد، آن گراف اصلاً وجود ندارد.

انواع گراف‌ها

نوع	یال چندگانه	طوقه
گراف ساده	✗	✗
چندگراف	✓	✗
شبه‌گراف	✓	✓

در این درس گراف = گراف ساده است مگر تصریح دیگری شود.

گراف کامل $K_n$ ادامهٔ فرمول را افقی ببین: هر دو رأس مجاورند، پس $\deg(v) = n-1$ ادامهٔ فرمول را افقی ببین و

q(K_n) = \binom{n}{2} = \frac{n(n-1)}{2}

گراف دوبخشی $K_{m,n}$ ادامهٔ فرمول را افقی ببین: رئوس به دو دستهٔ $A$ ادامهٔ فرمول را افقی ببین و $B$ ادامهٔ فرمول را افقی ببین تقسیم می‌شوند و هر یال یک سر در $A$ ادامهٔ فرمول را افقی ببین و یک سر در $B$ ادامهٔ فرمول را افقی ببین دارد؛ هیچ یالی درون یک دسته نیست. تعداد یال‌ها $q(K_{m,n}) = m \cdot n$ ادامهٔ فرمول را افقی ببین است.

گراف منتظم: اگر $\deg(v)=k$ ادامهٔ فرمول را افقی ببین برای همهٔ رئوس باشد، گراف $k$ ادامهٔ فرمول را افقی ببین-منتظم است و از قضیهٔ مجموع درجات:

q = \frac{kn}{2}

این رابطه خودش آزمون وجود است: اگر $kn$ ادامهٔ فرمول را افقی ببین فرد شود، چنین گرافی وجود ندارد.

گراف مکمل $\bar{G}$ ادامهٔ فرمول را افقی ببین: همان رئوس $G$ ادامهٔ فرمول را افقی ببین، ولی یال $uv$ ادامهٔ فرمول را افقی ببین دقیقاً وقتی در $\bar{G}$ ادامهٔ فرمول را افقی ببین هست که در $G$ ادامهٔ فرمول را افقی ببین نباشد.

q(G) + q(\bar{G}) = \frac{n(n-1)}{2} \qquad \deg_{\bar{G}}(v) = (n-1) - \deg_G(v)

گراف	رئوس	یال‌ها	منتظم؟
$P_n$ ادامهٔ فرمول را افقی ببین	$n$ ادامهٔ فرمول را افقی ببین	$n-1$ ادامهٔ فرمول را افقی ببین	خیر
$C_n$ ادامهٔ فرمول را افقی ببین	$n$ ادامهٔ فرمول را افقی ببین	$n$ ادامهٔ فرمول را افقی ببین	بله (۲-منتظم)
$K_n$ ادامهٔ فرمول را افقی ببین	$n$ ادامهٔ فرمول را افقی ببین	$\frac{n(n-1)}{2}$ ادامهٔ فرمول را افقی ببین	بله
$K_{m,n}$ ادامهٔ فرمول را افقی ببین	$m+n$ ادامهٔ فرمول را افقی ببین	$mn$ ادامهٔ فرمول را افقی ببین	فقط اگر $m=n$ ادامهٔ فرمول را افقی ببین

گراف جهت‌دار: هر یالش جهت دارد؛ درجهٔ خروجی $d^+(v)$ ادامهٔ فرمول را افقی ببین و درجهٔ ورودی $d^-(v)$ ادامهٔ فرمول را افقی ببین تعریف می‌شوند و همواره $\sum d^+(v) = \sum d^-(v) = |E|$ ادامهٔ فرمول را افقی ببین.

همبندی و مسیرها

مفهوم	تعریف
قدم	دنبالهٔ رئوس که هر دو متوالی مجاورند (تکرار مجاز)
دنباله	قدمی که یال‌هایش متمایزند
مسیر	قدمی که رئوسش متمایزند
دور	مسیری که رأس اول و آخرش یکی است

نکتهٔ کنکوری: هر مسیر یک دنباله است و هر دنباله یک قدم، ولی عکس آن لزوماً درست نیست.

گراف همبند است اگر بین هر دو رأس مسیری وجود داشته باشد. گراف ناهمبند به زیرگراف‌های همبند بیشینه به نام مؤلفه تقسیم می‌شود.

فاصله و قطر: $d(u,v)$ ادامهٔ فرمول را افقی ببین طول کوتاه‌ترین مسیر، $\text{ecc}(v)=\max_u d(v,u)$ ادامهٔ فرمول را افقی ببین خروج‌مرکزیت، $\text{diam}(G)=\max_{u,v} d(u,v)$ ادامهٔ فرمول را افقی ببین قطر و $\text{rad}(G)=\min_v \text{ecc}(v)$ ادامهٔ فرمول را افقی ببین شعاع است.

احاطه‌گری در گراف

تعریف: $D \subseteq V(G)$ ادامهٔ فرمول را افقی ببین یک مجموعهٔ احاطه‌گر است اگر هر رأس یا خودش در $D$ ادامهٔ فرمول را افقی ببین باشد یا حداقل یکی از همسایه‌هایش در $D$ ادامهٔ فرمول را افقی ببین باشد.

عدد احاطه‌گری $\gamma(G)$ ادامهٔ فرمول را افقی ببین اندازهٔ کوچک‌ترین مجموعهٔ احاطه‌گر است.

کران پایین طلایی:

\gamma(G) \geq \left\lceil \frac{n}{\Delta(G) + 1} \right\rceil

چرا؟ هر رأس انتخاب‌شده خودش و حداکثر $\Delta$ ادامهٔ فرمول را افقی ببین همسایه‌اش را می‌پوشاند، یعنی حداکثر $\Delta+1$ ادامهٔ فرمول را افقی ببین رأس. پس $k(\Delta+1) \geq n$ ادامهٔ فرمول را افقی ببین.

مقادیر معروف:

\gamma(K_n) = 1 \qquad \gamma(K_{1,n}) = 1 \qquad \gamma(P_n) = \gamma(C_n) = \left\lceil \frac{n}{3} \right\rceil \qquad \gamma(K_{n,n}) = 2

مینیمال در برابر مینیمم: مجموعهٔ مینیمال آن است که نتوان عضوی از آن حذف کرد؛ مجموعهٔ مینیمم کوچک‌ترین در کل گراف است. هر مینیمم مینیمال است، ولی عکسش برقرار نیست — و همین‌جا بیشترین اشتباه رخ می‌دهد.

روش عملی یافتن $\gamma(G)$ ادامهٔ فرمول را افقی ببین: اول کران پایین را حساب کن؛ بعد توجه کن که همسایهٔ هر برگ حتماً باید در $D$ ادامهٔ فرمول را افقی ببین باشد و از همان رئوس اجباری شروع کن؛ سپس رئوس پوشش‌نیافته را با رئوس پردرجه بپوشان.

مطالب فراتر از کتاب

درسنامهٔ کامل این مباحث را هم پوشش می‌دهد: درجه‌دنباله و قضیهٔ اردوس-گالای (شرط لازم و کافی برای اینکه یک دنبالهٔ عددی اصلاً درجه‌دنبالهٔ گرافی باشد)، رنگ‌آمیزی رأسی و عدد رنگی $\chi(G)$ ادامهٔ فرمول را افقی ببین به‌همراه کران $\chi(G) \leq \Delta(G)+1$ ادامهٔ فرمول را افقی ببین و قضیهٔ بروکس و کاربردش در مسئلهٔ زمان‌بندی، ایزومورفیسم گراف و پنج شرط لازم (و نه کافی) آن، و گراف‌های اویلری و همیلتونی با قضیهٔ اویلر و قضیه‌های دیراک و اور.

خلاصه‌ی درسنامه