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

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

خواص

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

مثال‌

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

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

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

منابع

• ریاضیات گسسته و کاربردهای آن (انگلیسی)

1. Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, p. 5, ISBN 0-444-19451-7.
2. Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6. Electronic edition, page 17.
3. Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40.
4. Knuth, Donald E. (2013), "Two thousand years of combinatorics", in Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37, ISBN 0191630624 {{citation}}: External link in |contributionurl= (help); Unknown parameter |contributionurl= ignored (|contribution-url= suggested) (help).
5. Read, Ronald C.; Wilson, Robin J. (1998), An Atlas of Graphs, Clarendon Press, p. ii, ISBN 9780198532897.
6. Garey, Michael R.; Johnson, David S. (1979), "[GT24] Balanced complete bipartite subgraph", Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, p. 196, ISBN 0-7167-1045-5.
7. Biggs, Norman (1993), Algebraic Graph Theory, Cambridge University Press, p. 181, ISBN 9780521458979.
8. Jungnickel, Dieter (2012), Graphs, Networks and Algorithms, Algorithms and Computation in Mathematic, vol. 5, Springer, p. 557, ISBN 9783642322785.
9. Lovász, László; Plummer, Michael D. (2009), Matching theory, Providence, RI: AMS Chelsea, p. 109, ISBN 978-0-8218-4759-6, MR 2536865. Corrected reprint of the 1986 original.