图论
基本概念
绘图程序
import networkx as nx
import matplotlib.pyplot as plt
def drawgraph(E):
# G = nx.Graph() # 无向图
G = nx.DiGraph() # 有向图
G.add_edges_from(E)
nx.draw(G, node_size = 200, node_color = 'k',
with_lables = True, font_color = 'w')
plt.show()
return
V = {'a', 'b', 'c', 'd', 'e', 'f', 'g'}
E = [('a', 'b'), ('a', 'f'), ('b', 'c'), ('b', 'e'), ('b', 'f'), ('c', 'd'),
('c', 'e'), ('c', 'f'), ('f', 'e')]
drawgraph(E)
基本概念
无序偶和有序偶
无序偶
$V$ 是非空集合，$x\in V$ 并且 $y\in V$，称 $(x,y)$ 是无序偶
有序偶
$V$ 是非空集合，$x\in V$ 并且 $y\in V$，称 $<x,y>$ 是有序偶
有向图和无向图
无向图
无向图是由无序偶构成的边的集合
def Cartesianproduct(X, Y): # 笛卡尔乘积
XY = set({})
for x in X:
for y in Y:
XY.add((x, y))
return XY
def creategraph(m, n): # 随机生成 m 点, n 边图
global V, XY
V = range(m)
XY = Cartesianproduct(V, V)
E = random.sample(XY, n)
return [V, E]
有向图
有向图是由有序偶构成的边的集合
带权图
def Cartesianproductweight(X, Y): # 带权笛卡尔乘积
XY = set({})
for x in X:
for y in Y:
weight = random.randint(1, 100)
XY.add((x, y, weight))
return XY
def weightedgraph(V0, E0, W0): # 随机生成带权图
V = V0
E = set({})
for (u, v) in E0:
w.random.randint(1, W0)
E = E | {(w, u, v)}
return [V, E]
图判断
def isgraph(V, E): # 是否为图
tv = True
for (u, v) in E:
tv = tv and (u in V) and (v in V)
return tv
基本结构
关系
图的基本结构是指图和顶点之间，边之间以及边与顶点之间的连接关系
- 邻接关系：顶点之间
- 关联关系：顶点与边之间
- 相邻关系：边与边之间
度
入度 $di(u)$
以 $u$ 为终点的边数称为点 $u$ 的入度。
出度 $do(u)$
以 $u$ 为起点的边数称为点 $u$ 的入度。
度 $deg(u)$
顶点的度
$deg(u) = di(u) + do(u)$
图的度
$deg(V) = \sum_{u\in V}deg(u)$
握手定理
设 $G = <V, E>$ 是 $(n, m)$ 图，则 $\sum_{u\in V}d(u) = 2m$
同构 (isomorphism)
设无向图 $G = <V, E>$ 和 $G’ = <V’, E’>$, 如果存在双射函数 $f: v\rightarrow v’$, 并且当且仅当 $e = (u_i, u_j)\in E$, 有 $e’ = (f(u_i), f(u_j))\in E’$, 则称 $G$ 和 $G’$ 同构
子图及算法
子图 (subgraph)
定义
设 $G = <V, E>$ 和 $G_s = <V_s, E_s>$ 是两个图，若
- $V_s \subseteq V$
- $E_s \subseteq E$
则称 $G_s$ 为 $G$ 的子图，记为 $G_s \subseteq G$
判断子图算法
def issubgraph(V, E, Vs, Es):
tv = (Vs <= V) and (Es <= E)
return tv
真子图 (proper subgraph)
定义
- $G_s \subseteq G$
- $V_s \subset V$
- 或
- $E_s \subset E$
则称 $G_s$ 为 $G$ 的真子图，记为 $G_s \subset G$
判断真子图算法
def ispropersubgraph(V, E, Vs, Es):
tv = (Vs <= V) and (Es <= E) or ((Vs < V) or (Es < E))
return tv
生成子图 (spanning subgraph)
定义
- $G_s \subseteq G$
- $V_s = V$
则称 $G_s$ 为 $G$ 的生成子图
判断生成子图算法
def isspanningsubgraph(V, E, Vs, Es):
tv = (Vs <= V) and (Es <= E) and ((Vs == V) and (Es <= E))
return tv
导出子图 (induced subgraph)
定义
- $G_s \subseteq G$
\forall (v; v in V_s; \forall (u; u in V_s; (u, v) in E ==> (u, v) in E_s))
则称 $G_s$ 为 $G$ 的导出子图
判断导出子图算法
def isinducedsubgraph(V, E, Vs, Es):
tv = (Vs <= V) and (Es <= E)
for (u, v) in E:
tv = tv and ((not((u in Vs) and (v in Vs))) or ((u, v) in Es))
return tv
特殊图及算法
补图
设 $G = <V, E>$ 是 $n$ 阶无向简单图
- 以 $V$ 为顶点
- 以所有使 $G$ 称为 完全图 $K_n$ 的添加边所组成的集合为边
的图称为 $G$ 的子图，记为 $\sim G$
相对补图
$G_1$ 是 $G_2$ 相对于 $G$ 的补图
连通问题
连通问题
通路 (path)
若 $u_k\in V, (u_k, u_{k+1}) \in E, k = 0, 1,…,n-1$，则顶点 $u_0$ 与顶点 $u_{n-1}$ 之间存在通路，记为 $u_0\Rightarrow u_{n-1}$
==简单==通路 (simple path)
每条 边 的出现不超过一次
==基本==通路 (basic path)
每个 顶点 的出现不超过一次
回路 (circuit)
设有向图 $D = <V,A>$，若 $u\in V$，从 $u$ 出发并返回 $u$ 的通路，称为回路，记为 $u\Rightarrow u$
简单回路 (simple circuit)
每条 边 的出现不超过一次
基本回路 (basic circuit)
每个 顶点 的出现不超过一次
圈 (acyclic)
定理
设 $G = <V, E>$ 是 $n$ 阶图，若顶点 $u, v$ 存在通路，则存在小于等于 $n-1$ 的通路
通路算法
初始通路
| $path0 = {(u0, v) | (u0, v)\in E\or (v, u0)\in E}$ |
def pathset0(V, E, u0):
# 找到所有从 u0 出发的路径
path1 = set({})
for (u, v) in E:
if (u == u0):
path1 = path1 | {(u, v)}
return path1
$(\omega, x, y) \in path(n) \rightarrow (\omega,x,y,v)\in path(n+1)$
- $u == y\and v\ not\ in\ path(n) \rightarrow(\omega, x,y,v)\in path(n+1) $
- $v == y\and v\ not\ in\ path(n) \rightarrow(\omega, x,y,u)\in path(n+1) $
def pathset(path0, E):
path = set({})
for p0 in path0:
y = p0[-1]
for (u, v) in E:
if u == v:
continue
p = p0
if (u == y):
p = p + tuple([v])
path = path | {p}
return path
def basicpathset(path0, E):
path = set({})
for pk in path0:
x = pk[-1]
for (u, v) in E:
if u == v:
continue
p = pk
if (u == x and (v not in pk)):
p = p + tuple([v])
path = path | {p}
return path
连通图
连通图的构建
def connectedgraph(V, E, V0, E0):
# 连通图
Vc = V0
Ec = E0
while E != set({}):
n = len(Ec)
for (u, v) in E:
if (u, v) not in Ec and (u in Vc or v in Vc):
Vc = Vc | {u, v}
Ec = Ec | {(u, v)}
if (len(Ec) == n):
break
return [Vc, Ec]
连通图判断
[Vc, Ec] 是图 G = <V, E> 的连通子图，若 Ec == E，则 G 为连通图，否则不然
def isconnectedgraph(V, E):
# 判断是否为连通图
V = list(V)
E = list(E)
(u, v) = E[0]
V0 = {u, v}
E0 = {(U, v)}
[Vc, Ec] = connectedgraph(V, E, V0, E0)
tv = (set(V) == set(Vc)) & (set(Ec) == set(E))
return tv
图的矩阵表示
邻接矩阵
| 设$G=<V,E>$是简单图，$ | V | =n$，矩阵$An\times n=[ai,j]$，若边$(vi,vj)\in E$，则$a_{i,j}=1$，否则，$a_{i,j}=0$，称矩阵$An\times n$是邻接矩阵。 |
def graph2array(V, E):
n = len(V)
A = np.zeros((n, n), dtype = 'int')
A = np.array(A)
for i in range(n):
for j in range(n):
if (i, j) in E:
A[i, j] = 1
return A
多重边图邻接矩阵
邻接矩阵$An×n=[ai,j]$，也可以表示有自环以及有多重边的图，其中，$a_{i,j}$表示顶点$v_i$和$v_j$邻接的边数目。
有向图邻接矩阵
邻接矩阵也可以表示有向图。矩阵$An×n=[a_{i,j}]$，若边$<v_i,v_j>\in E$，则$a_{i,j}=1$，否则，$a_{i,j}=0$。
无向图关联矩阵
| 设$G=<V,E>$是简单无向图，$ | V | =n$，$ | E | =m$，矩阵$An×m=[a_{i,j}]$，若顶点$v_i\in V$，$e_j\in E$，$e_j=(v_i,u)$或$e_j=(u,v_i)$，则$a_{i,j}=1$，否则，$a_{i,j}=0$，称矩阵$A_n×m$是关联矩阵。 |
有向图的关联矩阵
| 设$G=<V,E>$是简单有向图，$ | V | =n$，$ | E | =m$，矩阵$A_n×m=[a_{i,j}]$，顶点$u_i\in V$，$e_j\in E$，若$e_j=<u_i,v>$则$a_{i,j}=1$，若$e_j=<v,u_i>$，则$a_{i,j}=-1$，否则，$a_{i,j}=0$，称矩阵$A_n×m$是关联矩阵。 |
可达矩阵
设A是相邻矩阵，I是单位矩阵，B是布尔矩阵，R是可达矩阵，则$R=B(I+A+A^2+…+A^{n-1})=B[(I+A)^{n-1}]$
def reachabilityarray(A, n):
# 可达矩阵
m = len(A)
I = np.array(np.eye(m, dtype = 'int')) # 自身可达
Ai = I + A
An = Ai ** (n-1)
R = np.zeros((m ,m), dtype = 'int')
for i in range(m):
for j in range(m):
if An[i, j] != 0:
R[i, j] = 1
else:
R[i, j] = 0
return R
穿程问题
欧拉图
欧拉链
（欧拉链、欧拉圈、欧拉图）：设G＝<V,E>是连通无向图，经过G中每条边一次且仅一次的非闭合链称为欧拉链（通路）
欧拉圈
经过G中每条边一次且仅一次的闭合链称为欧拉圈
欧拉图
具有欧拉圈的图称为欧拉图
判定定理
定理1
设G是无向连通图，则如下三个命题等价
- G是欧拉图。
- G中所有顶点的度数是偶数。
- G是若干不重边圈的并。
定理2
无向图G为欧拉图，当且仅当G是连通图，并且G的每一个顶点都是偶顶点。
图的度、入度、出度
def degreeset(V, E):
# 获得图的度，入度，出度
V = sorted(V)
m = len(V)
d = [0] * m # 度
di = [0] * m # 入度
do = [0] * m # 出度
for (u, v) in E:
i = V.index(u)
j = V.index(v)
di[j] += 1
do[i] += 1
d[i] += 1
d[j] += 1
return [d, di, do]
欧拉通路
无向图G中有连接$u_i$和$u_j$的欧拉通路，当且仅当G是连通图，并且G中只有$u_i$和$u_j$ 是奇顶点。
欧拉图的构建方法
# 欧拉图的构建算法
def subEulercircuit(E,v0):
# 返回边 E 中以 v0 作为起点和终点的回路 circuit
# 返回回路中所经过的点集 S
circuit = tuple([v0])
S = set({})
while (circuit[0] != circuit[-1] or len(circuit) == 1):
y = circuit[-1]
for (u, v) in E:
if(u == y):
circuit = circuit + tuple([v])
E = E - {(u, v)}
S = S | {(u, v)}
break
return [circuit, S]
def set2V(E):
# edges to vertexes
V = set({})
for (u, v) in E:
V = V | {u, v}
return V
def Eulercircuit(E,v0):
[circuit, S] = subEulercircuit(E, v0)
E = E - S
while (E != set({})):
V1 = set(circuit)
V2 = set2V(E)
V1V2 = V1 & V2
for v0 in V1V2:
[subcircuit, S] = subEulercircuit(E, v0)
if S == set({}):
# 在现有边集 E 中无法找到 v0 开头的回路
continue
k = circuit.index(v0)
# 将找到的回路添加到原回路的适当位置
circuit = circuit[0:k] + subcircuit + circuit[k+1:-1] + tuple([circuit[-1]])
E = E - S
break
return circuit
一笔画问题（格雷码）
构建偶数度顶点图
# 构建偶数度顶点图
# 对于圈图，任取顶点 [u0, v0]，用 v0 替换 u0，并且 V = V - {u0}
# 重复 n 次
def replacevertex(V0,E0,n):
V = set(V0)
E = set({})
for k in range(n):
[u0, v0] = random.sample(V, 2)
V = V - {u0}
E = set({})
for (u, v) in E0:
if u == u0:
E = E | {(v0, v)}
elif v == u0:
E = E | {(u, v0)}
else:
E = E | {(u, v)}
E0 = E
return [V, E]
哈密尔顿图
哈密尔顿图
无向图G中穿过每个顶点一次且仅一次的圈，称为哈密顿圈,具有哈密顿圈的图称为哈密顿图。
哈密尔顿通路
无向图G中穿过每个顶点一次且仅一次的非闭合链，称为哈密顿链. 有向图D中穿过每个顶点一次且仅一次的非闭合通路，称为哈密顿通路。
定理
- 设G是具有n个顶点的连通无向图。若G中每一对顶点的次数之和大于或等于n-1，则G中存在一条哈密顿链。
- 若G中每一对顶点的次数之和大于或等于n，则G中存在一条哈密顿圈。
- 在一个有向完全图中必存在一条哈密顿通路。
构建邻接表
def adjacentlist(V,E):
# 返回与美国顶点直接相连的点集
Ea = []
for w in V:
e0 = [w]
e1 = []
for (u, v) in E:
if u == w and (v not in e1):
e1 = e1 + [v]
if v == w and (u not in e1):
e1 = e1 + [u]
e0 = e0 + [sorted(e1)]
Ea = Ea + [e0]
return sorted(Ea)
哈密尔顿图周游算法
程序tourpath0算法： （1）取路径path的末尾顶点path[-1]为w。 （2）取顶点w的邻接表E2。 （3）若邻接表E2中顶点u不在path上，则u加入path，否则，返回。
def tourpath0(V, E, path, m):
while(len(path) < m):
w = path[-1]
i = V.index(w)
E1 = E[i]
E2 = E1[1]
for u in E2:
if(u not in path):
path.append(u)
break
if(path[-1] == w):
break
return path
程序tourpath1算法： （1）取路径path的末尾顶点v=path.pop( )为v。 （2）若 path非空，取路径path的末尾顶点path[-1]为u。 （3）从顶点u的邻接表从顶点v以后依次检查k=E2.index(v)。 （4）若v=E2[k]不在path，则v为path的新末尾顶点，直至邻接表结束。 （5）若path有新顶点，则结束，否则，path弹出末尾顶点。
def tourpath1(V, E, path, m):
v = path.pop( )
while(len(path) != 0):
u = path[-1]
i = V.index(u)
E1 = E[i]
E2 = E1[1]
k = E2.index(v)
while(k < (len(E2) - 1)):
k = k + 1
v = E2[k]
if(v not in path):
path.append(v)
break
if(u != path[-1]):
break
v = path.pop( )
return path
程序tourpath算法： （1）若len(path) == m，则求新的周游通路，即tourpath1(V,E,path,m)。 （2）若len(path) != 0，依次迭代执行tourpath0与tourpath1。
def tourpath(V, E, path, m):
if(len(path) == m):
path = tourpath1(V, E, path, m)
while(len(path) != 0):
path = tourpath0(V, E, path, m)
if(len(path) == m):
break
path = tourpath1(V, E, path, m)
return path
哈密尔顿图算法
- 构建邻接表
- 设置初始顶点 v0
- 搜寻一条路径
- 若
len(path) == len(V)，则搜寻下一条路径
def Hamiltonpath(V, E, v0):
global Ea, paths
V = sorted(V)
Ea = adjacentlist(V, E)
paths = set({})
path = [v0]
m = len(V)
path = tourpath(V, Ea, path, m)
paths = paths | {tuple(path)}
while(len(path) == m):
path = tourpath(V, Ea, path, m)
if len(path) == m:
paths = paths | {tuple(path)}
print(path)
return paths
彼得森图 (Pertersen Graph)
完全图哈密尔顿圈
完全图G=<V,E>非重复边的哈密尔顿圈数为多少？
骑士周游问题
def Knighttouregraph(n):
P8=[[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2]]
N = n * n
V = list(range(N))
E = set({})
for k in range(N):
j = k % n
i = int(k / n)
for [u, v] in P8:
if 0 <= (i + u) and (i + u) < n and 0 <= (j + v) and (j + v) < n:
E = E | {(k,(i + u) * n + (j + v))}
return [V, E]
骑士周游图是欧拉图吗？
完全图哈密尔顿圈
- 完全图有哈密尔顿圈
- 寻找不重复的哈密尔顿圈
- 完全图的哈密尔顿圈数为
int(len(v)/2)
旅行商问题
通路问题
最短路径
在带权有向图G中，给定一个称为始点的顶点u和一个称为终点的顶点v，如果P是从u到v的通路中权值最小的通路，则称P为从u到v的最短通路。
Djikstra 最短通路算法
def shortpath(V, E, di, Hx, path, zn):
V = sorted(V)
Pm = []
for p in path:
vn = p[-1]
if vn == zn:
Pm = Pm + [p]
continue
if di[V.index(vn)] != 0:
Pm = Pm + [p]
continue
for (w, u, v) in E:
if u == vn:
kv = V.index(v)
if di[kv] > 0:
di[kv] = di[kv] - 1
vw = p[0] + w
if vw <= Hx[kv]:
Hx[kv] = vw
e = [vw] + p[1:] +[v]
Pm = Pm +[e]
return [di, Hx, Pm]
def shortestpath(V, E, v0, vn):
V = sorted(V)
[d, di, do] = degreesetw(V, E)
Pm0 = []
Pm = [[0, v0]]
inf = 10000
Hx = [inf for x in range(len(V))]
Hx[0] = 0
while Pm0 != Pm:
Pm0 = Pm
[di, Hx, Pm] = shortpath(V, E, di, Hx, Pm0, vn)
Pm = sorted(Pm)
return [Hx, Pm]
关键路径
最早完成时间算法
最晚完成时间算法
# 入度为 0
def stepu0v(di0,E):
S=set({})
for u0 in di0:
for (w,u,v) in E:
if u == u0:
S=S|{(w,u,v)}
return S
# 出度为 0
def stepuv0(do0,E):
S=set({})
for v0 in do0:
for (w,u,v) in E:
if v == v0:
S=S|{(w,u,v)}
return S
# 最早时间路径
def TEpath(S,Hx,di):
di0=set({})
for (w,u,v) in S:
if Hx[v] < Hx[u]+w:
Hx[v]=Hx[u]+w
if di[v]>0:
di[v]=di[v]-1
if di[v] == 0:
di0=di0 | {v}
return [Hx,di,di0]
# 最晚时间路径
def TLpath(S,Hy,do):
do0=set({})
for (w,u,v) in S:
if Hy[u] > Hy[v]-w:
Hy[u]=Hy[v]-w
if do[u]>0:
do[u]=do[u]-1
if do[u] == 0:
do0=do0 | {u}
return [Hy,do,do0]
def craticalTE(V, E, di, v0, vn):
Hx = [0] * len(V)
di0 = {v0}
while vn not in di0:
S = stepu0v(di0, E)
[Hx, di, di0] = TEpath(S, Hx, di)
E = E - S
return Hx
def craticalTL(V,E,do,Hn,v0,vn):
Hy= [1000]*len(V)
Hy[len(V)-1]=Hn
do0={vn}
while v0 not in do0:
S=stepuv0(do0,E)
[Hy,do,do0]=TLpath(S,Hy,do)
E=E-S
return Hy
关键路径算法
# 关键通路
def craticalpath(V,E,di,do,v0,vn):
Hx=craticalTE(V,E,di,v0,vn)
Hn=Hx[len(V)-1]
Hy=craticalTL(V,E,do,Hn,v0,vn)
V=list(V)
N=len(V)
C=set({})
for k in range(N):
if Hx[k] == Hy[k]:
C=C|{V[k]}
Pc=set({})
for (w,u,v) in E:
if u in C and v in C:
Pc=Pc|{(w,u,v)}
return Pc
树
引论
树概念
树的定义
设G=<V, E>是无向图，若G 连通且无圈，则称为树，记为GT=<V, E>。
定理
- 设 T 是树，则在 T 的任何两个不同顶点之间存在唯一的一条基本链。若在 T 的两个不相邻顶点之间加上一条边 e，则图 T+e 仅有一个圈
- 设树 T 是一个 (n, m) 图，则 m = n - 1
- 非平凡树 T 中至少存在两个次数为 1 的顶点
- 设 T 是非平凡 (n, m) 无向图，则下面五个命题等价
- T 是树
- T 连通且无圈
- T 的每一对顶点之间有唯一的一条基本链
- T 连通且 m = n - 1
- T 无圈且 m = n - 1
树的构建
def graph2tree(V, E):
E = sorted(E)
(u, v) = E[0]
Vt = {u, v}
Et = {(u, v)}
E = set(E)
n = len(V)
while (len(Et) < (n - 1)):
m = len(Vt)
for (u, v) in E:
if ((u in Vt and v not in Vt)
or (u not in Vt and v in Vt)):
Vt = Vt | {u, v}
Et = Et | {(u, v)}
E = E - Et
if (m == len(Vt)):
break
return [Vt, Et]
树的判断
def istree(V, E):
tv = True
E = sorted(E)
(u, v) = E[0]
Vt = {u, v}
E = set(E) - {(u, v)}
Et = {(u, v)}
while (E != set({})):
for (u, v) in E:
if (u in Vt) and (v in Vt):
tv = False
break
if ((u in Vt) and (v not in Vt)) or ((u not in Vt) and (v in Vt)):
Vt = Vt | {u, v}
E = E - {(u, v)}
Et = Et | {(u, v)}
if (tv == False):
break
if ((len(Vt) - 1) != len(Et)):
tv = False
return tv
各类树
根树
若一个有向树有一个引入次数为0的顶点，而所有其他顶点的引入次数都为1，则称该有向树为根树。引入次数为0的顶点称为树根。
m 元树
若根树中的每个顶点的引出次数都小于或等于 m，则称这种根树为 m 元树。
完全 m 元树
每个顶点的引出次数等于 m 或 0
位置 m 元树
任何顶点的 m 个子结点都有位置
二叉树
m = 2
有序树
设T=<V,E>是根树，并且每个顶点的子顶点是有序的，则称为有序树。
<u,v,k>表示u的第k个子
二叉树
定义
设T=<V,E>是有序树，并且每个顶点的最多有2个子顶点，则称为二叉树。
递归定义
定义：设 $T = <V, E>$
- $[\ ]$ 是二叉树。
- $a\in V$，$[a]$是二叉树。
- 若$a\in V$，$R_t$ 和 $L_t$ 是二叉树，则 $[a,L_t, R_t]$ 是二叉树。
二叉树构建算法 (set, list 结构)
def createbitree(nodes):
nodes = set(nodes)
if (len(nodes) == 0):
return []
if (len(nodes) == 1):
return list(nodes)
[a] = random.sample(nodes, 1)
nodes = nodes - {a}
k = random.randint(0, len(nodes) - 1)
Lnodes = random.sample(nodes, k)
Lnodes = set(Lnodes)
Rnodes = nodes - Lnodes
L = createbitree(Lnodes)
R = createbitree(Rnodes)
return [a, L, R]
def bitree(nodes):
nodes = list(nodes)
if (len(nodes) == 0):
return []
if (len(nodes) == 1):
return nodes
k = int(len(nodes) / 2)
a = nodes.pop(k)
Lnodes = nodes[0:k]
Rnodes = nodes[k:]
L = bitree(Lnodes)
R = bitree(Rnodes)
return [a, L, R]
二叉树与图
从树结构变换为图结构
- 若
len(tree)=0或len(tree)=1，则为空集。 - tree有左子树，则
L=tree2graph(tree[1]),gtree=gtree | {(tree[0],tree[1][0])} | L - tree有右子树，则
R=tree2graph(tree[2]),gtree=gtree | {(tree[0],tree[2][0])} | R
def tree2graph(tree):
gtree = set({})
if len(tree) == 0 | len(tree) == 1:
return gtree
if len(tree[1]) != 0:
L = tree2graph(tree[1])
gtree = gtree | {(tree[0], tree[1][0])} | L
if len(tree[2]) != 0:
R = tree2graph(tree[2])
gtree = gtree | {(tree[0], tree[2][0])} | R
return gtree
二叉树结构
从有序树生成二叉树
遍历
设G=<E,V>是二叉树，访问G的每个顶点的过程称为遍历。
设 $G=<E,V>$ 是二叉树，$r$ 根顶点，若 $V={r}$ ，则 $r$ 是前序遍历，否则，若 $T_1$ 和 $T_2$ 是 $r$ 的左右子树，则先访问顶点 $r$，而后分别前序遍历子树 $T_1$ 和 $T_2$ 。
前序遍历
def preordertraversal(tree):
if (len(tree) == 0):
return []
if (len(tree) == 1):
return [tree[0]]
else:
return [tree[0]] + preordertraversal(tree[1]) + preordertraversal(tree[2])
中序遍历
def inordertraversal(tree):
if (len(tree) == 0):
return []
if (len(tree) == 1):
return [tree[0]]
else:
return preordertraversal(tree[1]) + [tree[0]] + preordertraversal(tree[2])
后序遍历
def postordertraversal(tree):
if (len(tree) == 0):
return []
if (len(tree) == 1):
return [tree[0]]
else:
return preordertraversal(tree[1]) + preordertraversal(tree[2]) + [tree[0]]
表达式树
霍夫曼编码
二元前缀码
用0-1字符串作为代码表示字符，要求任何字符的代码都不能作为其他字符代码的前缀；
对于位置二叉树，可以采用二元前缀编码，使得每一个顶点都与唯一的一个取自字符表 {0,1} 的字符串对应
- 树根对应空串
- 字符串为 a 的顶点，左子结点的为 0，右子节点为 1
-
位置字符串的前缀编码 = {a a 的树叶对应的字符串}
霍夫曼编码
- 假设顶点集合为 $S$, $u_1$ 和 $u_2$ 是权值最低的两个顶点
- 构造一个新的顶点 $w$，令 $w$ 的左侧子结点为 $u_1$，右侧子结点为 $u_2$，权值为 $u_1$, $u_2$ 之和
-
$S\leftarrow(S-{u_1,u_2})\cup{w}$, 返回步骤 1，直至 $ S = 1$
霍夫曼树的构建与编码熵
def codingentropy(W, C):
# 求得编码熵
r0 = 0
r = 0
W = sorted(W)
C = sorted(C)
for k in range(len(W)):
r0 -= W[k][1] * math.log2(W[k][1])
r += W[k][1] * len(C[k][1])
r0 = math.floor((r0) * 1000) / 1000
r = math.floor((r) * 1000) / 1000
return [r0, r]
def Huffmantree(W):
# 构建霍夫曼树
W0 = []
for [a, w] in W:
W0 = W0 + [[w, a]]
tree = sorted(W0)
while len(tree) != 1:
w = tree[0][0] + tree[1][0]
w = math.floor(w * 10000) / 10000
tree = [[w, tree[0], tree[1]]] + tree[2:]
tree = sorted(tree)
return tree[0]
def Huffmantree2graph(tree):
gtree = set({})
if len(tree) == 2:
return gtree
L = Huffmantree2graph(tree[1])
R = Huffmantree2graph(tree[2])
a = math.floor(tree[0] * 10000) / 10000
l = math.floor(tree[1][0] * 10000) / 10000
r = math.floor(tree[2][0] * 10000) / 10000
gtree = {(a, l)} | {(a, r)} | L | R
return gtree
def htree2graph(G):
V = set({})
for [u, v] in G:
V = V | {u, v}
V = sorted(V)
V = V[::-1]
E = set({})
for [u, v] in G:
E = E | {(V.index(u), V.index(v))}
return [V, E]
def huffmancoding(subtree, code):
if len(subtree) == 2:
return [[subtree[1], code]]
else:
node0 = subtree[1]
node1 = subtree[2]
code = huffmancoding(node0, code + '0') + huffmancoding(node1, code + '1')
return code
def HuffmanCoding(tree):
code0 = huffmancoding(tree[1], '0')
code1 = huffmancoding(tree[2], '1')
return code0 + code1
生成树
生成树 (Spanning Trees)
如果无向图 G 的一个生成子图 T 是树，则称 T 是图 G 的一个生成树
最小生成树 (Minimum Spanning Trees, MST)
对于一个带权无向连通图，最小生成树是其生成树中边的权重之和最小的那个
最小生成树可能不唯一
安全边 (save edge)
对于边的集合 $A\subseteq T$, 其中 $T$ 是一棵最小生成树，如果集合 $A\cup{(u, v)}$ 同样属于 $T$，则 $(u,v)$ 是集合 $A$ 的安全边
若每一步都向集合中增加一条安全边，就可以找到图 G 的最小生成树
分割 (Cut)
表示为 $(S, V-S)$ 是图 $(V, E)$ 的一个划分，划分之和，一部分节点 $\in S$，其他节点 $\not\in S \Rightarrow \in {V-S}$
横跨 (Cross)
如果边 $(u, v)\in E$ 的一个端点在集合 $S$ 中，另一个端点在集合 $(V-S)$ 中，则称边 $(u,v)$ 是分割的横跨边
尊重 (Respect)
如果集合 A 中不存在横跨该分割的边，则称该分割 尊重 集合 $A$
轻边 (Light Edge)
在横跨一个分割的所有边中，权重最小的边，称为 轻边
定理（寻找安全边）
- 对于 带权无向连通图 $G(V, E, W)$
- 假设边的集合 $A$ 为一棵最小生成树的子集
- $(S, V-S)$ 为任意尊重 $A$ 的分割
- $(u,v)$ 是横跨分割 $(S, V-S)$ 的轻边
那么，边 $(u, v)$ 是 $A$ 的一条安全边
Kruskal 算法
算法思路
将图看作离散的点和一堆边
dot = []
while num(边) < n - 1:
从未选择的边中找到满足：<m ,n>
1. 权重最小
2. 两个端点不同时出现在已连接的点中
dot.append(m)
dot.append(n)
将边从未选择中删除
num(边) ++
|  |
|  |
Prim 算法
|  |
|  |
平面图及着色
平面图
所有边在顶点以外没有任何交叉的图称为 平面图
非平面图
$K_{3,3}$
- $k_{3,3}$ 是边数最少的非平面图
$k_{5}$
- $k_5$ 是顶点数最少的非平面图
$k_{3,3}$ 和 $k_{5}$ 删除任意一条边就是平面图
平面图的面
当把一个连通平面图 G 画在平面上，使它的边在顶点之外没有任何交叉时，G 的边把平面分割成许多区域，这样的一个区域称为图 G 的面。
有限面
平面图内部的各个有限区域
无限面
平面图外部的无限区域
周界
围成一个面的各边构成的闭合链，称为 周界
次数
一个平面图所有面的次数之和等于边的数量的两倍
==欧拉公式==
具有 $n$ 个顶点，$m$ 条边， $k$ 个面的 $(m,n)$ 连通平面图 $G$，等式（欧拉公式）恒成立：$n-m+k=2$
极大平面图
设图 G 是一个平面图，如果连接 G 的任意两个不邻接顶点 $u$ 和 $v$ ，都会使 $G+(u,v)$ 变成非平面图，则称图 $G$ 是极大平面图
定理
设 G 是具有至少三个顶点的极大平面图，则 G 的任何一个面都是 $k_3$，$3k=2m$
极大平面图的欧拉公式
- 若一个图的极大平面图，则 $m = 3n-6$
- 若一个图是平面图，则 $m\le 3n-6$，尚可加边
同胚
反复插入和（或）除去次数为 2 的顶点，它们能变成同构的图
库拉图斯基 (Kuratowski) 定理
图 G 是平面图，当且仅当它不包含同胚于 $k_{3,3}$ 或 $k_5$ 的子图
着色问题
给定一个无向图 $G(V, E)$，其中 $V$ 为顶点集合，$E$ 为边集合。图着色问题为：将 $V$ 分成 $K$ 个颜色组，没有相邻顶点同色，取最小的 $K$ 值
对偶图
设 $G$ 是一个平面图，有 $k$ 个面，记为 $F_1, F_2, …, F_k$，其中包括无限面，按如下方式构造的图 $G^*$ 称为图 $G$ 的对偶图：
- 将每个面 $F_i$ 作为 $G^*$ 的一个顶点 $f_j$
- 对于两个面 $F_i$ 和 $F_j$ 的公共边，对应图 $G^*$ 中的边 $(f_i, f_j)$
- 对于仅属于一个面的边（如悬挂边和桥边），则对应图 $G^*$ 中的自环
对偶图将地图的着色问题转换为一般图的顶点着色问题
平面图的着色
- 对给定的无向图 G 的顶点进行涂色，如果每个顶点只涂一种颜色并且任何两个邻接的顶点颜色不同，则称为图的一个正常着色。正常着色所需要的最少颜色数，称为图 G 的 着色数，记为 $\chi(G)$
- 对于不是零图的无向图 G，以下三个说法等价：
- 图 G 的着色数 $\chi(G) = 2$
- 图 G 是二分图
- 图 G 的所有圈的长度都是偶数
- 对以下图的着色数容易计算
- 对于 零图，$\chi(G) = 1$
- 对于具有 n 个顶点的完全图 $K_N$，着色数 $\chi(G) = n$
- 对于两个或两个以上节点的树 $T$，着色数 $\chi(G) = 2$
韦尔奇-鲍威尔算法
- 将图 G 的顶点按次数递减的顺序排序
- 用一种颜色涂染序列中的第一个顶点，以及与该顶点不相邻的每一个顶点
- 余下的节点重新排序，按照上述方法重新着色
此算法不保证能用最少色数
五色定理
对任意一个平面图 G，都有 $\chi(G) \le 5$
证明
二分图与匹配
二分图
设 $G = <V, E>$ 是一个无向图，如果可以把 $V$ 划分成两个子集 $X$ 和 $Y$，使得同一个子集中的任何两个顶点都不邻接，则称图 $G$ 为 二分图。$X$ 和 $Y$ 称为 $G$ 的互补顶点子集
完全二分图
$X$ 中的每个顶点都与 $Y$ 中的所有顶点邻接。若 $#X=p, #Y = q$，则将其记为 $K_{p,q}$
定理
- $G$ 是一个二分图，当且仅当非平凡无向图 $G$ 的所有圈的长度都是偶数
二分图匹配
匹配
设 $G = <V, E>$ 是一个二分图，如果 $E$ 的一个子集 $M$ 中的任何两条边都不相邻，则称 $M$ 为二分图 $G$ 的一个匹配
饱和顶点 & 非饱和顶点
此时，$M$ 中的边所关联的顶点称为 $M$ 的 饱和顶点，而 $G$ 的其他顶点为 非饱和顶点
最大匹配
在二分图 $G$ 的所有匹配中， 边数 最多的匹配称为 $G$ 的 最大匹配
交错链
设 $M$ 是二分图 $G$ 的一个匹配。如果 $G$ 中有这样一条基本链， 链中任何相邻的两条边中恰好有一条属于 $M$，则称这样的链为关于 $M$ 的 交错链
可扩充链
若一条交错链的两个端点是 $M$ 的非饱和顶点，则称该交错链为关于 $M$ 的 可扩充链 (M-augmenting path)
最大匹配相关定理
设 $M$ 是二分图 $G$ 的一个匹配，当且仅当 $G$ 中不存在关于 $M$ 的可扩充链时，$M$ 是 $G$ 的最大匹配
匈牙利算法
- 任取一个匹配 $M$ （可以冲空集或一条边开始）
- 令 $S$ 是非饱和顶点（尚未匹配的点）的集合
- 若 $S=\empty$，则 $M$ 已经是最大匹配
- 否则，从 $S$ 中取出一个非饱和顶点 $u_0$ 作为起点，从 $u_0$ 开始找到交错链 $P$
- 如 $P$ 是可扩充链，则令 $M = (M\cup P)-(M\cap P)$
- 如 $P$ 不是可扩充链，则去掉 $u_0$，回到第 3 步
从 $X$ 到 $Y$ 的匹配
如有二分图 $G$ 的匹配 $M$，使得 $X$ 的每一个顶点都是饱和的，则称 $M$ 为从 $X$ 到 $Y$ 的匹配
- 若存在从 $X$ 到 $Y$ 的匹配，则应该满足 $#X\le#Y$
- 若 $M$ 为从 $X$ 到 $Y$ 的匹配，则 $M$ 是二分图 $G$ 的最大匹配
判断从 $X$ 到 $Y$ 的匹配定理
设 $G$ 是一个具有互补顶点子集 $X$ 和 $Y$ 的二分图。当且仅当对于 $X$ 的任意子集 $U$，$#\Gamma(U)\ge#U$ 被满足时，存在 $G$ 的从 $X$ 到 $Y$ 的匹配
其中，$U$ 表示 $X$ 的子集，$\Gamma(U)$ 表示 $U$ 的邻域，即与 $U$ 中顶点邻接的所有顶点的集合，$\Gamma(U)\subseteq Y$
相异性条件
上述条件被称为 相异性条件
从 $X$ 到 $Y$ 匹配的算法
t 条件
设 $G$ 是具有互补顶点子集 $X$ 和 $Y$ 的二分图，如果能找到一个正整数 t，使得对 $X$ 中的任意顶点 $x$ 有 $d(x)\ge t$，对 $Y$ 的任意顶点有 $d(y)\le t$，则图 $G$ 存在从 $X$ 到 $Y$ 的匹配。定理中的条件称为 “t 条件”
二分图的稳定匹配问题
问题定义 & 描述
Gale-Shapley 算法
代数系统
知识回顾
集合
集合
集合是一些能够明确区分的对象构成的整体，集合一般用大写英文字母表示
- 集合是一组无序对象
- 在集合中没有重复出现的元素
元素
如果对象a在集合A中，则称a是A的元素
集合与元素的关系
- $a属于A, 记为a\in A$
- $a不属于A, 记为a\notin A$
- 在数理逻辑中，属于关系$\in$看作是一个谓词：$a\in A, \neg(a\in A$)
集合示例
-
$N={x x是自然数}$ -
$I={x x是整数}$ -
$Q={x x是有理数}$
集合运算
| 运算名称 | 集合表示 | 内涵定义 | 谓词逻辑表示 | python文字描述 | python表示 | python 意义 | |||
|---|---|---|---|---|---|---|---|---|---|
| 并运算 | $A\cup B$ | ${x | x\in A\vee x\in B}$ | $\forall x(x\in A\cap B\leftrightarrow x\in A\wedge x\in B$) | A.union(B) | A$ | $B | x in A$ | $B==(x in A) or (x in B) |
| 交运算 | $A\cap B$ | ${x | x\in A\wedge x\in B}$ | $\forall x(x\in A\cup B\leftrightarrow x\in A\vee x\in B$) | A.intersection(B) | A&B | x in A&B==x in A and x in B | ||
| 差运算 | $A-B$ | ${x | x\in A\wedge x\notin B}$ | $\forall x(x\in A-B\leftrightarrow x\in A\wedge\neg x\in B$) | A.difference(B) | A-B | x in A-B==x in A and not(x in B) | ||
| 对称差运算 | $A\oplus B$ | ${x | x\in A\oplus x\in B}$ | $\forall x(x\in A\oplus B\leftrightarrow x\in A\oplus x\in B$) | A.symmetric_difference(B) | A^B | x in A^B==x in A$\oplus$x in B | ||
| 补运算 | ~$A$ | {$x | x\notin A$} | $\forall x(x\in$~$A\leftrightarrow x\notin A)$ | U.differnce(A) | U-A | x in ~A==not x in A |
集合之间的关系
包含关系（子集）
定义
若集合A的元素都是集合B的元素，则称A是B的子集，也称A包含于B，或者B包含A，记为A$\subseteq$B
谓词逻辑表示
- $A\subseteq B\Leftrightarrow\forall x(x\in A\rightarrow x\in B$)
- $A\subset B\Leftrightarrow\forall x(x\in A\rightarrow x\in B$)$\wedge\exists x(x\in B\wedge x\notin A$)
- $A\subset B\Leftrightarrow\forall x(x\in A\rightarrow x\in B$)$\wedge A\cap B\neq\varnothing$
- $A\not\subseteq B\Leftrightarrow\exists x(x\in A\wedge x\notin B$)
相等关系
定义(外延性公理)：
如果集合A和B含有相同的元素，则称A和B相等，记为A=B
谓词逻辑表示
- $A=B\Leftrightarrow\forall x(x\in A\leftrightarrow x\in B$)
- $A=B\Leftrightarrow\forall x(x\in A\leftrightarrow x\in B$)$\wedge\forall x(x\in B\rightarrow x\in A$)
集合运算性质
| 定律 | 描述1 | 描述2 |
|---|---|---|
| 结合律 | ($A\cup B)\cup C=A\cup(B\cup C$) | ($A\cap B)\cap C=A\cap(B\cap C$) |
| 交换律 | $A\cup B=B\cup A$ | $A\cap B=B\cap A$ |
| 分配律 | $A\cup(B\cap C$)=($A\cup B)\cap(A\cup C$) | $A\cap(B\cup C$)=($A\cap B)\cup(A\cap C$) |
| 德·摩根律 | $\neg(A\cup B)=$$(\neg A)\cap(\neg B)$ | $\neg (A\cap B)=$$(\neg A)\cup (\neg B)$ |
| 幂等律 | $A\cup A=A$ | $A\cap A=A$ |
| 吸收率 | $A\cup(A\cap B$)$=A$ | $A\cap(A\cup B$)$=A$ |
| 对合律 | ~~$A=A$ |
函数
满射、单射和双射
$设函数f:X\rightarrow Y$
满射
若对于每个 y$\in$Y，都存在 x$\in$X使得 f (x) = y，则称f为满射，即
- $\forall y(y\in Y\rightarrow\exists x(x\in X\wedge f(x$$)=y))$
单射
若对于任意 x1$\in$X, x2$\in$X， 若 f (x$_1$) = f (x$_2$)则x1=x2，称 f 为单射，即
- $\forall x_1\forall x_2(x_1\in X\wedge x_2\in X\wedge f(x_1\()=f(x_2\))\rightarrow x_1=x_2$
双射
$f$既是单射又是满射，则$f$是双射函数。
关系
关系的定义
设X,Y是集合，若R$\subseteq$X × Y, 则称R为从X到Y的关系，简称为关系R
- 将<x,y>$\in$R表示为x$R$y, 读作“x和y有关系R”
- 将<x,y>$\not\in$R表示为x$\underline{R}$y, 读作“x和y没有关系R”
若R是从X到Y的关系，就是集合X中元素与集合Y中元素之间的对应
- 从集合X中选择一个元素x, 对应地再集合Y中选择一个元素y
- x和y组成一个有序偶(x,y)
- 有序偶(x,y)$\in$R
定义域和值域
定义域
关系R中所有有序偶的第一元组成的集合称为R的定义域，记为dom(R)
| dom(R)={x | $\exists$y(<x,y$\in$R>)} |
值域
关系R中所有有序偶的第二元组成的集合称为R的值域，记为ran(R)
| ran(R)={y | $\exists$x(<x,y>$\in$R)} |
特殊关系
空关系$\varnothing$
恒等关系
| $I_x={<x,x> | x\in X}$ |
全域关系
| $U_x={<x,y> | x\in X\wedge y\in X}$ |
$\varnothing\subseteq I_x\subseteq U_x$
关系的集合运算
设关系$R$和$S$是从$X$到$Y$的两个关系，则运算为$R\cap S,R\cup S,R-S,R$^$S,$~$R$
-
$R\cap S={(x,y) (x,y)\in R\wedge<x,y>\in S}$ -
$R\cup S={(x,y) (x,y)\in R\vee<x,y>\in S}$ -
$R-S={(x,y) (x,y)\in R\wedge<x,y>\not\in S}$ -
$R$^$S={(x,y) (x,y)\in R\oplus<x,y>\in S}$ -
~$R={(x,y) (x,y)\not\in R}$ - python运算符
- & 交
-
并 - $-$ 差
- ^ 对称差
复合运算
关系$R\subseteq X×Y$和关系$S\subseteq Y×Z$的复合
| $R\circ S={<x,z> | \exists y(<x,y>\in R\wedge<y,z>\in S$$)}$ |
逆运算
定义$R\subseteq X×Y$的逆关系
| $R^-$$^1={<y,x> | <x,y>\in R}$ |
将R中每个有序偶的第一元与第二元对调就得到$R$的逆关系$R^-$$^1$
幂运算
设$R$是$X$上关系，$n$是自然数，$R^n$定义如下:
-
$R^0=I_x\qquad\qquad\ X =m$ - $R^n\(^+\)^1=R^n\circ R\qquad R^m\(^+\)^1=?$
关系运算性质
若R和S都是从X到Y的关系，则$R\cap S,R\cup S,R-S,R+S,$~$R$仍然是从X到Y的关系
- $R\subseteq X×Y,\ S\subseteq X×Y\vDash R\cap\ S\subset X×Y$
- $R\subseteq X×Y,\ S\subseteq X×Y\vDash R\cup\ S\subset X×Y$
- $R\subseteq X×Y,\ S\subseteq X×Y\vDash R-S \subset X×Y$
- $R\subseteq X×Y,\ S\subseteq X×Y\vDash R+S \subset X×Y$
- $R\subseteq X×Y\vDash$~$R\subseteq X×Y$
复合性质
若$R$是从$X$到$Y$的关系，$S$是从$Y$到$Z$的关系，则$R\circ S\subseteq X×Z$
即$R\subseteq X×Y,\ S\subseteq Y×Z \vDash R\circ S\subseteq X×Z$
- $(R_1\circ R_2$$)\circ R_3=R_1\circ(R_2\circ R_3$)
- $R\circ I_A=I_A\circ R=R$
- $(R_1\cap R_2$$)\circ R_3\subseteq R_1\circ R_3\cap R_2\circ R_3$
- $R_1\circ($$R_2\cap R_3)\subseteq R_1\circ R_2\cap R_1\circ R_3$
- $(R_1\cup R_2$$)\circ R_3\subseteq R_1\circ R_3\cup R_2\circ R_3$
- $R_1\circ($$R_2\cup R_3)\subseteq R_1\circ R_2\cup R_1\circ R_3$
- 注意：一般不满足交换律
逆运算性质
- ($R_1\cup R_2$)$^-\(^1\)=R_1\(^-\)^1\(\cup\ R_2\)^-$$^1$
- ($R_1\cap R_2$)$^-\(^1\)=R_1\(^-\)^1\(\cap\ R_2\)^-$$^1$
- ($R_1-R_2$)$^-\(^1\)=R_1\(^-\)^1\(-R_2\)^-$$^1$
- (~$\ R_1$)$^-\(^1\)=\(\ $~$\ R_1\)^-$$^1$
- ($R_1\circ R_2$)$^-$$^1$$=R_2$$^-$$^1$$\circ\ R_1$$^-$$^1$
幂运算性质
- $R^mR^n=R^m\(^+\)^n$
- ($R^m$)$^n=R^m$$^n$
关系特性
- 集合X上的有一些重要的关系R
- 自反的($reflexive$)
- 矩阵的主对角线均为1，关系图中每个节点都有自环
- 反自反的($irreflexive$)
- 矩阵的主对角线均为0，关系图中每个节点都没有自环
- 对称的($symmetric$)
- 矩阵的所有元素关于主对角线对称，关系图中任意两个节点间或者没有边或者是双向边
- 反对称的($antisymmetric$)
- 矩阵关于主对角线对称位置至多有一个为1，关系图中任意两个节点间或者没有边或者单边。
- 传递的($transitive$)
- 任意两个节点间有路径，节点间一定有边。
- 自反的($reflexive$)
- 构建特性关系
- 自反关系
- 对称关系
- 传递关系
自反
- 定义设R是集合X上的关系
- 若对于每个x$\in X$都有$<x,x>\in R$, 则称R为自然的，即
- $\forall x(x\in X\rightarrow<x,x>\in R$)
反自反
- 定义设R是集合X上的关系
- 若对于每个$x\in X$都有$<x,x>\not\in R$, 则称R为反自反的，即
- $\forall x($$x\in X\rightarrow<x,x>\not\in R)$
- $\forall x($$x\in X\rightarrow\neg<x,x>\in R)$
对称
- 定义设$R$是集合$X$上的关系
- 若对于$x,y\in X$, 以及($x,y$)$\in R$, 就称R是对称的, 即
- $\forall x\forall y(x\in X\wedge y\in X\wedge(x,y$)$\in\rightarrow(y,x$)$\in R)$
反对称
- 定义设R是集合X上的关系
- 若对于每个$x,y\in X$, 以及$(x,y)\in R$, 且$(y,x)\in R$, 则有$x=y$, 就称$R$是反对称的，即
- $\forall x\forall y(x\in X\wedge y\in X\wedge (x,y\()\in R\wedge(y,x\))\in R\rightarrow x=y$
传递
- 定义设$R是集合X$上的关系
- 若对于每个$x,y,x\in X$, 以及$(x,y)\in R$且$<y,z>\in R$, 则有$<x,z>\in R$, 就称$R$是传递的，即
- $\forall x\forall y\forall z(x\in X\wedge y\in X\wedge z\in X\wedge(x,y)\in R\wedge<y,z>\in R\rightarrow<x,z>\in R)$
构造特征关系
- 自反
- 设 R是集合 X 上的关系，则 R’ 是自反的，其中 $R’=R\cup I_x$
- 反自反
- 设 R是集合 X 上的关系，则 R’ 是反自反的，其中 $R’=R-I_x$
- 对称
- 设 R是集合 X 上的关系，则 R’ 是对称的，其中 $R’=R\cup R^-$$^1$
- 反对称
- 设 R是集合 X 上的关系，则 R’是反对称的，其中 $R’=(R-(R\cap R^-$$^1))\cup R\cap I_x$
- 传递
-
设 R是集合 X 上的关系， X =m，则 R’是传递的，其中，$R’=\cup_n\(_=\)_1\(_,\)_m$$R^n$
-
关系特性的性质
定理：
设R是集合X上的关系
- $R是自反的当且仅当R=I_x\cup R$
- $R的反自反的当且仅当I_x\cap R=\varnothing$
- $R是对称的当且仅当R^-$$^1=R$
- $R是反对称的当且仅当R\cap R^-$$^1\subseteq I_x$
- $R是传递的当且仅当R\circ R\subseteq R$
关系特性与集合运算的性质探究
设$R_1, R_2\subseteq X×X$, 若$R_1, R_2$是自反的, 则$R_1\cup R_2$是自反的
| \ | $R_1\cup R_2$ | $R_1\cap R_2$ | $R_1-$$R_2$ | ~$R_1$ | $R_1\circ R_2$ | $R_1^-$$^1$ |
|---|---|---|---|---|---|---|
| 自反性 | $\surd$ | $\surd$ | - | - | $\surd$ | $\surd$ |
| 反自反性 | $\surd$ | $\surd$ | $\surd$ | - | - | $\surd$ |
| 对称性 | $\surd$ | $\surd$ | $\surd$ | $\surd$ | - | $\surd$ |
| 反对称性 | - | $\surd$ | $\surd$ | - | - | $\surd$ |
| 传递性 | - | $\surd$ | - | - | - | $\surd$ |
代数系统
代数运算
概念
设 $X$ 是一个集合，$\psi$ 是 $X\times X\rightarrow X$ 的映射，则称 $\psi$ 是 $X$ 的一个 代数运算
在集合 $X$ 中，任意两个有次序的元素 $a$ 与 $b$，依据一个法则，都有唯一确定的元素 $d$ 与它们对应，则称这个法则是集合 $X$ 的一个代数运算，称集合 $X$ 关于运算 $\psi$ 是封闭的。可记为 $a\circ b=d$
特点
- 唯一性
- 封闭性
代数运算实例
$\N,\ \Z,\ \Q,\ \R$ 分别为自然数、整数、有理数、实数集
$M_n(\R)$ 为 $n$ 阶实矩阵（实数矩阵）集合，$n\ge 2$
$P(B)$ 为幂集
| $X^X$ 为从 $X$ 到 $X$ 的函数集, $ | X | \ge 2$ |
| 集合 | 运算 |
|---|---|
| $\N,\ \Z,\ \Q,\ \R$ | $+,\ \times$ |
| $M_n(\R)$ | $+$(矩阵加法)$,\ \times$(矩阵乘法) |
| $P(B)$ | $\cup,\ \cap$ |
| ${0,1}$ | $\and,\ \or$ |
| $X^X$ | $\circ$(函数复合) |
$N_n$ 是有穷自然数集合
- $<N_n, \oplus>$
- $N_n = {0, 1,…,n-1}$
- $x\oplus y = (x+y) \mod{n}$
- $<N_n,\otimes>$
- $N_n = {1, …,n}$
- $x\otimes y = (x\times y)\mod{n}$
运算表
表示有穷集上的一元运算和二元运算
| $\circ$ | $a_1$ | $a_2$ | … | $a_n$ |
|---|---|---|---|---|
| $a_1$ | $a_1\circ a_1$ | $a_1\circ a_2$ | … | $a_1\circ a_n$ |
| $a_2$ | $a_2\circ a_1$ | $a_2\circ a_2$ | … | $a_2\circ a_n$ |
| … | … | … | … | |
| $a_n$ | $a_n\circ a_1$ | $a_n\circ a_2$ | … | $a_n\circ a_n$ |
结合律、交换律、分配律
结合律
设 $X$ 是集合，$X$ 上有代数运算 $\circ$，如果对 $X$ 中任意元素 $x,y,z$ 都有 $x\circ(y\circ z)=(x\circ y)\circ z$
交换律
$x\circ y=y\circ x$
分配律
$x\circ (y\oplus z) = (x\circ y)\oplus (x\circ z)$
幂等律、吸收律
==幂等律==
设X是集合，$X$上有代数运算$\circ$，$e$是$X$上的单位元，如果对$X$中任意元素$x$都有 $x\circ x = e$，则称运算在$X$上满足幂等律
==吸收律==
设$X$是集合，$X$上有代数运算$\circ$，如果对$X$中任意元素$x$都有 $x\circ x=x$，则称运算在$X$上满足吸收律
| 集合 | 运算 | 交换律 | 结合律 | 幂等律 |
|---|---|---|---|---|
| $\N, \Z,\Q,\R$ | $+$ | $\surd$ | $\surd$ | $\times$ |
| $\times$ | $\surd$ | $\surd$ | $\times$ | |
| $M_n(R)$ | $+$(矩阵加法) | $\surd$ | $\surd$ | $\times$ |
| $\times$(矩阵乘法) | $\times$ | $\surd$ | $\times$ | |
| $P(S)$ | $\cup$ | $\surd$ | $\surd$ | $\surd$ |
| $\cap$ | $\surd$ | $\surd$ | $\surd$ | |
| ${0,1}$ | $\and$ | $\surd$ | $\surd$ | $\surd$ |
| $\or$ | $\surd$ | $\surd$ | $\surd$ | |
| $X^X$ | $\circ$ （函数复合） | $\times$ | $\surd$ | $\times$ |
克莱恩 (Klein) 四元集合及运算
| $\circ$ | e | a | b | c |
|---|---|---|---|---|
| e | e | a | b | c |
| a | a | e | c | b |
| b | b | c | e | a |
| c | c | b | a | e |
特殊元
单位元
设$\circ$为$X$上的二元运算,如果存在$e\in X$，使得对任意 $x\in X$ 都有 $e\circ x = x$，则称 $e$ 是 $X$ 中关于$\circ$运算的左单位元。（同理定义右单位元）
$e$ 既为左单位元又为右单位元 $\Rightarrow$ $e$ 为 $X$ 上关于 $\circ$ 运算的单位元
零元
设$\circ$为$X$上的二元运算,如果存在$0\in X$，使得对任意 $x\in X$ 都有 $0\circ x = 0$，则称 $0$ 是 $X$ 中关于$\circ$运算的左零元。（同理定义右零元）
$0$ 既为左零元又为右零元 $\Rightarrow$ $0$ 为 $X$ 上关于 $\circ$ 运算的单位元
逆元
关于 $\circ$ 运算，若 $y\in X$ 既是 $x$ 的左逆元又是 $x$ 的右逆元则称 $y$ 为 $x$ 的逆元，表示为 $x^{-1}$ 。
如果 $x$ 的逆元存在，就称 $x$ 是可逆的。
幂等元
设 $\circ$ 为X上的二元运算,若 $x\in X$ 且 $x \circ x=x$，则称 $x$ 是 $X$ 中关于运算 $\circ$ 的幂等元。
特殊元实例
| 集合 | 运算 | 单位元 | 零元 | 逆元 |
|---|---|---|---|---|
| $\N,\ \Z,\ \Q,\ \R$ | $+$ | $0$ | $\times$ | $-x$ |
| $\times$ | $1$ | $0$ | $x^{-1}$ | |
| $M_n(\R)$ | $+$ (矩阵加法) | $0$ 矩阵 | $\times$ | $-X$ |
| $\times$ (矩阵乘法) | 单位矩阵 | $0$ 矩阵 | $X^{-1}$ | |
| $P(S)$ | $\cup$ | $\empty$ | $S$ | $\empty$ 的逆元为 $\empty$ |
| $\cap$ | $S$ | $\empty$ | $S$ 的逆元为 $S$ |
代数系统
设 $X$ 是非空集合，$X$上有 $m$ 个代数运算 $\psi_1, \psi_2, …, \psi_m$，集合 $X$ 及其代数运算组成的系统称为一个代数系统，简称代数，记为 $<X, {\psi_1,\psi_2,…,\psi_m}>$，其中，$m>0$。
在代数中，对象是抽象的而不是具体的，对象上的运算也是抽象的，其含义由一组给定公理规定。
公理
代数运算所具有的性质作为公理，并用方程的形式表示出来。如：结合律、交换律
代数常量
特殊元素：如单位元、零元等等
代数系统实例
<对象集合、运算集合、常量集合>
<$\N$，+，*，0，1>
$\forall a,b,c\in \N$
- (a+b)+c = a+(b+c), (a*b)*c = a*(b*c)
- a+b =b +a , a*b=b*a
- a+0 =0+a =a, a+(-a)=0, a*1 =1*a =a
- (a+b)*c = a*c+b*c
同态
定义
设集合 $X$ 与 $Y$ 各有代数运算 $\circ$ 及 $\bullet$ ，且 $\psi$ 是 $X$ 到 $Y$ 的一个映射，如果 $\psi$ 满足以下条件：在 $\psi$ 之下：$\psi(a\circ b)=\psi(a)\bullet\psi(b)$，称 $\psi$ 为代数系统 $<X,\circ>$ 与 $<Y,\bullet>$ 同态。记为 $<X,\circ>\sim<Y,\bullet>$
若 $\psi$ 是满射，则 $\psi$ 称为代数系统 $<X,\circ>$ 到 $<Y,\bullet>$ 的同态满射。简称 $<X,\circ>$ 与 $<Y,\bullet>$ 满同态
性质
- 若代数系统 $<X,\circ>$ 与 $<Y,\bullet>$ 满同态，则对代数运算 $\circ$ 及 $\bullet$
- 若 $\circ$ 满足结合律，则 $\bullet$ 也满足结合律
- 若 $\circ$ 满足交换律，则 $\bullet$ 也满足交换律
- 若代数系统 $<X, {\circ,\oplus }>$，$<Y, {\bullet,\otimes }>$ 满同态，若代数运算 $\circ, \oplus$ 满足分配律，则 $\bullet,\otimes$ 也满足分配律
同构
定义
设集合 $X$ 与 $Y$ 各有代数运算 $\circ$ 及 $\bullet$，且 $\psi$ 是 $X$ 到 $Y$ 的一个一一映射，如果 $\psi$ 满足以下条件：$\psi(a\circ b)=\psi(a)\bullet\psi(b)$，称 $\psi$ 为代数系统 $<X, \circ>$ 到 $<Y,\bullet>$ 的一个 同构映射，简称 $<X, \circ>$ 与 $<Y,\bullet>$ 同构。记为 $<X, \circ>\cong<Y,\bullet>$
性质
- 保持运算的所有性质
- 从抽象角度，两个代数系统完全相同
子代数
定义
设 $A=<X,\bullet>$ 是一个代数系统，若 $Y\not=\empty$ , $Y\in X$，并且对于代数 $A$ 的运算 $\bullet$ 封闭，则称代数系统 $A_s=<Y,\bullet>$ 是代数系统 $A$ 的子代数
性质
子代数保留原来代数系统中相关运算性质
商代数
定义
| 设 $R$ 是 $X$ 上的等价关系，$A=<X,\bullet>$ 是一代数系统，则 $A_q=<X/\R,\circ>$ 是一代数系统，称为 $A$ 的商代数。其中，$X/R={[x]_\R | x\in X}$ ，$\circ$ 定义为对任意的 $[x]\R,\ [y]\R\in X/\R,\ [x]\R\circ[y]\R=[x\bullet y]_\R$ |
等价关系定义为：设R是非空集合A上的二元关系，若R是自反的、对称的、传递的，则称R是A上的等价关系。
性质
- 一个代数系统 $<X, \bullet>$ 与其商代数 $<Y, \circ>$ 满同态。
- 商代数保留原代数系统的运算性质
积代数
定义
代数系统 $<X, \bullet>$ , $<X, \circ>$ 的积代数定义为 $<X\times Y,\otimes>$ ，其中 $\times$ 为笛卡尔积，运算 $\otimes$ 定义为：
对任意 $(x_1, y_1)$, $(x_2, y_2)\in X\times Y,\ (x_1,y_1)\otimes(x_2,y_2)=((x_1\bullet x_2),\ (y_1\circ y_2))$
性质
积代数保持两个代数运算共有的运算性质
半群
半群
定义
对代数系统 $<S,\circ>$ ，若对任意 $a,b,c\in S$，有 $(a\circ b)\circ c=a\circ(b\circ c)$，则称 $<S,\circ>$ 为半群
性质
- $<S, \circ>$ 为半群，若 $S$ 有限，则必有 $a\in S$ 使得 $a\circ a=a$
- 半群导出定理：设 $<S,*>$ 是半群，$<T,\odot>$ 是一个代数系统，若有一同态满射 $\psi:S\rightarrow T$，则 $<T,\odot>$ 也是半群
- 设 $<S,>$ , $<T,\odot>$ 是半群满同态，若 $<S,>$ 是幺半群，则 $<T,\odot>$ 也是幺半群，满同态映射作用于 $S$ 的单位元的象是 $T$ 的单位元
- 设 $\psi$ 是半群 $(S,\circ)$ 到 $(T,\odot)$ 的同态，$\mu$ 是半群 $(T,\odot)$ 到 $(U,*)$ 的同态，则 $\mu$ 到 $\psi$ 的复合映射 $\mu\cdot\psi$ 是一个 $(S,\circ)$ 到 $(T,\odot)$ 的同态
交换半群
对代数系统 $<S,\circ>$ ，若对任意 $a,b,c\in S$，有 $(a\circ b)\circ = a\circ (b\circ c)$ 且 $a\circ b=b\circ a$ ，则称 $<S,\circ>$ 为交换半群
独异点 | 幺半群
定义
若 $<S, \circ>$ 为半群，并且存在一个单位元 $e\in S$，对任意 $a\in S$ ，有 $a\circ e=e\circ a$ ，则 $<S,\circ,e>$ 为 独异点 或称 幺半群
定理
- $<S,\circ, e>$ 为独异点或幺半群，则关于 $\circ$ 运算的运算表中，任何两行或两列都不相同
- $<S,\circ, e>$ 为独异点或幺半群，若对任意 $a,b\in S$ ，都有逆元，则
- $(a^{-1})^{-1}=a$
- $a\circ b$ 有逆元且 $(a\circ b)^{-1}=b^{-1}\circ a^{-1}$
循环独异点 | 循环幺半群
定义
一个独异点 $<S,\circ, e>$ 称为 循环独异点 或 循环幺半群，若存在一个元素 $a\in S$ ，使得 $S$ 中每个元素 $b$ 都可以表示为：$a=a\circ a\circ a…\circ a=a^n,\ a^0=e$
也称 $<S,\circ>$ 是由元素 $a$ 生成的，$a$ 称为 $<S,\circ, e>$ 的生成元
性质
对循环独异点 $<S,\circ,e>,\ <S,\circ>$ 为交换半群
子半群
定义
设 $<S,\circ>$ 为一个半群，若
- $S^{‘}\subseteq S$
- $<S^{‘},\circ>$ 是半群
则称 $<S^{‘},\circ>$ 是 $<S,\circ$ 的 子半群
定理
$<S,\circ>$ 是一个半群，若 $S^{‘}\subseteq S$，且 $S^{‘}$ 关于 $\circ$ 运算封闭，则 $<S^{‘},\circ>$ 是 $<S,\circ>$ 的子半群
半群同态和同构
定义
设 $<S,>$, $<T,\odot>$ 是半群，若存在一个映射 $\Psi:S\rightarrow T$，对任意 $a,b\in S$，都有 $\Psi(ab)=\Psi(a)\odot\Psi(b)$，则称 $\Psi$ 为 半群同态
若 $\Psi$ 是满射，则称 $\Psi$ 是 半群满同态
若 $\Psi$ 是一一映射，则称 $\Psi$ 是 半群同构
若 $S$, $T$ 相同，则称 $\Psi$ 为 自同态/自同构
商半群
定义
对半群 $<S,>$，若 $R$ 是 $S$ 上的等价关系，则称 $<S/R,\oplus>$ 为 $<S,>$ 的商半群，运算 $\oplus$ 为 $*/R$
定理
半群和它的商半群满同态
半群直积
定义
设 $<S,>$ , $<T,\odot>$ 是两个半群，其上的代数系统直积 $<S\times T,\otimes>$，其中 $\times$ 为 $S, T$ 的笛卡尔积，$\otimes$ 定义为对任意 $A_1,a_2\in S$, $b_1,b_2\in T$, $(a_1, b_1)\otimes (a_2,b_2)=((a_1a_2),(b_1\odot b_2))$ 称为半群直积
定理
- 半群直积也称为半群
- 交换半群的直积也是交换半群
- 幺半群的直积也是幺半群，并且其独异点（单位元） 是两个半群单位元的笛卡尔积
- 有零元的半群直积的零元是两个半群零元的笛卡尔积
- 有逆元的半群直积的逆元是两个半群逆元的笛卡尔积
群
群
定义
设 $G$ 是一个非空集合， $\times$ 是儿园代数运算，如果满足以下条件：
- 代数运算 $\times$ 满足结合律，即对 $G$ 中的任意元素 $a,b,c$ 都有 $(a\times b)\times c=a\times(b\times c)$
- $G$ 中有 左 单位元 $e$，对于 $G$ 中的每个元素 $a$ 都有 $e\times a=a\times e=a$
- 对 $G$ 中每个元素 $a$，都有 左 逆元 $a^{-1}$，使得 $a^{-1}\times a=a\times a^{-1}=e$
则称 $G$ 对代数运算 $\times$ 作成一个 群
群 $\subseteq$ 独异点 $\subseteq$ 半群 $\subseteq$ 代数系统
公理
群理论可以采用数理逻辑方法表示，它有三条公理
-
满足结合律
$\forall x\in G,y\in G,z\in G$，有 $\forall x\forall y\forall z ((x\times y)\times z=x\times (y\times z))$
-
有单位元
$\forall x\in G$，有 $\forall x(e\times x=x\times e = x)$
-
有逆元
$\forall x\in G$，存在元素 $y\in G$ 使得 $\forall x\exists y(y\times x=x\times y=e)$
性质
- 群 $<G,\times>$ 的左单位元也是有单位元，单位元唯一
- 群 $<G,\times>$ 中元素的左逆元也是右逆元，逆元唯一
- 群 $<G,\times>$ 无零元
- 消去律：群 $<G,\times>$ 的运算 $\times$ 满足
- 如果 $a\times x=a\times x^{‘}$，则 $x=x^{‘}$
- 如果 $x\times a=x^{‘}\times a$，则 $a=x^{‘}$
- 唯一解： 群 $<G,\times>$ ，$\forall a,b\in G$，必存在唯一的一个 $x\in G$，使得 $a\times x=b$，$x\times a=b$
- 群 $<G,\times>$ 中只有单位元是幂等元
- 群中运算满足消去律
- $a\circ b=a\circ c\rightarrow b=c$
- $a\circ c=b\circ c\rightarrow a=b$
- 群的每一行每一列都是群元素的双射
- 群 $G$，对任意 $a,b\in G$，都有：
- $(a^{-1})^{-1}=a$
- $(ab)^{-1}=b^{-1}a^{-1}$
元素幂的性质
设 $G$ 为群，对于任意 $a,b\in G，有
- $a^ma^n=a^{m+n}$
- $(a^m)^n=a^{mn}$
元素的阶
| $ | a | =k$，使得 $a^k=e$ 成立的最小正整数 $k$ |
有限群元素的阶一定是有限阶，且是群的阶的因子
群的阶
一般情况下，群 $G$ 的阶 = 其因子的个数
当群 $G$ 为循环群时，群 $G$ 的阶为其生成元的阶
| 设有限群 $G$ 的阶是 $ | G | $，任意元素 $a\in G$，$a$ 的阶是 $ | a | $，则 $ | a | $ 整除 $ | G | $，即 $ | a | \ | \ | G | $ |
特殊群
有限群
| 给定群 $<G,\times>$ ，若 $G$ 是有限集，则称 $<G,\times>$ 是 有限群。元素个数称为群的阶，表示为 $ | G | $ |
无穷群
若集合 $G$ 是无穷的，则称 $<G,\times>$ 为 无穷群；阶无穷大
平凡群
只含单位元的群称为 平凡群
可交换群 (Abel 群)
给定群 $<G,\times>$ ，若 $\times$ 满足交换律，则称 $<G,\times>$ 是 可交换群 或 Abel 群
克莱恩 (Klein) 四元集
| $\circ$ | e | a | b | c |
|---|---|---|---|---|
| e | e | a | b | c |
| a | a | e | c | b |
| b | b | c | e | a |
| c | c | b | a | e |
模 N 集
$<I_N,\oplus>$ 称为模 N 整数加群，其中，$x\oplus y=(x+y)\mod{N}$
交换群 (Abel 群)
定义
若群 $G$ 的运算满足交换律，则称群 $G$ 为交换群，又称阿贝尔群
定理
- 群 $G$ 是阿贝尔群 $\Leftrightarrow$ 对任意元素 $a,b\in G$，有 $(ab)^2=a^2b^2$
循环群
定义
群 $G$，存在一个 $a\in G$，使得群中任意元素可以表示为 $a$ 的幂，则群 $G$ 称为 循环群，$a$ 称为 $G$ 的生成元，记为 $G=(a)$
循环群的阶
- 生成元的阶是无限的，则 $G$ 是无限循环群
- 生成元的阶是 $n$，则 $G$ 为 $n$ 阶群
性质
- 循环群的生成元不一定是唯一的
-
有限群 $G=(a)$，若 $ G =n$，则 $a^n=e$ 且 $G={a,a^2,…,a^n=e}$，其中 $e$ 是群 $G$ 的单位元
定理
- 任何一个循环群必是交换群
- 群 $G=(a)$
- 若 $G$ 是无限循环群，则 $G$ 的生成元是 $a$ 或 $a^{-1}$
-
若 $ G =n$，则 $G$ 有 $\phi(n)$ 个生成元，$\phi(n)$ 为 欧拉函数
-
在群 $G$ 中，$ a =n$，则 $ a^k =\frac{n}{(n,k)}$ - 任何一个循环群的子群也是循环群
- 无限循环群 $G$ 的子群除 ${e}$ 之外也是无限的
- 有限循环群 $G$，其子群的阶是群 $G$ 的因子，且 $G$ 有且仅有一个子群，其阶为该因子
变换群
定义
| $A$ 为非空集合，$F(A)={f | f:A\rightarrow A 上的双射}$，关于函数复合构成的群称为 变换群 |
性质
任何群 $G$ 都和一个变换群 $S$ 同构
置换群
定义
有限群的变换群称为 置换群
定理
每一个有限群都和一个置换群同构
置换与变换
置换
定义
置换 $\sigma$ 把 $a_1$ 变成 $\sigma(a_1)$，把 $a_2$ 变成 $\sigma(a_2)$，…，是一个一对一映射
表示方式
$\begin{pmatrix}1 & 2&…&n\ \sigma(1)&\sigma(2)&…&\sigma(n)\end{pmatrix}$
轮换
置换 $\begin{pmatrix}i_1 & i_2&…&i_{k-1}&i_k&i_{k+1}&…&i_n\ i_2&i_3&…&i_k&i_1&i_{k+1}&…&i_n\end{pmatrix}$ 称为 k-轮换
恒等变换
k = 1 的 k-轮换称为 恒等变换
对换
k = 2 的 k-轮换称为 对换
定理
- 有限置换可表示为不相交的轮换积
- 不相交轮换可以表示为对换积
陪集
定义
| 设 $H$ 是群 $G$ 的子群，$a\in G$，有 $aH={ax | x\in G},\ Ha={xa | x\in G}$ 则 $aH,Ha$ 分别称为群 $G$ 关于子群 $H$ 的一个左陪集，右陪集 |
性质
- $a\in aH$
- $a\in H\Leftrightarrow aH=H$
- $b\in aH\Leftrightarrow aH=bH$
- $aH=bH\Leftrightarrow a^{-1}b\in H$ 或 $b^{-1}a\in H$
- $b\in aH\Leftrightarrow aH=bH\Leftrightarrow a^{-1}b\in H$ 或 $b^{-1}a\in H$
- 若 $aH\cap bH\not=\empty$，则 $aH=bH$
- 群 $G$ 上全体不同的左陪集构成群 $G$ 的元素分类，对任意 $a,b$ 若同属一类，当且仅当 $a^{-1}b\in H$ （或 $b^{-1}a\in H$）
- 对于右陪集，上条同理
定理
-
$H$ 是 $G$ 的子群，则 $R={<a,b> a\in G,b\in G 且 a^{-1}b\in H}$ 是 $G$ 中一个等价关系，对于 $a\in G$，记为 $[a]_R={x x\in G 且 <a,x>\in R}$，则有 $[a]_R=aH$ -
一个子群 $H$ 的所有陪集都与 $H$ 等势
等势是数学术语，集合里的等势是指两个集合之间一一对应。
-
拉格朗日定理：$H$ 是 $G$ 的子群，若 $G$ 是有限群，$ G =n,\ H =m,\ (G:H)=k$，则 $n=km$ 群 $G$ 的阶为质数，则群 $G$ 无非平凡子群 / 真子群
-
群 $ G =n$ ，对于任意 $a\in G, a $ 是 $n$ 的因子，且必有 $a$，$a^n=e$。若 $n$ 是质数，则群 $G$ 是循环群。
指数
群 $G$ 的子群 $H$ 的所有不同左陪集（右陪集）的个数称为 $H$ 在 $G$ 里的指数，可表示为 $(G:H)$
不变子群
定义
$G$ 的子群 $N$，若对于任意 $a\in G$，都有 $aN=Na$，则称 $N$ 为不变子群或正规子群。记为 $N\trianglelefteq G$，若 $N\not= G$，则记为 $N\triangleleft G$
定理
若对任意 $a\in G$，$a^{-1}Na=aNa^{-1}=N$，则 $N\trianglelefteq G$
半群与群
- 对半群 $G$，若对任意 $a,b\in G$， 方程 $a x = b，x a = b$ 在 $G$ 中有解，则 $G$ 为群。
- 对有限半群 $G$ 无零元，若满足消去律，则 $G$ 为群
子群
定义
$<S,\times>$ 称为群 $<G,\times>$ 的子群，若
- $S\subseteq G$
- $<S,\times>$ 是一个群
记为 $S\le G$
性质
-
若 $ G \gt1$ ，则群 $<G,\times>$ 至少有两个子群： - $<{e},\times>$
- $<G,\times>$
称为 $G$ 的 平凡子群，其他子群称为 真子群 / 非平凡子群，记为 $S\lt G$
- $<S, \times>$ 是群 $<G, \times >$ 的非空子群，则群 $S$ 的单位元就是群 $G$ 的单位元，$S$ 中任意元素 $a$ 的逆元也是 $a$ 在群 $G$ 中的逆元。
定理
- 群 $G$ 的非空子集 $S$ 构成子群的充要条件是
- 若 $a,b\in S$，则 $ab\in S$
- 若 $a\in S$，则 $a$ 在 $G$ 中逆元 $a^{-1}\in G$
- 群 $G$ 的非空子集 $S$ 构成子群的充要条件是
- 若 $a,b\in S$，则 $ab^{-1}\in S$
- 群 $G$ 的非空 有限 子集 $S$ 构成子群的充要条件是
- 若 $a,b\in S$，则 $ab\in S$