天津理工大学：《离散数学》课程教学资源（PPT课件）第节章 图的基本概念 7.1 无向图及有向图 7.2 通路、回路、图的连通性

第7章图的基本概念（1-2节）

第7章 图的基本概念 （1-2节）

内容介绍$7.1无向图及有向图$7.2通路、回路、图的连通性$ 7.3图的矩阵表示$ 7.4最短路径及关键路劲$ 7.5例题分析

内容介绍 ✓§7.1 无向图及有向图 ✓§7.2 通路、回路、图的连通性 ✓§7.3 图的矩阵表示 ✓§7.4 最短路径及关键路劲 ✓§7.5 例题分析

S7.1无向图及有向图无序集1、设A、B为两个集合，称[a,b}IaEA^bEB}为A与B的无序集，记作A&B。例如，A=[a,a2}，B=[b1,b2]A&B=[(a1, b1), (a1,b2), (a2,b1), (a2, b2)A&A=((at, a), (a1, a2), (a2, a2))

§7.1 无向图及有向图 1、无序集 设A、B为两个集合，称 { {a,b} | a∈A ∧ b∈B }为A与B的无序 集，记作A&B。 例如，A={a1 ,a2 }，B={b1 ,b2 } A&B={(a1 , b1 ), (a1 , b2 ), (a2 , b1 ), (a2 , b2 )} A&A={(a1 , a1 ), (a1 , a2 ), (a2 , a2 )}

s7.1无向图及有向图2、定义7.1无向图一个无向图是一个七元组，即：G=，其中:（1）V是G的顶点集，V（G）(2)E是G的边集，也称无向边，E（G）

§7.1 无向图及有向图 2、定义7.1 无向图 一个无向图是一个二元组，即： G= ，其中： （1）V是G的顶点集，V（G） （2）E是G的边集，也称无向边， E（G）

87.1无向图及有向图无向图示例：eG=120eebV=[V1, V2, V3, V4,V5]esE=[(V1,V2),(V2,V2),(V2,V3)e5(V1,V3),(V1,V3),(V1,V4))V图 7-1(a)如右图7-1(a)所示：

§7.1 无向图及有向图 无向图示例： G= V={v1 , v2 , v3 , v4 ,v5 } E={(v1 ,v2 ),(v2 ,v2 ),(v2 ,v3 ), (v1 ,v3 ),(v1 ,v3 ),(v1 ,v4 )} 如右图7-1(a)所示： v2 v1 v4 v3 v5 e1 e2 e3 e4 e5 e6 图 7-1(a)

S7.1无向图及有向图3、定义7.2有向图一个有向图是一个二元组，即：D=，其中:（1）V是D的顶点集，V（D）(2)E是D的边集，也称无向边，E（D）

§7.1 无向图及有向图 3、定义7.2 有向图 一个有向图是一个二元组，即： D= ，其中： （1）V是D的顶点集，V（D） （2）E是D的边集，也称无向边， E（D）

S7.1无向图及有向图有向图示例：D= V=[V1, V2, V3, V4,V5]E=[(V1,V1),(V3,V2),(V3,V2)exes(V3,V4),(V2,V4),(V4,V5);(V5,V4), (V1,V2))图7-1(b)如右图7-1(b)所示：

§7.1 无向图及有向图 有向图示例： D= V={v1 , v2 , v3 , v4 ,v5 } E={(v1 ,v1 ),(v3 ,v2 ),(v3 ,v2 ), (v3 ,v4 ),(v2 ,v4 ),(v4 ,v5 ), (v5 ,v4 ), (v1 ,v2 )} 如右图7-1(b)所示： 图7-1(b) v2 v1 v5 v3 v4 e1 e2 e3 e4 e5 e6 e7 e8

s7.1无向图及有向图几个相关概念(1)有限图：V和E都是有穷集合的图(2)n阶图：顶点个数是n的图(3)的图。零图：E=Φ（没有边）（4）平凡图：只有1个顶点的图

§7.1 无向图及有向图 几个相关概念： （1）有限图：V和E都是有穷集合的图。 （2）n阶图：顶点个数是n的图。 （3）零图：E= ф（没有边）的图。 （4）平凡图：只有1个顶点的图

s7.1无向图及有向图4、定义7.3彼此关联（边和顶点）设ek=（vi，v）为无向图G=的一条边，称vi、V,为ek的端点，ek与v；（或vj是彼此关联的。V1问：边e,与谁关联？

§7.1 无向图及有向图 4、定义7.3 彼此关联（边和顶点） 设ek=（vi，vj）为无向图G= 的 一条边，称vi、vj 为ek的端点， ek与vi（或vj） 是彼此关联的。 v2 v1 v4 v3 v5 e1 e2 e3 e4 e5 e6 问：边e2与谁关联？

S7.1无向图及有向图(1)孤立点：无边关联的顶点。(2)环：一条边关联两个顶点重合。vi，v,重合时，为2；不(3)关联次数：v,不是ek的端点时，为0重合时，为1；1

§7.1 无向图及有向图 （1）孤立点：无边关联的顶点。 （2）环：一条边关联两个顶点重合。 （3）关联次数： vi，vj重合时，为2；不 重合时，为1； vi不是ek的端点时，为0