سرفصل‌های این مبحث

گراف

گراف دوبخشی

آخرین ویرایش: 09 اسفند 1402

دسته‌بندی: گراف

امتیاز:

نظر کاربران: برای نظر دادن اولین باش!

مقدمه‌ای بر گراف دوبخشی

فرض کنید در یک شرکت صنعتی تعدادی شغل بدون متصدی می‌باشند، تعدادی متقاضی برای این مشاغل اعلام آمادگی نموده‌اند حال این سوال مطرح می‌شود که آیا می‌توان به هر متقاضی شغلی متناسب آن اختصاص داد؟

برای حل چنین مساله‌ای که به مساله تخصیص موسوم است با استفاده از گراف می‌توان وضعیت‌های خاصی را پیاده‌سازی نمود.

بدین ترتیب که گروهی که متقاضی مشاغل هستند در مجموعه $V (G)$ و شغل‌های بدون متصدی را در مجموعه $W (G)$ قرار می‌دهیم.

گراف رسم شده چنین است که بعضی از اعضای مجموعه $V (G)$ یک یا چند عضو از مجموعه $W (G)$ را توسط یال‌ها وصل می‌نماید.

به‌عبارت دیگر، گراف به‌وجود آمده دارای یال‌ها $v_{i} w_{j}$ است که هر متقاضی $v_{i}$ از مجموعه $V (G)$ را به‌شغل‌های متناسب $w_{j}$ از مجموعه $W (G)$ متصل می‌کند.

به‌عبارت دقیق‌تر هیچ دو راس متعلق به مجموع $V (G)$ (متقاضیان) یا هیچ دو راس متعلق به مجموعه $W (G)$ (مشاغل) توسط هیچ یالی به هم وصل نیستند، چنین گرافی را گراف دوبخشی یا دوپارچه می‌گویند.

تعریف گراف دوبخشی

گراف دو بخشی، گرافی است که بتوان مجموعه راس‌های آن را به دو مجموعه $V (G)$ و $W (G)$ چنان افراز کرد که هر یال آن دارای یک انتها در $V (G)$ و یک انتها در $W (G)$ باشد، به‌طوری‌که هیچ دو راس از $V (G)$ یا هیچ دو راس از $W (G)$ با هم مجاور نباشند، چنین افرازی را دوبخشی کردن گراف ساده $G$ می‌نامند.

$V (G) \cap W (G) = \emptyset$

کل رئوس $V (G) \cup W (G) =$

تمرین

اگر داشته باشیم:

