1第三篇图论第八章图8
1图的基本知识内容提要8
1图的定义及有关术语定义8
1图（graph）G由三个部分所组成：（1）非空集合V(G)，称为图G的结点集，其成员称为结点或顶点（nodesorvertices）
（2）集合E(G)，称为图G的边集，其成员称为边(edges)
I（3）函数ΨG：E(G)→(V(G)，V(G))，称为边与顶点的关联映射（associatvemapping）
这里（V(G)，V(G)）称为VG的偶对集，其成员偶对（pair）形如（u，v），u，v为结点，它们未必不同
ΨG(e)=(u,v)时称边e关联端点u，v
当(u,v)用作序偶时(V(G)，V(G))=V(G)V(G)，e称为有向边，e以u为起点,以v为终点,图G称为有向图（directedgraph）；当(u,v)用作无序偶对时，(u,v)=(v,u)，称e为无向边（或边），图G称为无向图（或图）
图G常用三元序组,或来表示
显然，图是一种数学结构，由两个集合及其间的一个映射所组成
（l）当V和E为有限集时，称G为有限图，否则称G为无限图
本书只讨论有限图
（2）当ΨG为单射时，称G为单图；当ΨG为非单射时，称G为重图，又称满足Ψ(e1)=Ψ(e2)的不同边e1,e2,为重边,或平行边
（3）当Ψ(e)＝(v,v)（或）时，称e为环（loops）
无环和重边的无向单图称为简单图
当G为有限简单图时，也常用（n，m）表示图G，其中n=V，m=E
（4）Ψ为双射的有向图称为有向完全图；对每一(u，v)，uv，均有e使Ψ(e)＝(u,v)的简单图称为无向完全图，简称完全图，n个顶点的完全图常记作Kn
（5）在单图G中，Ψ(e)＝(u,v)（或）时，也用(u,v)(或)表示边e，这时称u，v邻接e,u,v是e的端点（或称u为e的起点，v为e的终点）;也称e关联
