第一章 命题逻辑的基本概念

1.1 命题与连接词

• 非真即假的陈述句称作命题

• 作为命题，是否知道它的真值并不重要，重要的是它有唯一的真值。如2050年的元旦下大雪

• 用小写英文(p,q,r,s…至少从p开始往后数)表示命题

• 否定式“非p”﹁p是复合命题；∧合取 ∨析取

• 相容或和排斥或

  • 相容或，即它联结的两个命题可以同时为真。如小明爱打球或跑步这两个命题可以同时为真，相容或
  • 排斥或，只有当一个为真，另一个为假时，才为真。但是这个形式化有两种情况。
    • ①”只能“，小芳只能挑选跳舞课或羽毛球课 这里p:小芳挑选跳舞课 q:小芳挑选羽毛球课,结果并不能单纯用p∨q表示，因为当p，q同真时结果也是真，即小芳既选了跳舞可，又选了羽毛球课，不满足”只能“。此复合命题为真应该时当且仅当p、q其中一个为真，另一个为假时才成立。（这里我们容易联想到”异或“关系）如何用形式化表达呢？不如我们表示得详细一点：小芳挑选跳舞课但不挑选羽毛球课或小芳挑选羽毛球课但不挑选跳舞课。于是用符号化表示：**(p∧﹁q)∨(﹁p∧q)**
    • ②不能同时为真的。小芳是江西人或安徽人 这里既可以用**(p∧﹁q)∨(﹁p∧q)** 表示，又可以用p∧q表示，因为小芳不可能既是江西人又是安徽人，即p、q不能同时成立。

• p→q称为p蕴涵q;规定p→q为假当且仅当p为真q为假。当p为假时无论q真假p→q都是真。

  p q	p→q
  0 0	1
  0 1	1
  1 0	0
  1 1	1

• 除非和否则。除非小王穿毛衣，否则天不冷 将”否“和”则“断开，否掉除非后的命题，改成如果小王不穿毛衣，则天不冷 这样就好判断蕴涵关系了。

  只有天冷，小王才穿毛衣 是q→p，只有……才……后面推前面。小王穿了毛衣说明天冷了。

• (p→q)∧(q→p)与p↔q的逻辑关系完全一样，都表示p与q互为充分必要条件。

• 优先顺序：”( )” > “﹁” > “∧” = “→” = “↔”

• 命题的中文说法与符号化

  • ﹁p “非p”
  • p∧q “p并且q”
  • p∨q “p或q”
  • p→q “如果p，则q”
  • p↔q ”p当且仅当q“

1.2 命题公式及其赋值

• 真值可以变化的陈述句叫命题变项，命题变项不是命题。命题变项用符号联结起来的符号称为合式公式，简称公式。命题用符号联结起来就是复合命题。区分：如果题目只有符号p之类的，就是命题变项；如果是p:简单命题那就是命题常项
• 公式的层数。单个命题变项算0层，﹁算1层，其他的就是max(i,j)
• 解释或赋值：用命题常项代替公式中的命题变项然后各指定一个真值0或1（不关心命题内容，只关心真假）
• 三种命题公式（设A为任一命题公式）
  • 重言式，A在它各种赋值下取值均为真，全为成真赋值。
  • 矛盾式，A在它各种赋值中取值均为假，全为成假赋值。
  • 非重言式的可满足式,A既有成真赋值又有成假赋值。（可满足式：不是矛盾时就是可满足式，至少有一个成真赋值。）

第二章 命题逻辑等值演算

2.1等值式

• 等值：在所有扶植下，A和B的真值都相同，则称A与B是等值的，记作

• 等值式模式

  

比较重要的等值式模式：1双重否定律、6德摩根律、8零律、9同一律、10排中律、11矛盾律

等值演算法做题顺序：

​ 1.消→，↔ （蕴涵等值式、等价等值式）

​ 2.消﹁( ) （德摩根律）

​ 3.消双重否定（双重否定律）

2.2 析取范式与合取范式

• 命题变项及其否定统称作文字。仅由有限个文字构成的析取式（合取式）称作简单析取式（简单合取式）。

  • 注意：p,﹁p,q,﹁q就即是简单析取式又是简单合取式。（单个文字析取0或者合取1，也是本身）

