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

گراف‌های کامل دوبخشی (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}$ نمایش داده می‌شود.

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

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

منابع ویرایش

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

↑ Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, p. 5, ISBN 0-444-19451-7.
↑ ^۲٫۰ ^۲٫۱ Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6. Electronic edition, page 17.
↑ Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40.
↑ 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).
↑ Read, Ronald C.; Wilson, Robin J. (1998), An Atlas of Graphs, Clarendon Press, p. ii, ISBN 9780198532897.
↑ 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.
↑ Biggs, Norman (1993), Algebraic Graph Theory, Cambridge University Press, p. 181, ISBN 9780521458979.
↑ Jungnickel, Dieter (2012), Graphs, Networks and Algorithms, Algorithms and Computation in Mathematic, vol. 5, Springer, p. 557, ISBN 9783642322785.
↑ 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.

[bm2-1] Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, p. 5, ISBN 0-444-19451-7.

[d4-2] ۲٫۰ ^۲٫۱ Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6. Electronic edition, page 17.

[:1-3] Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40.

[knuth-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.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]