资源描述
第一章命题逻辑
原式
P→Q
逆换式
Q→P
反换式
~P→~Q
逆反式
~Q→~P
第七章 图论
孤立结点
不与任何结点相邻接结点
零图
仅由孤立结点组成图
平凡图
仅由一个孤立结点组成图
邻接边
关联于同一结点两条边
自回路/环
关联于同一结点一条边
度数
与节点关联边数,成为结点度数
多重图
含有平行边任何一个图
简单图
由无向图衍生出,一个结点对有且仅有一条边。
完全图Kp
简单图G=<V,E>,每一对结点间都有边相连
Kn
有n个结点无向完全图
补图
给定一个图G,由G中全部结点和全部能使G成为完全图添加边组成图,称为G相对于完全图补图。
生成子图
若G子图包含G全部结点,该子图成为G生成子图。
相对补图
设G’=<V’,E’>是G=<V,E>子图,若给定另外一个图G’’=<V’’,E’’>使得E’’=E-E’,且V’’中仅包含E’’边所关联结点。则称G’’是子图G’相对于图G补图。
同构
设图G=<V,E>及图G’=<V’,E’>,假如存在一一对应映射g: vi→vi’且e=(vi,vj)(或<vi,vj>)是G一条边,当且仅当e’=(g(vi),g(vj))(或<g(vi),g(vj)>)是G’一条边,则称G与G’同构,记作G ~ G’
路
v0e1v1e2…envn称作联结vo到vn路
回路
路中,v0=vn时, 就称作回路
迹/简单路径
一条路中全部边e1,e2,…,en均不一样
通路/基础路径
一条路中全部结点v0,v1,…,vn均不相同
圈
闭通路;除v0=vn外,其它节点均不相同
连通
两节点之间存在一条路
连通图
图G中只有一个分支
点割集
设无向图G=<V,E>为连通图,若有点集V1⊂V,使图G删除了V1全部结点后,所得子集是不连通图,而删除了V1任意真子集后,所得到图仍是连通图,则称V1是G一个点割集。
割点
若某一个结点组成一个点割集,则称该结点为割点
边割集
设无向图G=<V,E>为连通图,若有边集E1⊂E,使图G删除了E1全部边后,所得子集是不连通图,而删除了E1任意真子集后,所得到图是不连通图,则称E1是G一个边割集。
边/桥
某一个组成一个边割集边
k(G)/(点)连通度
(平凡图)
min{|V1| | V1是G一个点割集}
λ(G)连通度
(非平凡图)
min{|E1| | E1是G边割集}
单侧连通
有向图:任何一对结点间,最少有一个结点到另一个结点是可达
强连通
有向图:任何一对结点,二者之间是相互可达
弱连通
有向图:看成无向图后图是连通
强分图
有向图:含有强连通性质最大子图
单侧分图
有向图:含有单侧连通性质最大子图
弱分图
含有弱连通性质最大分图
连接矩阵
书P288
adj
邻接
nadj
不邻接
可达性矩阵
书P291
完全关联矩阵
无向图:P294
欧拉图
给定孤立结点图G,若存在一条路,经过图中每边一次且仅一次。
欧拉回路
给定孤立结点图G, 若存在一条回路,经过图中每边一次且仅一次。
单向欧拉路(回路)
有向图G经过图中每边一次且仅一次一条单向路(回路)
汉密尔顿路
给定图G, 若存在一条路经过图中每个结点恰好一次
汉密尔顿回路
若存在一条回路, 经过图中每个结点恰好一次
汉密尔顿图
含有汉密尔顿回路图
W(G-S)
G-S中连通分支数
平面图
设G=<V,E>是一个无向图,假如能够把G全部结点和边画在平面上,且使得任何两条边除了端点外没有其她交点。
面
设G是一连通平面图,由图中边所包围区域,在区域内不包含图结点,也不包含图边,这么区域称为G一个面。
边界
包围一个面所组成回路称为这个面边界
无限面
不受约束面
面次数deg(r)
面边界回路长度
Vi⊕V j = Vi,j
有向图: Vi,j = Vi + V j
无向图: Vi,j = (Vi + V j) % 2
闭包
C(G)
给定图G=<V,E>有n个结点,若将图G中度数之和最少是n非邻接节点连接起来得图G’,对图G’反复上述步骤,直到不再有这么结点对存在为止, 所得到图, 称为是原图G闭包。
在2读节点内同构
给定两个图G1和G2,假如它们是同构,或者经过反复插入或除去度数为2结点后,使G1与G2同构,则称该两图是在2读结点内同构。
K3,3
2步图。上下顶点分别为3.
对偶图
书P318
树
一个连通且无回路无向图
森林每个连通分图
无回路且e=v-1
连通且e=v-1
无回路,但增加一条新边,得到一个且仅有一个回路
连通,但删去任一边后便不连通
每一对结点之间有一条且仅有一条路
树叶
度数为1结点
分至点/内点
度数大于1结点
森林
一个无回路无向图
生成树
若图G生成子图是一棵树,则称该树为G生成树
树枝
设图G有一棵生成树T,则T中边称作树枝
弦
图G不在生成树边
补
全部弦集合称为生成树T补
树权 C(T)
T全部边权和
最小生成树
在图G全部生成树中,树权最小那棵生成树
有向树
一个有向图在不考虑边方向时是一颗树
根树
一棵有向树, 假如恰有一个结点入度为0, 其它全部入度都为1
根
根树中入度为0结点
叶
根树中出度为0结点
分枝点/内点
出度不为0结点
m叉树
在根树中, 若每一个结点出度小于或等于m, 则称这棵树为m叉树
完全m叉树
假如每一个结点出度恰好等于m或0
正则m叉树
完全m叉树全部树叶层数相同
二叉树
这则m叉树当m=2时
通路长度
一个结点通路长度, 就是从树根到此结点通路中边数
内部通路长度
分枝点通路长度
外部通路长度
树叶通路长度
带权二叉树权
书P332
最优树
在全部带权二叉树中,w(T)最小那棵树
弟兄
T为带权w1≤w2≤…≤wt最优树,带权w1,w2树叶Vw1,Vw2是
前缀码
给定一个序列集合, 若没有一个序列是另一个序列前缀,该序列集合成为前缀码
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
