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

گراف‌های کامل دوبخشی (Complete bipartite graphs) به گراف‌های کاملی گفته می‌شود که در آن‌ها مجموعهٔ رأس‌ها را بتوان به دو زیرمجموعهٔ   و  افراز کرد، به‌گونه‌ای که هر راس از مجموعه  به تمام رئوس مجموعه  متصل باشد... Electronic edition, page 17. اگر   و   باشد، گراف کامل دوبخشیی که از این دو مجموعه رئوس ساخته میشود را معمولاً با  نمایش می‌دهند. آغاز نظریه گراف‌ها معمولاً با کار اویلر بر روی  هفت پلِ کونیکسبرگ در سال ۱۷۳۶ گره خورده است.Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40. با این حال، تاریخچه گرافهای کامل دوبخشی به رسم‌های رامون یوی در سال ۱۶۶۹ بازمی‌گردد...

 خواص 

 پیدا کردن جواب این سؤال که آیا یک گراف دوبخشی یک زیرگراف کامل دو بخشی به فرمِ  دارد ان‌پی‌کامل است..
 هر گراف کامل دو‌بخشی  یک گراف‌مور و یک cage از نوع  است..
 هر گراف کامل دوبخشی  به تعداد درخت پوشا دارد..
 به ازای هر  دلخواه هم یک ستاره هم یک درخت است.
  در اصطلاح نظریه گراف‌ها پنجه نام دارد و برای ساخت گرافهای پنجه آزاد بکار بگرفته می‌شود.. Corrected reprint of the 1986 original.

 مثال‌ 
گراف پایین ۵ راس دارد، دو راس آن به یکدیگر متصل نیستند ولی به تمام سه راس دیگر متصلند، همچنین سه راس گراف به یکدیگر متصل نیستند ولی به دو راس دیگر متصلند. این گراف در نظریه گراف‌ها با  نمایش داده می‌شود.

160px

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

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

 منابع 

 ریاضیات گسسته و کاربردهای آن 

رده:خانواده‌های پارامتری گراف‌ها