• 由有限个简单合取式的析取构成的命题公式称作析取范式，由有限个简单析取式做合取构成的命题公式称作**合取范式,**统称为范式。

  • 注意有些命题公式名字不唯一：p∧q∧r 即是由三个简单析取式做合取构成的合取范式，又是由一个简单合取式构成的析取范式（理解成 (p∧q∧r)∨1) )。
  • 析取范式容易求成真赋值，合取范式容易求成假赋值

• （范式存在定理）任一命题公式都存在与之等值的析取范式与合取范式。这就意味着我们可将所有的命题公式运用等值演算法转化为析取范式或合取范式的形式，方便求得赋值。

• 在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式恰好出现一个且仅出现一次[全部齐全]，而且命题变项或它的否定式按照下标从小到大或按照字典序排列，称这样的简单合取式（简单析取式）为极小项（极大项）

  • 简单合取出极小项，简单析取出极大项。
  • 由于命题变项还有否定形式，所以n个命题变项可以组成2^n个不同的极小项（极大项同理2ⁿ个）。每个极小项都有且仅有一个成真赋值，每个极大项也只有一个成假赋值，且不同的极小项（极大项）有不同的成真（成假）赋值。说明一个极小项可以提供一个成真赋值，一个极大项可以提供一个成假赋值。
  • 讲极小项的成真赋值对应的二进制数等于十进制i，将这个极小项记作m_i.例如p∨q∨r这个极小项成真赋值为111，对应十进制7，那么这个极小项记作m₇;极大项同理，记作M_i。
  • ﹁m_i⇔M_i , ﹁M_i⇔m_i

• 主析取范式（主合取范式）：全部由极小项（极大项）构成的析取范式（合取范式）。

  • 主析取范式是简单合取式的极小项做析取，直接看出所有成真赋值；主合取范式是简单析取式的极大项做合取，直接看出所有成假赋值。

  • 任何命题公式都存在与之等值的主析取范式和主合取范式，并且是唯一的。我将其称之为主范式存在定理，这条定理为我们转化范式提供依据。

  • 简单合取式转化为极小项的步骤，如：

    少了一个命题变项的

    p∧q⇔(p∧q)∧1 (同一律)

    ⇔(p∧q)∧(r∨﹁r) (排中律，置换规则)

    ⇔(p∧q∧r)∨(p∧q∧﹁r) (分配律)

    ⇔m₇∨m₆

    这样就变成了两个极小项做析取。

    少了两个命题变项的

    p⇔p∧1 (同一律)

    ⇔p∧(q∨﹁q) (排中律，置换规则)

    ⇔(p∧q)∨(p∧﹁q) (分配律)

    ⇔((p∧q)∨(p∧﹁q))∨1 (同一律)

    ⇔((p∧q)∨(p∧﹁q))∧(r∨﹁r) (排中律，置换规则)

    ⇔(p∧q∧r)∨(p∧﹁q∧r)∨(p∧q∧﹁r)∨(p∧﹁q∧﹁r) (分配律)

  • 简单析取式转化为极大项的步骤，如：

    少了一个命题变项的：

    p∨q⇔(p∨q)∨0 (同一律)

    ⇔(p∨q)∨(r∧﹁r) (矛盾律)//这一步和简单合取式变极小项不一样，前后的步骤基本一致,结果符号调换

    ……

    ⇔(p∨q∨r)∧(p∨q∨﹁r) (分配律)

    少两个命题变项的

    p⇔p∨0

    ……

    ⇔(p∨q∨r)∧(p∨﹁q∨r)∧(p∨q∨﹁r)∧(p∨﹁q∨﹁r) (分配律)

  • **总结简单合（析）取式转化为极大（小）项基本步骤**：

    • 缺少哪个变项就添加同时添加那个变项的原形和否定式，缺少多个就做排列组合

      如p∧q最后变成(p∧q∧r)∨(p∧q∧﹁r) ，p变成(p∧q∧r)∨(p∧﹁q∧r)∨(p∧q∧﹁r)∨(p∧﹁q∧﹁r)，原本是合取式加上后各部分做析取，原本析取的加上后各部分做合取

    • 出现重复的命题变项或极小项或矛盾式应消去，如，p∧p⇔p，m_i∨m_i⇔m_i，用0代替矛盾式

  • A是一个有3个命题变项的公式，假设主析取范式为 m₂∨m₅∨m₇，说明它的成假赋值有三个，010,101,111，那么剩下的2³-3=5个就是它的成真赋值了，则它的主合取范式为M₀∧M₁∧M₃∧M₄∧M₆，相当于把真值表分为成真和成假，成真赋值压缩到主合取范式，成假赋值压缩到主析取范式，一眼就可以看出来。

