ریاضیات

اف کامل
از ویکیپدیا، دانشنامه آزاد
 
گراف کامل

K 7 ، یک گراف کامل با 7 راس
راس ها
n
یالها
{\ displaystyle \ textstyle {\ frac {n (n-1)} {2}}}
شعاع
{\ displaystyle \ left \ {{\ start {array} {ll} 0 & n \ leq 1 \\ 1 & {\ text {در غیر این صورت}} \ end {array}} \ سمت راست.}
قطر
{\ displaystyle \ left \ {{\ start {array} {ll} 0 & n \ leq 1 \\ 1 & {\ text {در غیر این صورت}} \ end {array}} \ سمت راست.}
ولادت
{\ displaystyle \ left \ {{\ start {array} {ll} \ infty & n \ leq 2 \\ 3 & {\ text {other}} \ end {array}} \ right.}
اتومورفیسم ها
ن ! ( S n )
عدد رنگی
n
شاخص رنگیn اگر n فرد باشدn - 1 اگر n زوج باشد
طیف
{\ displaystyle \ left \ {{\ begin {array} {lll} \ emptyset & n = 0 \\\ چپ \ {0 ^ {1} \ راست \} & n = 1 \\\ چپ \ {(n-1) ^ {1} ، - 1 ^ {n-1} \ راست \} و {\ متن {در غیر این صورت}} \ پایان {آرایه}} \ درست.}
خواص( n - 1) منظمگراف متقارنvertex-transitiveیال انتقالیکاملا منظمانتگرال
نشانه گذاری
K n
جدول گرافها و پارامترها
در ریاضی زمینه نظریه گراف ، یک گراف کامل است ساده گراف بدون جهت که در آن هر جفت از متمایز راس توسط یک یال منحصر به فرد متصل گردد .گراف کامل است گراف جهتدار که در آن هر دو رأس متمایز توسط یک جفت از یال منحصر به فرد (یکی در هر جهت) متصل می شود.
تئوری گراف خود به طور معمول با کار لئونارد اولر در سال 1736 در هفت پل کونیگسببرگ آغاز می شود . با این حال ، نقاشی های گرافهای کامل ، با رئوس آنها روی نقاط یک چند ضلعی منظم ، در قرن سیزدهم ، در کار Ramon Llull ، ظاهر شد . [1] گاهی اوقات از چنین نقاشی به عنوان گل رز عرفانی یاد می شود. [2]
 
فهرست1خواص2هندسه و توپولوژی3مثال ها4همچنین ببینید5منابع6لینک های خارجی
خصوصیات [ ویرایش ]
گراف کامل K n  رئوس  مشخص می شود . برخی منابع ادعا می کنند که حرف K در این علامت مخفف کلمه آلمانی komplett است ، [3] اما نام آلمانی برای یک گراف کامل ، vollständiger Graph ، حاوی حرف K نیست ، و منابع دیگر بیان می کنند که این علامت گذاری به مشارکت Kazimierz Kuratowski به نظریه گراف. [4]
K N دارای N ( N - 1) / 2 یال است (یک عدد مثلثی)، و یک است گراف به طور منظم ازدرجه  N - 1 تمام گرافهای کامل حداکثر کلیک های خودشان هستند . آنها حداکثر به هم متصل شده اند زیرا تنها برش راس که گراف را قطع می کند مجموعه کامل رئوس است. گراف مکمل یک گراف کامل یک گراف خالی است  .
اگر به یالهای یک گراف کامل جهت دهی داده شود ، جهت دار حاصل را یک تورنمنت می نامند .
K N را می توان به تجزیه N درختان T من که T من است من راس. [5] حدس Ringel می پرسد آیا گراف کامل K 2 n +1 می تواند به کپی های هر درخت با n یال تجزیه شود . [6] شناخته شده است که این برای n کاملاً بزرگ درست است . [7] [8]
تعداد تطابق گرافهای کامل توسط شماره های تلفن داده می شود
1 ، 1 ، 2 ، 4 ، 10 ، 26 ، 76 ، 232 ، 764 ، 2620 ، 9496 ، 35696 ، 140152 ، 568504 ، 2390480 ، 10349536 ، 46206736 ، ... (دنباله A000085 در OEIS ).
این اعداد بیشترین مقدار ممکن از شاخص Hosoya را برای یک گراف n -vertex می دهند. [9] تعداد تطابق کامل گراف کامل K n (با n زوج) توسط فاکتوریل مضاعف ( n  - 1) داده می شود !!. [10]
اعداد عبور تا K 27 شناخته شده است، با K 28 نیاز به هم 7233 یا 7234 تسهیل عبور کند. مقادیر بیشتر توسط پروژه عدد تقاطع خطی جمع آوری می شود. [11] اعداد تقاطع خطی برای K n برابر هستند
0 ، 0 ، 0 ، 0 ، 1 ، 3 ، 9 ، 19 ، 36 ، 62 ، 102 ، 153 ، 229 ، 324 ، 447 ، 603 ، 798 ، 1029 ، 1318 ، 1657 ، 2055 ، 2528 ، 3077 ، 3699 ، 4430 ، 5250 ، 6180 ، ... (دنباله A014540 در OEIS ).
هندسه و توپولوژی [ ویرایش ]

مدل چند وجهی تعاملی Csaszar با رئوس نمایانگر گره ها. در تصویر SVG ، ماوس را برای چرخاندن آن حرکت دهید. [12]
یک گراف کامل با n گره نشان دهنده یالهای یک ( n - 1) - ساده است . از نظر هندسی K 3 مجموعه یالهای یک مثلث ، K 4 یک چهار ضلعی و غیره را تشکیل می دهد. چند وجهی Császár ، یک چند وجهی غیر محدب با توپولوژی یک توروس ، گراف کامل K 7 را اسکلت خود دارد . هر پلی پتوپ همسایگی در چهار بعد یا بیشتر نیز دارای اسکلت کاملی است.
K 1 تا K 4 همه گرافهای مسطح هستند . با این حال ، هر نقشه مسطح یک گراف کامل با پنج رئوس یا بیشتر باید دارای یک تقاطع باشد و گراف کامل غیر مسطح K 5 نقشی اساسی در توصیف گرافهای مسطح ایفا می کند: توسط قضیه کوراتوفسکی، یک گراف مسطح است اگر و فقط اگر باشد شامل نه K 5 و نه گراف دوبخشی کامل K 3،3 به عنوان یک بخش فرعی، و با واگنر قضیه را همان نتیجه نگه می دارد برای افراد زیر سن قانونی گراف به جای تقسیم بندی. به عنوان بخشی از خانواده پیترسن ، K 6نقش مشابهی را به عنوان یکی از خردسالان ممنوع برای تعبیه بدون لینک بازی می کند . [13] به عبارت دیگر ، و همانطور که کانوی و گوردون [14] ثابت کردند ، هر تعبیه K 6 در فضای سه بعدی به طور ذاتی با حداقل یک جفت مثلث پیوند خورده پیوند می خورد. کانوی و گوردون همچنین نشان دادند که هر تعبیه سه بعدی K 7 شامل یک چرخه همیلتونی است که به عنوان یک گره غیرتعارفی در فضا تعبیه شده است .
مثالها [ ویرایش ]
گرافهای کامل روی n رئوس ، برای n بین 1 تا 12 ، در زیر به همراه تعداد یالها نشان داده شده است:
K 1 : 0
K 2 : 1
K 3 : 3
K 4 : 6




K 5 : 10
K 6 : 15
K 7 : 21
K 8 : 28




K 9 : 36
K 10 : 45
K 11 : 55
K 12 : 66




همچنین به [ ویرایش ] مراجعه کنیدشبکه کاملاً متصل ، در شبکه رایانه ایگراف دو بخشی کامل (یا biclique ) ، گراف مخصوص دو بخشی که در آن هر راس در یک طرف دو قسمت به هر راس در طرف دیگر متصل است
منابع 
https://en.wikipedia.org/wiki/Complete_graph