ریاضیات

​
 
گراف کامل دو بخشی
​
یک گراف کامل دو بخشی با m = 5 و n = 3
رگه ها
n + m
یال ها
mn
شعاع
​
قطر
​
ولادت
​
اتومورفیسم ها
​
عدد رنگی
2
شاخص رنگی
حداکثر { M ، n }
طیف
​
نشانه گذاری
​
جدول گرافها و پاراMها
در حوزه ریاضی نظریه گراف ، گراف کامل یا دو سو یک نوع دوتایی کامل نوع خاصی از گراف دو بخشی است که در آن هر راس مجموعه اول به هر راس مجموعه دوم متصل می شود. [1] [2]
تئوری گراف خود به طور معمول با کار لئونارد اولر در سال 1736 در هفت پل کونیگسببرگ آغاز می شود . با این حال ، در اوایل سال 1669 ، در ارتباط با نسخه ای از آثار Ramon Llull ، ویرایش شده توسط Athanasius Kircher ، نقاشی هایی از گرافهای کامل از دو قسمت چاپ شده بودند . [3] [4] خود لول سه قرن قبل نقاشی های مشابهی را از گرافهای کامل انجام داده بود. [3]
 
فهرست1تعریف2مثال ها3خواص4همچنین ببینید5منابع
تعریف [ ویرایش ]
یک گراف دو بخشی کامل ، گرافی است که رئوس آن را می توان به دو زیر مجموعه V 1 و V 2 تقسیم کرد ، به طوری که هیچ یال ای هر دو نقطه انتهایی را در یک زیر مجموعه نداشته باشد ، و هر یال ممکن که بتواند رئوس را در زیر مجموعه های مختلف متصل کند ، بخشی از گراف است. یعنی یک گراف دو بخشی است ( V 1 ، V 2 ، E ) به گونه ای که برای هر دو راس v 1 ∈ V 1 و v 2 ∈ V 2 ، v 1 v 2 یک یال در E است. یک گراف کامل دو بخشی با پارتیشن های اندازه | V 1 | = M و | V 2 | = N ، مشخص است K M، N ؛ [1] [2] هر دو گراف با نماد همان ریخت .
مثالها [ ویرایش ]
​
ستاره گراف K 1،3 ، K 1،4 ، K 1،5 ، و K 1،6 .
​
گراف کامل دو بخشی K 4،7 نشان می دهد که مشکل کارخانه آجر سازی توران با 4 مکان ذخیره (لکه های زرد) و 7 کوره (لکه های آبی) به 18 محل عبور (نقاط قرمز) نیاز داردبرای هر k ، K 1 ، k ستاره می نامند . [2] همه گرافهای دوبخشی کامل که درختان ستاره است.گراف K 1،3 پنجه نامیده می شود و برای تعریف گرافهای بدون پنجه استفاده می شود . [5]گراف K 3،3 را گراف سودمندی می نامند . این کاربرد از یک معمای ریاضی استاندارد حاصل می شود که در آن سه ابزار باید هر کدام به سه ساختمان متصل شوند. به دلیل غیرپلانر بودن K 3،3 ، حل بدون عبور غیرممکن است . [6]حداکثر دودور هایی که به عنوان زیرگرافهای گراف یک رابطه یافت می شوند ، مفاهیم نامیده می شوند . هنگامی که یک شبکه با گرفتن ملاقات ها و پیوستن این زیرگراف ها تشکیل می شود ، رابطه دارای یک شبکه مفهومی القایی است . به این نوع تحلیل روابط ، تحلیل مفهوم رسمی گفته می شود .
خصوصیات [ ویرایش ]
مثال K p ، p گرافهای کامل دو بخشی [7]
K 3،3
K 4،4
K 5،5
​
​
​
​3 یال رنگی
​4 یال رنگی
​5 رنگ یال
چند ضلعی های پیچیده منظم شکل 2 {4} p دارای گرافهای کامل و کامل با 2 p راس (قرمز و آبی) و p 2 2 یال هستند. آنها همچنین می توانند به صورت p -edgeings رنگ آمیزی شوند.با توجه به گراف دوبخشی، تست که آیا آن را شامل دوبخشی زیرگراف کامل K من ، من برای یک پاراM  من یک IS NP کامل مشکل است. [8]گراف مسطح نمی تواند شامل K 3،3 به عنوان یک جزئی ؛ گراف outerplanar نمی تواند شامل K 3،2 به عنوان یک جزئی (اینها شرایط کافی برای planarity و outerplanarity، اما لازم). برعکس ، هر گراف غیرخطی شامل K 3،3 یا گراف کامل K 5 به عنوان جزئی است. این قضیه واگنر است . [9]هر گراف کامل دو بخشی K n ، n یک گراف مور و یک قفس ( n ، 4) است . [10]گرافهای دوتایی کامل K n ، n و K n ، n +1 حداکثر تعداد یال های ممکن را در بین تمام گرافهای بدون مثلث با تعداد راس های یکسان دارند. این قضیه مانتل است . نتیجه مانتل به تعمیم داده شد ک گراف -partite و گراف است که جلوگیری از بزرگتر دار و دسته به عنوان زیرگرافهای در قضیه توران ، و این دو گراف کامل دوبخشی نمونه هایی از هستند گراف توران ، گراف حدی برای این مشکل کلی تر. [11]کامل گراف دو بخشی K M ، N است راس پوشش تعداد از دقیقه { M ، N } و یال پوشش تعداد از حداکثر { M ، N }.گراف کامل دو قطعه K m ، n دارای حداکثر مجموعه مستقل از اندازه حداکثر { m ، n } است.ماتریس مجاورت یک گراف دوبخشی کامل K M ، N مقادیر عددی √ نانوM ، - √ نانوM و 0؛ با ضرب 1 ، 1 و n + m- 2 به ترتیب. [12]ماتریس لاپلاس از گراف دوبخشی کامل K M ، N مقادیر عددی N + M ، N ، M ، و 0؛ با ضرب 1 ، m -1 ، n -1 و 1 به ترتیب.یک گراف کامل دو طرفه K m ، n دارای درختان پوشا m n -1 n m -1 است . [13]گراف دوبخشی کامل K M ، N است تطابق بیشینه اندازه دقیقه { M ، N }.گراف دوبخشی کامل K N ، N است مناسب N یال رنگ آمیزی مربوط به یک مربع لاتین . [14]هر گراف دو بخشی کامل یک گراف مدولار است : هر سه رأس دارای یک میانه است که متعلق به کوتاهترین مسیرها بین هر جفت رأس است. [15]
همچنین به [ ویرایش ] مراجعه کنیدگراف بدون دودور ، یک کلاس از گرافهای پراکنده است که با اجتناب از زیرنویس های کامل دو بخشی تعریف شده استگراف تاج ، گرافی که با حذف یک تطبیق کامل از یک گراف کامل دو بخشی شکل گرفته استگراف چند بخشی کامل ، تعمیم گرافهای کامل دو بخشی به بیش از دو مجموعه راسحمله دودور سواری
منابع 
https://en.wikipedia.org/wiki/Complete_bipartite_graph
​