第三章 命题逻辑的推理理论

3.2 自然推理系统

常用的推理定理：

• 假言推理 (A→B)∧A⇒B
• 拒取式 (A→B)∧﹁B⇒﹁A
• 析取三段式 (A∨B)∧﹁B⇒A
• 假言三段式 (A→B)∧(B→C)⇒(A→C)

前提：

结论：

推理证明的两个技巧：

• 附加前提证明法。如结论是A→B，就可以把A作附加前提引入推出B。
• 归谬法，将结论的否定式作为附加前提引入并推出矛盾式。如结论是﹁q，就把q作结论的否定引入最终推出矛盾式。

第六章 集合代数

6.1 集合的基本概念

子集 ⊆

空集 ∅

空集的符号化表示为：∅={x|x≠x}

n元集

含有n个元素的集合简称n元集，它的含有m(m≤n)个元素的子集称作它的m元子集

对于A={1,2,3},0元子集：∅；1元子集：{1},{2},{3}；2元子集：{1,2},{2,3},{1,3}；3元子集：{1,2,3}

幂集 P(A)

定义：把集合A的全体子集（包括空集）构成的集合称为A的幂集

其中，P(∅)={∅}（空集是任何集合的子集），P({∅})={∅,{∅} }（想不通就把{∅}换成一个具体的数如{1}

例：A={1,2,3}

​ P(A)={∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,3},{1,2,3} }；

​ P(A)中有2ⁿ个元素，表示成|P(A)|=2ⁿ

例题：设A={ {∅},{ {∅} } },计算 P(A)

​ ✔正确答案：P(A)={∅,{ {∅} },{ { {∅} } },{ {∅},{ {∅} } } }

​ ❌易错答案：P(A)={∅,{∅},{ {∅} },{ {∅},{ {∅} } } }

​ 自己是个集合，因此A中元素外边还要加一层{}

6.2 集合的运算

并集 ∪

交集 ∩

相对补集 B-A

B-A={x|x∈B∧x∉A}

对称差集 ⊕

A⊕B=(A—B)∪(B—A)

或者A⊕B=(A∪B)-(A∩B)

绝对补集 ~

给定了全集A，~A=E-A={x|x∈E∧x∉A}

广义并∪ 广义交∩

广义运算可以转化为初级运算：

实例：

注意：

∪{ {a} }={a},∩{ {a} }={a}

集合的运算规则

一类运算：广义运算、幂集和~运算，

​ 运算由右向左进行

二类运算：初级运算∪、∩、—、⊕

​ 优先顺序由括号确定

混合运算：一类运算优先于二类运算

6.3有穷集的计数（21年不考）

文氏图/韦恩图

包容排斥原理

|A₁∪A₂|=|A₁|+|A₂|-|A₁∩A₂|

下面这一条不用记，等于|S|-|A₁∪A₂∪…∪A_n|，将上面公式代入即可

6.4 集合的恒等式

P101

第七章 二元关系

7.1 有序对和笛卡尔积

有序对 <x,y>

<x,y>

笛卡尔积 AXB

定义：A,B为集合，用A中元素为第一元素，B中元素为第二元素构成的所有有序对组成的集合称为A和B的笛卡尔积

AXB={<x,y>|x∈A∧y∈B}

特别强调：

(4)空集中取不出元素

A=B且C=D的必要条件是AXC=BXD，后不能推前。例如A={1},B={2},C=∅,D=∅

7.2 二元关系

二元关系

定义：一个集合满足①集合非空，且它的元素都是有序对 或者②集合是空集

二元关系都可看作是某个笛卡尔集的子集

定义2

A,B是集合，AXB的任何子集所定义的二元关系称作从A到B的二元关系(表示顺序)，特别当A=B是称作A上的二元关系

