完全かんぜん圖ず

完全かんぜん图
K7，含有がんゆう7个顶点的てき完全かんぜん图
顶点	n
边	$\textstyle {\frac {n(n-1)}{2}}$
自じ同どう构群	n!（Sn）
色いろ数すう	n n，若わかn为奇数すう n − 1，若わかn为偶数すう
属性ぞくせい	(n-1)-正せい则 顶点传递 边传递 单位距离 强つよ正せい则

在ざい图论中なか，完全かんぜん图是一个简单的无向图，其中每ごと一对不同的顶点都只有一条边相连。完全かんぜん有向ゆうこう图是一いち个有向ゆうこう图，其中每ごと一对不同的顶点都只有一对边相连（每まい个方向ほうこう各かく一いち个）。

图论起源きげん于欧おう拉ひしげ在ざい1736年ねん解かい决七なな桥问题上うえ做的工作こうさく，但ただし是ぜ通どおり过将顶点放ひ在ざい正せい多た边形上じょう来らい绘制完全かんぜん图的尝试，早はや在ざい13世せい纪拉ひしげ蒙こうむ·柳やなぎ利とし 的てき工作こうさく中ちゅう就出现了。这种画が法ほう有ゆう时被称しょう作さく神秘しんぴ玫瑰。

性せい质

在ざい$n$个顶点てん上じょう的てき完全かんぜん图被记作$K_{n}$，有ゆう些文献ぶんけん认为这个记号中ちゅう的てき字母じぼ$K$代表だいひょう德とく文ぶん komplett, 但ただし是ぜ完全かんぜん图的德とく文ぶんvollständiger Graph,并没有ゆう字母じぼ$K$，其他文献ぶんけん认为这个记号是ぜ为了纪念卡齐米べい日にち·库拉托たく夫おっと斯基对图论的贡献。

$K_{n}$有ゆう$n(n-1)/2$条じょう边，并且是ぜ$n-1$正せい则图。所有しょゆう的てき完全かんぜん图都是ぜ它们本身ほんみ的てき极大团。它们是ぜ极大连通的てき，因いん为唯一いち的てき割わり点てん集しゅう(vertex cut)是ぜ所有しょゆう顶点的てき集合しゅうごう。完全かんぜん图的补图是ぜ空そら图(empty graph)。

完全かんぜん图的每ごと一条边都被附上了定てい向むかい之これ后きさき形成けいせい的てき有向ゆうこう图被ひ称しょう作さく轮转(tournament)。

$K_{n}$可か以被分解ぶんかい成なり$n$个树$T_{i}$，且$T_{i}$有ゆう$i$个顶点てん。 Ringel猜想可か以被表ひょう述じゅつ为：完全かんぜん图$K_{2n+1}$能否のうひ被ひ分解ぶんかい成なり一些完全相同的$n$阶树。 对于足あし够大的てき$n$，这个结论是ぜ成立せいりつ的てき。

完全かんぜん图的匹ひき配はい数かず按照它们的てき阶数排列はいれつ，由ゆかりtelephone numbers给出： 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... （OEIS數列すうれつA000085）。这些数字すうじ给出了りょう在ざい$n$阶图上じょうHosoya指数しすう的てき最大さいだい可能かのう值。 在ざい$K_{n}$上うえ的てき完かん美び匹ひき配はい(perfect matching)的てき个数为$(n-1)$!!。 对于阶数小しょう于等于27阶的完全かんぜん图来说，它们的てき交叉こうさ数すう是ぜ已やめ知的ちてき，$K_{28}$的てき交叉こうさ数すう是ぜ7233或ある者もの7234。阶数更さら大だい的てき交叉こうさ数すう由ゆかりRectilinear Crossing Number project在ざい收集しゅうしゅう。$K_{n}$的てきRectilinear交叉こうさ数すう为：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, ... （OEIS數列すうれつA014540）。

几何和かず拓たく扑

$n$阶完全ぜん图可以代表だいひょう$(n-1)$-单纯形がた。几何上じょう，$K_{3}$构成了りょう三角形さんかっけい，$K_{4}$构成了りょう四よん面体めんてい，依よ次じ类推。Császár polyhedron, 一いち个非凸とつ的てき和わ环面同どう胚はい的てき多た边形，可か以由$K_{7}$作さく为它的てき骨ほね架かskeleton。

$K_{1}$到いた$K_{4}$都みやこ是ただし平面へいめん图，然しか而当$n\geqslant 5$时，在ざい平面へいめん上じょう绘制$K_{n}$时总是ぜ会かい有ゆう交叉こうさ，另外，非ひ平面へいめん图$K_{5}$在ざい刻こく画が平面へいめん图的性せい质时起おこり着ぎ重要じゅうよう的てき作用さよう：根ね据すえKuratowski's theorem，当とう且仅当とう一いち个图不ふ包含ほうがん$K_{5}$,以及完全かんぜん二に分ふん图$K_{3,3}$作さく为它的てき一いち部分ぶぶん时，这个图是平面へいめん图。根ね据すえWagner's theorem，当とう且仅当とう一いち个图不ふ包含ほうがん$K_{5}$,以及完全かんぜん二に分ふん图$K_{3,3}$作さく为它的てき图子式しき时，这个图是平面へいめん图。 作さく为Petersen family的てき一いち部分ぶぶん, $K_{6}$起おこり到いた了りょう一个了类似的作用，为了保ほ证一个图的てきlinkless embedding,它不能ふのう作さく为这个图的てき图子式しき出で现。 更さら精せい确地说，Conway和わGordon 证明了りょう每ごと一いち个$K_{6}$在ざい3维空间中的てき嵌入かんにゅう都と是ぜintrinsically linked 的てき，且至少しょう有ゆう一いち对linked的てき三角形さんかっけい。Conway和わGordon还证明あきら了りょう 任意にんい$K_{7}$在ざい3维空间中的てき嵌入かんにゅう都と包含ほうがん了りょう一个作为一个非平凡的扭结嵌入かんにゅう在ざい空そら间里的てき哈密顿环。

例れい子こ

K1: 0	K2: 1	K3: 3	K4: 6
K5: 10	K6: 15	K7: 21	K8: 28
K9: 36	K10: 45	K11: 55	K12: 66

另见

• Fully connected network：全ぜん连接网络
• 完全かんぜん二に分ふん图，一种特殊的二分图，其中每ごと个节点てん都和つわ另一个部分的所有节点相连。

外部がいぶ链接

• 埃ほこり里さと克かつ·韦斯坦ひろし因いん. Complete Graph. MathWorld.