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

گراف‌های کامل دوبخشی (Complete bipartite graphs) به گراف‌های کاملی گفته می‌شود که در آن‌ها مجموعهٔ رأس‌ها را بتوان به دو زیرمجموعهٔ $V_1$ و $V_2$ افراز کرد، به‌گونه‌ای که هر راس از مجموعه $V_1$ به تمام رئوس مجموعه $V_2$ متصل باشد. اگر $|V_1|=n$ و $|V_2|=m$ باشد، گراف کامل دوبخشیی که از این دو مجموعه رئوس ساخته میشود را معمولاً با $K_{n,m}$ نمایش می‌دهند. آغاز نظریه گراف‌ها معمولاً با کار اویلر بر روی هفت پلِ کونیکسبرگ در سال ۱۷۳۶ گره خورده است. با این حال، تاریخچه گرافهای کامل دوبخشی به رسم‌های رامون یوی در سال ۱۶۶۹ بازمی‌گردد.

خواص

• پیدا کردن جواب این سؤال که آیا یک گراف دوبخشی یک زیرگراف کامل دو بخشی به فرمِ $K_{i,i}$ دارد ان‌پی‌کامل است.
• هر گراف کامل دو‌بخشی $K_{n,n}$ یک گراف‌مور و یک cage از نوع $(n,4)$ است.
• هر گراف کامل دوبخشی $K_{n,m}$ به تعداد$n^{m-1}{m}^{n-1}$ درخت پوشا دارد.
• $K_{1,n}$ به ازای هر $n$ دلخواه هم یک ستاره هم یک درخت است.
• $K_{1,3}$ در اصطلاح نظریه گراف‌ها پنجه نام دارد و برای ساخت گرافهای پنجه آزاد بکار بگرفته می‌شود.

مثال‌

گراف پایین ۵ راس دارد، دو راس آن به یکدیگر متصل نیستند ولی به تمام سه راس دیگر متصلند، همچنین سه راس گراف به یکدیگر متصل نیستند ولی به دو راس دیگر متصلند. این گراف در نظریه گراف‌ها با $K_{2,3}$ نمایش داده می‌شود.

جستارهای وابسته

• گراف‌های کامل

منابع

• ریاضیات گسسته و کاربردهای آن الگو:نشان زبان