对于任一集合A定义

空关系 ∅

对于任何集合A，空集∅是AXA的子集，称作A上的空关系

全域关系E_A

E_A={<x,y>|x∈A∧y∈A}=AXA

恒等关系I_A

I_A={<x,x>|x∈A}

单位阵（第一元素作行，第二元素作列）

小于等于关系L_A

L_A={<x,y>|x,y∈A,x≤y}

上三角矩阵

整除关系D_A

D_A={<x,y>|x,y∈A,x|y}

x|y,即x是y的因子

包含关系R_⊆

R_⊆={<x,y>|x,y∈A,x⊆y}

例如：A={∅,{a},{a,b} }

R_⊆={<∅,∅>,<∅,{a}>,<∅, {a,b} >,<{a},{a}>,<{a},{a,b}>,<{a,b},{a,b}>}

关系矩阵

关系矩阵行表示第一元素，列表示第二元素，若x_iRx_j则是1，否则是0

关系图

<x_i,x_j>，从x_i到x_j的有向边

7.3关系的运算

定义域 domR

第一元素的集合

值域 ranR

第二元素的集合

域 fldR

定义域和值域的并集，即第一元素和第二元素的集合

逆关系 R^-1

R^-1={<x,y>|<y,x>∈R}

合成运算

看作矩阵的乘法

限制

取第一元素在A中的有序对。

xRy: 如果<x,y>∈R，记作xRy

像

取限制的值域（第二元素的集合）

定理

合成满足结合律；第二条看作矩阵的逆

I_A看作单位阵

定理 7.4

合成运算与并满足分配律，但是和交运算不满足分配律，用包含于连接

定理 7.5

限制与交、并满足分配律；像与并满足分配律，与交不满足分配律

n次幂Rⁿ的定义

定义

设R为A上的关系，n为自然数，则R的n次幂Rⁿ定义为

1）R⁰={<x,x>|x∈A}=I_A}

2）Rⁿ⁺¹=Rⁿ∘R

注意：由定义1)我们可知∅⁰结果也是I_A

关系矩阵

有：

1）M_R1∘R2=M_R1M_R2

2）M_Rⁿ=M_Rⁿ

注意：这里M带角标R表示的是R的关系矩阵

Rⁿ重复性定理

定理：

设A为n元集，R是A上的关系，则存在自然数s和t，使得R^s=R^t

理解 因为R是A上的关系，对于任何自然数k，R^k都是AXA的子集（二元关系都可以看作是某个笛卡尔积的子集）.又|AXA|=n²（A是n元集），所以其子集总数为2ⁿ²个。因此可知，R^k的取值情况是有限的，最多也就2ⁿ²个不同的值，然而R的幂是无穷多的，因此必有重复的

Rⁿ关系图的规律

由定义可知R²=R∘R,这里假设等号右边取<a,b>,<b,c>,结果是<a,c>。此时在R和R²的关系图中我们可以看到R这边从第一个元素a走到b走了一步，b到c又走了一步一共走了两步对应到了R²中的a→c。而R上所有第一元素能走三步到另外一个元素的情况就构成了**R³**的关系图。

7.4 关系的性质

自反与反自反

例题：

这里注意R₂既不是自反，也不是反自反。因为定义中要求是对于任意的x而当x取1、2的时候在R₂中都有对应的<x,x>。两个条件都不满足，故既不是自反，也不是反自反。

一个关系不可以既是自反又是反自反。

对称与反对称

例题：

这里R₃是反对称因为前件为假，蕴含式结果为真而空集即是对称也是反对称也是前件为假的原因。

对称也就是说如果我R里面的有序对的元素是A的元素那么这些有序对的一二元素交换也得是我R里的元素

判断反对称只需要找x≠y的关系，如果有<x,y>那么<y,x>必不能在，对于所有的都满足那么就有是反对称的

传递

也就是说若R中有能合成的有序对，那么其结果也在R内。

关系性质的充分必要条件

设R为A上的关系，则

五种性质：自反性、反自反性、对称性、反对称性、传递性

注意：

• 自反性是对于任意的x而言的，也就是说所有的<x,x>都应该在R里！反自反同理，即不能够出现<x,x>！
• 一个关系不能既是自反的又是反自反的
• 一个关系可以既是对称的也是反对称的

