•
同构的判断
•
关于欧拉,哈密尔顿图
• 二部图K2，3是（）(北京理工,02年) • A.欧拉图B. 哈密尔顿图C.非平面图 • D.平面图
•
• 下列命题中( )是正确的. • 1.欧拉图的子图一定是欧拉图 • 2.哈密顿图的子图一定是哈密顿图 • 3.平面图的子图一定是平面图 • 4.树的子图一定是树. • (北京理工,00年)
•
关于彼得森图
• 证明: • 1.不是二部图 • 2.不是欧拉图 • 3.不是平面图 • (大连理工,01年)
•
平面图的判定
• 问:K4，3与 K4，4是否为平面图？为什么？ • （南京理工，01年）
•
• T=〈V，E〉是一个图，证明： • 1.若且
握手定理
• 简单无向图有21条边,3个4度结点,其余均 为3度结点,则G有___个结点.
• (东北大学,02年)
•
• 一个简单图G=<V,E>,若G不连通,则它的 补图一定连通.(南京理工,01年)
•
• 至少要删除多少条边,才能是Kn(n>2)不连 通,且其中有一个连通分支恰有k个结点.
• (复旦,02年)
|V1|> |V2|,证明V1中一定有树叶. • (南京理工,99年)
•
•精品课件
！
•
•精品课件
！
图论的习题
•
关于有向连通图的可达性
• 设D是n(n>=2)阶有向连通图，则D的可达 性距阵的所有元素之和至少为——
• （北京大学，00年）
•
• 一个无向图有4个结点，其中3个的度数 为2，3，3，则第4个结点的度数不可能 是————(北京理工,99年)
• A.0 B. 1 C. 2 D. 4
•
•
• 判断: • 设G为无向图,若G恰有n个结点,n-1条边,
则G必为一棵树. • 下面图中恰有两棵不同够的生成树. • (西安交大,97年)
•
• 证明: • 若简单无向图G中恰有两个奇结点,则两
个结点一定可达.(国防科大,01年) • 并请判断: • 若简单无向图G中恰有两个奇结点,则G中
任意两个结点u和v之间必存在一条基本 路径.