最新公告
  • 欢迎您光临IO源码网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 关于LKH算法的图论知识 PDF 下载

    关于LKH算法的图论知识 PDF 下载

    本站整理下载:
    链接:https://pan.baidu.com/s/1sJx0zdAbOj766d__x3yp1g 
    提取码:6lrz 
     
     
    相关截图:
     
    主要内容:

    1 Trees
    Today we’ll talk about a very special class of graphs called trees. Trees arise in all sorts
    of applications and you’ll see them in just about every computer science class that you’ll
    take at MIT. There are at least half a dozen ways to define a tree, but the simplest is the
    following.
    Definition. A tree is a simple 1 , connected, acyclic graph.
    For example, a tree might look like this.
    On the other hand, this is not a tree
    and neither is this
    1 Recall that we only consider simple graphs in this class, that is, graphs without loops or multiple edges.
    2 Graph Theory III
    Sometimes we’ll draw trees in a leveled fashion, in which case we can identify the top
    node as the root, and every edge joints a “parent” to a “child”.
    Parent
    Child
    Leaf
    Root
    The nodes at the bottom of degree 1 are called leaves.
    Definition. A leaf is a node in a tree with degree 1.
    For example, in the tree above there are 5 leaves. It turns out that no matter how we
    draw a tree, every tree with more than 1 node always has some leaves.
    Theorem 1. Every tree with more than 1 node has at least one leaf.
    Proof. We prove the theorem by contradiction. Suppose it is not true. Then there exists
    a tree T = (V,E) where every node has degree at least 2. Let P = v 1 ,v 2 ,…,v m be a
    path of maximum length in T, i.e., there is no path with m + 1 or more nodes in T (recall
    that all nodes in a path are distinct by definition). Note that we are implicitly using the
    well-ordering principle here.
    Since |V | ≥ 2 and T is connected, such a P exists and we have 2 ≤ m ≤ n. Since
    T has minimum degree at least 2 by assumption, v m is joined to at least 2 nodes. In
    particular, there is a node x 6= v m−1 such that {v m ,x} ∈ E. Since P has maximum length,
    v 1 ,v 2 ,…,v m ,x is not a path, which means x = v i for some 1 ≤ i < m − 1. But then
    v i ,v i+1 ,…,v m−1 ,v m ,v i is a cycle in T. But T is a tree, and so by definition contains no
    cycle. This is a contradiction.
    As it turns out, every tree has at least 2 leaves, which you’ll prove in the problem sets.
    There is also a close correlation between the number of nodes and number of edges in a
    tree. In the previous example we saw that N = 7 and E = 6. We also have the following
    examples.

     

    *** 次数:10600 已用完,请联系开发者***

    1. 本站所有资源来源于用户上传和网络,因此不包含技术服务请大家谅解!如有侵权请邮件联系客服!384324621@qq.com
    2. 本站不保证所提供下载的资源的准确性、安全性和完整性,资源仅供下载学习之用!如有链接无法下载、失效或广告,请联系客服处理,有奖励!
    3. 您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容资源!如用于商业或者非法用途,与本站无关,一切后果请用户自负!
    4. 如果您也有好的资源或教程,您可以投稿发布,成功分享后有★币奖励和额外收入!

    IO 源码网 » 关于LKH算法的图论知识 PDF 下载

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    IO源码吧
    一个高级程序员模板开发平台

    发表评论

    • 84会员总数(位)
    • 10537资源总数(个)
    • 68本周发布(个)
    • 8 今日发布(个)
    • 400稳定运行(天)

    提供最优质的资源集合

    立即查看 了解详情