例: A={1,2,3},R是A上的关系，R1={<1,1>,<2,2>}，R2={<1,1>,<2,2>,<3,3>,<1,2>}，R3={<1,3>}

答：R1具有对称性、反对称性，既不是自反也不是反自反；R2具有自反性；R3是反自反的。

用关系矩阵记忆：自反性则主对角线全是1，反自反性则主对角线上全是0，对称性矩阵是对称矩阵，反对称性若r_ij为1则r_ij为0，传递性，M²中1所在的位置对应M上也是1.

7.5 关系的闭包

闭包就是最少的添加

闭包的关系图

设关系R, r(R), s(R), t(R)的关系图分别记为 G ，G_r ， G_s ，G_t ,，则 G_r ，G_s ，G_t 的顶点集与 G 的顶点集相等. 除了 G 的边以外, 以下述方法添加新的边：

(1) 考察G 的每个顶点, 若没环就加一个环，得到 G_r

(2) 考察 G 的每条边, 若有一条x_i 到 x_j 的单向边, i≠j, 则在 G 中加一条x_j 到 x_i 的反向边, 得到 G_s

(3) 考察 G 的每个顶点 x_i , 找 x_i 可达的所有顶点 x_j (允许i=j )， 如果没有从 x_i 到 x_j 的边, 就加上这条边, 得到图 G_t

tsr(R)=t(s(r(R)))，表示R的自反、对称、传递闭包，从里到外。

7.6 等价关系与划分

等价关系

设R为非空集合A上的关系。如果R是自反的、对称的和传递的，则称R为A上的等价关系。（对角线全为1，且是对称矩阵，M²的1对应M也是1）

等价类

x的等价类 [x]_R={y|y∈A∧xRy}

通俗来说就是R中哪些第一元素是x就把第二元素拿出来

商集

设R为非空集合A上的等价关系，以R的所有等价类作为元素（不同块的集合）的集合成为A关于R的商集，记作A/R，即 A/R={[x]_R|x∈A}

例如：

其中的等价类有：[1]=[4]=[7]={1,4,7}，[2]=[5]=[8]={2,5,8}，[2]=[6]={3，6}

商集为：{ {1,4,7}，{2,5,8}，{3,6} }

划分

满足条件：

1. 是A子集的构成的集合
2. 空集不存在里面
3. 子集的交集是空集
4. 这个子集族π(A的子集构成的集合，π⊆P(A))的并集就是A

则称π是A的一个划分，称π中的元素为A的划分块。

例：A={a,b,c,d}，给定π₁={ {a}，{a,b,c,d} }，π₂={∅，{a,b}，{c,d} }，π₃={ {a,b}，{c}，{d} }，则*π₁和π₂都不是A的划分，π₃*是A的划分（可以不止一个划分）。

在等价关系中，划分就是商集，划分块就是等价类。

7.7 偏序关系

小于等于

设R为非空集合A上的关系。如果R是自反的、反对称的和传递的，则称R为A上的偏序关系，记为≼。设≼为偏序关系，如果<x,y>∈≼，则记作x≼y，读作x”小于等于“y。

注意：这里的”小于等于“（也可理解为大于等于）不是指数的大小，而是指在偏序关系中的顺序性。依照不同定义的序，x排在y的前边或者x就是y。

三种符号：

• xRy：<x,y>∈R
• x~y：<x,y>∈R且R是等价关系
• x≼y：<x,y>∈R且R是偏序关系

例如，恒等关系I_A，小于等于关系L_A、整除关系D_A和包含关系R_⊆都是相应集合上的偏序关系。一般全域关系E_A不是A上的偏序关系

定义：

• 若x≼y ∧ x ≠ y , 则记作x≺y,读作x小于y。 （x≺y说明<x,y>∈R∧x≠y）
• x与y可比有三种情况：x=y，x≺y，y≺x

例如，A={1,2,3}，≼是A上的整除关系，则有1≺2，1≺3；1=1，2=2，3=3；2和3不可比（不满足整除）

全序关系

设R为非空集合A上的偏序关系，如果∀x,y∈A，x与y都是可比的，则称R为A上的全序关系

