最大割问题分析

前言：

本篇博客主要记录最大割问题的描述以及给出最大割问题的目标函数

目录

1.最大割问题描述

2.结合实例分析最大割问题描述

3.最大割问题的目标函数

---

1.最大割问题描述

将图G的顶点集V划分为S和T，目的是使得顶点子集S和互补子集T之间的边数最大。

我们需要注意的两个点：

（1）是将V划分为两个非空的顶点子集,并且顶点全集V=SUT，S和T无公共顶点；

（2）最大割：是要顶点子集S和顶点子集T之间的关联的边数尽可能的大，这个边是图G中真实存在的

注意：如果边带有权重，最大割问题的划分目标就是使得S和T之间关联边的权重之和最大。本文分析的是边不带有权重的情况，二者之间的目标函数只是差了个权重系数而已。

2.结合实例分析最大割问题描述

存在无向图G如下图所示：

对图G进行最大割划分，下面仅给出几种划分方式用于问题分析，帮助理解。

方式（1）：S={v1},T={v2,v3,v4}, 此时S和T之间关联的边数:（v1,v2),割为1

方式（2）：S={v1,v2},T={v3,v4},此时S和T之间关联的边数:（v2,v3),(v2,v4)割为2
 

 方式（3）：S={v1,v3,v4}   T={v2},此时S和T之间关联的边数:（v1,v2),(v3,v2),(v4,v2)割为3

 对于给定的图G，最大割为3，顶点划分对应方式3

注意：图G的最大割数值是一定的，但是顶点划分方式不一定是唯一的，S={v1,v3},T={v2,v4}也是图G最大割为3时一种最优划分

最大割问题的关键就在于顶点集V的划分，实际上就是一个组合优化问题，下面给出最大割问题的目标函数。

3.最大割问题的目标函数

结合图G进行问题的分析，图G的顶点集V={v1,v2,v3,v4},边集E={(v1,v2),(v2,v3),(v2,v4),(v3,v4)}

我们随机将V划分为S和T，如果边e所关联的两个顶点在不同的集合中我们就认为这是一个割，我们的目标就是要使得E中的边e，e关联的两个顶点尽可能不在同一个集合中，我们给定变量

我们利用下式结果来判断边(u,v)的两个关联顶点是否在同一个顶点子集合中，结果为0，说明在同一个集合中；结果为1说明u，v在不同集合中。

 所以我们的优化目标: 

以上都是我自己在网上查阅材料之后形成的个人理解，如果有不恰当的地方欢迎批评指正。下次更新如何用QAOA求解最大割问题。