1年前 (2018-07-23)  java测试 |   抢沙发  6 
文章评分 0 次,平均分 0.0

欧拉图及欧拉路径

  • 欧拉图
    • 如果图G上有一条经过所有顶点、所有边的闭路径(边不重复,顶点可以重复)
    • 充分必要条件
      • 无向图:G连通,所有顶点的度都是偶数
      • 有向图:G弱连通,每个顶点出度与入度相等
  • 欧拉路径
    • 如果图G上有一条经过所有顶点、所有边的路径(边不重复,顶点可以重复)
    • 充分必要条件
      • 无向图:G连通,恰有两个顶点的度是奇数
      • 有向图:G连通,恰有两个顶点的出度与入度不相等,其中一个出度比入度多1,另一个入度比出度多1。

哈密顿图及哈密顿通路

  • 哈密顿图
    • 如果图G上有一条经过所有顶点的回路(不要求经过所有的边,也称作哈密顿回路)
    • 充分非必要条件:如果具有n个顶点的图G的每一对顶点度数之和不小于n,且n>=3
  • 哈密顿通路
    • 如果图G上有一条经过所有顶点的通路(非回路)
    • 充分非必要条件:如果具有n个顶点的图G的每一对顶点度数之和不小于n-1,那么G中有一条哈密顿通路

    哈密顿通路问题在上世纪七十年代被证明是“NP完全的”

图的连通性

  • u可达v
    • u=v或存在一条u到v的路径
  • 连通的无向图
    • 无向图中的任意两个顶点都是可达的
  • 连通的有向图
    • 有向图中的任意两个顶点都是互相可达的
  • 单向连通的有向图
    • 任意两个顶点至少从一个顶点到另一个顶点是可达的
  • 弱连通的有向图
    • 将有向图看作是无向图时是连通的
 

除特别注明外,本站所有文章均为HadoopAll原创,转载请注明出处来自http://hadoopall.com/413.html

发表评论

表情 格式

暂无评论

登录

忘记密码 ?

切换登录

注册

扫一扫二维码分享