无序积

设A,BA,BA,B为任意的两个集合，称{{a,b}∣a∈A∧b∈B}\{\{a,b\} | a\in A\land b\in B\}{{a,b}∣a∈A∧b∈B}为AAA与BBB的无序积，记作A&BA\&BA&B.

可见无序积是一个集合，其中的每个元素都是一个含两个元素的小集合 (无序对)。

将无序积中的无序对{a,b}\{a,b\}{a,b}记作(a,b)(a,b)(a,b)。

注意：(a,b)=(b,a)(a,b) =(b,a)(a,b)=(b,a)、A&B=B&AA\&B = B\&AA&B=B&A

笛卡尔积无序积表示形式A×BA\times BA×BA&BA\&BA&B元素有序对无序对(a,b)(a, b)(a,b)图的基本概念

图论研究的图是不同于几何图形、机械图形的另一种数学结构,。

由于图的顶点位置和边的长度的任意性, 一个图的图形表示并不是唯一的。

图论中，不关心图中顶点的位置, 边的长短和曲直形状, 只关心有多少顶点,哪些顶点之间有边.

注意到：

V,EV,EV,E都是一个集合，其中VVV中的元素是普通的单个顶点，而EEE中的元素为无序对（或有序对）。

GGG是V,GV,GV,G的二元组，严格意义上GGG不能称为集合。“多重子集”意味着图中可以存在重边

图中顶点的个数（即顶点集VVV中的元素个数）称为图的阶, nnn个顶点的图称为nnn阶图。

若图中没有边（即边集EEE为空集），则称为零图。注意零图与图中顶点的个数无关。

特别的，1阶零图又称为平凡图。平凡图只有一个顶点，没有边。

在图的运算中可能会产生顶点集为空集的运算结果，规定顶点集为空集的图为空图，记为∅。（注意，图的定义中，顶点集是不能为空集的）

注意区分零图与空图

一条边eee与其所连接的两个端点 vi,vjv_i, v_jvi​,vj​ 之间是关联的，则eee与viv_ivi​（vjv_jvj​）的关联次数均为1；若vi=vjv_i=v_jvi​=vj​（即是一个自环），则eee与viv_ivi​的关联次数为2；若eee与viv_ivi​不关联，则eee与viv_ivi​的关联次数为0.

图论中 环特指自环。

无向图中顶点所连接的边数为该顶点的度dGd_GdG​，注意：一个环给它的顶点提供2个度。

对于有向图，度可分为入度dD−d^-_DdD−​和出度dD+d^+_DdD+​，度 = 入度 + 出度。

对于整个图而言，定义最大度Δ(G)\Delta(G)Δ(G)和最小度δ(G)\delta(G)δ(G)（有向图中还定义有最大入度、最小出度、…）

对于无向简单图，0≤δ(G)≤d(vi)≤Δ(G)≤n−10≤ \delta(G)≤d(v_i)≤\Delta(G)≤n-10≤δ(G)≤d(vi​)≤Δ(G)≤n−1对于有向简单图，0≤δ(D)≤d(vi)≤Δ(D)≤2(n−1)0≤ \delta(D)≤d(v_i)≤\Delta(D)≤2(n-1)0≤δ(D)≤d(vi​)≤Δ(D)≤2(n−1)

度数是单个顶点的属性，而最大度数、最小度数是整个图的属性。

度为1的顶点称为悬挂顶点，与它关联的边称为悬挂边。

度为奇数（偶数）的顶点称为奇度顶点（偶度顶点）。

若两个顶点之间有一条边相接，则称这两个顶点相邻；若两个边至少有一个公共端点，则称这两条边相邻。

：vi→vjv_i\rightarrow v_jvi​→vj​ ，称viv_ivi​为始点，vjv_jvj​为终点，viv_ivi​邻接到vjv_jvj​，vjv_jvj​邻接于viv_ivi​.

拓展：

设DDD为nnn阶有向简单图，若DDD的基图为nnn阶无向完全图，则称DDD为nnn阶竞赛图。

可见nnn阶竞赛图的边数为n(n−1)2\frac{n(n-1)}{2}2n(n−1)​.

正则图并非唯一的（因为阶数不确定）。

基本定理

握手定理

