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

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的邻接矩阵。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新工科课程建设探讨——以能源与动力工程专业为例

4.2 非线性方程求解

这里主要以简单的牛顿迭代法介绍非线性方程的求解,维基百科对“牛顿迭代法”的解释:

1120
来自专栏YoungGy

基于RNN的语言模型与机器翻译NMT

语言模型 传统的语言模型 基于RNN的语言模型 机器翻译 基于统计的机器翻译架构 基于RNN的seq2seq架构 seq2seq结构 优化seq2seq att...

3157
来自专栏数据结构与算法

二项式定理

其实二项式定理也就一句话:$(x + y)^n = \sum_{i = 0}^n C_{n}^i x^{n - i} y^{i}$

411
来自专栏知识分享

当年参加飞思卡尔自己写的双线识别算法

原理 先找到一个白点A,然后向右找到黑点,记录黑点的位置,以当前黑点的竖坐标位置向上判断,上面的点是什么点,如果为黑点向左找白点,如果为白点向右找黑点(找到边界...

2737
来自专栏书山有路勤为径

特征向量(Feature Vectors)

已经可以从图像中提取基于形状的特征,如何使用这一组特征来检测整个对象,以山峰图像角点检测举例:

1532
来自专栏算法channel

动态规划|相邻约束下的最优解(House Robber II )

01 House Robber II This time, all houses at this place are arranged in a circl...

3574
来自专栏封碎

快速排序为什么那样快

本文转载自 http://www.kuqin.com/algorithm/20080615/9581.html

1613
来自专栏数据结构与算法

15:细菌的繁殖与扩散

15:细菌的繁殖与扩散 总时间限制: 1000ms 内存限制: 65536kB描述 在边长为9的正方形培养皿中,正中心位置有m个细菌。假设细菌的寿命仅一天,但...

3477
来自专栏懒人开发

(2.4)James Stewart Calculus 5th Edition: The Precise Definition of a Limit

后面是 经典的叙述(记得大学,epsilon【ε】,delta【δ】 这段话都快背疯了)

1252
来自专栏PaddlePaddle

【进阶篇】Recurrent Group教程

导语 PaddlePaddle 高度支持灵活和高效的循环神经网络配置。接下来的进阶篇推文将围绕RNN模型展开,指导你如何在 PaddlePaddle 中配置和使...

3355

扫码关注云+社区