数学建模社区-数学中国

标题: 各位高手，有8道基础菜鸟级的图论题亟待解决 [打印本页]
作者: 东京流浪猫    时间: 2013-1-19 12:18
标题: 各位高手，有8道基础菜鸟级的图论题亟待解决
1、        拥有p个顶点，q条边，r个区域，kge连结成分的平面图G，满足等式p-q+r-k=1。证明之。
* ?. Q, ^# o; ~) c8 {4 @2、        K是奇数，请证明k正则图的顶点数为偶数。
& e5 N$ x7 C5 a7 ?- P" _* l3、        G是连通图。请证明G的任意两条最长路径都通过某个共同顶点。- E$ z$ \! R" }, H
4、        G是顶点数4个以上的2连通图。请证明以下两个命题等价:; |5 C& @3 K% Y: w  v2 D
          (1)        从G删除相邻连接的顶点后将是非连通图；  q- i0 b$ _8 O  J) j9 j  C
      (2)        两顶点之间相连的边收缩后的图不是2连通图。
5 ?' O( V" }% X5 V  U" w/ t" A5、        请画一个不拥有1因子的3正则图。# D/ G1 S; j6 l; ~1 I4 f/ q# w
6、        请证明图K2，n的全域树的个数是n2n-12 b  t2 d6 h5 K- {9 O( T4 ~4 w" U
7、        G是平面图。请证明G的任意平面图不持有相互邻接的5个面（包括外面）。
& a' z- ~/ F8 I( D  _& z4 ?7 C$ E8、        请画出拥有8条边且不包含三角形的最小顶点数的图。并证明这个图是最小顶点数的图，且有2个存在。
/ s# J! m9 w. O4 A/ z" k



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5