计算机科学论坛--图论的小问题问问

新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚

XML论坛

W3CHINA.ORG讨论区

计算机科学论坛

SOAChina论坛

Blog

开放翻译计划

新浪微博

首页

软件下载

资料下载

核心成员

帮助

>> 研友的交流园地，讨论关于计算机考研的方方面面。

[返回] 计算机科学论坛 → 计算机理论与工程 → 『计算机考研交流』 → 图论的小问题问问

◇查看新帖 ◇ 用户列表 ◇

(订阅本版)

您是本帖的第 8591 个阅读者　　

*	贴子主题：图论的小问题问问	举报打印推荐 IE收藏夹
	本主题类别:

Supremgoooo

  等级：大四下学期(考上研究生啦!)
  文章：201
  积分：1872
  门派：XML.ORG.CN
  注册：2006/4/9

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	楼主

图论的小问题问问

（1）教材P168，定理11.5的证明：而d（v）等于C的长度。为啥呀？
（2）教材P179，12题，3-正则图咋可能是2-边连通？
（3）13题提示一下吧.
PS:
(1)定理11.5：n(n>=4)阶级大平面图G中，最小度>=3.
证明：由定理11.4（G为n阶(n>=3)简单的连通平面图，G为级大平面图当且仅当G的每个面次数均为3）可知，G的围长g(G)=3，且与任意顶点v相邻的顶点均在某圈C上，由于g（G）=3，所以C的长度大于等于3，而d（v）等于C的长度，所以d（v）>=3，由于v的任意性，可知G的最小度>=3
（2）设G为n（n>=4）阶级大的平面图，证明G的对偶图G*是2-边连通的3-正则图。
（3）设G是2-边连通的简单平面图，且每两个面的边界至多有一条公共边，证明G中至少有两个面的次数相同。

[此贴子已经被作者于2006-8-23 19:10:03编辑过]

收藏分享
顶(0)

2006/8/22 21:19:00

GoogleAdSense

  等级：大一新生
  文章：1
  积分：50
  门派：无门无派
  院校：未填写
  注册：2007-01-01

	广告

2024/6/27 18:14:11

本主题贴数20，分页： [1] [2]

*树形目录（最近20个回帖）	顶端
主题：图论的小问题问问(702字) － Supremgoooo，2006年8月22日
回复：假设d（v）=x，则c是由x个顶点构成的一个圈，显然其长度为x=的（v）..(63字) －栖憧，2007年10月14日
回复： yangling的证明也是越了很大的步骤,实际上:"则G'中必定存在一个圈C，使v在C中，且任意u..(294字) － yourwk，2006年8月24日
回复：我觉得是不是可以借助定理11.4的思路。极大平面图每个面的度数都为3。对G中任意一顶点v,v在外部..(484字) － yangling_1985，2006年8月24日
回复：昨晚跳了大步,今晚就试图来详细的解一下:对于题只要证明对于圈C的任意点是2度的(就圈C而言),结..(1280字) － yourwk，2006年8月23日
回复：我是这么想的，但确实找不到更好的方法，不过这个不是什么大问题吧``没必要在这里纠缠.......(89字) － zsmjlu，2006年8月23日
回复：我上午想了一下,关于极大平面图必是轮图的并,大家看这样对不对若不是则存在如下情形，(图中的一部分..(788字) － zsmjlu，2006年8月23日
回复：我相信“极大平面图必是轮图的并”（这个命题似乎等价于“对每个顶点的v，存在一个圈C，使得C的顶点恰..(242字) － Logician，2006年8月23日
回复： 1.关于书上的这个证明中说到是某个圈,这个某是特指(即与v相邻的所有点构成的一个圈)下面在证明一下..(724字) － yourwk，2006年8月22日
回复： [quote][b]以下是引用[i]yourwk在2006-8-22 23:37:00[/i]的发..(1018字) － Supremgoooo，2006年8月23日
回复： [quote][b]以下是引用[i]yourwk在2006-8-22 23:37:00[/i]的发..(406字) － Logician，2006年8月23日
回复： logican 确实思路比较多,佩服`````(32字) － zsmjlu，2006年8月22日
回复： [quote][b]以下是引用[i]Supremgoooo在2006-8-22 21:19:00[..(399字) － zsmjlu，2006年8月22日
回复： [quote][b]以下是引用[i]zsmjlu在2006-8-22 23:09:00[/i]的发..(277字) － Supremgoooo，2006年8月23日
回复： [quote][b]以下是引用[i]zsmjlu在2006-8-22 23:09:00[/i]的发..(269字) － Logician，2006年8月23日
回复： [quote][b]以下是引用[i]Logician在2006-8-23 0:25:00[/i]的..(489字) － zhongyuan17，2007年10月15日
回复： [/quote] 问题是，怎么证明任何顶点v和它的邻顶正好构成一个轮图呢？也就是说，怎么..(248字) － zsmjlu，2006年8月23日
回复：（1）不知道。@_@（2）3-正则图怎么不可能是2-边连通的？首先，3-正则图不一定是就是3-边..(694字) － Logician，2006年8月22日
回复： [quote][b]以下是引用[i]Logician在2006-8-22 23:02:00[/i]..(813字) － Supremgoooo，2006年8月23日
回复：你把问题说全吧,我现在手边没书.:)不好意思~(49字) － carroty，2006年8月22日


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	101.563ms