v2 v3 3 有向图G1 是有向图G1的子图，是连通的。但它是不 是极大的呢？能不能找到包含它的更大的子 图也是连通的？ 找不到包含它的更大的子图也是连通的， 所以它就是极大的。所以它是强连通分量
• 是有向图G1的子图，是连通的。但它是不 是极大的呢?能不能找到包含它的更大的子 图也是连通的？ • 找不到包含它的更大的子图也是连通的， 所以它就是极大的。所以它是强连通分量 。 v1 v2 v3 v4 有向图G1 v1 v3 v4
有向树：在有向图中，一个顶点入度为0，其余 顶点的入度都是1，则是一棵有向树。 判断下面两个图是不是有向树？ vl 3 v4 v3 v4
有向树：在有向图中，一个顶点入度为0，其余 顶点的入度都是1，则是一棵有向树。 判断下面两个图是不是有向树？ v1 v3 v4 v1 v3 v4
。2、无向图（直观的说：不带箭头的就是无 向图) 2 v3 75 无向图G2 顶点：即图中的圆圈。 无向图G2共有四个顶点：V1,V2,V3,V4,V5 边：即图中的线段。 无向图G2共有6条边：记为(v1,V2),(V1,V4) (v2,v3),(2V5),(v3,V4),(V3,V5)
• 2、无向图（直观的说：不带箭头的就是无 向图） v4 v5 v3 v1 v2 无向图G2 顶点：即图中的圆圈。 无向图G2共有四个顶点：v1,v2,v3,v4, v5 边：即图中的线段。 无向图G2共有6条边：记为（v1,v2）,（v1,v4）, （v2,v3）,（v2,v5）,（v3,v4）,（v3,v5）
v2 y3 v5 无向图G2 。无向图的二元组表示：G2=(V,E) ·V={V1,v2,v3,V4,v5} E={(V1,V2),(V1,V4),(V2V3), (V2,V5),(V3,V4),(V3,v5)}
• 无向图的二元组表示： G2＝（V，E） • V={v1,v2,v3,v4,v5} E={（v1,v2）,（v1,v4）,（v2,v3）, （v2,v5）,（v3,v4）,（v3,v5）} v4 v5 v3 v1 v2 无向图G2
例请用二元组描述无向图 A B V=A,BCD} A=(A,B),(A,C),(AD),(C,D),(B,D)}
• 例请用二元组描述无向图 D A B C V={A,B ,C ,D } A={（A,B）,（A,C）,（A,D）, ( C,D) , (B,D) }