1.图的基本概心与基本定理 定理8.1所有顶点次数之和 等于所有边数的2倍。 定理8.2在任一图中,奇 点的个数必为偶数
定理8.1 所有顶点次数之和 等于所有边数的2倍。 定理8.2 在任一图中，奇 点的个数必为偶数。 1.图的基本概念与基本定理
1图的基本概A与基本定理 图的连通性: 链:由两两相邻的点及其相关 联的边构成的点边序列;如 oseisvise2v2ye3,v3y.sVn-I,en, vn, ,vn分别为链的起点和终点 简单链:链中所含的边均不相同 初等链:链中所含的点均不相同 也称通路;
22 图的连通性： 链： 由两两相邻的点及其相关 联的边构成的点边序列; 如: v0 ,e1 ,v1 ,e2 ,v2 ,e3 ,v3 ,…,vn-1 ,en , vn ; v0 ，vn分别为链的起点和终点； 简单链：链中所含的边均不相同； 初等链：链中所含的点均不相同, 也称通路； 1.图的基本概念与基本定理
1图的基本概心与基本定理 回路:着v≠vn分称该链为开链,否 则称为闭链或回路 圈:除起点和终点外链中所含的点均 不相同的闭链 连通图:图中任意两点之间均至少有 条通路,否则称作不连通图
23 • 回路：若 v0 ≠ vn 分称该链为开链，否 则称为闭链或回路； • 圈：除起点和终点外链中所含的点均 不相同的闭链； • 连通图：图中任意两点之间均至少有 一条通路，否则称作不连通图。 1.图的基本概念与基本定理
1.图的基本概心与基本定理 子图:设G=[V1,E1,G2=V2,E21 子图定义:如果V≌V,E2E1称G2是 G1的子图; 直子图:如果V2cV,E2CE称G2是G1 的真子图; 部分图(支撑子图):如果V2=V, E2cE1称G2是G1的部分图 导出子图:若V2sVE2{v唯"p"∈V2, 称G2是G1中由V2导出的导出子图
子图： 设 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,M起点u终点v 路:若有从到v不考虑方向的链且 各方向一致则称之为从L到的路; 初等路:各顶点都不相同的路 初等回路:U=V的初等 路 通图:若不考虑方向 是无向连通图 图:任两点有路;
有向图：关联边有方向 弧：有向图的边a=(u ,v),起点u,终点v; 路：若有从 u 到 v 不考虑方向的链,且 各方向一致,则称之为从u到v的路； 初等路: 各顶点都不相同的路； 初等回路:u = v 的初等 路; 连通图： 若不考虑方向 是无向连通图; 强连通图：任两点有路; 1.图的基本概念与基本定理