定理1：图G=(V,日中,所有点的次之和是边数的两倍，即：Zd(v) = 2qEVU定理2：任意一图中，奇点的个数为偶数证明：设V,--奇点的集合V2--偶点的集合Z.d(v)+ Z d(v) =Nd(v)= 2qVEVVEV2VEVI偶数偶数偶数
d v d v d v q v V v V v V ( ) ( ) ( ) 2 1 2 偶数 偶数 偶数 d v q v V ( ) 2 定理1: 图G=(V, E)中, 所有点的次之和是边 数的两倍, 即: 定理2: 任意一图中, 奇点的个数为偶数. 证明:设 V1 -奇点的集合, V2 -偶点的集合
链：点边交错系列，记为：(i,e,Vi.. Y,ei,Yi?)无重复点，无重复边圈：Vi=Vi,的链初等链：点Vi,Vi.,Vi均不相同e有重复点，无重复边初等圈：点简单链：4链中边均不相同。台en简单圈：圈中边均不相同。e6es注：以后说到链（圈），除非es (圈)特别交代，均指初等链Ve413e
链：点边交错系列， 记为： 圈： 的链。 初等链：点 均不相同。 初等圈：点 均不相同。 简单链：链中边均不相同。 简单圈：圈中边均不相同。 例：右图 (v ,e ,v ,.,v ,e ,v ) 1 1 2 k 1 k k i i i i i i k i i v v 1 1 2 k i i i v ,v ,.,v 1 2 k 1 i i i v ,v ,.,v 1 v 2 v 3 v 4 v 1 e 2 e 3 e 4 e 5 e 6 e 7 e 无重复点,无重复边 有重复点,无重复边 注：以后说到链（圈），除非 特别交代，均指初等链（圈）
连通图：任意两点之间至少有一条链不连通图：连通分图：对不连通图，每一连通的部分称为一个连通分图。支撑子图：对G=（V，E），若G=(V,E),使V=V,ECE,则G'是G的一个支撑子图（生成子图）：G-V:图G去掉点v及v的关联边的图
连通图：任意两点之间至少有一条链。 不连通图： 连通分图：对不连通图，每一连通的部分 称为一个连通分图。 支撑子图：对G=（V，E），若 G`=(V`,E`), 使V`=V, E` E, 则G`是G的一 个支撑子图（生成子图）. G-v: 图G去掉点v及v的关联边的图
有向图的有关概念基础图：对D=(V,A),去掉图上的箭头对弧的始点，v为a始点和终点方向可以不同的终点.链：点弧交错序列，若在其基础图中对应一条链，则称为 D的一条链圈，初等链，初等圈：类似定义
有向图的有关概念 基础图: 对D=(V, A), 去掉图上的箭头. 始点和终点: 对弧a=(u, v), u为a的始点, v为a 的终点. 链: 点弧交错序列, 若在其基础图中对应一条链 , 则称为 D的一条链. 圈, 初等链,初等圈: 类似定义. 方向可以不同
方向相同道路:若（Vi,ai,Vi2,ai,...ik-1,aik-1,Vik是D中的一条链，且ait=(Vit,Vit+1），t=1,2,.,k-1,称之为从Vi到Vik,的一条道路。回路： Vin= Vik的路.初等路：道路中点不相同初等回路：回路中点不相同简单有向图：无自环，无多重弧多重有向图：有多重弧
道路:若 （vi1 ,ai1 ,vi2 ,ai1 ,.,vik-1 ,aik-1 ,vik） 是D中的一条链，且ait=(vit,vit+1 ) ， t=1,2,.,k-1,称之为从vi1 到 vik,的一条道路。 回路: vi1= vik的路. 初等路: 道路中点不相同. 初等回路: 回路中点不相同. 简单有向图: 无自环, 无多重弧. 多重有向图: 有多重弧. 方向相同