1 图的基本概念
- 格式：ppt
- 大小：651.00 KB
- 文档页数：54
下载文档原格式
合集下载
离散数学 7-1图概念7-2路与回路
若一条路中所有的边e1, …, en均不相同,称作迹 。 若一条路中所有的结点v0, v1,…, vn均不相同,称作通路 。 闭的通路,即除v0=vn之外,其余结点均不相同的路,称作圈。
例如
路：v1e2v3e3v2e3v3e4v2e6v5e7v3 迹：v5e8v4e5v2e6v5e7v3e4v2 通路：v4e8v5e6v2e1v1e2v3
学习本节要熟悉如下术语(22个)： 路、 路的长度、 回路、 迹、 通路、 圈、 割点、
连通、连通分支、 连通图、 点连通度、
点割集、
边割集、 割边、 边连通度、 可达、 弱分图、
单侧连通、 强连通、 弱连通、 强分图、 单侧分图 掌握5个定理，一个推论。
7-2 路与回路
路
无向图的连通性
7-1 图的基本概念
图的定义
点的度数
特殊的图 图同构
三、特殊的图
1、多重图 定义7-1.4：含有平行边的图称为多重图。 2、简单图：不含平行边和环的图称为简单图。 3、完全图 定义7-1.5：简单图G=<V，E>中，若每一对结点 间均有边相连，则称该图为完全图。 有n个结点的无向完全图记为Kn。 无向完全图：每一条边都是无向边 不含有平行边和环 每一对结点间都有边相连
3、图的分类：
①无向图：每条边均为无向边的图称为无向图。 ②有向图：每条边均为有向边的图称为有向图。
③混合图：有些边是无向边，有些边是有向边的图称
为混合图。
v1 (孤立点) v5 V1’ v1 环
v2
v4 v3 (a)无向图
V2’
V3’ (b)有向图 V4’
v2
v4 v3 ( c ) 混合图
4、点和边的关联：如ei=(u，v)或ei=<u，v>称u， v与ei关联。 5、点与点的相邻：关联于同一条边的结点称为邻 接点。
例如
路：v1e2v3e3v2e3v3e4v2e6v5e7v3 迹：v5e8v4e5v2e6v5e7v3e4v2 通路：v4e8v5e6v2e1v1e2v3
学习本节要熟悉如下术语(22个)： 路、 路的长度、 回路、 迹、 通路、 圈、 割点、
连通、连通分支、 连通图、 点连通度、
点割集、
边割集、 割边、 边连通度、 可达、 弱分图、
单侧连通、 强连通、 弱连通、 强分图、 单侧分图 掌握5个定理，一个推论。
7-2 路与回路
路
无向图的连通性
7-1 图的基本概念
图的定义
点的度数
特殊的图 图同构
三、特殊的图
1、多重图 定义7-1.4：含有平行边的图称为多重图。 2、简单图：不含平行边和环的图称为简单图。 3、完全图 定义7-1.5：简单图G=<V，E>中，若每一对结点 间均有边相连，则称该图为完全图。 有n个结点的无向完全图记为Kn。 无向完全图：每一条边都是无向边 不含有平行边和环 每一对结点间都有边相连
3、图的分类：
①无向图：每条边均为无向边的图称为无向图。 ②有向图：每条边均为有向边的图称为有向图。
③混合图：有些边是无向边，有些边是有向边的图称
为混合图。
v1 (孤立点) v5 V1’ v1 环
v2
v4 v3 (a)无向图
V2’
V3’ (b)有向图 V4’
v2
v4 v3 ( c ) 混合图
4、点和边的关联：如ei=(u，v)或ei=<u，v>称u， v与ei关联。 5、点与点的相邻：关联于同一条边的结点称为邻 接点。
(图论)图的基本概念--第一章
证明 设G＝<V，E>为任意一图，令
V1＝{v|v∈V∧d(v)为奇数} V2＝{v|v∈V∧d(v)为偶数} 则V1∪V2＝V，V1∩V2＝ ，由握手定理可知
2m d (v) d (v) d (v)
vV
vV1
vV2
由于2m和 d (v) ，所以 d (v) 为偶数，
举例
NG(v1) ＝ {v2，v5} NG(v1) ＝ {v1，v2，v5} IG(v1) ＝ {e1，e2，e3}
Г+D(d ) ＝ {c} Г-D(d ) ＝ {a，c} ND(d ) ＝ {a，c} ND(d ) ＝ {a，c，d}
简单图与多重图
定义1.3 在无向图中，关联一对顶点的无向边如果多于1条，则 称这些边为平行边，平行边的条数称为重数。 在有向图中，关联一对顶点的有向边如果多于1条，并且这些 边的始点和终点相同(也就是它们的方向相同)，则称这些边 为平行边。 含平行边的图称为多重图。 既不含平行边也不含环的图称为简单图。
无向图和有向图
定义1 一个无向图是一个有序的二元组<V，E>,记作G，其中 （1）V≠称为顶点集，其元素称为顶点或结点。 （2）E称为边集，它是无序积V&V的多重子集，其元素称为无向 边，简称边。
定义2 一个有向图是一个有序的二元组<V，E>，记作D，其中 （1）V≠称为顶点集，其元素称为顶点或结点。 （2）E为边集，它是笛卡儿积V×V的多重子集，其元素称为有向 边，简称边。
vV2
vV1
但因V1中顶点度数为奇数， 所以|V1|必为偶数。
问题研究
问题：在一个部门的25个人中间，由于意见不同，是否可能每 个人恰好与其他5个人意见一致？
图论讲义1图路树
这便证明了 G 是一个二部图。 证毕。
7. 连通性 图中两点的连通：如果在图 G 中 u，v 两点有路相通，则称顶点 u，v 在图 G 中连通。 连通图（connected graph）：图 G 中任二顶点都连通。 图的连通分支（connected branch, component）：若图 G 的顶点集 V(G)可划分为若干非空子集
这便定义出一个图。
2. 图的图示
通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的）。 这样画出的平面图形称为图的图示。
例如，例 1.1.1 中图的一个图示为
v1
v2
e1
e6 e5
e2
e4
v5
e7
v3
e3 v4
注：（1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。
3
（8） 完全图(complete graph)
（9） 图的顶点数（图的阶）ν 、边数 ε
（10） 顶点 v 的度(degree)：d(v) = 顶点 v 所关联的边的数目（环边计两次）。
（11） 图 G 的最大度： ∆(G) = max{dG (v) | v ∈V (G)}
图 G 的最小度：δ (G) = min{dG (v) | v ∈V (G)}
证明：按每个顶点的度来计数边，每条边恰数了两次。 推论 1.1.1 任何图中，奇度顶点的个数总是偶数（包括 0）。 4. 子图
子图(subgraph)：如果V (H ) ⊆ V (G) 且 E(H ) ⊆ E(G) ，则称图 H 是 G 的子图，记为 H ⊆G。
生成子图(spanning subgraph): 若 H 是 G 的子图且V (H ) = V (G) ，则称 H 是 G 的生成子图。
7. 连通性 图中两点的连通：如果在图 G 中 u，v 两点有路相通，则称顶点 u，v 在图 G 中连通。 连通图（connected graph）：图 G 中任二顶点都连通。 图的连通分支（connected branch, component）：若图 G 的顶点集 V(G)可划分为若干非空子集
这便定义出一个图。
2. 图的图示
通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的）。 这样画出的平面图形称为图的图示。
例如，例 1.1.1 中图的一个图示为
v1
v2
e1
e6 e5
e2
e4
v5
e7
v3
e3 v4
注：（1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。
3
（8） 完全图(complete graph)
（9） 图的顶点数（图的阶）ν 、边数 ε
（10） 顶点 v 的度(degree)：d(v) = 顶点 v 所关联的边的数目（环边计两次）。
（11） 图 G 的最大度： ∆(G) = max{dG (v) | v ∈V (G)}
图 G 的最小度：δ (G) = min{dG (v) | v ∈V (G)}
证明：按每个顶点的度来计数边，每条边恰数了两次。 推论 1.1.1 任何图中，奇度顶点的个数总是偶数（包括 0）。 4. 子图
子图(subgraph)：如果V (H ) ⊆ V (G) 且 E(H ) ⊆ E(G) ，则称图 H 是 G 的子图，记为 H ⊆G。
生成子图(spanning subgraph): 若 H 是 G 的子图且V (H ) = V (G) ，则称 H 是 G 的生成子图。
图论（1）--图的基本概念
图论（1）--图的基本概念有向图和⽆向图的建⽴以及赋权图引⼊Q：什么是图论？A：图论是数学的⼀个分⽀。
它以图为研究对象。
图论中的图是由若⼲给定的点及连接两点的线所构成的图形，这种图形通常⽤来描述某些事物之间的某种特定关系，⽤点代表事物，⽤连接两点的线表⽰相应两个事物间具有这种关系。
现在我们来探讨⽆向图和有向图的概念以及如何去建⽴最基本的图的模型什么是图对于初⼊图论的⼈来说，复杂的定义可能会直接劝退他们，现在我来举⼀个⾮常简单的例⼦。
这就是最常见的图，由于它没有指向，即没有明确的⽅向，它被称为⽆向图。
图是由顶点和边组成的，你应该很容易就知道那些元素是顶点，那些是边。
下⾯的具有⽅向的便是有向图：若有的边有向，有的边⽆向，则称为混合图。
接下来我们将引⼊更多的概念：若两个顶点有边相连，则称两个顶点相相邻，两个点称为起点/终点或端点如1指向2，则这两个顶点相邻，这两个顶点被称为断点，⽽1被称为起点，2被称为终点。
仅含⼀个顶点的边称为⾃环在⽆向图中，包含顶点v的边的个数，称为顶点的度。
在有向图中，以v为起点的边的个数，称为点的出度，以v为终点的边的个数，称为顶点的⼊度。
⽆向图的建⽴建⽴简单⽆向图，我们使⽤Matlab，版本为R2017a。
% 函数graph(s,t)：可在 s 和 t 中的对应节点之间创建边，并⽣成⼀个图% s 和 t 都必须具有相同的元素数；这些节点必须都是从1开始的正整数，或都是字符串元胞数组。
s1 = [1,2,3,4]; %s为顶点，必须保证连续且从1开始的正整数t1 = [2,3,1,1]; %边 s与t之间是⼀⼀对应的G1 = graph(s1, t1);plot(G1) %画出效果图效果图：带汉字的⽆向图：% 注意字符串元胞数组是⽤⼤括号包起来的哦s2 = {'学校','电影院','⽹吧','酒店'};t2 = {'电影院','酒店','酒店','KTV'};G2 = graph(s2, t2);plot(G2, 'linewidth', 2) % 设置线的宽度% 下⾯的命令是在画图后不显⽰坐标set( gca, 'XTick', [], 'YTick', [] );效果图：有向图的建⽴：% ⽆权图 digraph(s,t)s = [1,2,3,4,1];t = [2,3,1,1,4];G = digraph(s, t);plot(G)set( gca, 'XTick', [], 'YTick', [] );注意边的顺序和⽅向，依次为1指向2,2指向3,3指向1,4指向1和1指向4效果图：赋权图的建⽴：赋权图，每条边都有⼀个⾮负实数对应的图。
图论-图的基本概念
若 i, j 中有奇数，比如 i 是奇数，则路 P 上 v0 到 vi 的一段与边 v0vi 构成一个偶圈； 若 i, j 都是偶数，则路 P 上 vi 到 v j 的一段与边 v0vi 及 v0v j 构成一个偶圈。证毕。 例 1.1.4 设 G 是简单图，若δ (G) ≥ 3 ,则 G 中各个圈长的最大公因数是 1 或 2。 证明：由上例知，G 中有长分别为 i + 1, j + 1和 j − i + 2 的圈。若 i + 1, j + 1， j − i + 2 三 数有公因数 m > 2 ，则 m | ( j − i) ，于是 m | 2 ，这是不可能的。因此 i + 1, j + 1， j − i + 2
证明：按每个顶点的度来计数边，每条边恰数了两次。 推论 1.1.1 任何图中，奇度顶点的个数总是偶数（包括 0）。 4. 子图
子图(subgraph)：如果 V (H ) ⊆ V (G) 且 E(H ) ⊆ E(G) ，则称图 H 是 G 的子图，记为 H ⊆G。
生成子图(spanning subgraph): 若 H 是 G 的子图且V (H ) = V (G) ，则称 H 是 G 的生成子图。
这便定义出一个图。
2. 图的图示
通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的）。 这样画出的平面图形称为图的图示。
例如，例 1.1.1 中图的一个图示为
v1
v2
e1
e6 e5
e2
e4
v5
e7
v3
e3 v4
注：（1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。
证明：按每个顶点的度来计数边，每条边恰数了两次。 推论 1.1.1 任何图中，奇度顶点的个数总是偶数（包括 0）。 4. 子图
子图(subgraph)：如果 V (H ) ⊆ V (G) 且 E(H ) ⊆ E(G) ，则称图 H 是 G 的子图，记为 H ⊆G。
生成子图(spanning subgraph): 若 H 是 G 的子图且V (H ) = V (G) ，则称 H 是 G 的生成子图。
这便定义出一个图。
2. 图的图示
通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的）。 这样画出的平面图形称为图的图示。
例如，例 1.1.1 中图的一个图示为
v1
v2
e1
e6 e5
e2
e4
v5
e7
v3
e3 v4
注：（1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。
计算机中图的名词解释
计算机中图的名词解释在计算机领域中，图（Graph）是一种常见的数据结构，用于描述对象之间的关系和相互作用。
图的概念最早由数学家欧拉提出，并且在计算机科学中得到广泛运用。
本文将从图的基本概念和操作开始，逐步介绍计算机中图的相关术语和应用。
1. 图的基本概念图由节点（Node）和边（Edge）组成。
节点表示对象或实体，边表示节点之间的连接关系。
图可以分为有向图（Directed Graph）和无向图（Undirected Graph）。
在有向图中，边具有方向性，表示从一个节点流向另一个节点；而在无向图中，边没有方向性，表示两个节点之间的相互关系。
2. 图的存储方式为了在计算机中表示和处理图，常见的存储方式有邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）。
邻接矩阵是一个二维数组，其中行和列表示节点，矩阵的值表示节点之间是否有边相连。
邻接表则使用链表的形式来表示节点之间的连接关系，每个节点对应一个链表，链表中存储了与该节点相连的其他节点。
3. 图的遍历图的遍历是指沿着图中的路径，依次访问所有节点的过程。
常见的图遍历算法有深度优先搜索（Depth-First Search）和广度优先搜索（Breadth-First Search）。
深度优先搜索先选择一个起始节点，沿着路径一直深入直到无法继续，然后回溯到其他未访问的节点，继续深入；而广度优先搜索则是从起始节点开始，并逐层扩展，逐层访问。
4. 最短路径算法最短路径算法用于计算两个节点之间的最短路径，即路径上边的权值之和最小。
其中，最常用的最短路径算法是狄克斯特拉算法（Dijkstra Algorithm）。
该算法通过逐步更新节点到其他节点的距离，找到起始节点到目标节点的最短路径。
5. 拓扑排序拓扑排序（Topological Sorting）是一种对有向无环图进行排序的算法。
在有向图中，如果节点 A 的边指向节点 B，那么 B 必须在 A 之后才能出现在排序结果中。
第14章-图基本概念
环（长为1的圈）的长度为1，两条平行边构成的圈长度为 2，无向简单图中，圈长3，有向简单图中圈的长度2.
不同的圈（以长度3的为例） ① 定义意义下 无向图：图中长度为l（l3）的圈，定义意义下为2l个 有向图：图中长度为l（l3）的圈，定义意义下为l个 ② 同构意义下：长度相同的圈均为1个
试讨论l=3和l=4的情况
v 的关联集 I( v ) { e |e E ( G ) e 与 v 关 } 联 ② vV(D) (D为有向图)
v的后继D 元 (v)集 {u|uV(D)v,u E(D)uv} v的先驱D 元 (v)集 {u|uV(D)u,v E(D)uv} v的邻域ND(v)D (v)D (v) v的闭邻N域 D(v)ND(v){v}
2 m d (v) d (v) d (v)
v V
v V 1
v V 2
由于2m, d(v) 均为偶数，所以 d(v) 为偶数，但因为V1中
vV2
vV1
顶点度数为奇数，所以|V1|必为偶数.
12
握手定理应用
补例1 无向图G有16条边，3个4度顶点，4个3度顶点，其 余顶点度数均小于3，问G的阶数n为几？ 解 本题的关键是应用握手定理. 设除3度与4度顶点外，还有x个顶点v1, v2, …, vx， 则
8
多重图与简单图
定义14.3 (1) 无向图中的平行边及重数:如果关联一对顶点的无向边多
于1条，则称这些边为平行边，平行边的条数称为重数。 (2) 有向图中的平行边及重数（注意方向性） 如果关联一对顶点的有向边多于1条，并且这些边的始点与
终点相同，则称这些边为平行边，平行边的条数称为重数。 (3) 多重图：含平行边的图称为多重图。 (4) 简单图：既不含平行边也不含有环的图。 在定义14.3中定义的简单图是极其重要的概念
不同的圈（以长度3的为例） ① 定义意义下 无向图：图中长度为l（l3）的圈，定义意义下为2l个 有向图：图中长度为l（l3）的圈，定义意义下为l个 ② 同构意义下：长度相同的圈均为1个
试讨论l=3和l=4的情况
v 的关联集 I( v ) { e |e E ( G ) e 与 v 关 } 联 ② vV(D) (D为有向图)
v的后继D 元 (v)集 {u|uV(D)v,u E(D)uv} v的先驱D 元 (v)集 {u|uV(D)u,v E(D)uv} v的邻域ND(v)D (v)D (v) v的闭邻N域 D(v)ND(v){v}
2 m d (v) d (v) d (v)
v V
v V 1
v V 2
由于2m, d(v) 均为偶数，所以 d(v) 为偶数，但因为V1中
vV2
vV1
顶点度数为奇数，所以|V1|必为偶数.
12
握手定理应用
补例1 无向图G有16条边，3个4度顶点，4个3度顶点，其 余顶点度数均小于3，问G的阶数n为几？ 解 本题的关键是应用握手定理. 设除3度与4度顶点外，还有x个顶点v1, v2, …, vx， 则
8
多重图与简单图
定义14.3 (1) 无向图中的平行边及重数:如果关联一对顶点的无向边多
于1条，则称这些边为平行边，平行边的条数称为重数。 (2) 有向图中的平行边及重数（注意方向性） 如果关联一对顶点的有向边多于1条，并且这些边的始点与
终点相同，则称这些边为平行边，平行边的条数称为重数。 (3) 多重图：含平行边的图称为多重图。 (4) 简单图：既不含平行边也不含有环的图。 在定义14.3中定义的简单图是极其重要的概念
图论讲义-图的基本概念
到目前为止，判断两图同构 还只能从定义出发。判断过 程中不要将两图同构的必要 条件当成充分条件。
注意：在研究图的过程中，顶点的位置以及边的曲直长短 都是无关紧要的。而且也没有假定这些顶点和边都要在一 个平面上（正方体的顶点和棱也可构成图）。我们研究的 只是顶点的多少及这些边是连接那些顶点的。
五、顶点的度
若e=(u,v)，则表示u到v的一条边（Edge），此时的
图称为无向图(Undigraph)。
有向图（Digraph）、无向图(Undigraph)
V1 V4
V1
V5 V2 V3 V2 V3
V4
有向图（Digraph）、无向图(Undigraph)
例1、设V={v1,v2,v3,v4,}，E={e1,e2,e3,e4,e5}，满足e1=(v1,v2)，
六、路与图的连通性
v1 v2 v5
图G中，取Γ1=v1v2v3，
v3
v4
G
Γ2=v1v2v3v4v2， Γ3=v1v2v3v2v3v4 则 Γ1,Γ2,Γ3依次为长为2,4,5的 通路，其中Γ1与Γ2为简单通路， Γ1为基本通路。 由定义可看出,G中v1v2v5v1为 长为3的圈，v1v2v3v4v2v5v1为 长为6的简单回路。
e2=(v2,v3)，e3=(v2,v3)，e4=(v3,v4)，e5=(v4,v4),则G=(V,E)是一个图。图 中边集E的边也可直接由点对表示，而将E作为多重集（即允许E中有相同元素的 集合）。 例2、设V={v1,v2,v3,v4}，E={(v1,v2)，(v1,v2)，(v2,v3)}，则H=(V,E)是 一个图。 e
d (V ) 2m
i 1 i
n
五、顶点的度
推论：任何图（无向图或有向图）中，度为奇数的顶点个
图论—基本概念
2) 在无向图中，两个结点间(包括结点自身间)若有几条 边，则这几条边称为平行边；
3) 两结点vi，vj间相互平行的边的条数称为边(vi，vj) 或<vi，vj>的重数；
4) 含有平行边的图称为多重图； 5) 非多重图称为线图； 6) 无自回路的线图称为简单图。
2020年3月14日
计算机科学与技术学院
G3＝<V3,E3>＝<{1,2,3,4,5},{<1,2>,(1,4),<4,3>,
<3,5>,<4,5>}>
2020年3月14日
计算机科学与技术学院
第9页
几个基本概念
1) 在一个图中，关联结点vi和vj的边e，无论是有向的 还是无向的，均称边e与结点vI和vj相关联，而vi和 vj称为邻接点，否则称为不邻接的；
设V＝{v1, v2,…,vn}为图G的结点集，称 (deg(v1),deg(v2),…,deg(vn))为G的度数序列。
上图的度数序列为（3,3,5,1,0）。
2020年3月14日
计算机科学与技术学院
第18页
例
1) （3,3,2,3），（5,2,3,1,4）能成为图的度数序列吗？ 为什么？
2) 已知图G中有10条边，4个度数为3的结点，其余结点 的度数均小于等于2，问G中至少有多少个结点？为什 么？
对任意e∈E，都有e与<u,v>∈VV或者
(u,v)∈V&V相对应。
2020年3月14日
计算机科学与技术学院
第6页
图的分类(按边的方向)
1) 若边e与无序结点对(u，v)相对应，则称边e为无向边, 记为e＝(u，v)，这时称u，v是边e的两个端点；
3) 两结点vi，vj间相互平行的边的条数称为边(vi，vj) 或<vi，vj>的重数；
4) 含有平行边的图称为多重图； 5) 非多重图称为线图； 6) 无自回路的线图称为简单图。
2020年3月14日
计算机科学与技术学院
G3＝<V3,E3>＝<{1,2,3,4,5},{<1,2>,(1,4),<4,3>,
<3,5>,<4,5>}>
2020年3月14日
计算机科学与技术学院
第9页
几个基本概念
1) 在一个图中，关联结点vi和vj的边e，无论是有向的 还是无向的，均称边e与结点vI和vj相关联，而vi和 vj称为邻接点，否则称为不邻接的；
设V＝{v1, v2,…,vn}为图G的结点集，称 (deg(v1),deg(v2),…,deg(vn))为G的度数序列。
上图的度数序列为（3,3,5,1,0）。
2020年3月14日
计算机科学与技术学院
第18页
例
1) （3,3,2,3），（5,2,3,1,4）能成为图的度数序列吗？ 为什么？
2) 已知图G中有10条边，4个度数为3的结点，其余结点 的度数均小于等于2，问G中至少有多少个结点？为什 么？
对任意e∈E，都有e与<u,v>∈VV或者
(u,v)∈V&V相对应。
2020年3月14日
计算机科学与技术学院
第6页
图的分类(按边的方向)
1) 若边e与无序结点对(u，v)相对应，则称边e为无向边, 记为e＝(u，v)，这时称u，v是边e的两个端点；
1图的基本概念
(或若边<vi,vj>∈E,当且仅当 边<f(vi),f(vj)>∈E’),则称G与
G’同构,记作G≌G’. (同构a图 要保持b 边的“1 关联”4关系)
例如:右边所示的两个图: c
d
3
2
G=<V,E> G’=<V’,E’>
构造映射f:VaV1’ b 2 c 3 d 4
a 1 b 2 c 3 d 4
degi(a)=2 degi(b)=2 degi(c)=1 degi(d)=1
dego(a)=2 dego(b)=3 dego(c)=1 dego(d)=0
定理8-1.3 G=<V,E>是有向图, 则G的所有结点的出度之和
等于入度之和.
证明: 因为图中每条边对应一个出度和一个入度. 所以所
有结点的出度之和与所有结点的入度之和都等于有向边
如果可能,请试画出它的图. 哪些可能不是简单图?
a) (1,2,3,4,5)
b) (2,2,2,2,2)
c) (1,2,3,2,4)
2.已知无向简单图G中,有10条边,4个3度结点,其余结点的
度均小于或等于2,问G中至少有多少个结点?为什么?
1. a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4)
足够的。例如“目”的图形就是满足条件的例子。
七. 有向图结点的出度和入度:(in degree out degree)
G=<V,E>是有向图,v∈V v的出度: 从结点v射出的边数.
记作deg+(v) 或 dego(v)
a
b
c d
v的入度: 射入结点v的边数. 记作deg-(v) 或 degi(v)
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
这些学科都以图作为工具来解决实际问题和理 论问题。
5
图论在计算机科学中的应用： 地图信息系统、电路设计、超文本、计算机
网络、程序结构、数据结构、Petri网、形式语 言与自动机…..
6
图的基本概念 1. 图
7
定义（无序对）对于二元集合{a,b}，由于元素 之间没有次序，称{a,b}为无序对，记为（a,b）。
（2）给定有向图D=<V，E>，其中V={a,b,c,d}， E={<a,a>,<a,b>,<a,b>,<a,d>,<d,c>,<c,d>,<c，b>}
画出G与D的图形。
14
定义1.3 在无向图中， G的两个 顶点之间可能存在若干条不同的边， 称这些边为平行边或重边（multiple edges） 。
这样问题就等价于在图中从某一结点出发找一条通 路，通过它的每条边一次且仅一次，并回到原结点。
1736年数学家欧拉发表了第一篇图论论文，解诀了 哥尼斯堡七桥问题。欧拉认证了该问题无解。
3
从十八世纪中叶到二十世纪中叶，漫长的200年 中，图论几乎停留在数学游戏阶段，在此阶段，图论 问题大量出现，如著名的四色问题、Hamilton问题以 及图的可平面问题等。
15
图的有关规定和概念 通常G泛指图，包括无向图和有向图。 V、E 分 别 表 示 G 的 顶 点 集 和 边 集 ， 所 以 用 | V|、
|E|分别表示G的顶点数和边数。 如果|V|和|E|是有限的，则称G为有限图；否则
为无限图。 本课程只涉及有限图。
16
图的有关规定和概念 图的顶点数|V|称为图的阶（order）。 若|V|=n，则称G为n阶图。 若E=，则称G为零图（null graph）。含有n个顶
当vi=vj时，称ek为环，它是vi到自身的有向边。
11
每条边都是无向边的图称为无向图（undirected graph）。
每条边都是有向边的图称为有向图（directed graph）。
既有无向边又有有向边的图称为混合图（mixed graph）。
将有向图各有向边均改成无向边后得到的无向图 称为原来有向图的基图（underlying graph）。
图 论（Graph Theory）
1
哥尼斯堡七桥问题
每逢假日，城中居民进行环城逛游，这样就产生了 一个问题：能不能设计一次‘遍游’，使得从某地出发， 对每座跨河桥只走一次，而在遍历了七座桥之后，却又 能回到原地。
2
城的四个陆地部分分别以点A，B，C，D表示， 将陆地设想为图的结点，把桥画成相应的连接边。
当vi=vj circuit）。
时
，
称
ek
为
环
（
loop
）
或自
回
路
有向图directed graph） 一个有向图是 一个有序的二元组<V，E>，记作D，即D=<V，E>，其 中
⑴ V={v1，v2，…，vn}是非空集合，称为D的顶 点集，V中元素称为顶点或结点；
⑵ E为边集，是笛卡儿积V×V的多重子集，其元 素称为有向边，简称边。 vj是由ek定的义端，点有，向vi图为的ek的边始ek点是（有o序ri对gin<）vi，，vvjj为>，ek称的终vi， 点（terminus）。
12
在一些具体问题中，图的每条边上标注了具有 特定含义的数值，该数值称为该边的权（weight）。
边上带权的图成为带权图（weighted graph）或 网（network）， 记为G=<V, E,W> 。
13
例（1）给定无向图G=<V，E>，其中V={v1,v2,v3,v4,v5}， E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5), (v1,v5),(v4,v5)}
平行边的条数称为重数。 在有向图中，两个顶点间方向相 同的若干条边称为平行边。 两个顶点间方向相反的两条有向 边称为对称边（symmetric edges）。 含平行边的图称为多重图 （multigraph） ，既不含平行边也不 含 环 的 图 称 为 简 单 图 （ simple graph） 。
⑴ V={v1，v2，…，vn}是非空集合，称为G的 顶点集（vertex set），V中元素称为顶点或结点；
⑵ E={e1，e2，…，en}是无序积V&V的一个多 重子集，称为的边集（edge set），E中的元素称为无 向边，简称边。
无 ver序tic由e对s定）（。义v知i，，vj图）G，的边称evki是，Vv的j 是两e个k 的元素端v点i，（vje的nd
定义（无序积）设A，B为集合，则称{（a,b）| aA∧bB}为A与B的无序积，记为A&B。
说明： （1） A、B非空时，A×BB×A。 （2）无论a，b是否相等，均有(a,b)=(b,a)，
所以A&B=B&A。
9
定义1.1（无向图undirected graph）一个无向图 是一个有序的二元组<V，E>，记作G，即G=<V，E>， 其中
点的零图称为n阶零图，记作Nn，特别的称N1为平凡 图（trivial graph）。
规定V=的图为空图（empty graph），并记为。 称 顶 点 或 边 用 字 母 标 定 的 图 为 标 定 图 （ labeled graph），否则称为非标定图。 边很少（如|E|<|V|log2|V|）的图称为稀疏图（sparse graph）；边很多的图称为稠密图（dense graph）
在二十世纪中叶以后是图论的快速发展和应用 阶段。
由于生产管理、军事、运筹学、交通运输、计 算机科学、数字通讯等方面提出的实际问题的需要， 特别是许多离散性问题的出现、刺激和推动，以及由 于有了大型电子计算机，而使大规模问题的求解成为 可能，图论及其应用的研究得到了飞速的发展。
4
图论的应用非常广泛，主要有运筹学、网络理 论、信息论、控制论、博奕论、化学、生物学、社 会科学、语言学，以及计算机科学等等。
定义（有序对）由两个元素x和y（允许x=y）按 一定顺序排列成的二元组叫做一个有序对，记作<x， y>，其中x是它的第一元素，y是它的第二元素。
有序对<x，y>的性质（与无序对不同之处）： 1、当xy时，<x，y><y，x> 2、<x，y>=<u，v>的充分必要条件是x=u且y=v
8
定义 (笛卡儿积) 设A，B是任意两个集合，用A 中元素作第一元素，B中元素作第二元素，构成的有 序对，所有这样有序对的全体组成的集合称集合A和B 的笛卡儿积，记作A×B。
5
图论在计算机科学中的应用： 地图信息系统、电路设计、超文本、计算机
网络、程序结构、数据结构、Petri网、形式语 言与自动机…..
6
图的基本概念 1. 图
7
定义（无序对）对于二元集合{a,b}，由于元素 之间没有次序，称{a,b}为无序对，记为（a,b）。
（2）给定有向图D=<V，E>，其中V={a,b,c,d}， E={<a,a>,<a,b>,<a,b>,<a,d>,<d,c>,<c,d>,<c，b>}
画出G与D的图形。
14
定义1.3 在无向图中， G的两个 顶点之间可能存在若干条不同的边， 称这些边为平行边或重边（multiple edges） 。
这样问题就等价于在图中从某一结点出发找一条通 路，通过它的每条边一次且仅一次，并回到原结点。
1736年数学家欧拉发表了第一篇图论论文，解诀了 哥尼斯堡七桥问题。欧拉认证了该问题无解。
3
从十八世纪中叶到二十世纪中叶，漫长的200年 中，图论几乎停留在数学游戏阶段，在此阶段，图论 问题大量出现，如著名的四色问题、Hamilton问题以 及图的可平面问题等。
15
图的有关规定和概念 通常G泛指图，包括无向图和有向图。 V、E 分 别 表 示 G 的 顶 点 集 和 边 集 ， 所 以 用 | V|、
|E|分别表示G的顶点数和边数。 如果|V|和|E|是有限的，则称G为有限图；否则
为无限图。 本课程只涉及有限图。
16
图的有关规定和概念 图的顶点数|V|称为图的阶（order）。 若|V|=n，则称G为n阶图。 若E=，则称G为零图（null graph）。含有n个顶
当vi=vj时，称ek为环，它是vi到自身的有向边。
11
每条边都是无向边的图称为无向图（undirected graph）。
每条边都是有向边的图称为有向图（directed graph）。
既有无向边又有有向边的图称为混合图（mixed graph）。
将有向图各有向边均改成无向边后得到的无向图 称为原来有向图的基图（underlying graph）。
图 论（Graph Theory）
1
哥尼斯堡七桥问题
每逢假日，城中居民进行环城逛游，这样就产生了 一个问题：能不能设计一次‘遍游’，使得从某地出发， 对每座跨河桥只走一次，而在遍历了七座桥之后，却又 能回到原地。
2
城的四个陆地部分分别以点A，B，C，D表示， 将陆地设想为图的结点，把桥画成相应的连接边。
当vi=vj circuit）。
时
，
称
ek
为
环
（
loop
）
或自
回
路
有向图directed graph） 一个有向图是 一个有序的二元组<V，E>，记作D，即D=<V，E>，其 中
⑴ V={v1，v2，…，vn}是非空集合，称为D的顶 点集，V中元素称为顶点或结点；
⑵ E为边集，是笛卡儿积V×V的多重子集，其元 素称为有向边，简称边。 vj是由ek定的义端，点有，向vi图为的ek的边始ek点是（有o序ri对gin<）vi，，vvjj为>，ek称的终vi， 点（terminus）。
12
在一些具体问题中，图的每条边上标注了具有 特定含义的数值，该数值称为该边的权（weight）。
边上带权的图成为带权图（weighted graph）或 网（network）， 记为G=<V, E,W> 。
13
例（1）给定无向图G=<V，E>，其中V={v1,v2,v3,v4,v5}， E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5), (v1,v5),(v4,v5)}
平行边的条数称为重数。 在有向图中，两个顶点间方向相 同的若干条边称为平行边。 两个顶点间方向相反的两条有向 边称为对称边（symmetric edges）。 含平行边的图称为多重图 （multigraph） ，既不含平行边也不 含 环 的 图 称 为 简 单 图 （ simple graph） 。
⑴ V={v1，v2，…，vn}是非空集合，称为G的 顶点集（vertex set），V中元素称为顶点或结点；
⑵ E={e1，e2，…，en}是无序积V&V的一个多 重子集，称为的边集（edge set），E中的元素称为无 向边，简称边。
无 ver序tic由e对s定）（。义v知i，，vj图）G，的边称evki是，Vv的j 是两e个k 的元素端v点i，（vje的nd
定义（无序积）设A，B为集合，则称{（a,b）| aA∧bB}为A与B的无序积，记为A&B。
说明： （1） A、B非空时，A×BB×A。 （2）无论a，b是否相等，均有(a,b)=(b,a)，
所以A&B=B&A。
9
定义1.1（无向图undirected graph）一个无向图 是一个有序的二元组<V，E>，记作G，即G=<V，E>， 其中
点的零图称为n阶零图，记作Nn，特别的称N1为平凡 图（trivial graph）。
规定V=的图为空图（empty graph），并记为。 称 顶 点 或 边 用 字 母 标 定 的 图 为 标 定 图 （ labeled graph），否则称为非标定图。 边很少（如|E|<|V|log2|V|）的图称为稀疏图（sparse graph）；边很多的图称为稠密图（dense graph）
在二十世纪中叶以后是图论的快速发展和应用 阶段。
由于生产管理、军事、运筹学、交通运输、计 算机科学、数字通讯等方面提出的实际问题的需要， 特别是许多离散性问题的出现、刺激和推动，以及由 于有了大型电子计算机，而使大规模问题的求解成为 可能，图论及其应用的研究得到了飞速的发展。
4
图论的应用非常广泛，主要有运筹学、网络理 论、信息论、控制论、博奕论、化学、生物学、社 会科学、语言学，以及计算机科学等等。
定义（有序对）由两个元素x和y（允许x=y）按 一定顺序排列成的二元组叫做一个有序对，记作<x， y>，其中x是它的第一元素，y是它的第二元素。
有序对<x，y>的性质（与无序对不同之处）： 1、当xy时，<x，y><y，x> 2、<x，y>=<u，v>的充分必要条件是x=u且y=v
8
定义 (笛卡儿积) 设A，B是任意两个集合，用A 中元素作第一元素，B中元素作第二元素，构成的有 序对，所有这样有序对的全体组成的集合称集合A和B 的笛卡儿积，记作A×B。