复杂网络(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 条评论
登录 后参与评论

相关文章

来自专栏移动开发面面观

OpenGL ES——导入.stl格式的3D模型

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

Day4晚笔记

数据结构 并查集:捆绑两个点的信息,判断对错 倍增:LCA, 字符串 hash,模拟, 最小表示法 给定一个环状字符串,切开,使得字符串的字典序最小 图和树 割...

2504
来自专栏bboysoul

1475: C语言实验题――一元二次方程 II

描述:求一元二次方程ax2+bx+c=0的解。a,b,c为任意实数。 输入:输入数据有一行,包括a b c的值 输出:按以下格式输出方程的根x1和x2。x1...

1063
来自专栏ACM算法日常

翻转瓷砖Fliptile(开关反转)- POJ 3279

Farmer John knows that an intellectually satisfied cow is a happy cow who will g...

912
来自专栏每日一篇技术文章

OpengL ES _ 入门_02

顶点是啥? 顶点就是坐标位置,不管你是画直线,三角形,正方体,球体,以及3D游戏人物等,都需要顶点来确定其形状。 顶点坐标创建 1.记住顶点的坐标数据类型...

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

2-SAT速成

本文只做总结性说明 2-SAT 2-SAT是k-SAT问题的一种,k-SAT问题在k>=3时已经被证明是NP完全问题 2-SAT问题定义比较简单 有n个布尔变量...

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

1038 一元三次方程求解

1038 一元三次方程求解 2001年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver ...

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

4768 跳石头

4768 跳石头 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 一年一度的“...

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

2039 骑马修栅栏

题目描述 Description Farmer John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。 John是一个与其他农民一样懒的人...

36211
来自专栏小鹏的专栏

tensorflow使用BN—Batch Normalization

注意:不要随便加BN,有些问题加了后会导致loss变大。 上一篇是 Batch Normalization的原理介绍,看一下tf的实现,加到卷积后面和全连接层...

6537

扫码关注云+社区