-->
当前位置:首页 > 题库 > 正文内容

主观题:二部图

Luz2年前 (2022-12-13)题库1965
这是一个主观题模板。请在这里写题目描述。






答案:1、设$K_n$的顶点集为$V$,对$n$为奇数和偶数两种情况进行讨论。
(1)$n$为奇数时,$n=2k+1$,将$V$分成两个互补的顶点子集$V_1$与$V_2$,$V_1\cap V_2=\varnothing,~V_1\cup V_2=V$,且$|V_1|=k=\frac{n-1}{2}=r,~|V_2|=k+1=\frac{n+1}{2}=s$,在$K_n$中将两个端点都在$V_1$或都在$V_2$中的边删除,所得子图$K_{r,s}$为所求边数最多的$K_n$的生成子图。所得边数为$rs=\frac{n^2-1}{4}$。$n=5$时所得要求子图为$K_{2,3}$.


(2)$n$为偶数,即$n=2k$,在$K_n$中将两个端点都在$V_1$或都在$V_2$中的边删除所得子图$K_{r,s}$为所求边数最多的$K_n$的生成子图,即完全图二部图,$K_{r,s}$,其中$r=s=\frac{n}{2}$。 $n=6$时所得要求子图为$K_{3,3}$.


2、在同一顶点子集的所有的顶点之间加上边,即可生成$K_n$,下边两个图由$k_{2,3}$与$K_{3,3}$分别生成$K_5$与$K_6$的示例,其中虚线是要加的边。

![ch14-2.jpg](~/2071f795-9b0a-437d-ab9e-be34cfdb88fd.jpg)




发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。