1图的基本概A与基本定理 图的连通性: 链 由两两相邻的点及其相关联的 边构成的点边序列;如 0,℃15V1,2 3, n-1 V n 凶V,分别为链的起点和终点 简单链:链中所含的边均不相同; 初等链:链中所含的点均不相同,也 称通路
21 图的连通性： 链： 由两两相邻的点及其相关联的 边构成的点边序列;如: v0 ,e1 ,v1 ,e2 ,v2 ，e3 ,v3 ,…,vn-1, en , vn ; v0 ，vn分别为链的起点和终点； 简单链：链中所含的边均不相同； 初等链：链中所含的点均不相同,也 称通路； 1.图的基本概念与基本定理
1图的基本概心与基本定理 回路:若v≠vn分称该链为开链, 否则称为闭链或回路 除起点和终点外链中所含的点 均不相同的闭链; 连通图:图中任意两点之间均至少有· 条通路,否则称作不连通图
22 圈： 除起点和终点外链中所含的点 均不相同的闭链； 回路： 若 v0 ≠ vn 分称该链为开链， 否则称为闭链或回路； 连通图：图中任意两点之间均至少有一 条通路，否则称作不连通图。 1.图的基本概念与基本定理
1.图的基本概心与基本定理 子图设G[V1,E1],G=[V2,E2 子图定义:如果VcV,E2∈E1称G2 是G1的子图; 真子图:如果VcV,ECE称G是 G,的真子图 部分图(支撑子图):如果V=V,E2C E1称G是G1的部分图; 导出子图: 如果VC v,∈V},称 G是G中由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.图的基本概念与基本定理
1.图的基本概念与基本定理 有向图:关联边有方向 弧:有向图的边a=(u,),起点U,终点v 路:若有从u到V不考慮方向的链,且 各方向一致,则称之为从u到v的路; 初等路:各顶点都不相同的路 初等回路:u=V的初等 路 连通图:若不考慮方向 是无向连通囹 强连通图:任两点有路;
有向图：关联边有方向 弧：有向图的边a=(u ,v),起点u,终点v； 路：若有从 u 到 v 不考虑方向的链,且 各方向一致,则称之为从u到v的路； 初等路: 各顶点都不相同的路； 初等回路:u = v 的初等 路; 连通图： 若不考虑方向 是无向连通图; 强连通图：任两点有路; 1.图的基本概念与基本定理
2.树和小支树 树及其性质 在各种各样的图中,有一类图 是十分简单又非常具有应用价值的 图,这就是树。 例8.3:已知有六个城市,它们 之间要架设电话线,要求任意两个 城市均可以互相通话,并且电话线 的总长度最短
31 2.树和最小支撑树 一 、树及其性质 在各种各样的图中，有一类图 是十分简单又非常具有应用价值的 图，这就是树。 例8.3：已知有六个城市，它们 之间 要架设电话线，要求任意两个 城市均可以互相通话，并且电话线 的总长度最短