计算机数学基础－孙继荣
图论－图的基本概念
通路、回路、图的连通性
通路与通路的长度，设图G＝<V，E>，V＝ {v0,v1,…,vn},E={e1,e2,…,em},结点与边的交替序 列v0e1v1e2…vi-1eivi,成为结点v0到结点vi的通路. v0,vi是通路的起点和终点. 通路中边的数目就是通 路的长度. 回路，起点和终点重合的通路. 简单通路(回路)：边不重复的通路(回路). 初级通路(回路)：结点不重复的通路(回路). 复杂通路(回路)：边有重复的通路(回路).
计算机数学基础－孙继荣
图论－图的基本概念
图的矩阵表示
（无环有向图）关联矩阵： n ∑ 1 m ij = 0，列元素和为0 i = 每行元素绝对值之和等于对应点的度数， 其中1的个数为对应点的出度，－1的个数 为对应电的入度 ∑ m = deg( v )
m
所有元素的和为0，1的个数等于－1的个数，都 等于边数m
计算机数学基础－孙继荣
图论－图的基本概念
通路、回路、图的连通性
定理：一个有向图是强连通的充分必要条件 是G中有一个回路，它至少经过每个结点一 次的。 强分图：既有强连通性的最大子图 单侧分图：既有单侧连通性的最大子图 弱分图：既有弱连通性的最大子图 定理：在有向图D＝<V，E>中，它的每个 结点位于且仅位于一个强分图中
计算机数学基础－孙继荣
图论－图的基本概念
图的矩阵表示
(无向图)关联矩阵设G=<V,E>, V = n , E = m 关联矩阵M(G)= (m ij )n × m ,其中mij=vi与ej的 n× 关联次数(行为结点，列为边) m 性质：
列元素和为2 ∑ m ij = 2 m i =1 行元素和为结点的度数 ∑ m ij = deg( v i ) j =1 若行元素和为0，则对应的结点为孤立点 全部元素之和为G的总度数 ∑ ∑ m = 2 m 平行边对应的两列完全相同
计算机数学基础－孙继荣
图论－图的基本概念
图的基本概念
在无向图G＝<V,E>中，与结点v(∈V)关联的 边数，即为结点度数 度数deg(v)或d(v).； 度数 有向图G＝<V,E> < >中，，以结点v为始点的变 v 的条数为该点的出度 出度，记作deg+(v);以结点v 出度 为终点的边为该点的入度，记作deg－(v)； 结点v的出度和入度之和为度数 度数. 度数 最大度数，(G)＝max{d(v)v∈V}； 最大度数 最小度数，δ(G)=min{d(v)v∈V} 最小度数
计算机数学基础－孙继荣
图论－图的基本概念
图的基本概念
补图 G=<V,E′>，设G＝<V,E>, 以V为结点集，以 使G成为完全图所添加的边为边集E′的图，就是图G 的补图G ，即<V,E∪E′>是完全图, 其中E∩E′＝. 图的同构，设G1=<V1,E1>和G2=<V2,E2>, 存在双射 f：V1→V2，(vi,vj)∈E1, 当且仅当 (f(vi),f(vj))∈E2， 且(vi,vj)与 (f(vi),f(vj))的重数相同. 则G1≌G2. 同构充分条件：建立两个图的对应关系，这个关系 是双射函数. 同构必要条件：①结点数相同；②边数相同；③度 数相同的结点个数相同.
计算机数学基础－孙继荣
图论－图的基本概念
图的基本概念
握手定理:结点度数之和为边数的两倍 设G=<V，E>，有 ∑V deg( v ) = 2 E v∈ deg (v) = ∑ deg+ (v) ∑ 在有向图图D＝<V,E>中， v∈V v∈V 奇数度结点的个数为偶数个. 如果一个图中只有两个奇数度节点，则这两 个节点相连通。
计算机数学基础－孙继荣
图论－图的基本概念
图的基本概念
平凡图，仅有一个结点的图； 平凡图 零图（空图）：边集为空集的图<V, >，即仅有 < 零图 结点的图. . 自回路(环)，关联于同一个结点的边. 自回路 无向平行边，联结相同两个结点的多于1条的无向 无向平行边 边；有向平行边 有向平行边，联结两个结点之间的多于1条且 有向平行边 方向相同的有向边. 简单图，不含平行边和自回路的图. 简单图
计算机数学基础－孙继荣
图论－图的基本概念
通路、回路、图的连通性
点割集与割点，设无向图G＝<V，E>，存在结点集 点割集与割点 V′V，使得P(G－V′)>P(G)，而对任意V″V′，都有 P（G－V″）＝P(G)，V′称为图G的点割集. 若V′是单 元集，V′＝{v}，v叫做割点. 边割集与割边，设无向图G＝<V，E>，存在边集 边割集与割边 E′E，使得P(G－V′)>P(G)，而对任意E″E′，都有 P（G－E″）＝P(G)，E′称为图G的边割集. 若E′是单 元集，E′＝{e}，e叫做割边(桥).
计算机数学基础－孙继荣
图论－图的基本概念
图的矩阵表示
由有向图D的邻接矩阵推断从ai到aj 的长度 为l的通路的数目：Al(D) 由有向图D的邻接矩阵推断D的可达矩阵P(D) D D P(D) vi 可达v j P(D)= ( ) ，其中 p = 1
pij
n
ij
0
否则
P(D)＝ A1(D)＋ A2(D)＋…＋ An(D)将其中大 于0的元素都改为1，再将主对角线上的元素 改为1。
j =1
ij
i
计算机数学基础－孙继荣
图论－图的基本概念
图的矩阵表示
（有向图）邻接矩阵：设D＝<V,E>，相邻 矩阵 A(D)= (a ij )n ，其中aij =vi邻接到vj的 边的条数(行、列均为结点) 所有元素之和为D中长度为1的通路 n m
∑∑
i =1
j =1
a ij = m
有向图的邻接矩阵不一定对称
计算机数学基础－孙继荣
图论－图的基本概念1
图的基本概念
有n个结点的且每对结点都有边相连无向简单图， 无向完全图Kn. 此时有 E = 1 n ( n 1 ) ；有n 2 个结点的且每对结点之间都有两条方向相反的边相 关连的有向简单图为有向完全图 有向完全图，.此时有 E = n ( n 1 ) 有向完全图 设G＝<V,E>, V，E的子集V′,E′构成的图G′=<V′,E′> 是图G的子图 子图；若G′G且G′≠G，(V′V或E′E)，G′ 子图 是G的真子图 真子图. 真子图 生成子图，设图G＝<V,E>, 若E′E, 则图<V,E′>是 生成子图 <V,E>的生成子图. 即结点与原图G相同的子图，为 生成子图.
计算机数学基础－孙继荣
图论－图的基本概念
求最短路径的方法 求关键路径的方法
求各结点的最早完成时间 求各结点的最晚完成时间 求缓冲时间 求关键路径
计算机数学基础－孙继荣
图是指某些具体的事物以及这些事物之间的联系
图是一个有序对<V ，E>， V是结点集， E 是边集， 当 V,E有限时，<V,E>称为有限图；否则称无 限图. 无向边, 与无序结点(v,u)相关联的边 有向边，与有序结点<v,u>相关联的边. 无向图，每条边都是无向边的图，记作G＝<V,E>; 每条边都是有向边的图，记作D＝<V,E>. 混合图，既有有向边，也有无向边的图.
计算机数学基础－孙继荣
图论－图的基本概念
通路、回路、图的连通性
点连通度：最小的点割集的点数目 边连通度：最小的边割集的边数目 定理5： K (G ) ≤ λ (G ) ≤ δ (G )
计算机数学基础－孙继荣
图论－图的基本概念
通路、回路、图的连通性
单侧通路，有向图中，任意一对结点之间至 单侧通路 少有一个结点可达另一结点. 强连通，在有向图中任何一对结点都相互可 强连通 达. 弱连通，略去有向图D各边的方向成为无向 弱连通 连通图，称D是弱连通图. 必是 必是 由定义可知：强连通 →单侧连通 弱连通. →
n m i =1 j =1 ij
计算机数学基础－孙继荣
图论－图的基本概念
图的矩阵表示
m (无向图)相邻矩阵:设G＝<V,E>, V = n, E =， 相邻矩阵 A(G)= (a ij )n ，其中aij =vi与vj相 关联的边的条数(行、列均为结点) 性质：
A(G)是对称矩阵
对角线上的元素表示该结点处环的个数 m n v ∑aij (= ∑aij ) = deg(i ) ，若vi是孤立结点，则
计算机数学基础－孙继荣
图论－图的基本概念
通路、回路、图的连通性
定理：若图中具有n各结点，从结点vi多幅奥结点vj 存在一条通路，则从vi到vj存在一条不多于n－1条 边的通路 推论：在一个具有n个结点的图中，如果存在结点vi 到vj的一条通路，则必存在一条从vi到vj的不多于n －1条边的初级通路 定理：在一个具有n个结点的图中，如果存在结点vi 到自身的回路，则从vi到自身存在不多于n条边的回 路。 推论：在一个具有n个结点的图中，如果存在结点vi 到自身的简单回路，则从vi到自身存在不多于n条边 的初级回路。计算机数学基础－孙继荣
图论－图的基本概念
通路、回路、图的连通性
连通与连通图，无向图G中，结点u,v存在通 路，那么u,v是连通的，G中任意结点u,v都 是连通的，G是连通图. 连通分支，设G＝<V,E>，V的连通等价类V1， V2，…,Vm,子图G(V1),G(V2),…,G(Vm)成为连 通分支，P(G)表示图G连通分支的个数.
图论－图的基本概念
教师： 教师：孙继荣 电话： 电话：87768609 Email:sunjr@
图论－图的基本概念