小猹的图论笔记

• 关联矩阵中的元素就是关联次数，纵向和必定是2，可以找到这条边关联的顶点。
  横向和是该点的度，对应各个关联边

  关联次数：是点和边之间的概念。有一个环，该点的关联次数就加2。
• 任何图中，奇点的个数一定是偶数（握手定理）
• 若无向图中恰有两个奇点，则这两个奇点必连通：每一个连通分支都是一个单独的图,而图的奇度顶点是偶数个,所以图G中的两个奇度顶点必在同一连通分支内,所以这两个奇度顶点必然连通
• 强连通图中的可达关系是等价关系
• 哈密顿通路一定是简单通路 ：简单通路是边不重，哈密顿通路是点不重，而点不重边必然不重
• 若有向图是欧拉图，则一定是强连通的
• 任何非平凡的无向树都是二部图
  • 无向树先找一个根结点（根顶点）,然后与根节点距离为偶数的结点归为一个点集合,与根节点距离为奇数的结点归为另外一个点集合,那么这两个点集合就构成了图中所有顶点集合的划分,而且无向树中所有的边两端的顶点分别属于这两个集合,所以无向树是一个二部图.
• 树没有回路，所以不是欧拉图或者哈密顿图
• 无向简单图的$\Delta$(G)$\leqq$n-1
• n阶完全图 K_n K₂很特殊，没有回路
• K_3,3，K₅不是平面图，K_n(n$\leqq 4$)和K_2,n(n$\geqq 2$)都是平面图, K_n(n$\geqq 5$)和K_s,t(s,t$\geqq 3$)都不是平面图
• 极大平面图：设G为简单平面图，若在G的任意两个不相邻的顶点之间加一条边，所的图为非平面图，则G为极大平面图
  • K₁,K₂,K₃,K₄,K_5-e都是极大平面图
  • 极大平面图一定是连通的，并且n$\ge$3时没有割点和桥
  • 设n$\ge$3的简单连通平面图，G为极大平面图当且仅当G的每个面的次数均为3
  • 设n$\ge$3的极大平面图G，m=3n-6 对于任意一个简单平面图，m（边数）的上界=3n-6
  • 设G为简单平面图，则G的$\delta$$\le$5
• 极小非平面图：若在非平面图G中任意删一条边，所得图为平面图，则G为极小平面图
  • K₅，K_3,3都是极小非平面图
• K₄不是欧拉图
• 同构的图具有相同的度序列，而 度序列相同的图未必同构
• 
  讯享网
• 悬挂点不在任何的点割集中
• 连通度：点连通度
• $\kappa(G) $$\leqq$$\lambda(G)$$\leqq$$\delta(G)$ 等号取到：K_n和N~n都满足 严格小于：在两个K_n之间放一个顶点，并且

连接每一个K_n的两个顶点 书本page305

• 强连通图与哈密顿图的关系

  • 强连通图：G中存在经过每个顶点至少一次的回路。
  • 所以强连通图（边多容易）很难是哈密顿图（边少容易），强连通图的回路大都要经过一个点很多次，
    哈密顿图不允许
  • 弱连通图：基图是连通图
  • 单向连通图：存在经过每个顶点至少一次

• 有割点的图一定不是哈密顿图。
• 
• n阶完全图是哈密顿图，不一定是欧拉图（偶数个点），（顶点个数为偶数点时， 哈密顿回路的条数是==(n-1)!/2==
  • 给一个完全图确定方向，得到的有向图是欧拉图的方法：为了保证出度=入度，先画出来一条欧拉通路再标
  • K_s,t不一定是欧拉图，当s,t都是偶数的时候才是欧拉图，当|V₁=V₂|时，是哈密顿图，当|V₂|=|V₁|+1时，是半哈密顿图
