吴紫航

不在故不思

0%

发表于 分类于 阅读次数： 评论数：

有序对

  • 无序对：
    • 含有1个或2个元素的集合
    • ，
  • 有序对： 当且仅当 且
  • 有序对的集合表示：

有向图和弧

    • ：顶点集
    • ：弧集，一个有向对的集合。弧又称为有向边
  • 一些术语
    • 弧的尾
    • 弧的头
    • 环弧：头尾相同的弧
    • 并行弧：具有相同头的相同尾的弧
    • 简单有向图：无环弧，无并行弧
    • 反向弧：简单有向图中头尾相反的弧

度和邻点

阅读全文 »

发表于 更新于 分类于 阅读次数： 评论数：

9.1

  • 反设在遍历v点时发现BE，连向黑色的节点w，则之前在bfs中，队列弹出w时，会发现v为w的未访问过的邻居，则之前的BE实际上是TE的二次遍历，矛盾。
  • 反设在遍历v点时发现DE，连向遍历树中v的后继节点w，但v的后继节点在v刚出队列时必然都是白色节点，即未被访问过。此时该DE实际上还是TE，在遍历树中，w是v的孩子，矛盾。

9.2

不成立，反例：五边形。不唯一。

9.3

阅读全文 »

发表于 更新于 分类于 阅读次数： 评论数：

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。‘ ## 8.2 + 所有点染成白色 + 对于每一个调用如图算法

本题要注意顶点出栈的时机，以保证染色的行为和递归实现是一致的。染色行为如下： + 顶点白色表示之前未访问过 + 顶点灰色表示访问到了，但是子节点还未访问完 + 顶点黑色表示以该顶点出发的深度遍历子树都已经访问完了

8.5

+ v为割点，即连通图G去掉v点后变得不连通，记为G' + 则G'中必然存在两个点w和x，使得w和x没有路径 + 假设G中，存在w到x的路径，该路径上没出现v，则w和x在G'中必连通，矛盾 + 则G中，v必出现在w和x的所有路径上

阅读全文 »

发表于 更新于 分类于 阅读次数： 评论数：

边染色

相关概念

  • 边染色
    • ：色为的边集
  • 边正常染色：相邻的边不同色
  • 边色可染的： 能找到一个边正常染色
  • 边色数：
    • 边色可染的最小
    • 记作
  • 只考虑无环图，可以有重边

边色数的性质和意义

  • 和匹配的联系：
    • 至少要被划分成个匹配
    • 如果能被划分为个匹配，则
阅读全文 »

发表于 更新于 分类于 阅读次数： 评论数：

可平面图的判断

剖分

  • 剖分：在一条边上加入一个新的顶点，将其分为两条边
  • Kuratowski子图：图中的，是或剖分的子图
  • Kuratowski定理：可平面图的充要条件是没有kuratowski子图
  • Wagner定理：可平面图的充要条件是没有可以收缩到或的子图

DMP算法

H-fragment

阅读全文 »

发表于 更新于 分类于 阅读次数： 评论数：

平面图的概念

可平面图

  • 定义：能画在平面上，且任意两边不交叉
  • 交叉：包含端点以外的其他公共点
  • 这个画法叫做一种平面嵌入
  • 画出来的结果是一个平面图
  • 两个很重要的不可平面图，是

可平面图的性质

  • 可平面图的子图是可平面图
  • 环边和重边不影响可平面图
阅读全文 »

发表于 更新于 分类于 阅读次数： 评论数：

边独立集

边独立集

  • 边独立集（匹配）：两两不相邻的边
  • 极大边独立集（极大匹配）：不是任何边独立集的真子集
  • 最大边独立集（最大匹配）：边数最多
  • 边独立数：最大边独立集的势

边独立集与点覆盖集

  • 对任何无环边的图，
  • 二部图有饱和的匹配当且仅当
  • 二部图，
阅读全文 »

发表于 更新于 分类于 阅读次数： 评论数：

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ## 19.1 决策树每个节点进行比较，最坏情况就是决策树从根到叶的最长路径L，显然，其中叶子的数目至少是，对应着第k大元素的n个不同的结果。因此，即最坏情况时间复杂度的下界是

19.3

  • 最多有一个逆序对意味着逆序只可能出现在相邻两个元素之间，那么所有非相邻的元素都不是逆序对
  • 只要找到这个相邻逆序对，调换位置即可完成排序，说明次操作确实可以完成排序
  • 为了便于理解，可以用图的方式刻画这个过程，即n个元素是n个点，比较一次的结果可以确定两个点之间边的方向，可以根据两个点之间的可达性判断逆序情况
  • 假设某算法A自认为可以用不到次比较，就判断出逆序对是个还是个
  • 对手先采取这样的策略：输入数据设置为无逆序，这样算法A的每次比较都返回不是逆序对，最终一定返回无逆序对
  • 进行了不到次比较，说明至少有一对相邻的节点之间是没有边的
  • 此时在图中相互不可达，思考为什么
  • 如果此时添加一条从到的边，图不会出现圈，思考为什么
  • 对手可以按图当前表示的顺序关系重新构造输入数据，算法A有可能还是输出无逆序对，之所以说有可能是考虑到随机算法。
  • 说明该算法有可能出错，从而得出矛盾，故比较次数的下界是

19.5

(1)

阅读全文 »

发表于 更新于 分类于 阅读次数： 评论数：

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ## 18.1 ### (1) 首先所有元素都要进栈一次，而出栈的元素，都是因为不满足海景房的条件，那么现在问题就从证明返回的栈中的元素就是所有海景房，变成证明，返回的栈中的每个元素都是海景房，也就是说都比自己东边的元素高。

那么我们找的循环不变式就是，每次外循环第次结束时，栈中元素从栈底到栈顶高度递减，且每个元素都比的所有元素高，只要证明了这个不变式，那么取循环结束时的情况，就证得了原命题。

这个不变式的证明用类似于数学归纳法的思想，但是为有穷步的归纳推理： + 起始情况：栈中只有一个元素，显然成立$ + 归纳推理：假设第次循环结束，栈中元素递减，且栈中的任意元素比的元素都高，那么对于下一次循环k+1，如果大于栈顶则把栈顶弹出，然后再把压入栈顶，这保证了第次循环结束时，栈中元素从底到顶是递减的；同时由栈顶是栈中最小的元素，这保证了栈顶的进入后，依然有栈中任意元素比大。 + 故循环不变式得证

故原命题得证。

###(2) 由于每个元素都进行了且只进行了一次，故算法一共进行了次，而的次数必然不超过的次数，故算法复杂度为

阅读全文 »

发表于 更新于 分类于 阅读次数： 评论数：

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ## 16.1 这是一个概率论的问题 + 总的样本空间是 + 符合要求的子样本空间是 + 故概率是两者的商

16.4

(1)

采用封闭寻址时，哈希表的存储消耗考虑： + 个表头，每个表头1个单位空间 + 个节点，每个节点2个单位空间 + 空间消耗为，即

同样的空间，即，用于开放寻址哈希表，节点还是个，每个节点需要1个单位空间，则位置个数为。故负载因子是，即

阅读全文 »