偏序集

集合A和A上的偏序关系一起叫做偏序集≼，记作<A,≼>。

覆盖

x≺y且 x，y 之间没别的元素，则称 y 覆盖 x。

哈斯图

只连覆盖关系，y覆盖x则把y画在x上方

例：偏序集<{1,2,3,4,5,6,7,8,9}，整除关系>和<P({a,b,c},R_⊆)的哈斯图

最小元、最大元、极小元、极大元

<A,≼>为偏序集，B⊆A，y∈B

• 最小(大)元：y小于(大于)等于B中的任何一个元素
• 极小(大)元：B中没有其他元素小于(大于)我

例：A={1,2,…,36}上的整除关系，B={2,3,4,12}

最小元：无（不会是2，因为2没办法整除3，不满足y小于等于B中的任何一个元素）

最大元：12（12可以大于等于2,3,4）

极小元：2，3（没有再可以整除2和3的了，有两个）

极大元：12（没有12能整除的数了）

上界、下界

<A,≼>为偏序集，B⊆A，y∈A（y不同于上面的定义，这个范围更大）

• 上界和下界定义和最大元和最小元相同，不同的是y的范围。

• C={y|y为B的上界}，则称C的最小元为B的最小上界或上确界。（上界中的最小）

• D={y|y为B的下界}，则称D的最大元为B的最大下界或下确界。（下界中的最大）

注意：

1. B的上界、下界、最小上界、最大下界都可能不存在
2. 如果存在，最小上界与最大下界是唯一的，而上下界不一定唯一
3. 集合中如果存在最小元，那么这个最小元就是其最大下确界；最大元是上确界
4. 画出哈斯图一般会有利于判断

例：A={1,2,…,36}整除关系，B={6,12,18}，C={4,6,12}

B的最小元是6，下界是1,2,3,6。下确界即为最小元6

B的最大元没有，上界是36，上确界为36

C的最小元没有，下界是1,2，下确界为2

C的最大元为12，上界为12,24,36，上确界为最大元12

第十四章 图的基本概念

14.1 图

无序积：{ {a,b}|a∈A∧b∈B}，记作A&B

无序积中的无序对记作(a,b)

二元组

一个无向图G是一个有序的二元组<V,E>，其中

• V是一个非空有穷集，称作顶点集，其元素称作顶点或结点
• E是一个无序积V&V的有穷多重子集(可重复)，称为边集，其元素称作无向边，简称为边

而有向图的二元组中的E的元素为有向边

图

• 图，有向图和无向图的统称
• 阶，顶点数称作图的阶，n个顶点的图称作n阶图
• 零图，一条边也没有的图；平凡图，1阶零图称作平凡图，只有一个顶点，没有边
• 定义中V要是非空的，但是运算中可能会出现顶点集为空集的情况，规定顶点集为空集的图为空图，记作∅
• 如果给每一个顶点和每一条边指定一个符号，称这样的图为标定图，否则非标定图

相邻

对于无向图，若两个顶点 v_i 与 v_j 之间有一条边连接，则称这两个顶点相邻。若两条边至少有一个公共端点，则称这两条边相邻

对于有向图，顶点之间有一条有向边则相邻，两条边一条的终点是另一条的起点，则两条边相邻

没有边关联的顶点称作孤立点

• 无向图G=<V,E>中，
  • 邻域是所有与我相邻的点，不包括我自己
  • 闭领域是邻域并上子集
  • 关联集是所有与我关联的无向边(环那条也算)
• 有向图D=<V,E>中，
  • 有向图的先驱元集和后继元集的定义中<u,v>,u不等于v，即不能是自己(环的情况)
  • 邻域是先驱元集和后继元集的并
  • 闭邻域即邻域加上自己

平行边

无向图中，关联一对顶点的两条或以上的边为平行边

有向图中，关联一对顶点的有向边多于1条，称为平行边

简单图

含平行边的图称作多重图(存在相同的无序对)

既不含平行边也不含环的图称作简单图

度数

无向图中，v作为边的端点的次数称为度数，记为d(v)

有向图中，v作为边的始点的次数为v的出度，记为d⁺(v)；作为边的终点的次数为v的入度，记为d^-(v)

度数列

