Name: Password: Sign in
离散数学 · 图 中的文章

本文在 署名-非商业性使用-相同方式共享 3.0 版权协议下发布, 转载请注明出自 kyleslight.net

[Lecture 1] 图和图模型

1 图的定义

  • (无向)图 G:由顶点的非空集合 V 和边集 E 构成;上下文清楚地时候我们只用图表示 无向图
  • 简单图:每条边连接两个顶点;两个顶点间至多只有一条边相连的图;这样我们在使用顶点对 (u,v) 来表示边的时候才没有歧义;多重图即两个顶点间可能有多个边相连;成环的图称为 伪图
  • 有向图 (V,E):由顶点非空集合 V 和有向边集 E 构成,每条边 (u,v) 的表示有向边由 u 指向 v;不包含环与多重有向边的有向图即 简单有向图

2 图的术语与特殊的图

2.1 术语与定理

2.1.1 无向图的术语

  • 邻接:无向图 G 中一条边上的两个顶点 uv 互相邻接,顶点 uv 也称与 (u,v) 相联系边的 端点
  • :无向图中与顶点 v 相关联的边的数目 deg(v);成一次环度数加 1;度数为 0 的点是孤立的;

2.1.2 无向图的定理

定理 1(握手定理):设 G=(V,E) 是有 e 条边的无向图(该定理对于含有多重边与环的图同样成立),那么

2e=vVdeg(v)

所有度数求和正好是边数的两倍,因为每条边都贡献了两次度数(相当于每次握手都会有两只手参与)

定理 2:无向图有偶数个奇数度顶点

2e=vV1deg(v)+vV2deg(v)

上式中 V1 是偶度数顶点,第一项为偶数,所以第二项为偶数,所以奇数度顶点 V2 的元素必然是偶数个

2.1.3 有向图的术语

  • 入度与出度:有向图中,入度(deg(v))即以 v 为终点的边数,出度(deg+(v))即以 v 为起点的边数;自成环对出度和入度的贡献都为 1

2.1.4 有向图的定理

定理 3:有向图 G(V,E)

vVdeg(v)=vVdeg+(v)=|E|

即每条边产生一个入度一个出度

2.2 特殊的图

完全图n 个顶点的完全图 Kn 即每个顶点间都有一条边的简单图;

圈图:圈图 Cnn3) 是由顶点 v1,v2...vn 与边 (v1,v2),(v2,v3)...(vn1,vn),(vn,v1) 构成

偶图:简单图 G 的顶点分为不相交的非空集合 V1V2,图中每一条边的两个端点一个在 V1 中一个在 V2 中,因而 G 中没有边连接 V1V2 的两点;称 (V1,V2)G 顶点集的二部划分

定理 4:一个图是偶图,当且仅当图中的顶点都被分为两种不同的颜色,且任何一条边的两个端点的颜色不同

完全偶图:完全偶图 Km,n,两个顶点间有边,当且仅当一个顶点属于 V1 另一个顶点属于 V2

2.3 旧图到新图

  • 子图G(V,E) 的子图是 H(W,F),其中 WVFE

  • 并图 :简单图 G1=(V1,E1)G2=(V2,E2) 的并图由顶点集 V1V2 与边集 E1E2 构成,表示成 G1G2

Copyright (c) 2014-2016 Kyles Light.
Powered by Tornado.
鄂 ICP 备 15003296 号