前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >复杂网络(1)--图论的基本理论

复杂网络(1)--图论的基本理论

作者头像
锦小年
发布2018-01-02 14:26:05
1.8K0
发布2018-01-02 14:26:05
举报
文章被收录于专栏:锦小年的博客

1 图论的基本概念

1.1 图(graph)及其分类

(1) 图的定义:图是由点集V={vi}以及V中元素无序对的集合E={ek}所构成的二元组,记为G=(V,E),V中的元素vi称为节点,E中的元素ek称为边。通俗理解:图是节点和边构成及集合。 (2) 简单图:不含环和多重边的图称为简单图。 多重图:含有多重边的图 (3) 完全图:每一对节点之间都有边相连的简单图称为完全图,有n个节点的无向完全图记为Kn 有向完全图: 每一对节点间有且仅有一条有向边的简单图 (4) 二部图:图G(V,E)的点集V可以分成两个非空子集X,Y,即X并Y等于V,X交Y等于空集,如果E中的每条边的两个端点必有一个属于X,另一端点属于Y,则成G为二部图,有时记为:G = (X,Y,E)。

1.2 节点的度(degree)

(1) 节点的度的定义:与节点(node)V相连的边(edge)数之和称为节点的度,记为deg(v),简记为:d(v) (2) 悬挂点:度为1的节点称为悬挂点 悬挂边:连接悬挂点的边称为悬挂边 (3) 任何图中,节点的度之和等于边数的2倍,次数为奇数的节点必为偶数个。 (4) 出度:在有向图中,以节点vi为起始点的边数称为出度 入度:在有向图中,以节点vi为终止点的边数称为入度

1.3 子图(subgraph)

(1)图G=(E,V),若E’是E的子集,V’是V的子集,且E’中的边仅与V’中的节点相关联,则称G’=(V’,E’)是G的一个子图。

1.4 连通图

(1)各边相异的道路称为迹(trace),也成为简单路劲(simple path);各节点相异的道路称为轨(track),也称为基本路径(essential path);起点和终点重合的道路称为回路(circuit),否则称为开路(open circuit)。 (2)连通图:图中任意两点间至少有一条道路相连,则称该图为连通图。

1.5 图的矩阵表示

赋权图G=(E,V),其边(vi,vj)有权wij,构造矩阵A=(aij)n*n,则成矩阵A为赋权图G的邻接矩阵。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1 图论的基本概念
    • 1.1 图(graph)及其分类
      • 1.2 节点的度(degree)
        • 1.3 子图(subgraph)
          • 1.4 连通图
            • 1.5 图的矩阵表示
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档