就是把各个顶点的度数列出来d(v1)= ,d(v2)=,…

最大度Δ(G)

最小度(G)

握手定理

在任何无向图中，所有顶点的度数之和等于边数的2倍

可图化

• 给定的非负整数列d=(d1,d2,..,dn)，若存在以V={v1,v2,…,vn}为顶点集的n阶无向图G，使得d(vi)=di，则称d是可图化的（即每个顶点度数要够）
• 可简单图化：若得到的图是简单图，则d是可简单图化的

判断方法：非负整数列d=(d1,d2,..,dn)是可图化的当且仅当奇数度顶点个数为偶数

例：(3,3,2,1)和(3,2,2,1,1)奇数度顶点个数为3，不是偶数，不是可图画的。而(3,3,2,2)和(3,2,2,2,1)画一下图发现满足，是可图化的

完全图

• n阶完全图，G中每个顶点均与其余的n-1个顶点相邻称为n阶无向完全图，简称n阶完全图
• n阶有向完全图，有向图D中每个顶点都邻接到其余的n-1个顶点
• n阶竞赛图，基图为K_n的有向简单图

14.2 通路与回路

G为无项标定图，，G中顶点与边交替的序列Г=v_i0e_j1v_i1e_j2…e_jlv_il称为从起点v_i0到终点v_il的通路，Г中边的条数称为它的长度。

回路

若起点和终点相同，则称Г为回路。

简单通路、简单回路

若Г所有边各异，则称Г为简单通路；若简单回路的起点和终点相同，则称为简单回路。

初级通路、初级回路（圈）

若所有顶点各异（除起点和终点可能相同外），所有边也各异，则称Г为初级通路；若又有起点和终点相同，则称为初级回路或圈

注意

• 初级包含于简单，简单回路包含于简单通路，但是初级回路和初级通路在应用中完全分开。
• 长为1的圈（初级回路）只能由环生成，长为2的圈只能由平行边生成；而在简单无向图中，圈的长度至少为3，因为简单无向图中没有环和平行边。

14.3 图的连通性

距离d(u,v)

无向图G中u,v之间长度最短的通路为u,v之间的短程线，短程线的长度成为u,v之间的距离，记作d(u,v)。

点割集、边割集

全部拿掉后，连通分支数增加、只拿掉其中一部分不影响。

割点、桥

点割集{v}，则v是割点，同理的边成为桥（割边）。

无向连通图不一定有点割集（如K_n），但一定有边割集（只要去掉足够多的边，一定会有点连不上）

点连通度k(G)、边连通度λ(G)

想把我从连通图变为非连通图，则至少删去k个顶点/边

短程线、距离d<vi,vj>

短程线，最短的通路；短程线的长度称为距离

连通图、单向连通图、强连通图

定义

若有向图D的基图是连通图，则称D为弱连通图，简称为连通图。（一眼看上去是一个整体）

若∀v_i,v_j∈V,v_i→v_j与v_j→v_i至少成立其一，则称D为单向连通图。

若∀v_i,v_j∈V,均有v_i↔v_j，则称D为强连通图。（任意两点相互可达）

连通图⇒单向连通图⇒强连通图，条件要求越来越高

判别定理

定理 14.8 有向图D=<V,E>是强连通图当且仅当D中存在经过每个顶点至少一次的回路。

定理 14.9 有向图D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路。（只需证v_i可达v_j或v_j可达v_i）

二部图

将无向图划分成两部分V1和V2，使得每条边的两个端点都是一个属于V1，一个属于V2，则称无向图G为二部图。（环一定不是）

若G是简单二部图且V1中的每个顶点与V2中所有顶点相邻（有一条边相连），则称G为完全二部图，记为K_r,s,其中r=|V1|,s=|V2|。

注意：n(n≥2)阶零图为二部图

将图按如下方式尝试分成两部分，判断(a)为二部图

（e)为完全二部图，上面r个点，下面s个点，共有rxs条边，点连通度为min{r,s}，即拿掉少的部分的所有点；边连通度也为min{r,s}，即拿掉一个点的所有边。

14.4 图的矩阵表示

关联矩阵M(G)

关联矩阵表示的是顶点和边的关系，行是各点，列是各边，记录关联次数（注意无向图中环的点边关联次数为2）