• n(n$\ge$2)阶零图为二部图
• n(n$\ge$2)阶竞赛图必定有哈密顿通路
• 二部图首先是无向图 二部图$\leftrightarrow$ 无奇圈
• 若两个不邻点u，v的度和>=n ，且G∪（u，v）是哈密顿图，那么G图一定也是哈密顿图（充要）
• K₅ K_3,3 是所有非平面图的基准（最小单位）
• 无回路的连通图是树
• K_s,t的边数 s*t
• 设T是连通无向图G的一颗生成树，则T的余树不含有G的任何边割集

  哈密顿图专项

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lqwCgXX8-47)(https://i.loli.net/2020/12/29/ofvLWD8h3PJmpBy.jpg)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iUfrxMUb-53)(https://wkretype.bdimg.com/retype/zoom/77eef822ccbff121dd36834b?pn=7&o=jpg_6&md5sum=96fb370a1b34feaa51b0fdc4ccd54976&sign=50ef25d342&png=-&jpg=-)]

哈密顿有向图中有一条包含所有顶点的圈，因此哈密尔顿有向图一定是强连通的

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5ZMCr8iv-57)(https://i.loli.net/2020/12/29/FnUifZrRQm79jqw.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ro5P9pLI-62)(https://i.loli.net/2020/12/29/ctuY6e7MFAQmvgn.png)]

小猹的数理逻辑笔记

一阶逻辑等值演算

量词辖域扩张收缩

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XiQvprsG-65)(https://powerpoint.officeapps.live.com/pods/GetClipboardImage.ashx?Id=e82dccec-93c7-4580-bd71-f652d24bcd92&DC=PUS1&wdoverrides=GetClipboardImageEnabled:true)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wBfIVjPg-68)(https://powerpoint.officeapps.live.com/pods/GetClipboardImage.ashx?Id=4e62fd0b-3e18-46e2-8ea0-c96&DC=PUS1&wdoverrides=GetClipboardImageEnabled:true)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TQdtIJZr-70)(https://powerpoint.officeapps.live.com/pods/GetClipboardImage.ashx?Id=923ec53e-c222-4c43-bcb6-a96db39a734a&DC=PUS1&wdoverrides=GetClipboardImageEnabled:true)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-W03gsyn4-74)(https://powerpoint.officeapps.live.com/pods/GetClipboardImage.ashx?Id=22f3982d-d60c-48ce-83f6-8589d5931ee7&DC=PUS1&wdoverrides=GetClipboardImageEnabled:true)]

前束范式

1. 否定词的消去和内移
2. 利用换名规则和代替规则使得每个量词所约束的变元彼此不同，并且使得不含有既是约束又是自由的个体变项
3. 辖域扩张

推理理论要用到的等式

• 命题逻辑中等值式的代换实例。
• 量词消去等值式
• 量词否定等值式
• 量词辖域收缩与扩张等值式
• 量词分配等值式
• 其它等值式

  其他等值式

  1. $\forall$x$\forall$yQ(x,y)$\iff$$\forall$y$\forall$xQ(x,y)
  2. $\exists$x$\exists$yQ(x,y)$\iff$$\exists$y$\exists$xQ(x,y)

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CBpLlqGf-76)(https://i.loli.net/2020/12/28/R5LZQkqBoAg4IhT.png)]

  四条重要的推理规则（只可以对前束范式使用

  全称量词消去规则

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-P0gN6slt-78)(https://i.loli.net/2020/12/28/7Cw152DmP4yMAOb.png)]

  全称量词引入规则

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MyyBKTzo-80)(https://i.loli.net/2020/12/28/nbUCf8Xmr1plV3u.png)]

  存在量词引入规则

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PtwmpMXh-83)(https://i.loli.net/2020/12/28/GLMKvP67X3IBEpR.png)]

  存在量词消去规则

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6h4Yi4Db-85)(https://i.loli.net/2020/12/28/US2T4LR9qVHcGQI.png)]

小猹的有趣习题

集合、关系

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-U9E36AZF-87)(https://i.loli.net/2020/12/28/qjQzlPyDdFw4kR1.png)] [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Zoje2O3t-89)(https://i.loli.net/2020/12/28/39rDVZHIhQYzibf.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ADSLhJan-92)(https://i.loli.net/2020/12/29/1Mo52FCmI68g7Uy.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zMxflnO5-94)(https://i.loli.net/2020/12/28/VGF9zK4iynd1COo.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Z87RuuFe-97)(https://i.loli.net/2020/12/28/hNMnaHeSzE1qGr5.png)]

数理逻辑部分

1. 相容或:它联结的两个命题可以同时为真

   排斥或:只有当一个为真，另一个为假时，才为真

   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WlqCq2IS-99)(https://i.loli.net/2020/12/28/WUEZPlyrF67Ndf8.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wJHamy6b-02)(https://i.loli.net/2020/12/28/fUuyOFkYCE6wN9d.png)]

• [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yDBzok9N-05)(https://i.loli.net/2020/12/28/3AbyKmD9EXi7ZQL.png)]
• 
• 任意对析取无分配律 存在对合取无分配律
• C项 $\forall$xA(x)$\to$$\forall$xB(x) 前件为假

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-93jVSe5g-07)(https://i.loli.net/2020/12/28/ORBTntCYFULHAe5.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wiCcFoOk-08)(https://i.loli.net/2020/12/28/mgqjEGsthOdQyl1.png)]

图论部分

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GMbWDrmq-10)(https://i.loli.net/2020/12/28/2Lz7owb4VlICfuQ.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-781w0lQA-12)(https://i.loli.net/2020/12/28/Kn3QxbPqGYMwSua.png)]

小猹的重要课本习题

• 习题五 一阶逻辑等值演算

  5，8，12（1，3，5），13（1，2）

  作业：习题五

[外链图片转存中…(img-wiCcFoOk-08)]

图论部分

[外链图片转存中…(img-GMbWDrmq-10)]

[外链图片转存中…(img-781w0lQA-12)]

小猹的重要课本习题

• 习题五 一阶逻辑等值演算

  5，8，12（1，3，5），13（1，2）

  作业：习题五

  15(2,4), 24