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

相关文章

来自专栏小樱的经验随笔

图的基本算法(BFS和DFS)

图是一种灵活的数据结构,一般作为一种模型用来定义对象之间的关系或联系。对象由顶点(V)表示,而对象之间的关系或者关联则通过图的边(E)来表示。 图可以分为有向图...

2505
来自专栏高性能服务器开发

算法与数据结构系列之探秘堆结构

此处所说的堆为数据结构中的堆,而非内存分区中的堆。堆通常可以被看做是树结构,满足两个性质: 1)堆中任意节点的值总是不大于(不小于)其子节点的值; 2)堆是一棵...

932
来自专栏懒人开发

(8.1)James Stewart Calculus 5th Edition:Arc Length

半立方抛物线?? 这名词.... 也就是求一个函数,2个点之间的弧长 这2个点,我们知道对应的x取值范围 可以得到对应的表达式为

702
来自专栏aCloudDeveloper

探秘堆结构

一、概述   此处所说的堆为数据结构中的堆,而非内存分区中的堆。堆通常可以被看做是树结构,满足两个性质:1)堆中任意节点的值总是不大于(不小于)其子节点的值;2...

19910
来自专栏编舟记

命令式到函数式编程

应用场景:当我们用到 if-elseif-else 的时候,可以考虑使用 Optional 语义。 举例说明:

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

P1983 车站分级

题目描述 一条单向的铁路线上,依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别,最低为 1 级。现有若干趟车次在这条线路上行驶,每一...

3279
来自专栏有趣的Python

15-数据结构探险系列-图篇数据结构探险之图篇

图的存储结构:邻接矩阵(数组);邻接表(链表)有向; 十字链表(链表)有向;邻接多重表(链表)无向

703
来自专栏北京马哥教育

Python有趣的小案例

2294
来自专栏苍云横渡学习笔记

【慕课-数据结构-C++语言】图篇

1806
来自专栏ml

HDUOJ---1133(卡特兰数扩展)Buy the Ticket

Buy the Ticket Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/327...

2615

扫码关注云+社区