有向图中无环的关联矩阵中，用1表示这个点是这条边的始点，0表示不关联，-1表示这个点是这条边的终点

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

有向图，表示从顶点vi邻接到顶点vj有多少条边，行和列都是点。

vi指向vj才加1，环自身加1

邻接矩阵A和A^l反应的几个信息：

• a_ij^(l)为D中v_i到v_j长度为 l 的通路数
• 对角线上的a_ii^(l)表示到自身长度为 l的回路数
• 矩阵所有元素之和表示D中长度为 l 的通路（含回路）总数
• 其中对角线元素之和表示长度为 l 的回路总数

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

首先首先，对角线先全标上1，自己可达自己

vi可达vj则标上1，否则为0

注意：什么叫可达？不是说一步走到是可达，而是存在通路即可，走多少步没关系，只要能走到就是可达！

D为强连通当且仅当P(D)为全1矩阵

第十五章 欧拉图与哈密顿图

15.1 欧拉图

欧拉通路

通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的通路称作欧拉通路。

欧拉回路

通过图中所有边一次且仅一次行遍所有顶点的回路称作欧拉回路。

欧拉图

具有欧拉回路的图称作欧拉图。

半欧拉图

具有欧拉通路而无欧拉回路的图称作半欧拉图。

注意1

• 规定平凡图是欧拉图。(平凡图是只有一个孤立点组成的图)
• 欧拉通(回)路是简单通(回)路，但不一定是初级通(回)路。因为欧拉可以走环，而走了环就不满足所有点各异的条件，也就不是初级。

无向欧拉图的判别方法

定理15.1 无向图G是欧拉图当且仅当G是连通图且没有奇度顶点。

​ 即顶点的度数为偶数。理解：因为经过一个点需要走进来再走出去，而度数是由边提供的，故顶点度数为偶数。

定理 15.2 无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度顶点。

有向欧拉图的判别方法

定理 15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度等于出度（度数为偶）。

​ 一个图要是欧拉图它得首先是个强连通图。

定理 15.4 有向图D是半欧拉图当且仅当D是单向连通的且恰有两个奇度顶点，其中一个顶点的入读比出度大1，另一个顶点的出度比入度大1，而其余顶点的入度等于出度。

​ 一个图是半欧拉图它得首先是个单向连通图

定理15.5

G是非平凡的欧拉图当且仅当G是连通的且是若干个边不重的圈（无向）的并。

很好理解，如果是若干个边不重的圈的并，那么每个点度数都为偶

15.2 哈密顿图

• 经过图（有向图或无向图）中所有顶点一次且仅一次的初级通路称为哈密顿通路。

• 经过图中所有顶点一次且仅一次的初级回路称为哈密顿回路。

• 具有哈密顿回路的图称为哈密顿图。

• 具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。

首先哈密顿通路一定是初级通路。但是对于哈密顿回路，如果加是初级回路的前提，那么哈密顿回路可以不是初级回路，例如v₁ev₂ev₁，出现了重复的边，不是初级回路，但它确实是经过所有顶点一次且仅一次的回路。

哈密顿图的必要条件

定理15.6 无向图G<V,E>是哈密顿图，则对于任意V₁⊂V,且 V₁≠∅，均有**p(G-V₁)≤|V₁|**。

​ p是连通分支数，理解:分两种情况，一种v1,v2不相邻，去掉三个点，连通分支数为3；一种v1,v2相邻，与v3不相邻，去掉后两部分；当然如果都相邻去掉后为1，都满足p≤3

是半哈密顿图，则有p(G-V₁)≤|V₁|+1

作为必要条件，用来初步判断其不是哈密顿图/半哈密顿图

看看完全二部图什么时候是哈密顿图，用必要条件初步判别

哈密顿图的充分条件

G为n阶无向简单图，若对于G中任意不相邻的顶点u,v,均有度数和d(u)+d(v)≥n-1，则G中存在哈密顿通路。

（存在哈密顿通路说明其可能是哈密顿图也可能是半哈密顿图

推论：设G为n(n≥3)阶无向简单图，若对于G中任意两个不相邻的顶点u*,v均有 d(u)+d(v)≥n*则 G 中存在哈密顿图

哈密顿图解决实际问题