新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 计算机考研交流 』 → 图论的小问题问问 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 8573 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 图论的小问题问问 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客楼主
    发贴心情 图论的小问题问问

    （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)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/22 21:19:00
     
     carroty 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(GRE考了1600分!)
      文章：153
      积分：1257
      门派：IEEE.ORG.CN
      注册：2006/4/4

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给carroty发送一个短消息 把carroty加入好友 查看carroty的个人资料 搜索carroty在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看carroty的博客第2楼
    发贴心情 
    你把问题说全吧,我现在手边没书.

    :)

    不好意思~

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/22 22:27:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第3楼
    发贴心情 
    （1）不知道。@_@
    （2）3-正则图怎么不可能是2-边连通的？首先，3-正则图不一定是就是3-边连通的（下面有两个反例）。其次，即使是3-边连通的，根据定义，3-边连通的图自然也是2-边连通的和1-边连通的（注意，证明2-边连通就是证明删除1条边后还连通就可以了，并不要求证明“边连通度为2”）。

    我们知道，K_4是3-边连通的3-正则图。两个K_4的并是不连通的3-正则图。
    而下面两个3-正则图的边连通度分别是2和1：

      * ── *
    / \    / \   
    *   *  *   *
    \ /    \ /
      * ── *

    ┌ * - * ─ * - * ┐
    │ |   |    |   | │
    │ * - *    *   * │
    │  \ /      \ /  │
    └─ *        * ─┘

    总之，我们从正则性得不出太多关于边连通度的结论。

    （3）对偶图 + 鸽巢原理。就是证明“简单图中必有两个度数相同的顶点”。

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/22 23:02:00
     
     zsmjlu 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(C++考了100分!)
      文章：52
      积分：307
      门派：IEEE.ORG.CN
      注册：2006/5/31

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给zsmjlu发送一个短消息 把zsmjlu加入好友 查看zsmjlu的个人资料 搜索zsmjlu在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看zsmjlu的博客第4楼
    发贴心情 
    以下是引用Supremgoooo在2006-8-22 21:19:00的发言：
    （1）教材P168，定理11.5的证明：而d（v）等于C的长度。为啥呀？
    （2）教材P179，12题，3-正则图咋可能是2-边连通？
    （3）13题提示一下吧.


    1,可以自己画一个轮图看一下,与中心相邻的点所在的圈长=d(v)
    2,对课本定义理解不透,k-边连通是指最小边连通度>=k ,即可(我理解) ,3-正则图最少删除2条边后连同分支才可>=2,故为2-边连通,没错!!!!

    ----------------------------------------------
    用怀疑的目光看这个世界得一切``````

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/22 23:09:00
     
     zsmjlu 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(C++考了100分!)
      文章：52
      积分：307
      门派：IEEE.ORG.CN
      注册：2006/5/31

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给zsmjlu发送一个短消息 把zsmjlu加入好友 查看zsmjlu的个人资料 搜索zsmjlu在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看zsmjlu的博客第5楼
    发贴心情 
    logican 确实思路比较多,佩服`````

    ----------------------------------------------
    用怀疑的目光看这个世界得一切``````

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/22 23:19:00
     
     yourwk 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(猛啃高等数学)
      文章：5
      积分：134
      门派：XML.ORG.CN
      注册：2006/5/25

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给yourwk发送一个短消息 把yourwk加入好友 查看yourwk的个人资料 搜索yourwk在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看yourwk的博客第6楼
    发贴心情 
    1.关于书上的这个证明中说到是某个圈,这个某是特指(即与v相邻的所有点构成的一个圈)下面在证明一下这个圈必定存在,假设存在对于v1,v2(为是与v相邻的任两点)(v1,v2)不属于E(G).这就是说极大平面图有大于圈长为3的面存在,矛盾,所以(V1,V2)肯定属于E(G)因为任意就知道这个圈是存在的

    2.边连通度>=K就说图是K连通的,并不是你想的边连通度=2,比如说该题连通度=5.图是1边连通的也是2边连通的也是3边连通的...要证明它是2边连通的只要证明删除任一条边还是连通的即可

    3.答案
    13,设G是2-边连通的简单平面图，且每两个面的边界至多有一条公共边，证明G中至少有
    两个面的次数相同。
    证明做G的对偶图G*，只要证明G*上至少有2个顶点的度数相同即可。

    G是连通图，显然G*也是连通图。

    设G*上有n个顶点，这n个顶点的度数只能是1至n-1，根据鸽巢原理，至少有2个
    顶点的度数相同。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/22 23:37:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第7楼
    发贴心情 
    以下是引用yourwk在2006-8-22 23:37:00的发言：
    1.关于书上的这个证明中说到是某个圈,这个某是特指(即与v相邻的所有点构成的一个圈)下面在证明一下这个圈必定存在,假设存在对于v1,v2(为是与v相邻的任两点)(v1,v2)不属于E(G).这就是说极大平面图有大于圈长为3的面存在,矛盾,所以(V1,V2)肯定属于E(G)因为任意就知道这个圈是存在的


    从“v1,v2不属于E(G)”推不出“极大平面图有大于圈长为3的面存在”吧？

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/23 0:24:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第8楼
    发贴心情 
    以下是引用zsmjlu在2006-8-22 23:09:00的发言：
    1,可以自己画一个轮图看一下,与中心相邻的点所在的圈长=d(v)


    问题是，怎么证明任何顶点v和它的邻顶正好构成一个轮图呢？
    也就是说，怎么证明存在一个圈C，它的顶点恰为（既不多也不少）v的所有邻顶呢？

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/23 0:25:00
     
     zsmjlu 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(C++考了100分!)
      文章：52
      积分：307
      门派：IEEE.ORG.CN
      注册：2006/5/31

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给zsmjlu发送一个短消息 把zsmjlu加入好友 查看zsmjlu的个人资料 搜索zsmjlu在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看zsmjlu的博客第9楼
    发贴心情 

    [/quote]
    问题是，怎么证明任何顶点v和它的邻顶正好构成一个轮图呢？
    也就是说，怎么证明存在一个圈C，它的顶点恰为（既不多也不少）v的所有邻顶呢？

    [/quote]


    可能是极大平面图的缘故把，我看书定理11.4的证明图想到的，应该是这样,还没相好怎么证明

    ----------------------------------------------
    用怀疑的目光看这个世界得一切``````

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/23 7:47:00
     
     zsmjlu 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(C++考了100分!)
      文章：52
      积分：307
      门派：IEEE.ORG.CN
      注册：2006/5/31

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给zsmjlu发送一个短消息 把zsmjlu加入好友 查看zsmjlu的个人资料 搜索zsmjlu在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看zsmjlu的博客第10楼
    发贴心情 
    我上午想了一下,关于极大平面图必是轮图的并,大家看这样对不对
    若不是则存在如下情形，(图中的一部分)
         (1)               b------a------e    不存在轮图                                                    
                             \   /   \  /                                                    
                               c  ----d  
      此时b,e必存在边相连    
        或 (2)        ------b------a------                                                    
                             \       \  /                                                    
                               c  ----d ------
    与c相邻的顶点所在的圈还有其他点(不与c相邻),此时已经不是极大平面图了
    因此递归到整个图,比是轮图的并

    希望大家举出反例

    ----------------------------------------------
    用怀疑的目光看这个世界得一切``````

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/23 13:19:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 计算机考研交流 』 的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/6/21 20:43:44

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

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 148.438ms