首页
>
知识点讲解
图的定义及术语
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用数据结构 > 树和图 > 图 >
被考次数：
2次
被考频率：
低频率
总体答错率：
59%
知识难度系数：
由 软考在线 用户真实做题大数据统计生成
相关知识点：4个
图
G
是由两个集合
V
和
E
构成的二元组，记作
G
=（
V
，
E
），其中
V
是图中顶点的非空有限集合，
E
是图中边的有限集合。从数据结构的逻辑关系角度来看，图中任一顶点都有可能与图中其他顶点有关系，而图中所有顶点都有可能与某一顶点有关系。在图中，数据结构中的数据元素用顶点表示，数据元素之间的关系用边表示。
.有向图：若图中每条边都是有方向的，则称为有向图。从顶点
ν
i
到
ν
j
的有向边<
v
i
，
v
j
>也称为弧，起点
ν
i
称为弧尾；终点
ν
j
称为弧头。在有向图中，<
ν
i
，
ν
j
>与<
ν
j
，
v
i
>分别表示两条弧，如下图（a）所示。
有向图和无向图示意图
.无向图：若图中的每条边都是无方向的，顶点
ν
i
和
ν
j
之间的边用（
ν
i
，
ν
j
）表示。在无向图中，（
ν
i
，
ν
j
）与（
ν
j
，
ν
i
）表示的是同一条边。5个顶点的一个无向图如上图（b）所示。
.完全图：若一个无向图具有
n
个顶点，而每一个顶点与其他
n
-1个顶点之间都有边，则称之为无向完全图。显然，含有
n
个顶点的无向完全图共有
n
（
n
-1）/2条边。类似地，有
n
个顶点的有向完全图中弧的数目为
n
（
n
-1），即任意两个不同顶点之间都存在方向相反的两条弧。
.度、出度和入度：顶点
ν
的度是指关联于该顶点的边的数目，记作
D
（
ν
）。若
G
为有向图，顶点的度表示该顶点的入度和出度之和。顶点的入度是以该顶点为终点的有向边的数目，而顶点的出度指以该顶点为起点的有向边的数目，分别记为ID（
ν
）和OD（
ν
）。例如，上图（a）中，顶点1，2，3，4的入度分别为1，2，1，1，出度分别为3，0，0，2。上图（b）中，顶点1，2，3，4，5的度分别为3，2，4，3，2。
.路径：在无向图
G
中，从顶点
ν
p
到顶点
ν
q
的路径是指存在一个顶点序列
ν
p
，
ν
i
1
，
ν
i
2
，…，
ν
in
，
ν
q
，使得（
ν
p
，
ν
i
1
），（
ν
i
1
，
ν
i
2
），…，（
ν
in
，
ν
q
）均属于
E
（
G
）。若
G
是有向图，其路径也是有方向的，它由
E
（
G
）中的有向边<
ν
p
，ν
i
1
>，<
ν
i
1
，
ν
i
2
>，…，<
ν
in
，
ν
q
>组成。路径长度是路径上边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路或环。若一条路径上除了
ν
p
和
ν
q
可以相同外，其余顶点均不相同，这种路径称为一条简单路径。
.子图：若有两个图
G
=（
V
，
E
）和
G
'=（
V
'，
E
'），如果
且
，则称
G
'为
G
的子图。
.连通图：在无向图
G
中，若从顶点
ν
i
到顶点
ν
j
有路径，则称顶点
ν
i
和顶点
ν
j
是连通的。如果无向图
G
中任意两个顶点都是连通的，则称其为连通图。上图（b）所示的无向图是连通图。
.强连通图：在有向图
G
中，如果对于每一对顶点
ν
i
，
ν
j
∈
V
且
ν
i
≠
ν
j
，从顶点
ν
i
到顶点
ν
j
和从顶点
ν
j
到顶点
ν
i
都存在路径，则称图
G
为强连通图。上图（a）所示的有向图不是强连通图。以顶点1和顶点3为例，顶点1至顶点3存在路径，而顶点3至顶点1没有路径。
.网：边（或弧）具有权值的图称为网。
从图的逻辑结构的定义来看，图中的顶点之间不存在全序关系（即无法将图中的顶点排列成一个线性序列），任何一个顶点都可被看成第一个顶点；另一方面，任一顶点的邻接点之间也不存在次序关系。为便于运算，为图中每个顶点赋予一个序号。
本知识点历年真题：
隶属试卷
题号/题型
题干
难度系数/错误率
2017年上半年
数据库系统工程..
上午试卷
综合知识
第19题
选择题
在进行软件开发时，采用无主程序员的开发小组，成员之间相互平等;而主程序员负责制的开发小组，由一个主程序员和若干成员组成，成员之间没有沟通。在一个由8名开发人员构成的小组中，无主程序员组和主程序员组的沟通路径分别是( )。
60%
2011年上半年
数据库系统工程..
上午试卷
综合知识
第15题
选择题
包含8个成员的开发小组的沟通路径最多有（15)条。
58%
相关知识点：
邻接链表表示法
邻接矩阵表示法
图
图的存储结构
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师
系统分析师
系统架构设计师
网络规划设计师
系统规划与管理师
初级资格科目
程序员
网络管理员
信息处理技术员
信息系统运行管理员
中级资格科目
系统集成项目管理工程师
网络工程师
软件设计师
信息系统监理师
信息系统管理工程师
数据库系统工程师
多媒体应用设计师
软件评测师
嵌入式系统设计师
电子商务设计师
信息安全工程师
本网站所有产品设计（包括造型，颜色，图案，观感，文字，产品，内容），功能及其展示形式，均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部，违者将依法追究责任，特此声明。
本站部分内容来自互联网或由会员上传，版权归原作者所有。如有问题，请及时联系我们。
工作时间：9:00-20:00
客服
商务合作
客服邮箱
service@rkpass.cn
京B2-20210865
|
京ICP备2020040059号-5
|
京公网安备 11010502032051号
|
营业执照
| Copyright ©2000-2023 All Rights Reserved 软考在线版权所有
