一、基本概念
- 区别于集合：边集可以重复
- G = （V，E），教材中的另一个对应关系的参数不重要
- V(G) 顶点集
- E(G) 边集合
- 关联：指顶点与边相连
- 相邻：点与点 边与边
- 重边：
- 有限图：边数顶点数都是有限的图
- 平凡图：顶点只有一个的图：不一定没有边，环也有可能
- 简单图：不含重边和环的图
- 平面图：可以用画在纸上的图，且各条边只在顶点处相交
- 同构：边与点数目相同，对应关系相对而言相同，即不做标记的图可以是同构，只是记号改变的图
- 完全图：每个顶点都与其他顶点相连
- 二部图：顶点集合分成两部分
- 完全二部图：顶点集合分成两部分，每一部分中的顶点都与另一部分中的任何一个顶点相连
二、图与子图
关联矩阵与邻接矩阵
$M(G)=[m_{ij}]$ $v_i与e_j关联次数$ 环为2
$A(G)=[G_{ij}]$ $a_{ij}表示v_i与v_j相关联的次数$
三、度的相关定理
$\sum_{v\in V}d_G(v)=2\epsilon$
环算两条边
$\delta(G)最小度$
$\Delta(G)最大度$
$\delta(G)=\Delta(G)=k$ 称为k正则图
四、一个常用的证明方法
介绍一个常用的证明方法：贡献法
左边变化等于右边变化则证明相等，有点类似与归纳法
证明：$\sum_{v\in V}d_G(v)=2\epsilon$
可以一开始取$\epsilon=1$ 显然等式成立，然后变化的时候两个等式相同即证明等式成立
推论：在任何图中，奇度点个数总等于偶数
这个比较容易证明，考虑以下等式即可证明
$V_1\rightarrow 奇度$
$V_2\rightarrow 偶度$
$\sum_{v\in V_1}d(v)+\sum_{v\in V_2}d(v)=\sum_{v\in V}d(v)$
五、途径、迹、路
途径：点边交替出现的序列，点边都是可以重复的
$w=v_0 e_1 v_1 e_2 ...e_k v_k$
简单图中$w$ 的顶点序列可以唯一确定一条途径，所以可以省略边不写
迹：$w$ 中边互不相同
路：$w$ 中的点互不相同当然边肯定也互不相同
途径一定会包括路和迹
迹和路一定是途径而途径不一定是路和迹
六、圈
一条起点和内部顶点互不相同的闭迹
定理：
一个圈是二部图当且仅当它不包含奇圈
