第七章 图论.ppt

第7章图论
图的基本概念
路与回路
图的矩阵表示
欧拉图
哈密尔顿图
树
二部图和平面图
第7章图论
图的基本类型
所谓图G是一个三元组,G=<V(G),E(G),φG>,其
中V(G)是一个非空的结点集合,E(G)是边的集合,φG是从边
集合E到结点无序偶或有序偶集合上的函数。
如果两个结点之间有多条边(对于有向图,则有多条
同方向的边),则称这些边为平行边,两相结点a,b间平行边的
条数称为边的重数。含有平行边的图称为多重图,不含平行边和
自回路的图称为简单图。
第7章图论
图中结点的度数

设图G是无向图,v是图G中的结点,所有与v关联的边
的条数,称为点v的度数,记作deg(v)。
设图G是具有n个点,m条边的无向图,其中结点集
合为V={v1,v2,…,vn},则
第7章图论
图中结点的度数

设图G是有向图,v是图G中的结点,以v为始点的有向
边的条数称为v的出度,记个deg+(v),以v为终点的有向边的条数
称为v的入度,记作deg-(v)。
设有向图G具有n个结点,m条边,其中结点构成的集
合V={v1,v2,…,vn},则有
第7章图论
完全图

在n阶无向图中,如果任意两个不同的结点之间都有
一条边关联,则称此无向图为无向完全图,记作Kn。
n个结点的无向完全图Kn的边数是。
第7章图论
完全图

n个结点的有向完全图Kn的边数是n2。
在n阶有向图中,如果任意两个结点都有两条方向相反的
有向边关联,且每一个结点都有自回路,则称此有向图为有向完
全图。
第7章图论
完全图

设G为n阶有向图,如果G的底图为无向完全图Kn,则称G
为竞赛图。
第7章图论
图的同构
设图G的点集为V,边集为E,图G′的点集为V′,边集
为E′。如果存在着V到V′的双射函数f,使对任意的u,vV,(u
,v)E(或<u,v>E),当且仅当(f(u),f(v))E′(或<f
(u),f(v)>E′),则称图G和G′同构,记作GG′。
第7章图论
补图
设G=<V,E>为任意的n阶无向简单图,则所有使G成为
Kn添加的边和G的n个结点构成的图称为图G的补图,记作。
设G=<V,E>是任意一个n阶无向图,V={v1,v2,…,
vn},称d(v1),d(v2),…,d(vn)为G的度数列。对于结点
标定的无向图,它的度数列是唯一的。反之,对于给定的非负整
数列d=(d1,d2,…,dn),若存在以V={v1,v2,…,vn}为结点
n阶无向图G,使得d(vi)=di,则称d是可图化的。特别地,若得
到的图是简单图,则称d是可简单图化的。
第7章图论
补图
设非负整数列d=(d1,d2,…,dn),当且仅当为偶数
时,d是可图化的。
设非负整数列d=(d1,d2,…,dn),(n-1)
≥d1≥d2≥…≥d n≥0,则d是可简单图化的,当且仅当对于每个
整数r,1≤r≤(n-1),≤r(r-1)+且为偶数。
设非负整数列d=(d1,d2,…,dn),(n-1)
≥d1≥d2≥…≥d n≥0,则d是可简单化的当且仅当d′=(-1,-
1,…,-1,,…,)。