PDF《离散数学基础：图论》

2. 有时使用V (G), E(G)分别表示图G的顶点集和边集,|V (G)|, |E(G)|分别表示G的顶点数和 边数;

若|V (G)| = n,则称G是n阶图;

3. 若|V (G)|和|E(G)|都是有限数,则称G是有限图,我们只讨论有限图;

4. 对于图G,若|E(G)| = 0,则称G是零图,此时若G有n个顶点,则称G是n阶零图,记为Nn, 特别地,称N1为平凡图;

5. 在图的定义中要求顶点集非空,但在图进行运算时,可能使得顶点集为空,因此特别称顶点 集为空的图为空图;

6. 对于图的直观表示,如果使用了符号标记顶点与边,则称为标定图,否则称为非标定图;

7. 有向图的基图是指去掉所有有向边的方向后得到的无向图. 1.1 图的基本定义

3 下面如果只说图,则是指无向图.我们下面继续给出一些简单的术语定义: 定义 1.1.5 对于无向图或有向图G = (V, E), (1) 对于边e∈E,若e = (u, v) (或e = u, v ) ,则称边e与顶点u, v关联(incident);

(2) 对于顶点u, v∈V ,如果存在边e∈E,使得e = (u, v) (或e = u, v ) ,则称u与v邻接(adjacent), 或说u和v是相邻的顶点;

(3) 对于边e1, e2∈E,若e1和e2关联共同的顶点,则称e1和e2邻接,或说e1和e2是相邻的边. 这些术语给出了边与边、顶点与顶点之间的邻接(或说相邻)关系,以及顶点与边之间的关联 关系.实际上,我们无需纠缠于这些术语的严格定义,直观理解即可,上述定义只是如果在有歧义 的情况下,给出一个标准的说法而已. 定义 1.1.6 对于无向图或有向图G = (V, E), (1) 若边e = (v, v) (或e = v, v ) ,即它关联同一个顶点,则称e是环(loop);

(2) 若边e = (u, v)(或e = u, v )且e = (u, v)(或e = u, v ) ,即e和e 都关联相同的顶点,则称e和e 是重边(parallel edges). 注意,在有向图中,边e = u, v 和e = v, u 并不是重边.下面我们定义图的一些特殊类别: 定义 1.1.7 对于无向图G = (V, E),如果G既没有环也没有重边,则称G是简单图,在后面我们 提到图时,如果没有特别声明,都是指简单图.对于有向图G = (V, E),如果G既没有环也没有重边, 则称为有向简单图,同样,如果没有特别声明,我们所讲的有向图,都是有向简单图. 备注 1.1.8 在G. Chartrand, Ping Zhang的教材《图论导引》中,所谓的 graph 就是指简单图, 而一般的图则采用术语 multigraph . 定义 1.1.9 对于无向图G = (V, E),如果对V 的任意两个顶点u, v,都存在边e = (u, v)或e = (v, u),则称G是完全图(complete graph).具有n个顶点的完全图记为Kn.对于有向图G = (V, E), 如果对V 的任意两个顶点u, v,都存在边e = u, v 及e = v, u ,则称G是有向完全图. 利用子集的概念可定义子图的概念: 定义 1.1.10 给定图G = (V, E),如果图G = (V , E )满足V ? V 且E ? E,则称G 是G的子 图(subgraph).特别地,如果V = V ,则称G 是G的生成子图(spanning subgraph).对于G的顶点 集V 的任意子集V ? V ,取E = {e∈E | e = (u, v) 且u∈V 且v∈V },也即E 是E中那些两个端点 都在V 中边构成的集合,则称G = (V , E )是G的由V 导出的子图(induced subgraph). 上述定义是针对无向图定义的,读者不难对有向图也定义子图、生成子图及导出子图的概念. 可在图G = (V, E)上定义一些操作,而得到它的一些子图: 定义 1.1.11 对于图G = (V, E), (1) 删除顶点集:设V ? V ,则G ? V = (V ? V , E )是G的子图,G ? V 的顶点集是V ? V , 而E = {e∈E | e = (u, v) 且u ∈ V 且v ∈ V },也即E 是E中那些两个端点都不在V 中的边构成的 集合;

(2) 删除边集:设E ? E,则G ? E = (V, E ? E )是G的子图,G ? E 的顶点集仍是V ,而边集 是E ? E .