图论基本概念
重要定义:
有向图:每条边都是有向边的图。
无向图:每条边都是无向边的图。
混合图:既有有向边又有无向边的图。
自回路:一条边的两端重合。
重数:两顶点间若有几条边,称这些边为平行边,两顶点 a,b 间平行边的条数成为(a,b)
的重数。
多重图:含有平行边的图。
简单图:不含平行边和自回路的图。
注意!一条无向边可以用一对方向相反的有向边代替,因此一个无向图可以用这种方法转
化为一个有向图。
定向图:如果对无向图 G 的每条无向边指定一个方向由此得到的有向图 D。称为的 G 定向
图.
底图:如果把一个有向图的每一条有向边的方向都去掉,得无向图 G 称为的 D 底图。
逆图:把一个有向图 D 的每条边都反向由此得到的图称为 D 的逆图。
赋权图:每条边都赋上了值。
出度:与顶点相连的边数称为该定点的度数,以该定点为始边的边数为出度。 入度:以该
定点为终边的边数为入度。
特殊!度数为零的定点称为孤立点。度数为一的点为悬挂点。
无向完全图:在阶无向图中如果任何两点都有一条边关连则称此图是无向完全图。Kn
完全有向图:在阶有向图中如果任意两点都有方向相反的有向边相连则称此图为完全有向
图。
竟赛图:阶图中如果其底图是无向完全图,则程此有向完全图是竟塞图。
注意!n 阶有向完全图的边数为 n 的平方;无向完全图的边数为 n(n-1)/2。
下面介召图两种操作:①删边:删去图中的某一条边但仍保留边的端点。
② 删点:删去图中某一点以及与这点相连的所有边。
子图:删去一条边或一点剩下的图。
生成子图:只删边不删点。
主子图:图中删去一点所得的子图称的主子图。
补图:设为阶间单无向图,在中添加一些边后,可使成为阶完全图;由这些添加边和的个
顶点构成的图称为的补图。
重要定理:
定理 5.1.1 设图 G 是具有 n 个顶点 m 条边的有向图,其中点集 V={v,v,….,v}
deg+(vi)=deg-(vi)=m
定理 5.1.2 设图 G 是具有 n 个顶点 m 条边的无向图,其中点集 V={v,v,v,……,v}
deg(vi)=2m
推论 在无向图中,度数为积数的顶点个数为偶数。
通路和富权图的最短通路
1 通路和回路
基本概念:
通路的长度:通路中边的条数。
回路:如果通路中始点与终点相同。
简单通路:如果通路中各边都不相同。
评论0