$\{\begin{cases} V (G) = {V_{1}, ..., V_{5}} \\ W (G) = {W_{1}, ..., W_{4}} \end{cases}$

یک گراف دوبخشی رسم کنید.

گراف دوبخشی - پیمان گردلو

دریافت مثال

دریافت فایل PDF

قضایا گراف دوبخشی

قضیه

اگر گراف دوبخشی ( $r$ - منتظم) دارای دوبخش $V (G)$ و $W (G)$ باشد، آن‌گاه تعداد عناصر $W (G)$ و $V (G)$ باهم برابرند، یعنی:

$|V (G)| = |W (G)|$

اثبات

فرض می‌کنیم $V (G)$ دارای $m$ راس و $W (G)$ دارای $n$ راس از راس‌های گراف دوبخشی ( $r$ - منتظم) باشند، ثابت می‌کنیم $m = n$ است:

از هر راس در مجموعه $V (G)$ به‌تعداد $r$ یال خارج می‌شود. (چون طبق فرض گراف مورد نظر ( $r$ - منتظم) است)

پس تعداد کل یال‌ها برابر $q = r m$ است.

چون جمعا $m + n$ راس داریم، لذا مطابق قضیه مجموع درجه‌های راس‌ها و تعریف گراف ( $r$ - منتظم) داریم:

$\begin{array}{l} \sum_{}^{} \deg (v_{i}) = r m + r n = r (m + n) = 2 q \end{array}$

$\{\begin{cases} r (m + n) = 2 q \\ q = r m \end{cases}$

$\Rightarrow r (m + n) = 2 (r m)$

$\Rightarrow r m + r n = 2 r m$

$\Rightarrow r n = r m$

$\Rightarrow n = m$

قضیه

اگر در یک گراف ساده و دوبخشی، مرتبه $p$ و اندازه $q$ باشد، آن‌گاه:

$q \leq \frac{p^{2}}{4}$

اثبات

چون گراف $G$ دوبخشی است، لذا بیش‌ترین تعداد یال‌های آن (مطابق قضایای گراف کامل دوبخشی) $u = m n$ خواهد بود که $m$ تعداد راس‌های بخش $V (G)$ و $n$ تعداد راس‌های بخش $W (G)$ است.

توجه کنید که بیش‌ترین تعداد یال، مربوط به زمانی است که گراف دوبخشی کامل باشد که بعدا بحث خواهد شد.

از طرفی می‌دانیم:

$\{\begin{cases} p = m + n \Rightarrow m = p - n \\ u = m n \end{cases}$

$\Rightarrow u = (p - n) n$

$\Rightarrow u = n p - n^{2}$

چون $u$ آهنگ تغییرات تعداد یال‌ها را نشان می‌دهد، پس:

$\begin{array}{l} \frac{d u}{d n} = 0 \Rightarrow p - 2 n = 0 \Rightarrow n = \frac{p}{2} \end{array}$

$\frac{d^{2} u}{d n^{2}} = 0 \Rightarrow - 2 < 0$

پس بیش‌ترین مقدار $u$ در نقطه $n = \frac{p}{2}$ اتفاق می‌افتد، یعنی:

$\max (u) = (\frac{p}{2}) p - {(\frac{p}{2})}^{2}$

$\Rightarrow \max (u) = \frac{p^{2}}{2} - \frac{p^{2}}{4}$

$\Rightarrow \max (u) = \frac{p^{2}}{4}$

بنابراین تعداد کل یال‌ها نمی‌تواند از $\frac{p^{2}}{4}$ بیش‌تر باشد، در نتیجه:

$q \leq \frac{p^{2}}{4}$

دریافت مثال

دریافت فایل PDF

نکته

گرافی دوبخشی است، اگر و تنها اگر شامل هیچ دور با طول فرد نباشد.

تعداد دور به طول $2 k$ در گراف کامل دوبخشی برابر است با:

$(\begin{matrix} m \\ k \end{matrix}) (\begin{matrix} n \\ k \end{matrix}) \frac{k! (k - 1)!}{2}$

دریافت مثال

دریافت فایل PDF

تعریف گراف کامل دوبخشی

در دسته‌ای دیگر از گراف‌های ساده $G = (V, E)$ مجموعه راس زیر را:

$V (G) = \{u_{1}, ... u_{m}, w_{1}, ... w_{n}\}$

می‌توان به دو زیر مجموعه زیر تجزیه کرد:

$\{\begin{cases} u (G) = \{u_{1}, ..., u_{m}\} \\ w (G) = \{w_{1}, ... w_{n}\} \end{cases}$

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

یک گراف کامل دوبخشی با $(m, n)$ راس که به‌صورت $k_{m, n}$ نمایش داده می‌شود که دومجموعه $u (G)$ و $w (G)$ در خاصیت‌های زیر صدق می‌کند:

یک یال از هر راس $u (G)$ مانند $u_{i}$ به هر راس $w (G)$ مانند $w_{j}$ موجود است.
یک یال از هر راس $u (G)$ مانند $u_{i}$ به هر راس $u (G)$ مانند $u_{k}$ موجود نباشد.
یک یال از هر راس $w (G)$ مانند $w_{j}$ به هر راس دیگر $w (G)$ مانند $w_{f}$ موجود نباشد.

تمرین

یک گراف کامل دوبخشی $k_{3, 3}$ نشان دهید:

گراف دوبخشی - پیمان گردلو

یک گراف کامل دوبخشی $k_{3, 4}$ نشان دهید:

گراف دوبخشی - پیمان گردلو

یک گراف کامل دوبخشی $k_{2, 5}$ نشان دهید:

گراف دوبخشی - پیمان گردلو

دریافت مثال

دریافت فایل PDF

قضایای گراف کامل دوبخشی

قضیه

در یک گراف کامل دو بخشی، داریم:

$q (k_{m, n}) = m n$

$q$ اندازه گراف $k_{m, n}$ است.

اثبات

می‌دانیم گراف $k_{m, n}$ دارای $m$ راس در یک مجموعه و $n$ راس در مجموعه دیگر است و از طرفی تعداد کل راس‌ها $p = m + n$ (مرتبه گراف) می‌باشد:

برای یافتن تعداد یال‌های گراف کامل دوبخشی $k_{m, n}$ ابتدا تعداد کل یال‌های یک گراف کامل از مرتبه $m + n$ را محاسبه می‌کنیم، سپس تعداد کل یال‌هایی که راس‌های دو مجموعه را در خود مجموعه‌ها به‌هم وصل می‌نماید از آن کم می‌کنیم، داریم:

$\begin{array}{l} q (k_{m, n}) = (\begin{array}{l} m + n \\ 2 \end{array}) - [(\begin{array}{l} m \\ 2 \end{array}) + (\begin{array}{l} n \\ 2 \end{array})] \end{array}$

$\begin{array}{l} = \frac{(m + n) (m + n - 1)}{2} - [\frac{m (m - 1)}{2} + \frac{n (n - 1)}{2}] \end{array}$

$\begin{array}{l} = \frac{{(m + n)}^{2} - (m + n)}{2} - \frac{m^{2} + n^{2} - m - n}{2} \end{array}$

$\begin{array}{l} = \frac{(m^{2} + n^{2} + 2 m n) - m - n - m^{2} - n^{2} + m + n}{2} \end{array}$

$\begin{array}{l} = \frac{2 m n}{2} \\ = m n \end{array}$

دریافت مثال

دریافت فایل PDF

قطر گراف کامل دوبخشی

تمام گراف‌های کامل دو‌بخشی به‌غیر از $k_{1, 1}$ قطر $(2)$ دارند، زیرا برای هر دونقطه دل‌خواه در $U (G)$ و $W (G)$ دقیقا به‌فاصله $(2)$ از یک‌دیگر قرار دارند (فاصله، کوتاه‌ترین مسیر بین دو راس بود).

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

به‌عنوان نمونه، به گراف کامل دوبخشی زیر توجه کنید:

گراف دوبخشی - پیمان گردلو

در این گراف اگر از راس $W_{1}$ حرکت می‌کنیم، یک یال ما را به $U_{1}$ می‌رساند و یک یال ما را از $U_{1}$ مثلا به $W_{3}$ می‌رساند یعنی با دو یال به دو راس $W_{1}$ و $W_{3}$ از $W (G)$ رسیدیم.

گراف کامل دوبخشی $k_{1, 1}$ تنها گرافی است که قطرش $(1)$ می‌باشد، زیرا این گراف تنها دو راس دارد و کوتاه‌ترین مسیر بین آنها به طول یک است.

دریافت مثال

دریافت فایل PDF

نکته

1- هر گراف دوبخشی، زیر گراف یک گراف دوبخشی کامل می‌باشد.

2- هر زیر گراف از یک گراف دوبخشی کامل، یک گراف دوبخشی است.

دریافت مثال

دریافت فایل PDF

خرید پاسخ‌ها

گراف دوبخشی

4,000تومان

برای ارسال نظر وارد سایت شوید

گراف

گراف دوبخشی

مقدمه‌ای بر گراف دوبخشی

تعریف گراف دوبخشی

قضایا گراف دوبخشی

تعریف گراف کامل دوبخشی

قضایای گراف کامل دوبخشی

قطر گراف کامل دوبخشی

nenomatica

مجموعه قوانین

دسترسی سریع

آیا می‌خواهید فیلم معرفی را مشاهده نمایید؟