1图的基本概心与基本定建 回路:若V≠vn分称该链为开链 否则称为闭链或回路 圈 出起点和终点外链中所含的点 均不相同的閉链; 连通图:图中任意两点之间均至少有 条通路,否则称作不连通图
22 圈： 出起点和终点外链中所含的点 均不相同的闭链； 回路： 若 v0 ≠ vn 分称该链为开链， 否则称为闭链或回路； 连通图：图中任意两点之间均至少有一 条通路，否则称作不连通图。 1.图的基本概念与基本定理
1.图的基本概念与基本定理 子图设G[V1,B1],G=[V2,E2 子图定义:如果V2cV,E2∈E称G 是G1的子图; 真子图:如果V2cV,E2CE1称G2是 G的真子图; 部分图:如果V=V,ECE1称G是 G的部分图 导出子图: 如果V三V,E[v,Vv,v,称 G是G1中由V导出的导出子图
子图 设 G1=[ V1 , E1 ],G2=[ V2 ,E2 ] 子图定义：如果 V2 V1 , E2 E1 称 G2 是 G1 的子图； 真子图：如果 V2 V1 , E2 E1 称 G2 是 G1 的真子图； 部分图：如果 V2 = V1 , E2 E1 称 G2 是 G1 的部分图； 导出子图： 如果V2 V1, E2={[vi,vj]∣vi,vjV2},称 G2 是 G1 中由V2 导出的导出子图。 1.图的基本概念与基本定理
l.图的基本概心与基本定理 有向图:关联边有方向 弧:有向图的边a=(u,v),起点u,终点v; 路:若有从u到V不考慮方向的链,且 各方向一致,则称之为从u到v的路 初等路:各顶点都不相同的路; 初等回路:=V的初等 路 连通图:若不考慮方向 是无向连通图 强连通图:任两点有路
有向图：关联边有方向 弧：有向图的边a=(u ,v),起点u,终点v； 路：若有从 u 到 v 不考虑方向的链,且 各方向一致,则称之为从u到v的路； 初等路: 各顶点都不相同的路； 初等回路:u = v 的初等 路; 连通图： 若不考虑方向 是无向连通图; 强连通图：任两点有路; 1.图的基本概念与基本定理
2.树和最小支撑树 树及其性质 在各种各样的囹中,有一类图 是十分简单又非常具有应用价值的 图,这就是树。 例8.3:已知有六个城市,它们 之间要架设电话线。要求任意两个 城市均可以互相通话,并且电话线 的总长度最短
31 2.树和最小支撑树 一 、树及其性质 在各种各样的图中，有一类图 是十分简单又非常具有应用价值的 图，这就是树。 例8.3：已知有六个城市，它们 之间 要架设电话线，要求任意两个 城市均可以互相通话，并且电话线 的总长度最短
2.树和最小支撑树 V5 V6 图8.8
32 2.树和最小支撑树 图8.8 v6 v3 v4 v2 v5 v1