第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无向图一个无向图是一个七元组<V，E>，即：G=<V，E>，其中:（1）V是G的顶点集，V（G）(2)E是G的边集，也称无向边，E（G）
§7.1 无向图及有向图 2、定义7.1 无向图 一个无向图是一个二元组<V，E>，即： G= <V，E>，其中： （1）V是G的顶点集，V（G） （2）E是G的边集，也称无向边， E（G）
87.1无向图及有向图无向图示例：eG=<V, E>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，E> 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)