所有顶点的度数之和=边数×2所有顶点的度数之和 = 边数\times 2所有顶点的度数之和=边数×2对于有向图，特别的，所有顶点的入度之和=所有顶点的出度之和=边数对于有向图，特别的，所有顶点的入度之和 = 所有顶点的出度之和 = 边数对于有向图，特别的，所有顶点的入度之和=所有顶点的出度之和=边数奇度顶点的数目为偶数奇度顶点的数目为偶数奇度顶点的数目为偶数

度数列可图化

非负度数列是可图化的⇔所有顶点的度数之和为偶数非负度数列是可图化的 \Leftrightarrow 所有顶点的度数之和为偶数非负度数列是可图化的⇔所有顶点的度数之和为偶数

注意：

若存在无向图的度数列为ddd，则称ddd是可图化的。标定无向图的度数列是唯一的，但度数列所对应的无向图却不一定唯一。

一个度数列是可简单图化的判断条件：

设d={d1,d2,...,dn}d = \{d_1,d_2,...,d_n\}d={d1​,d2​,...,dn​}是非负不增数列，则d是可简答图化的⟺∑i=1kdi≤k(k−1)+∑i=k+1nmin{k,di}d是可简答图化的\Longleftrightarrow \sum_{i=1}^kd_i\le k(k-1)+\sum_{i=k+1}^nmin\{k,d_i\}d是可简答图化的⟺i=1∑k​di​≤k(k−1)+i=k+1∑n​min{k,di​}

连通

在n阶图中，若从顶点u到v(u≠v)存在通路，则从u到v存在长度小于等于n−1的在n阶图中，若从顶点u到v(u\neq v)存在通路，则从u到v存在长度小于等于n-1的在n阶图中，若从顶点u到v(u​=v)存在通路，则从u到v存在长度小于等于n−1的初级通路初级通路初级通路。

在n阶图中，如果存在v到自身的回路，则从v到自身存在长度小于等于n的初级回路在n阶图中，如果存在v到自身的回路，则从v到自身存在长度小于等于n的初级回路在n阶图中，如果存在v到自身的回路，则从v到自身存在长度小于等于n的初级回路。

有向图连通性的判别

有向图D是强连通的⟺D中存在经过每个顶点至少一次的回路有向图D是强连通的\Longleftrightarrow D中存在经过每个顶点至少一次的回路有向图D是强连通的⟺D中存在经过每个顶点至少一次的回路。

有向图D是单向连通的⟺D中存在经过每个顶点至少一次的通路有向图D是单向连通的\Longleftrightarrow D中存在经过每个顶点至少一次的通路有向图D是单向连通的⟺D中存在经过每个顶点至少一次的通路。

标定图的矩阵表示

图无法与二元关系一一对应，因为图是多重集合而二元关系是集合。

注意：关联矩阵 ≠ 关系矩阵。

无向图的关联矩阵M(G)M(G)M(G)

矩阵第iii行，第jjj列的元素为顶点viv_ivi​和边eje_jej​的关联次数，取值仅有3种：0、1、2。

关联矩阵的行描述的是顶点的性质，列描述的是边的性质。

有向无环图的关联矩阵M(D)M(D)M(D)

矩阵第iii行，第jjj列的元素描述的是顶点viv_ivi​和边eje_jej​的关系，取值仅有3种：-1、0、1。

有向图的邻接矩阵A(D)A(D)A(D)

Al中的元素aij(l)表示从vi到vj的长度为l的通路数。Al中所有元素之和即图中长度为l的通路数。Al中主对角线元素之和即图中长度为l的回路数。A^l中的元素a^{(l)}_{ij}表示从v_i到v_j的长度为l的通路数。\\A^l中所有元素之和即图中长度为l的通路数。\\A^l中主对角线元素之和即图中长度为l的回路数。Al中的元素aij(l)​表示从vi​到vj​的长度为l的通路数。Al中所有元素之和即图中长度为l的通路数。Al中主对角线元素之和即图中长度为l的回路数。

注意此处邻接矩阵的乘法就是普通的矩阵乘法，而并非布尔运算。

设Bl=A+A2+A3+...+AlB_l = A + A^2 + A^3 +...+A^lBl​=A+A2+A3+...+Al，则

BlB_lBl​中元素bij(l)b^{(l)}_{ij}bij(l)​为DDD中vi到vjv_i到v_jvi​到vj​的长度小于等于lll的通路数，

BlB_lBl​中元素之和为图中长度小于等于lll的通路总数，

BlB_lBl​中对角线元素之和为图中长度小于等于lll的回路数。

有向图的可达矩阵P(D)P(D)P(D)