最近备考复习算法课，非常感谢 @ 让我更清楚地理解了第一部分的内容。自己看视频的时候做了一份笔记特来分享，希望能有所帮助。
体现图的property的一些数据
例如：图的环数量、使图没有环所需要去掉的顶点数量、最大环的长度
每个节点只有2个邻居的图叫做path
path是指从图上一点到另外一点所经过的不会重合的点和边的集合，可以将它视为一种特殊的图（这种图两端点的度数为1，中间端点度数为2）。
定义1：把一个图分解成两个完全不相通的图所需要封锁的vertex量。
定义2：图的所有树分解中，所有树分解中最小的宽是树宽
树宽 = 警察数 - 1
一种把图化简成树的方法 - tree width is used in this process，so it is known as “tree width” instead of “graph width”
注意：树分解不是唯一的，一个图有很多树分解
G代表图，V代表G有哪些vertices，E代表G的edges
T代表图分解成的树的顶点（这些顶点我们也叫做bag），X记录了树的顶点与图顶点的对应关系
条件1：G（图）中任意一个顶点都至少需要包含在一个bag里。G中的一个vertex可以被包含在多个bag中
条件2：G中每条edge（边）的两个定点都得在一个包中
条件3：如果树的两个bag有交集，则在树中必须存在一条能够连通这两个bag的路径
条件4：如果两个bag里存在同一个的G中的顶点，那么同时与这两个bag相连的其它bag中必须要包含这个顶点。
条件5：分解后必须要产生树，而不是环
如何判断新的树的节点（包bag）是否相连？
两个bag如果含有公共的图节点，则它们相连
最大的bag的size-1
宽是对树分解的描述，树宽是对图的描述
确定要封锁的地方
树的tree width： 1
环：2，具体如下图：
内容：把一个树分成k个子图，且这些子图至少与其它一个子图有交集（两两有交集），那所有子图相交也必定不为空集。
子图（minor）：汉语中多称为图子式。指如果一个图所有的vertices and edges都被原图包含，则其为原图的子图。
note：该性质不仅限于树分解（所有树都具有）
内容：如果一个图中有一个团，那这个团中的顶点一定全部在一个包里。
团（clique）：任意两个顶点两两相交，即完全图。
证明：如果将团分成多个bag，至少会有一条团的edge不被包含，导致变成invalid tree decomposition(非法树分解)。
条件1：每个节点只有1至2个子节点（包）
条件2：一个节点如果只有1个子节点，那这个子节点与主节点包含的原图顶点只有一个不同（只相差一个）
条件3：一个节点如果2个子节点，那这两个子节点都与主节点一样
当一个树分解满足上述3个条件时，我们称其为好的树分解
内容：如果有一个图G，其树宽为k，那么G中一定存在一个顶点，该顶点的度≤k。
内容：一个图G如果有n个vertices，树宽为k，那么该图G最多有n*k条edges。
内容：对一个树宽为k的含n个顶点的图G，必定存在一个k+1个顶点的集合S，能够使得图被分成两份，每一份的节点数都小于等于n/2 (n out of 2)
内容：树宽为k的图G，一定存在k‘ * k’的网格可以作为G的子图，其中k‘ 满足以下条件：
内容：如果一个图是k*k的网格，其树宽为k
引理（lemma）：如果有一个图G，G有一个k*k的子图，那么G的树宽一定≥k
内容：一个有n个顶点的完全图的树宽为n-1
证明：在完全图的树分解中，所有顶点必定在一个包中（如之前所提到的团的性质一样）.该树分解的宽为n-1，且只有这一种树分解，所以该完全图的树宽为n-1。
如果一个图有大小为k的团（clique，完全子图），其树宽必定≥k-1
如果一个图的最长的环长度为k，该图的树宽≤k-1
即对树宽为k的图G进行操作后，形成新的图G’的树宽的性质：减少操作一定不会增加树宽，增加操作一定不会减少树宽
减少操作：
删除边
删除点
融合点
定义：径分解所含的大小最大的包的size-1（cops数量-1）
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/162135.html