1
2
比如，顶点3的度是3。
3
Input Output
Total
4
5
• 有向图中，分入度和出度两部分，满足： TD(v) =
ID(v) + OD(v) 。
1
2
比如，顶点3的入度是1，出度为1，
度为2
3
4
7.2 图的相关术语
7.2.5 度
• 一般地，若图G中有n个顶点，e条边或弧，则图中
边与顶点的度的关系如下：
能否从河岸或小岛 出发，通过每一座 桥，而且仅仅通过 一次回到原地？
1736 年 29 岁的欧拉解决了该问题，这也意味新的 数学分支——图论的诞生
7.1 图的定义和基本术语
7.1.1 背景
• 四色问题（世界三大数学难题之一）
证明不论地图多么复 杂，最多使用四种颜 色就能保证相邻地区 使用不同颜色。
• G1是有向图（包含弧的图）
7.1 图的定义和基本术语
1
2
3
4
G1
7.1.3 图的基本术语
• G2是无向图（没有弧的图） • G2中有边(1,4), (1,2), (2,3),
(2,5), (3,5), (3,4) • 无序对（x，y）表示x和y之间的
一条边（edge）。所谓无序对， 就是指（x，y）等同于（y，x） • 1条边等于2条弧，即(1,4)等于 <1,4>加上<4,1>
• 图就是数据元素间为多对多关系的 1
2
数据结构。怎么理解？
3
• 线性表是一对一关系：每一对结点
中，前者只有一个直接后继，后者只 4
5
有一个直接前驱
• 树是一对多关系：每一对结点中，前者可能有多个直
接后继（孩子），而后者只能有一个直接前驱（双亲）
• 图中每一对顶点中，它们都同时可能有多个邻接点
7.1 图的定义和基本术语
7.2 图的相关术语
7.2.8 路径和回路
1
2
1
2
1
2
3
4
3
4
3
4
• 无向完全图：有n（n-1）/2条边的无向图（这意 味着图中每个顶点和其余n-1个顶点都有边相连）
7.2 图的相关术语
7.2.2 子图
• 设有两个图G=（V，R）和图G / =（V/，R/）,若 V/V且R/ R，则称图G/为G的子图。
• 有向图的子图
1
2
11
21
2
7.1.2 图的定义
• 图的形式化定义 与线性结构、树型结构有什么不同？
ADT Graph { 数据元素：V={vi| vi∈D0, i=1,2,…,n, n≥0, D0为某一数据对象} 结构关系：R＝｛<vi,vi+1> | vi, vi+1∈D0, i=1,2, …,n-1｝ 基本操作： • 常规操作：创建/初始化，销毁，清空，插入，删除，查找/
v/）与顶点v和v/ 相关联。
4
5
G2
Hale Waihona Puke 比如，顶点3的邻接点是顶点2,4,5
1
2
• 对于有向图G=（V，R）而言，若
弧<v，v/>∈R，则称顶点v邻接到
顶点v/，顶点v/ 邻接自顶点v。
3
4
7.2 图的相关术语
G1
7.2.4 顶点的位置序号
• 同一个顶点的多个邻接点之间有无前后次序？
• 我们需要将图中的顶点按某种序列排列起来。顶
为权。
• 网（赋权图）：带权的图。
15 2
4
2
8
7.2 图的相关术语
6
9
3
7
16
5
5
4
5
7.2.7 图的种类
• 有向图（Directed Graph, DG） • 有向网（Directed Network, DN） • 无向图（Undirected Graph, UDG） • 无向网（Undirected Network, UDN）
定位 ，遍历 • 新增操作：找到本顶点的第一个邻接点，找到本顶点的下一
个邻接点，插入/删除弧 }
7.1 图的定义和基本术语
7.1.3 图的基本术语
• 图G1中有4个顶点（vertex） （一个顶点对应一个数据元素）
• G1中有弧<1,2>,<1,3>,<3,4>, <4,1>
• <x，y>表示从顶点x到顶点y的 一条弧（arc），并称x为弧尾 （tail）或起始点，称y为弧头 （head）或终端点。
1976年，美国数学家阿佩尔与哈肯用计算机化了 1200个小时，作了100亿次判断，完成证明
7.1 图的定义和基本术语
7.1.1 背景
• 本课程主要不是要解决图论中的问题——这是离 散数学的任务。 • 本课程的任务是理解已有的解决方案，把它转化 成算法和程序。
7.1 图的定义和基本术语
7.1.2 图的定义
点在这个人为的随意排列中的位置序号称为顶点
在图中的位置。
比如，右下图中各顶点的顺序是顶点1,2,3,4
1
2
注意：实际的图中，圈内的数值可
能是指顶点的位置序号，也可能是
数据元素的值，根据上下文确定 3
4
7.2 图的相关术语
7.2.5 度
• 无向图中，顶点v 的度（Degree）是指和v相关联
的边的数目，记作TD(v)。
n
TD(Vi )
原因是1条边/弧与2
e i1 2
个顶点相关联
1
2
比如，右图中有5个顶点（度分别
是2,3,3,2,2）和6条边，满足：
3
e=6=(2+3+3+2+2)/2
4
5
7.2 图的相关术语
7.2.6 权和网
• 在实际应用中，有时图的边或弧上往往与具有一定
意义的数（比如距离或耗费等信息）有关，该数称
23
4
3
4
G1的子图举例
4
G1
还有子图吗？
7.2 图的相关术语
7.2.2 子图
• 无向图的子图
1
2
3
4
5
G2
1
21
2
3
4
1
25
G2的子图举例
7.2 图的相关术语
7.2.3 邻接点
• 对于无向图G=（V，R），如果边 1
2
（v，v/）∈R，则称顶点v，v/互
3
为邻接点，即v，v/ 相邻接。边（v，
1
2
3
4
5
G2
7.1 图的定义和基本术语
7.1.4 本章的假设
• 我们只讨论简单图（Simple Graph），即没有自环 也没有多重边的图。
• 自环：两个顶点为同一顶点的边。
1
• 多重边：两个点之间不止一条边。
1
4
7.1 图的定义和术语
2. 图的相关术语
7.2.1 完全图
• 有向完全图：有n（n-1）条弧的有向图（这意味着 图中每个顶点和其余n-1个顶点都有弧相连）。
1. 图的定义和基本术语
7.1.1 背景
• 图状结构是四大逻辑结构之一，是一个非线性结 构。 • 我们这里涉及的是图论（Graph Theory）的基 本内容。图论是“离散数学”中的重要内容之一。 • 图论的应用非常广泛，有很多经典的问题。
7.1 图的定义和基本术语
7.1.1 背景
• 哥尼斯堡七桥问题