tutorials/combinatorial_optimization/DC-QAOA_CN.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 大规模量子近似优化分治算法\n",
    "\n",
    "<em> Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved. </em>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 概览\n",
    "\n",
    "[量子近似优化算法](./QAOA_CN.ipynb)（quantum approximate optimization algorithm, QAOA）是一个将量子与经典结合起来，用于解决组合优化问题的算法。但是，由于现阶段量子比特数量的限制，该算法无法处理大规模问题，且该算法的运行时间随着问题规模的增大，成指数增长。关于量子近似优化算法更详细的讨论见 [1]。\n",
    "\n",
    "分治法（divide-and-conquer, DC）是可以解决上述瓶颈的一种方法。主要是将一个大问题拆分若干个相似的子问题，将这些子问题解决之后再将子问题合并，从而得到母问题的解。Junde Li 等人在2021年提出量子近似优化的分治算法 [2] 将上述技术应用于解决较大规模的最大割问题。本教程所使用的方法在该论文的基础之上做出了一些改进。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 具体算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 大图分割\n",
    "\n",
    "在图论中，我们用一个图形的边 $E$ 和顶点 $V$ 定义一个图形 $G=(V,E)$。假设它有 $|V| = n$ 个顶点，但是含噪中型量子（noisy intermediate-scale quantum, NISQ）设备上最多可以运行 $k$ 个量子比特（$n > k$）。这种情况下，我们使用``大图分割 LGP``的方法将图形 $G$ 拆分两个子图 $G_0$ 和 $G_1$。为了防止遗漏任意一条边，在拆分的时候至少有一个点被两个子图共同拥有。我们把这些共有的顶点叫做分离顶点（集合），并且约束这个集合的大小小于 $k$。以下的代码定义了如何进行大图分割。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-16T03:41:44.449329Z",
     "start_time": "2021-05-16T03:41:43.034272Z"
    }
   },
   "outputs": [],
   "source": [
    "import networkx as nx # networkx的版本 >= 2.5\n",
    "import matplotlib.pyplot as plt\n",
    "from itertools import combinations\n",
    "import warnings\n",
    "warnings.filterwarnings(\"ignore\")\n",
    "\n",
    "# 将一个图形分割成两个有重合的分离顶点子图\n",
    "def NaiveLGP(g, k):\n",
    "    E = list(g.edges)\n",
    "    E = [(min([u, v]),max([u, v])) for (u, v) in E]\n",
    "    E.sort(key=lambda tup:tup[0])\n",
    "    V = list(g.nodes)\n",
    "    V.sort()\n",
    "\n",
    "    counter = 1\n",
    "    while counter < k:\n",
    "        num_nodes = counter\n",
    "        nodes_combo = list(combinations(V, num_nodes))\n",
    "        # 找有效的分离顶点\n",
    "        for p in nodes_combo:\n",
    "            V1 = [x for x in V if x not in p]\n",
    "            E1 = [e for e in g.edges if e not in g.edges(p)]\n",
    "            G1 = nx.Graph()\n",
    "            G1.add_nodes_from(V1)\n",
    "            G1.add_edges_from(E1)\n",
    "            S = [G1.subgraph(c).copy() for c in nx.connected_components(G1)]\n",
    "            if len(S) == 2:\n",
    "                # 将分离顶点加入不相连的子图中\n",
    "                V_S0 = list(S[0].nodes)\n",
    "                E_S0 = list(S[0].edges)   \n",
    "                V_S1 = list(S[1].nodes)\n",
    "                E_S1 = list(S[1].edges)\n",
    "                for (u, v) in g.edges(p):\n",
    "                    if u in V_S0 or v in V_S0:\n",
    "                        S[0].add_edges_from([(u, v)])\n",
    "                    if u in V_S1 or v in V_S1:\n",
    "                        S[1].add_edges_from([(u, v)])\n",
    "                    if u in p and v in p:\n",
    "                        S[0].add_edges_from([(u, v)])\n",
    "                        S[1].add_edges_from([(u, v)])\n",
    "\n",
    "                return S\n",
    "\n",
    "        counter += 1\n",
    "    print(\"G的连接度大于k\")\n",
    "\n",
    "    return {}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们给了以下的例子去说明``大图分割``是如何进行的。假设一个随机图形有10个顶点，但是 NISQ 设备最多支持9个量子比特，即 $k=9$。那么根据``大图分割``，红色的顶点0和2将被选为分离顶点。首先将这些分离顶点去掉，剩下的图将是一个不连接图形并可以被分成两个子图，比如下图中的顶点3-9和顶点1。随后，我们再将这些分离顶点和相关边分别加回两个子图中，从而保证所有的边都不会被遗漏。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-16T03:41:44.839484Z",
     "start_time": "2021-05-16T03:41:44.455664Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA1MAAADnCAYAAAD7CwxiAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAABKyElEQVR4nO3ddbhc1fXG8e8bF0LwIMUdSvG2uNMEL07QluLQ4tKW4k6huBPcnWKlWLHiBYrzo1iDBkJCbjzr98c+KUnuzJXJzJyR9/M887TMnDmzbu7cc/basrYiAjMzMzMzM+ucLnkHYGZmZmZmVo+cTJmZmZmZmZXAyZSZmZmZmVkJnEyZmZmZmZmVwMmUmZmZmZlZCZxMmZmZmZmZlcDJlJmZmZmZWQmcTJmZmZmZmZXAyZSZmZmZmVkJnEyZmZmZmZmVwMmUmZmZmZlZCZxMmZmZmZmZlcDJlJmZmZmZWQmcTJmZmZmZmZXAyZSZmZmZmVkJnEyZmZmZmZmVwMmUmZmZmZlZCZxMmZmZmZmZlcDJlJmZmZmZWQmcTJmZmZmZmZXAyZSZmZmZmVkJnEyZmZmZmZmVwMmUmZmZmZlZCZxMmZmZmZmZlcDJlJmZmZmZWQmcTJmZmZmZmZXAyZSZmZmZmVkJnEyZmZmZmZmVwMmUmZmZmZlZCZxMmZmZmZmZlcDJlJmZmZmZWQmcTJmZmZmZmZXAyZSZmZmZmVkJnEyZmZmZmZmVoFveAVhhErMCuwIrATMDI4G3gCsj+CjP2DpKogvwC2BLYE4ggM+AO4CHI5iUY3hmVqMk+gGDgdWBWYEW4ANgSARv5RmbmTUvCQGrATsA85Da0V8C9wN3RzA+x/AsJ4qIvGOwKUj8BPg9sDkwCegzxcvjsueeAU6O4JHqR9i+rCG0L3Aw0BvoN8XLAYwiJYd/Bi6OYFTVgzSzmiOxMHAEsBPpWtd3ipfHAxOAfwOnAHdF4BuYmVWcRA/g18DhwOykttmUs7tGAhOB84G/RDCs6kFabpxM1RCJ7YErgJ5A13YObwHOAv5USw0KiXmAx0k9Nr3bOXw08CGwbgSfVzYyM6tlEusDdwK9aH/WxCjgFmDPCCZUOjYza14S/YEHgGWZuoO7kDHAcGDtCN6pcGhWI5xM1QiJbYCraT8BmdIo4JwI/lCZqDpHYjbgX8AAOj6FdDwwFFg+gm8rFJqZ1TCJNUmNlfYaKlNqISVfO9dSh5KZNQ6J3sCzwBKkju6OmAR8B6wQwYcVCs1qiAtQ1ACJRYGr6FwiBWkKzIESG5U9qNLcThr+7sxavO7AXKReZjNrMhKzAH+lc4kU2fFbAHuWOyYzs8yFwGJ0PJGC1LaeEfhbtsbKGpyTqdpwICmpaOXaa2HoUPjuO3jnHdh991aH9AGOqWx47ZNYClgZ6DHl8z16wOWXw4cfwogR8PLLMHBgq7f3AFaXWKQqwZpZLdmdItOaO3D96wsc7QaLmZVbVghsewp0dC+xBDzyCAwfDu+9B1ts0ertXUkdxetUOEyrAU6mcibRF9iNIsnUKafAAgtA//6w2WZw4omwwgqtDvuJxBIVDbR9B1LgZ+jWDT75BNZaK/0MRx8Nt9wC88/f6v1dgQMqH6aZ1Yqs4ufBFBmV6uD1rz9usJhZ+f0aWlcd7toV7r4b/vpXmGUW2HNPuO46WHTRVu/vCxxWhTgtZ06m8rcVBf5YJ3vzTRg3Lv3/iPRYeOFWh3UF9qlQfO2S6AnsSIHpfS0tcNxx8NFHKfb77oP//AdWXLHVaboDu0su12/WRNZi6op9U+ng9a8vqTPHzKycfkeBjp4lloC554azz4ZJk+Cxx+Dpp2HnnVu9X8A6EnNUIVbLkZOp/C1KG40JgAsugFGj0jSXzz6D++9vdUh34McViq8jOnyhmGMOWGwxeOONgi93Je2pZWbNYVHaqVzageufgCUrFJ+ZNaFs6vBcRV4r+NyPC7fCxgCt5+JYQ3Eylb9ZoO35/vvtB/36weqrwx13wNixhY56cV1JkccDlvwYRrS7eLxbN7j+erj66tQwKmAiU+9JZWaNrR/tFKzp2PWv7Q4pM7NO6gWFq4S+/TZ8+SUcdlhq12ywQVrK0Kd4K8jtmgbnZCp/wyjyBzulSZPSMPKPfgT7FJzQt9IjEaE8HvDWvDBjS1vxS2kx+bhxsP/+RQ/rCoxo79/CzBrGCGh/n6j2r398X+7AzKypjaFIR/eECangxMYbw+efwyGHpLXgn35a9Fxu1zQ4r0/J3zukhkCHei66dSu4ZmA88Gp5w+qUL9s74IorYMAA2GijdCEqYjx4rymzJvIuTIqO9usVvv5FAG+2M8BvZtZhEYTEp8B8hV5//XVYe+0f/vvpp9OsmwJ6gveaanQemcrfHRRpBcw+O2y3HfTtC126wIYbwg47wKOPtjp0InBRheMsKoJxpH2yxhd6/aKLYMklYdNNYcyYoqcZB1wWwcSKBGlmNUNST0lbQZeD4POCk2M6fv1rAQYuK+lISfNWPHgzaxZnA6MKvbDMMtCzJ/TunUam5poLrrqq1WEBPBzB15UN0/LmZCpnEYyGuAImthqviUhTWj79FL79Fs48Ew48EO65p9VpXorg/WrE24ZzKTBdZ775YO+9Ybnl0nD4yJHpMXjwtEdOCuD8KsRpZjlQsoqki4ChwP4Qd0Of35Myoql0/PrX52N4dGdgIeBVSX+XtKskr1Mws+lxFUUK5Oy8cyqI8+WXsN56ad3U5MqjUxgFnFnZEK0WKKLd5TpWQZJmh2WvhmcGQp9S5qm0AL+M4G/ljq2zJP4OrE7ndgoHxk+ARyfBwL2Bq8JfSrOGIWkhYCdgZ9Io+jXA9RHxUXqdmUjTYPqXcPpRwAERDMk+qxewKbALsAZwb/Z5j0aER73NrFMkLoEJu0G3Hp1758RJ0OVt0I8j2l8Xb/XNI1M5krQl8Bq8+gaM3QYY3clTtACn1kIildkG+Iwi0/2KGAfdP4ST1iHt6XCPpLkrEZyZVYekmSTtIelJ4DlgdmAwsGREnDw5kQKIYDgwiAKjU+1oAW4i9R5n54oxEXFrRGwKLAa8AJwCfCzpdEnLTMePZWZNRJKg/0fwOjCpcB3RgmIijJwES70H6mQSZvXIyVQOJM0i6XrgNGDriDgsYubbSRvfttB+davIjjsBOLGiwXZCBN8CPwfeo2MNoxbgLWCViH88A/wUeAX4l6Qd04XMzOqBpO6SNpF0C/AR8AvgDGCeiDggIl4oNuocwbPAQGAkaf1ke0YBQ4A9i/X6RsSXEXFuRKwEbEAaFbtf0iuSDpI0Z6d/SDNrCpK6AufDiO3ghB9Dl2cpsn5qGqNBQ+HTZeDtCcBDkmaqaLCWO0/zqzJJGwOXArcBR0VEy9SvswRwGLADMImp90+ZXL7h76QRqacrH3HnSfQBdif9HDOTfobJidEkUhL1NXA6MCSCMVO/XysBV5MqHe4dEe1WCzSz6ss6PFYgTavbHnifNK3ulojodGVOifmAg4DfZE/NMMXL40jXj+eA0yJ4oIR4uwJrZfFuDjybxXt3RHR2ZoCZNSBJfYAbSG2XrSJihEQ3Uof34cACpOUMU66nGkmaXXQ2cHEEwyV1Af5M6swZFBGfVO+nsGpyMlUlkvqT/sjWAX4VEY+3fTwzkqbFLA/MCnxHSi6ujeCzykZbHtkO4msBmwGTe4E/B+4EnmprHnG29uFYYDfggIi4taLBmlmHZVXzdiQlJb1ICcl1EVGWQjgSvUnThn9OmiI4CviAdP37T3k+Q32BLUg/w8qk69I1wJMRMakcn2Fm9UXSbKS1lu8Bv4mIViPlEisC2wLzAN1J7Zq/AQ8Wqkgs6SDgYGDjiHitguFbTpxMVYGkDYHLgfuAwyNiZM4h1Q1JPyeNUr0C7BcRw3IOyawpZdXxtiQlH8uRRtevBZ6u96Ix2TrNwcCupD3/rgOujYh3cg3MzKpG0sLAA8AtwNHlvK5J2ga4ANghIh4p13mtNjiZqqCs8XEGsBGwe0Q8nHNIdUlSb+Ak0jSivSOidXF4Myu7bFrceqRKfJsC/yAlUPdGRPFd4+pUNm1xWdLPOxj4mDRadZM7cswal6SVgbuB4yLikgp9xhqkTqhDI+LaSnyG5cMFKCpE0jrAa6Qh4GWcSJUuIkZHxMHAdsDZkq6RNHPecZnlQWIBiTMlvpQYJzFRYqTEgxLrZdNrp/MztIyk00nJxEnA88CiEbFZVi2v4RIpgEj+FRGHAPMCxwCrAf8n6U5JW0rq5NYPrUnMK3GKxOcSY7Pf4fcSj0j8QvK92axaJG1Cmjm0V6USKYCIeJK01OMESUe5yFbj8MhUmWXz8E8hTYfZKyLuyzmkhiJpBlIVxM2APSLiwZxDMqsKifmBK4FVSR1h05bcDdLaou+A30ZwR+fOrzlJhW92AWbjh6lub05n6HVP0ozAVqR/m2WAW0kjVv/szFQgiXlIv8M1SUV5CiVmI0m/x4MjuHE6QzezNkjai7Q+e/OIeL5Knzk3KXn7J2lNeHsVnK3GOZkqI0mrkfY8eQ74bUR8k29EjUvSesAVwMPAIRExIueQzCpG4ifAY6SNbbu2czikipnHRnBG2+dVb1JVu12AVUjTXK4BHncRhsIkzc8PxTe6kqY9XhsRbRbGkFiSNE1yJqBbBz6qBTg9guOmK2AzayUbFTqBNONlULmK53Ti8/uRpvyNJa2j6kjZdatRTqbKIGuQnEC6we4bEXfmHFJTyHqLJ5cd3d2LOq0RZeXCXyFtM9CZaSEtpBGqK6Y+n7oAa5CSgS1JnT/XAnf5ht5xWWNsJX4oC/8W6d/x1ogYPvWxzA38izTi19nf4RERnF+GkM0MkNQDuAxYHNg0Ir7KKY7upK1ylsri8DYwdcrJ1HSS9FNStbnXSdXmcvmjbGaSBpIujPcAR0TE9zmHZFY2En8D1qVjI1LTGgPMF8FXkhYnFVbYCRhBGoG6ISKGli3YJpU1zgaR/n03AB4kJVYPRcR4ibuAjenYiNS0xgCLRPDfMoVr1rSyTtjbSHtC7TDtXp85xCPSNMMdgYHVHiGz8vAi1xJJ6inpJNJ+BMdGxLZOpPKRrZtahrTB56uS1sw5JLOykJiXNIpUNJFaZBEYPRquLVgbalLAHZdJeg54HOhNWhvwk4g404lUeUTEuIi4OyK2BhYkTck8CvhUWvxSmDSIaRKpHj3g8svhww9hxAh4+WUYOLDoR+xdwfDNmkK2VukfpM3Ft8w7kYL/Fb05hrQW/ElJP8s7Juu8ph2ZkpgD+DVpU8iZSQt+3wYui+Cttt+r5UmjUR+QSnV/XuFwrYMkbQZcRNon4vcRMbr4sfQgbdr5S2AAMAn4DLiJIpvvmVWTxCnAQRQuVADAQw9B797w0Uew886Fjhg+FubZElr+5oXO1SVpEbjxUth8beg91fS+Pn3gsMPgqqvg449ho43gxhthmWXS73Ia3wIDIhhfncjNGoukpUlFHy4GTqvFvfEkbQwMIW0W7C1g6kjTJVMSywNHk6ZkBKmndrIJwHjgDeCkCO6a+r3qDvwe2A84BLiuFv8gm52kWYHzgRWAXSPin1O/zizAocA+pB7/ftOcYiRpas3ZwLkReB2J5UJiKDBXsde32w623BLefDONUBVOphgJbBDBcxUK09og8QFptKpdr74Kxx0Hd7SuwzgC2DyCx8sbnVnjk7QWqYP1kIi4Lu942iJpJdKShRMi4qK847GOaappfhI7AE+Rqlf1YupECtI0jN6kRcXXSVwgpek1kn5MKmP5M2D5iLjWiVRtiohhEbED8AfgLkmnSeoFILEIaf+vg0lVtaZNpMiem52UdL8oMWdVAjdrbaZiL/TrB8cfD4cc0u45JgFzlDEm65xZOnLQHHPAYovBG28UPWT2skVk1iQkbUfaymBwrSdSABHxIrA6cKCkU7wXVX1ommRKYmtSKe0+dOzn7gvsBhMvlLoeRZoDfyGwcUR4IXAdiIjbgJ8AiwAvSb8eBDxL6unvyMabvbP3PisVb9SaVVDRtVInnABXXAGfftruOUTaPNzy0W7RiW7d4Prr4eqr4Z13Ch4iWu8rZmZFKDkYOANYv56q/UbEB6TNwtcCrskK3FgNa4pkSmJB0hqnaUei2tMHxv0G9h4MrBQRV3g0qr5kpUa3hi4nwSH3wMRZ6Nz3vhsp+bq+IgGata3gFNNll4X114ezz+7QOYK05sbyMbKtF6VUPGTcONh//6KHTcK/Q7MOkdSVNE3/V8CqEfFaziF1WkR8DaxH6ti/X1L/nEOyNjRFMgX8ljZ6B9uuhtW7C5zfNSJaLwm2upAS4In/B0uOg65Tfef32w9eeAHGjIEhQ4qeoiewrsQCFQ7VbFpPkBrSU1l7bVhggVS44LPP4NBDYaut4KWXCp6jB/ByRaO0tjwCxYvZXHEFDBiQfn8TipcH6QU8X4HYzBpKtu/nzcCywBoR0f7YfY3KCmhtQ9rD7klJP8o5JCui4ZMpid7Ab2hjisQFF6QGdRtnmV9ipXLHZlV1CHTpNe2TQ4fCiSfClVe2+34B+1YiMLM2nEnaD2Uql14KCy8Myy2XHhdfDPfdB7/4Rav3TwBuieC7ikdqxZwFjC30wkUXwZJLwqabpg6dIiYB90TwdYXiM2sIWfGph4FxpD2bhucb0fSLiImkAYFrgWey9ftWYxo+mQI2I01zKWi77WD4cHik7dm0PUkV/KwOSfQjfQ9afd/vvBPuvhuGDWv3ND2BvSW8GNSq6Rngi2mfHD0avvjih8f336fG+Netm9vjSNNdLCcRvAx8OO3z880He++dkuHPP4eRI9Nj8OBWpxgN/LnigZrVMUkLAk+TioztFBEFOzDqUbYX1RnAEcCjktbJOyabWim7sdebhUlFJ1qZXA1rvfVg993bPEdXYMkKxGbVMRepUdmRohNt6UWav/z9dEdk1gERhMQBwG20sebzuOMKPj2atF/aq5WJzjrht6QN3v/3O/z447Reqh2jSZuMeoqfWRGSViSVEz85Ii7IO55KiYgbJX0O3CTpwIi4Me+YLGmGkal+FKmI1YlqWJPPY/VpBtoYneyECfh7YFUWwf2kfdFaOvG20cCrQOtxDqu6CB4hzW4ouol4AaNJG8lvHVGW65dZw5E0CHgA2K+RE6nJIuIxUmGKUyUd5tLptaEZRqa+IzWCp/pZJ1fDWn75Dp9nRJnjsuoZSXk6Drrj74HlIIILJYZBDIExPVNhnIImkEZh7wd2iii8VseqL4IhEsOB60idO30LHzke6DIGuj4CbBvRqQTMrGlI2h04Edg8Ip7NO55qiYh/S1qVdJ2fLxulKlrkxiqvGZKpt0g9fFONKExZDQtghhmga1dYailYccVW55gAvFLpQK1i/ksb+/V0wgg6NzpgVjYR3CytMAE2Og9OnATqz9RV4nqQSvj/JYLiW79abiK4U2IuYGfgMGA20v1lsh7w6utw6MiIxzfNJUizGpeNxhxD+jtaKyLezTmkqouI/0paE7gduE3S4Kz6n+VAjb5tkkR30gLumad8vndvmHHGH/770ENTcrXPPgUXcY8GVozgrYoGaxUjcQWwC9N0IHTtmjbMPOYY+NGPYI89Unniia37eEYDp0VQeHWKWRVIehy4DOIGUunfAaQk6lvg1Yi29zSy2pEVs1kGmJO0nnM48BpoPPAfUiPx7fwiNKs9kroDl5D+djaJiFYFeppJtqHvlcBCwGbZ/lRWZQ2fTAFIHE/qBWxVGnuyY45J+03tvHPBl1+I4KcVCs+qQGIZ4DmmWcR/zDFw7LFTH3vssQUX9I8BFozg80rFaNYWSasANwCLRkTxHYms7kk6GlggItoujWTWRCT1A24ljeZuFxEFNzVvNtlI3UnA1qSS8B/kHFLTaZZkai7gXVIhgs5qIS0AfqC8UVm1STwO/JzOV/UbDdwRwU5lD8qsgyTdBTzcDIusm52kWYD3gGXredNRs3KRNBdwH/AisK87lFqTtA9wNGkNWZu7p1p5NUM1PyL4jLTPUGfXu7SQpnY5kWoMvwQ+LziJr7gxwDukjZ/NciFpKVJHQPvbS1vdi4hvgCHAwXnHYpY3SUuQ9ty7HdjLiVRhEXERsDdwn6SN846nmTRFMgUQwWOkhOp7UrWrtkwiJVLHAydUODSrkgi+hc32g/cCJnVkoeYo4AVgrQjGVDg8s7YcDpzrBcZN5WxgN0mz5h2IWV4krQ48DhwbESdFM0ynmg4RcQ+wKXC5pD3yjqdZNMU0vylJzA/8Dlp+C93HQ/cp11GNBkQqN3l6BM/lEqRVhKQ5gRfhRwfAJ3OQGqgDSJs6T96rYSKMEYz9BPofDdwUwficQjZD0nykaqILR8TwnMOxKpJ0OfBxRByfdyxm1SZpK+AiYKeI+Fve8dQTSYuS9t+6ATjGSWhlNV0yBSBpAPR6B4YeDDMvBcxO2o/q/4AbIvgq3wit3LIKQH8HHo+IY9JzCFgVGAjMRRqRHAo794Dr5o+IHXML2Cwj6RxgbEQcnncsVl2SFgeeBBb0YntrJpJ+RyoctklE/CvncOqSpDmAe0lbBO0REe4YrpBmTab2B34WEYVr91nDkXQmsDTpwtzmmilJs5MWf8/jBozlSdJspOI5P46IoXnHY9Un6TbgHxFxbt6xmFWapC7AGcAgYFBEfJRzSHVNUl/gRlI1660jYkTOITWkplkzNY3BpC+XNQFJ2wJbAjt2ZJfwiPgKeJY079gsTwcAtzmRamqnAYdko+tmDUtSL1LbbCVgNSdS0y/rEN6SNPPqCUlz5xxSQ2q6ZErSgsCiwMN5x2KVl1VBuwDYKquQ1VE3kJJus1xImgHYl9RLa00qK3H8HrBD3rGYVYqkmYGHsv/8RUR8m2c8jSSrfrgvcDPwTNYusjJqumQK2J7U0+u5ow1O0ozAHcBhEfFKJ99+F7BWtt+LWR72AB6LiPfyDsRydypwRDYFyqyhSJofeJq0h9QOEeHquWUWyamkfagek7RG3jE1kma8MA8mjTpYA8t2BB9CKjhxVWffHxEjSb1kW5U5NLN2SepB2mPotLxjsZrwCKna7CZ5B2JWTpKWIyVSl0bEIRExKeeQGlpEXAvsCNwuaZu842kUTZVMSVoG6E/6w7XGdhjwI+B303GOG/FUP8vHjsBbEfFS3oFY/rKyxqcCR2UdRWZ1T9KGwN+AAyPiLzmH0zQi4u/ABsBZkg7KO55G0FTJFGnO+U3u+WhsktYFDiJVrhk7Had6AFhW0jzlicysfdlUriNIjWezye4EZgU8PcfqnqRdgWuALSPitrzjaTYR8Sppa5jdJf1FUte8Y6pnTZNMZb15O+Apfg1N0rzA9aTKfZ9Mz7myedt3AduVITSzjtocGAE8lncgVjuySqSnA0fmHYtZqZT8ETgWWDsinso5pKaVtZFWB5YFbpbUO+eQ6lbTJFPAz4ExwKt5B2KVIakncCtwdkQ8WqbT3oCraFmVZJ0+RwKnesd6K+Ba0mj5cnkHYtZZkroBlwC/BFaJiLdzDqnpRcRwYCAwHnjYRbdK00zJ1A7ADW6gNLS/AEMpbynpx4B5JS1axnOaFbM2aV3nXfmGYbUom7Z8NmkaqFndyDaPvQuYjzQi9Xm+Edlk2XVlR+AZ4GlJC+QbUf1pimQq6w3ZDm/U27Ak7QasC+xWzoQ5m1pzMx6dsuo4Ejjd6zqtDZcCG0haOO9AzDpC0gDgceBLYNOsWq7VkIiYFBGHAxeSEqoV8o6pnjRFMkVqZH8UEe/nHYiVn6TlSaNRv4yIERX4iBuAwa6iZZWU3byWJq35Mysou8ZdDByadyxm7ZG0GGnE4z5gd+/xWdsi4jxgf+BBSQPzjqdeNEsy5cITDSqb33s7sF9EvFmhj3ke6A4sX6Hzm0GaunXWdFagtOZwLrCdpDnzDsSsGEmrAE8AJ0fEsV5mUR8i4k5gC+AqSb/OOZy6oEb/bkvqBXwGLB0RQ/OOx8onKyF9H/BmRBxS4c86EegZEYdV8nOsOWVr8p4BFvIUGOsISecDIyPiqLxjMZuWpC1IU1J3jYgHcg7HSiBpceB+Ugn7450MF9cMI1MbAS87kWpIfwL6UJ1SwTcC22cJnFm5HQpc5ETKOuHPwJ6S+ucdiNmUJO0HXAAMciJVvyLiHdJeVJsCl0nqnnNINasZGoaDceGJhiNpY+A3wHbVmIMdEW8A35D2ZDArG0lzAdsA5+Udi9WPiPgPaWPxvfOOxQzSbBFJpwIHAKtHxEt5x2TTJyK+IFWZnRu4W9IM+UZUmxp6mp+kGYFPgAUi4tu847HyyKpYPUMqOPFMFT/3SNJ3yY0XKxtJpwG9I+K3ecdi9UXSMsDfgAWzTcbNcpHt83glsACwWUQMyzciK6esKvZFwArAxi5tP7VGH5n6JfC4E6nGIakPqeDECdVMpDI3AVtJ6lHlz7UGJWkm0gjrn3MOxepQRLwOvAjsmncs1ryy69gDQC9gfSdSjSciJgB7kvYKeyZbT2WZRk+mXMWvgWSlyS8G/k2aj11VEfEh8C6wQbU/2xrWvsBfI+KjvAOxunUqcHjWc2xWVZLmBZ4EXge2jYjROYdkFRLJCcDxwBOSVss7plrRsMmUpDmAnwP35h2Llc3ewLLAnjlWlbmBtA7PbLpI6g38Fjg971isfkXE08BQYKu8Y7HmIuknpCn3Q4ADs03urcFFxFWk0fA7Jfm6QwMnU6QF3X+NiJa8A7Hpl+1XcRywVc6/01uBjSX1zTEGawy/Ap7LipuYTY9TgSO9sbhVi6R1gb8Dh0bEWS6b3Vwi4iHgF8C5kpp+vW8jJ1OD8RS/hiBpAHALaff09/OMJSK+BP5JKhVqVpJsStZhpEaw2fS6H+hGatyYVZSkHUlVkreJiJvzjsfyERGvAKsB+0g6o5m3jmnIH1zSAsBiwMM5h2LTKWt03gRcFRG1MmXzRtJ6PLNSbQt8HBHP5h2I1b9sVOBUqrPnnjUpJUcCJwPrRsQTecdk+crWkq9GWlZzQ1bVsek0ZDIFbA/cVo39h6ziTgHGAsfmHMeU7gTWljRL3oFY/cmmYh2JR6WsvG4G5s+mRJuVlaSupMJP2wOreHqyTRYR35AKc3UFHpI0c84hVV1DJFMSPSVmluiaPeWNehuApK2BrYEda2lha0SMIO3tsiUAUm+kmWjiIW4rTKKLxEwSvad4ehAQwIM5hWUNKCtdfCZwxOTnJLpm98am7C22NkhC6oPUv717V7YlyR3AosCaETG0KjFa3cj2udsOeBl4StJ8bR0vIYkZJGaUqPu1nnXb+JNYUOIsie+AFuBzYLw09r9wyLzw4as5h2jTQdKSpA3itq7FPSv2gmfughOQRgMjgS+A8UivI+1Ekw51G0j0kthZ4t/AeNJ3Y6TEaIkr4efHA6d6wbZVwBCYaVXptRMlPiR9/z4HWiS+k/izxAK5Rmj5kpZHug4YDYwAviTdu15B2p5p9lGUNDvwKDCctFnriGqHbPUhIiZFxMHA5aS9qJab8vUsgVpH4j5gHPAt8DUwXuIxiUFSfeYlqrf7ucQcwPXA6qRksMAGqmPHQ88JwIXAERHUzKiGtU9SP+B54IyIuDLveKYiLQbcHLD4BOjdvfBRI7P/PRo4l3r7I7OSZL1rB/HDlNR+rY+aNBHGdoGe/4Iu20aQa0EVaxwS3YAzYPz+MBHoVWjfqbGkUdEngcERfF3NGC1H0lKk9ccLAz3hfzN5pjSS9P04koiLJC1C2oz3ZuBodwBZR0nahjQtdMeIeFhibeBqYBagLxQcjfoeGAX8JoK/VivWcqirZCrrUXsGmA0o0o6dSgvpprFpBF4/VQey9SS3AsMiYq+845mKtDKpFOwMdGxUt4V08djPCVVjyxKpi4GdgD4deMskUsNlvQheqmRs1vgkepAq+q1Cx75/40g9wqtE8HElY7MaIK0KPETxRuy0Wt6Fu5aAdQOOjYhLKhugNSJJawC3wfm3wn6/hqmmu7dlNHBwBBdXLrryqptkSmIW4BVgHgr3qBTTAtxD6oWrjx+2iUk6lFTpbI2IGJt3PP8jLQy8BPTv5DtHAacTcXz5g7JaIXECaVSqs/uPDQdWiOA/ZQ/KmkKWyN8MbELHGyuQhq8+AZaPYHgFQrNaIC1BmulRYKS8uFEQz8FV60b8ujKBWTOQ7tgVBg2B3p1dFzUa2DGCOysRV7nV09zEPwEDmCaReuwxGD0aRo5Mj7ffbvW+PqSbzLpVidJKJmkd4FDSOqnaSaSSiyl0M5p5ZrjjDvj+e/jwQ9ihVcX0vsBRpHL91oAkFgYOoUAi1YHrUz/S2kCzUm0AbMQ0idR++8ELL8CYMTBkSMH3dQXmIk1HtsZ1OYU6edq5d/UFrQs7IM1TnTCt0aT1T1ueUiiRmn9+uO8++OYb+OwzOO886Dr1MElv4Kp6KZ5TF8lUVglrdyj8j7r//tCvX3ossUTBU/QlNdKtRkn6EWkt3E4RUVvTTlJVmjUo9PdywQUwbhwMGAA77ggXXQRLLdXqDMD+lQ/UcnIAbYyWt3N96gqsLeEGi5XqMApM7Rs6FE48Ea5se9VpT2CPemmwWCelNU8rUvq9C2DvCkdpjWsD0rKIVi68EL78EuaaC5ZbDtZaC/bdt9VhAraqbIjlURfJFGna1/RM0RNusNSsbJO3W4FzI+LvecdTQOs/cYA+fWCrreDoo2HUKHj6abjnHth552mP7Ans6Qp/jWeKjp4ChXA6LIB9yhORNROJ+UjFmFr1/N55J9x9NwzrWC3UrcscmtWGwh09Hb939QL2Q+rIGnWzaR1OkWRqwQXhlltg7Fj44gt48EFYeulWh/Vjiq0ealm9JFM708Z831NOga++gqeeStltEZOATSsQm02/s0jle0/LO5AidqDQqOhii8HEifDeez889+qrBa8IpAbz6hWKz/KzBunaUlQHrk+9gB0rEJs1vk2Zvo5GSPfWXcoQi9We7ShUrKtz966uwE8rFJ81qKwozloUKXhyzjmw/fbQuzfMPTcMGpQSqgIWz6p417R6SaYGFHvhiCNgoYVgnnng0kvh3nvTfxfQi1QF0GqIpF2A9YHdarjsauHdvGeYAb77burnvvsuzecqzN+/xjM7bVTH6sT1aaYKxWeNbXbSvW161XxjxUpSuGBS5+5dge9d1nkzQ/Eq2k88kXL3ESPgv/+FF1+Eu+4qeOg46uD7Vy/JVNE4n38+rZ8cNw6uuSaNVm+0UcFD1dZ5rPqyDd3+DGwZEd+1c3ieCn9vvv8eZpxx6udmnDFVGmjN37/G1IU2kqlOXJ/83bBSlOt74+9fY/K9y/LShSKj5hI89FCqf9K3L8w6a6qHclrhuUlBHXz/aj7ATMdmfQMR6RdVwFjSbstWAyTNDNwOHBARb+QdTzsK3mF4913o1g0WWeSH55ZdFt4o+ONMwt+/RvQNdHxT8DauTyPKFZA1lW9IPbflOI81nu8LPtu5e1fge5d13rcUKRo3yyww33xw/vmpo/Gbb1LF0SIdjT2og+9fvSRTd5L265lK//6w4YbQs2cqqTh4MKy5Zsp4Cwjg4QrHaR0gqQtwHXBPRNyUdzwdcB8wodWzLS2pa+X449OC3lVXhc03h2uvLXSOHqQNp62xPE2RG0Ynrk/job52e7ea8TBFkvmuXX/47k35/wsYBdxRwRgtPw9S6PvRuXtXd+CFCsdpDSaCMcBrhV4bNgw++AD22Sddk/r3h113Tcv2CvgCGFrBUMuiXpKpqyhQkaZ791T69auv4Ouv4YADYIstUqdLAa9H0HqXF8vDH0mLng/PO5AO+gvF5v7uu29aQfnll3Djjenq8Oab0x41AbiFCI8+NJhss9PbKdBg6cT1aQJwTqVjtcYTwRvAO4Ve++Mf0x5TRx2VirSNGZOeK6ALcE0Fw7T8nEWaldNax+5d44GriWjVmW3WAadRZGbPllvCwIHp/vj++zBhAhx0UKvDRgFnRkx3kZ2KU+2u+Z+axHXA9rSxn0sbvgd2i+D28kZlnSVpEHAZsFJEfJ53PB0mvQwsX+K7W4BViSjc72J1TWIF4EkK7PXTQc9H8LMyhmRNRGI70sasBUsQt2MCcH0Eu5U1KKsd0pvAkiW+ezSwPBEFE3aztmQV/b4CZmzv2CJGA3NG1P40+HoZmYI0mlF4/m/bxgJvAHeXNxzrLEkLkUYZt6+rRCrZl5QUdVYLcKcTqcYVwcvAvZT+/fCGzjY97oCvPy82ANGO74FjyhyP1Za9SY3SzmoBrnciZaWKYBx8fBSMaXP7kCJGAX+sh0QK6iiZiuBDYEPSkGFHh9PGAP8BBkYUWPNiVSOpN2k61EkR8VTe8XRaxD+BnejcTakF+Cfwq4rEZLVkF9K6gs4kVC3ADhFej2DTQ7+BxWeASZ+Q7nkdEaR76QYRfFS52Cx3Ef8g3YM6e+/6B95M3KaDpIVh/gPh9ichOntvvBI4uzKRlV/dJFMAETwPrAJ8QptJ1cRJpAvHE8BPs3UNlhNJAi4C3gTOyzmc0kXcCWwMfBvFKvwlY0mNmpuAXxBRdK8FawypB44NgFtIv/s2hglGTYL4FhgUwT1VCdAajqQukk4BDoRvVoPePwaegvHjYUKxDsfJSdTHwM8ieLFK4VqeIm4GtgC+o+1715jscTWwCRHuhLaSSFqZNP39rIgd1wb9lpQktbX+roX0/TsW+F09rJWarG7WTE1Jogup4XI4sBqp4ZLVop/YA25qgW1Xj+jeajWlVZ+kvYH9gJ9HIyxklXrcBEf/BA5eKnVIjCN9/7qSSqBfBFxAxCd5hmn5kJifNC10b9L3YyJpr5YeEG/AbnPAvXtFfPNAnnFa/ZLUg9RzuyCwWUQMy57vBst9AHe8CguuR1oTNYn0/etJGm04A3gkglKm3lg9k3oCWwJHAosx9b1rAnABcBER/80tRqt7kjYhXZ92j4h7f3iefqQZPkeQNhyf3NHcjbQ9yJnAkIjaL4U+rbpMpqYkMTswN2nx93fw1Ucwx7+BLcLrVHIn6Wek9SSrRcR7ecdTLpKuAN4MuBEYQGqoDAc+IKIc+75YncsW3y4EzETq8PkigqGSdgZ+FRHr5hmf1SdJ/UmlzL8DdoyI0VO8tj2wX0SsIdEXmB/oT+rx/W8EX+cRs9Ug6UfAHPywj88HnkVh00vSXqSRpc0j4vnCxyBgAWBWUofjN8AH9dzBU/fJVCGSTga6RsQRecfSzCTNAbwI7B8RDTOdSal37zPgJxHxad7xWH2R1B14H9g2Ip7LOx6rH0oN4PtJU9gPjIiJU7wm4BXgDxFxX04hmlkTyq4/JwDbAYMi4v2cQ6qquloz1Qk3Attnm8NaDtJ0E24CrmmkRCozCHjNiZSVIlLv75mkqQ5mHSJpGdLG39cAv50ykcr8gjRd6/5qx2ZmzSubdnwVafnNqs2WSEGDJlMR8Tpp/uWqecfSxE4izcFuxLK7g4Eb8g7C6toVwGqSSt3/xZqIpHWBR4DDI+LMKDyl5Ejg1CKvmZmVnaQZgfuAmYF1IuKrnEPKRUMmU5kbSY1eqzJJW5GGegcX6D2ta5L6kXqAvQG0lSwiWoDzgcPyjsVqm6TBpPvZthFxU5FjViGtj7q5mrGZWfOSNDepqM17wJbZfa0pNeSaKQBJCwLPAfOEF1VWjaQlSH9cG0VEw5XdzYoHbBsRm+Ydi9U3SbOQ1k4tG678aNPI1iAcRqqEulFEvNHGsXcBD0fEBVUKz8yamKSlSSNSFwOnNfuIeMOOTEXEf4D/A9bPO5ZmkY3a3AEc1YiJVGYHPMXPyiAivgGGAAflHYvVFkldSXvy7Uhag9BWIrUU8HPSd8nMrKIkrQU8CvwxIjy1mAYemQKQdACwckTskncsjS7rRb0Z+C4i9sg7nkqQNDtpOHuehtgvy3KXVWd7DVh08l5B1twk9SF12MwAbBUR37Vz/FXAuxFxchXCM7MmJmk7UkfPDhHxSN7x1IqGHZnK3AJslt2crLIOIu2pc0DegVTQ1sD9TqSsXLKKkHeSpnJZk5M0G6nQxEjS1L72Eqn5gE2BC6sQnpk1KSWHkCrRru9EamoNnUxFxBfA88DGecfSyLIh38NJvahj8o6ngiYvBDcrpzOA/SX1zTsQy4+khUmlzx8FdomObf59MHBFRAyvZGxm1ryyacd/AX5Fmnb8Wr4R1Z6GTqYyrupXQZLmIf0b7xwRH+UdT6VkPcBLAg/lHYs1loh4G3gS2D3vWCwfklYmfQfOiog/dGQNQjaKtQupkWNmVnaSepOWcPwEWN3FkgprhmTqDmBdSTPlHUijyTZquxU4PyIezjueCtseuL2DvcVmnXUqcIik7nkHYtUlaRNSVay9IuLiTrx1f+C2iBhamcjMrJlJmhV4GBgHDPQIeHENn0xlc87/DmyZdywN6M/AV6SGYKPzFD+rmIh4gVTcZIe8Y7HqkbQncBmwSUTc24n3zQDsS5oiamZWVtn2Qk8DTwE7RcTYnEOqaQ2fTGU81a/MJO0EDAR2jYhJecdTSVnp4dlI03DMKuVU4EhJzXJdblrZYu4TSPtIrRERz3fyFHsAj0fEe+WPzsyamaQVSUnUeRFxZKO38cqhWW7a9wErSpor70AagaRlgbNJO14PzzmcatgBuDkiJuYdiDW0R4AWUnU2a1DZ9OirgA1Ji7nfL+H9BwOnlT86M2tmkgYBDwL7exPwjmuKZCoiRgP3ANvmHUu9kzQzcDvw24h4Pe94Ki3bP8sb9VrFZUUHTgWOyr531mAkzQj8FZgZWCcivirhNDsCb0XES2UNzsyamqTdSZt/bxYRd+YdTz1pimQqcwNejzBdsulH1wD3RUSzrB9aGZgEvJx3INYU7gRmAdbMOxArL0lzA/8A3ieN6reUcI4uwBE0xzpVM6uCbNrxscDvgTUj4tmcQ6o7zZRMPQIsmO3lYaX5A6lH9dC8A6miHYAbOlKq2Gx6ZVNJTweOzDsWKx9JS5P2kLoJ2C8iJpR4qs2BEcBj5YrNzJpXVkH2CtJ+rKtGxLs5h1SXmiaZym5et5JKXFsnSRoI7A1sExHj846nGrKN6rbDVfysuq4FfiJpubwDsemXbWr+KPDHiDi11I6ZbOrnkUDJ5zAzm0xSP+BeYA5g7Yj4IueQ6lbTJFOZG4EdvR6hc7ISmVcD20fEZ3nHU0VrAZ9FxDt5B2LNIytBezZpOpfVMUnbkjrxBkfEddN5urWB/sBd03keM2tyWUG2J4CPgS0iYlTOIdW1ZkumngX6kHZytg7Idr++DTglIpqtNPhgXHjC8nEpsIGnJdenbA3CwaS9+NaPiEfKcNojgdNcptjMpoekJUnTju8gbRZe6rRjy6jZZgtIOoX0c3tNQjuyEbwrgN6kntWm+bJI6gkMBZaNiE/zjseaj6QTgVkjYp+8Y7GOy6YH/xlYHxgUEZ+U4ZwrAHcDC0fEuOk9n5k1J0mrkyoyHxERV+UcTsNotpEpSFP9dvDGmB2yB/BTYI9mSqQyA4HXnUhZjs4FtpM0Z96BWMdkI/k3A8sCq5cjkcocAZzlRMrMSiVpK9Jo1M5OpMqrGROK14GRwCp5B1LLJP0UOJFUwvf7vOPJwWBceMJyFBFfkqaZ/i7vWKx9kmYFHgbGAwPLtaG5pEWBdYHLynE+M2s+kn4HnANsGBF/yzueRtN00/wAJP0BmDsi9ss7llokaXbgReB3EXFXzuFUXVbh5lNgoYgYlnc81ryy4i8vkr6L3+UdjxWW/Z4eIE3FO6qc65okXQJ8HhHHlOucZtYcsllYZwCDSNOOP8o5pIbUrMnUQsA/4etNYdalSBWSRgEfAY9G0LSL8SR1Ax4Eno+I3+cdT6VJzAWsQ9ooNYCvYZmZ4N+bRMSmuQZnBki6jjTl9LS8Y7HWJK0I3EMq0nN+mc89F/AGsFhEfF3Oc5tZY5PUi1SJeU5Sxb5vcw6pYXXLO4Bqk+gNsRZ82A/6PwFMIP07TMwe4yTOBS6N4PM8Y83JCaSk4ui8A6kUCQFrkjYf3gAYB3Qn/dwT4KW+8H/PSawUwYs5hmoGcBrwN0nnRMSYvIOxH0gaRGqs7BURd1bgIw4ErnUiZWadIWkW0jYKnwG/8L2jsppqZEpiceBxYIbsUcxoUsN6cAR3VyG0miDpl8BfgJUi4qucw6kIiV6kfV/WIZXJL7LnWEwEjSWtWdk7gonVitFsWpL+CtwbEZfkHYslknYHTgJ+GRHPVuD8MwH/B6zgqTlm1lGS5idNO34AOMzbKVRe0yRTEksC/yQlUR0tvDEa+FUEN1cssBohaXHgSWDjiHgh73gqQaIHKZlejlTuvSNagL8BW0XgC5LlIitnezWwuPcEyVe2ZcQxwM6kNQjvVuhzjgKWiIhdK3F+M2s8kpYD/gqcGRF/yTea5tEU1fwk+pMa0f3o3M/cG7hSYuVKxFUrJM1AKpf5h0ZNpDJXkEoWdzSRgjR6tQGpsqFZLiLiKdJ0ja3yjqWZSepOuo5sDKxawUSqN6mK4+mVOL+ZNR5JG5I6fw90IlVdTZFMAbuRRqQKTunabjt48034/nt4/31YffWpXu5NWkfUkLJe1stJo3aX5xxOxUjMD2xNSo6mssQS8MgjMHw4vPcebLFFq7f3BQ6UmLHScZq14RTgyOxv1qosq/J5LzAAWCcivqjgx+0GPBcRb1TwM8ysQUjaFbiGtJ3NbXnH02waPpnKig0cRoFGNMD668Npp8GvfgX9+sGaa8IHH0x9CmAtiR9VPtpc/A5YFNi/wTfm3ZcCyXTXrnD33fDXv8Iss8Cee8J118Gii7Z6/yRgpyrEaVbM/aRiORsCSPSVmF9iEYnZsmudVUBWVe8J4GNg87LtvSf1QZoPaVGk2ZGUVVQ9DDi1LJ9hZg0rXTL0R+BYYO1sFoNVWcOvmZJYh1S2tmDBiaefhiuugCuvbPM0Y4CzIvhD+SPMj6Q1gVuAn0fEhzmHUzES3YGvofXI0tJLwz//mRLpyR56CJ57Dv70p1an+iiCBSoXqVnbpB47wRaHwi1fAWuRKlEGqRrll6T9RK6JwHtSlYmkJUgLua8ATpruTqc0srgOKWFaj6l/h8PuhUd2h4W/jFhtuj7HzBpa1vFyIbASsFFENGMF6prQ8CNTpC9Zz0IvdOkCK60Es8+epnd98gmcdx706tXq0F6khkvDkDQ3cBOwayMnUpl5ga6FXig0YUqCH/+44Hl+lFUDNKs6iZ/B2NPgyp9ArEdqfPcldRT1JH3PTwE+kzjGI1XTLyv88ThwXEScWIZEagXgQ9Lmvr+g9e9w7vVhx89gJaSTSRtumplNJVvrfjcwH7CWE6l8NcOFembSDauVAQOgRw/YemtYYw1YbjlYfnn44x8LnmemyoVYXZJ6kMqDXxgRD+UdTxX0h8Klzd9+G778Eg47DLp1gw02gLXWgj4FJ4Uyjgb6Hlj9kBgIPAqaG2ZQ4W4AIDXMe5NGPa52QlU6SVuRCvPsEhFXleGE65Iqps5HG2t4e0OXrtAD+C1wixMqM5uSpAHAY8AXwKYRMTLnkJpeM1ykR0PhktajR6f/Pe88+PxzGDYMzjoLNtqo6HkaxRnAMODkvAOpkjEUabhMmJAKTmy8cfoOHHII3HILfPppwfN0pbG+B1YHJFYAbqfIus8i+gJb4nU3JZH0O+Ac0maXfyvDCZch9SJ39nc4MIvDzAxJiwHPAPcBu0fE+JxDMpojmfqUIg3g4cPT1L4OTNwI0tSMuidpMKms7y5NtJHb56Se3oJefx3WXhtmmw0GDoSFFoLnny94aADuAbJqu4wijfB2KpH2BX4reZ1fR0nqIunPwF7AahHxSplOfSHp9/GDkSOnfkyYAOeeO+37+gK7k9ZtmVkTk7QKqRDOyRFxbIMXDasrzZBM3UmR9TIAQ4bAAQekdVMzzQQHHpgqu03je+DiikVYJZJ+Qurl3DIihuccTtVE8C3wFCkZamWZZaBnT+jdO41MzTUXXHVVq8MmADd4416rJomlgSULvdaBSqSQrvH7VzjMhiCpF3AjsDKwekR8VKYTLwysyLSj4/36/fAYMCBNlbj11kJn6Eaa8mdmTUrSFqTR7V9HxBU5h2PTaPhkKoLhpPVBBdfMnHACvPACvPsuvPUWvPIKnHRSq8NGAI9WNNAKkzQTaarQQRHxWs7h5OEMiFGFXth5Z/jss7R2ar310rqpceNaHTYO+EuFYzSb1oEUWfN53HFw/PGp8mQEDB2aHtPoAewpFS7CY4mkmYGHSAnPhhHxTRlPfwApISpu663TBejJJwu92h3YFalvoRfNrLFJ2g+4ABgUEQ/kHY+11vCl0QEklgOepnPz1TMtAZc/Db8bVLa9RapMaQHzXcBHEXFAzuHkQurzM/jgKZijWwl9CBOBVyNYsQKhmRUl8RUw27TPd+mSBjL+9Cf4zW9SBdK77kqFVMaMaXWaEcAmERRsqTc7SfOTSp8/ABxW9unP0qfAPG0e88gj8I9/pAy5sO+AbSnH+i0zqwtZ2+0UYHNSIvWfnEOyIhp+ZAoggn8BJwAFRybaMAa6/QMO+Q/wL0lrlD246jgKmBU4JO9Aqk1ST0knweh74Ng/QJfOfgeC1BjdqgLhmbWnX6EnO1mJNEh//zYNScuROtoujYhDKrSOtH+br847byohevXVbR3VBZilnEGZWe2S1BO4DlidtH7TiVQNa4pkKnMaaZpWSwePbwGehR4bR4zfBTgYuFnS2ZJ6VyjGspO0IbAfsE1EtJ681sAkLQ+8APwYWDbi4tOBQaQiEh1pNE0EvgHWjmiMAiTWGDpXiXR4f9jiTknhx9QP4BXSqNHZlfqMkUU2jP+fXXaBp56CDz8s63fEzOpTtizjAdLec+tHxLB8I7L2NE0yFUFE8EdgF+A90ihVoQb1SFID+mRgw4g0mhUR9wDLAHOSRql+XpXAp4OkBYBrgB0iovVqigYlqbukY0hrIM4Atpi8oV021Wll4EFgLKls+rRasudvB5aLoBnXmFltKFg9shOVSIGZRsBda0aE/EgPYDfgS6Di/y794L9t/np22aW9USlI96pyruMysxokaV7SfnSvA9tGhLdjqQNNsWZqWtlGliuTRptWJE2lGU0qf34O8NcIJhR/v7YGzgeuAo6NiEIN8lxllameAq6PiLPzjqdaJP0YuJrUUPpNRBRtyEjMTSqBvDVpM95JwLfAtcCVEbg3yHIlcRmp4d+qgMFxx8GgQWmPtPHj4Z574PHH0zqqaYwEZo9gbKXjrXWSBPwB2B3YKCLeqsKH/gXYl0KFRFZZBR5+GOacM9W3L64FmIMoXETHzOpfVnH5PuBs4GyXPq8fTZlMlYOkOUjl0hcn7dn0Us4hTUXS5aQkcftm+IOU1A04jJQgHwlc2Qw/tzW2rDT6C0CrqcXdusE558DgwanoxC23wOGHw9ipU6ZxwHkRHFqdiGtXdo24EFgJ2DgiPqvSBy8M/Bvo1eq1iy+GPn3S6FRx44HLidi3MgGaWd4krUfamuGAiLg573isc5xMTYesl3MHUi/CJcCJtbAuSdJvSEnFT+u1AmFnKG1oeRVpP7Ddo1z7w5jVAImXgBVKfPsYYMlmX/OnVFb8ZtII3zYRUd3Nt6UngdWYdq+pjhkNLE/EO+UNysxqgaSdgD+TpvU9kXc81nlNs2aqEiK5AVie1Nh5TtKyecYkaWXSeq9fNnoiJamrpINJ0xmvIe0P40TKGs0edLxwzpRGAec6kdIA4HHS1N9Nq55IJfvQ+WqyZO+5womUWeNRchRwErCuE6n65WSqDLLiDpsC5wJ/l/THbEpJVUmajbRB8V7R4DdfSYuQGkhbAD+LiAujMmWNzXIVwcuk0vydSahGAXeQprw2LUmLAc+Q1iHsHhHjcwkk4t/AZnQuoRpFquj1u4rEZGa5kdSVtBHvdsAqEfFGziHZdHAyVSbZKNUQ0gjVGsCzkpaq1udnf5g3AjdFxJ3V+txqk9RF0v7AP0nV9taOiP/LOSyziorgQWBdUmW470l7RxUyijQt7HRg14iixzU8SasA/wBOjohjc19DGfEYsCbwMW3/DidXEz0X2A53Epk1FEl9SJ1di5IqijZNteVG5TVTFZCtpdqTNHR7OvDniJhY4c88Cfg58IuIKFqJsJ5lpd6vJC3G363RR9/MpiXRBVgPOBxYi1ScYBLQA/ictBXANRGMyC3IGiBpC+AyUnGgB3IOZ2rp/rA2qWDO+vzwO+wODCP9Dq8iYnhOEZpZhUiaHbgXeAfYoxbW2dv0czJVQZIWJDX+e5Ia/+9W6HM2B84DVoqILyvxGXnKktM9SMnpGVQhOTWrdRJ9gVlJidS3wDfNPBI1maT9gN8Dm9ValdVWUg/1rKR7xHBgGL4pmzWkbHnCA8BNwJ9yHy23snEyVWGSugD7AccAJwDnlXNtT7Ym4Clgk4h4vlznrRWSfgRcDswG7Op5xWZWSHatPQXYHBgUEf/JOSQzMwAk/Qy4i7Q36SU5h2Nl5mSqSiQtSirfPQH4VUR80N4bSPPrlwZmJK2F+BB4kGwRdVbu9zlSglaTf5wSPwI2BGbJnhoGPBRBm3OEs9GoXUnTJM8FTstt8biZVVf6+1+JtKl6f9Iaov8C9xExusDhPYEhwPykESlvuG1mlSHNCmwEzA50Jc0MeJyI9wsfrs2AK0htv79WLU6rGidTVZQViTgQOAo4Grik1SiV1B/YDTgUmIn0h9qdlISNI82tv2A0XNQnTXkbC/y6loaLJURa13EYKSGcQJrGAine7sAjwJnA49NOTZI0F3ApMB9pzcOrVQrdzPKUpr1tDxwBzEMqktQdmEi6/ok0dfq8yQ0XSTORFnMPB3aMAsmWmdl0k34KHEKqzDme1K7pQmrXdAVeInUA30e2FEHS3qSZSZs34uwhS5xM5UDSksDVwAhSIvRx9sIKwMOkP9C+bZxizHjo8mv49Dr4cS01HiR6kcqzr036GYptUhmkqlUPAYMjGDvNJsiXAid4caZZk5AWJm13MBMwQxtHjiMlVwcrlTy/H3gMOMhrKc2s7FJH+PnALkAv2q6E/T3w+nAYNHMqFLQNadqxqw43MCdTOcn2oTocOAg4cjy82i01CNpKQKYyCcZ0gd2IuLmCoXaYRA/Sz7A8qeJeR7QAL8Byg+HV84AlSMU6XqhQmGZWa6SFgBdJU/o6tGXHRBjzJxhzMpwInFVLo/Nm1iBSJ++NwCa03cn9PwFjh8LYH8Pbw9N69q8qGaLlz8lUziQtMxdc/w4s0S9NZ+msFmANIl4ud2ydJTEE2Bbo07l3ThgL10yE3c8HjomIMRUIz8xqkdQLeA+Ym07ufTgBxnWDzYl4sCKxmVlzk35Pqg7aoURqsnEwqQs83i1ivcoEZrXEm/bmLCJe/whu71VoNGrkyKkfEybAuedOe1Rv0nzcXEnMTVrr0CqRmn9+uO8++OYb+OwzOO886Np1yiO69YTdukGc6UTKrOlsS5ra1/p+NPPMcMcd8P338OGHsMMOU73cLZWFP7UKMZpZs5F6k9a4T51IdaBt1gO6dIOfI/2kegFbXpxM5U3q2h0O6A7dWr3Wr98PjwEDYPRouPXWVmcANkSasxrhtmHvYi9ceCF8+SXMNRcstxystRbsu++0R3WZCPymkgGaWU06gmJrpC64AMaNS9e/HXeEiy6CpZaa9qhF3WAxswrYBgrs3dexthmkzp4DKxui1QInU/nbiPQH17att04ZyZNPFjtiz3IG1RkSXYH9SQszW1lwQbjlFhg7Fr74Ah58EJZeutVhvYGDJH8nzZqGtDywQMHX+vSBrbaCo4+GUaPg6afhnntg552nPbIHae2pmVk5HQ70a/OItttm3YDtkdo+h9U9N1zztyJtV65Kdt0Vrrmm2Ku9gNXLGFNnDaBIIgVwzjmw/fbQuzfMPTcMGpQSqgL6k6b7mFlzWIFCPb8Aiy0GEyfCe+/98NyrrxbqiekGrFKh+MysGaXCE0u0e1zbbTNIJdQXLVNUVqOcTOVvNtqr3jfvvGlu3NVXt3XUzOUMqpP6k/aSKuiJJ1L7Z8QI+O9/4cUX4a67Ch46PjuXmTWH/hQrvDPDDPDdd1M/9913aWpNa+75NbNyKtpB/D8da5sFbtc0PCdT+RvZ7hG77AJPPZUWYBfxBKwkKfJ4wAJvwvcFGzMSPPRQWkPety/MOmtaU37aaQV/jC5AzeyZZWYVN5q0Z1Rr338PM8449XMzzpgWfLfmwjVmVk5jaa+N3IG2WcbtmgbnZCp/H5PKmxe3yy7t9XxMWguGRITyeMCHfWGGsYUCm2UWmG8+OP/8tI78m29gyBDYaKOCP0cX4JuO/bOZWQP4hDQi3dq770K3brDIIj88t+yy8MYbhY7+uBLBmVmTipgEfNvmMe23zQB6Av8tU1RWo5xM5e8W2vo9rLIKzDNPsUoxk40GLilzXB0WQQtwPzBp2teGDYMPPoB99knl0Pv3T1OMX3211WkmArdHMK7yEZtZjfhb0VdaWtKQ9vHHp2IUq64Km28O11477ZEjgfMrGaSZNaXLSCNUrXWsbQbwGhGflDswqy1OpvIWMQy4hwKJCJAyj8n7rBQ3FHi+/MF1ypkUGcrecksYOBC++grefz9tyXBQ69pbY4GzKhyjmdWSiHHARRRrsOy7b6pc8+WXcOONqVfmzTenPWoi6RpqZlZOF1KsQE7H2mYjgdMrEJfVGEUU/p5YFUkrAU9QYMPbDhgFHEDEkPIG1TkSAt4iVa3pbJI+EXgzAu8VY9ZspPmAt0nbI3TWaOAMInLfuNzMGpD0ILAuxQrltO1rYG4iCk9ltobhkalaEPEicDIpMeqM0cCDwFXlDqmzIghgU6DNbppCbyX13mxe9qDMrPZFfAzsRXtrR1sbC7wCnFT2mMzMkp1JSVHhQjnFtQAbOZFqDk6masfJwF/oeINiFCmRGkyNDC9G8B6wNmnRZkcuPBNIBSfWiuA/FQzNzGpZxLXAwXS86lUL8BIwKJsqaGZWfhFfAauSllN05FoTpE7lTYh4oZKhWe1wMlUrIoKIPwI7Am+QGgvTJiSTR3GGAkcAW9daQyKCV4DlSIU1xlA4ORyVvXYjsGwEr1UtQDOrTRGXABsBz5GSqkI9uiOBYcApwNpEjKhegGbWlCI+JLVrriS1XwrNwBmTPe4FfkrEY9UKz/LnNVO1SloB+B2wAmlDyhbgfeBc4JFaGY1qi8TMwG7AYGAWUjI4DLgBuDqC4bkFZ2a1S1qcdP1bjbTh5RhS+fMLgPuIKLpJuJlZxUh9ge2BXwNzAF2B4cDdwCVEfJ5fcJYXJ1NmZmZmZmYl8DQ/MzMzMzOzEjiZMjMzMzMzK4GTKTMzMzMzsxI4mTIzMzMzMyuBkykzMzMzM7MSOJkyMzMzMzMrgZMpMzMzMzOzEjiZMjMzMzMzK4GTKTMzMzMzsxI4mTIzMzMzMyuBkykzMzMzM7MSOJkyMzMzMzMrgZMpMzMzMzOzEjiZMjMzMzMzK4GTKTMzMzMzsxI4mTIzMzMzMyuBkykzMzMzM7MSOJkyMzMzMzMrgZMpMzMzMzOzEjiZMjMzMzMzK4GTKTMzMzMzsxI4mTIzMzMzMyuBkykzMzMzM7MSOJkyMzMzMzMrgZMpMzMzMzOzEjiZMjMzMzMzK4GTKTMzMzMzsxI4mTIzMzMzMyuBkykzMzMzM7MSOJkyMzMzMzMrgZMpMzMzMzOzEjiZMjMzMzMzK4GTKTMzMzMzsxI4mTIzMzMzMyuBkykzMzMzM7MS/D97sme0/9yH+QAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 1080x288 with 3 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 生成一个有 10 个顶点的图形\n",
    "n = 10\n",
    "G = nx.Graph()\n",
    "G.add_nodes_from([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])\n",
    "G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (1, 7),\n",
    "                  (5, 6), (6, 7), (7, 8), (8, 9), (9, 0)])\n",
    "    \n",
    "k = 9 # 设定量子比特的最大数量\n",
    "S = NaiveLGP(G,k) # 利用大图分割对图形 G 进行分割\n",
    "sep_node = list(set(S[0].nodes).intersection(set(S[1].nodes))) # 找到分离顶点\n",
    "\n",
    "# 图形示例\n",
    "options = {\n",
    "    \"with_labels\": True,\n",
    "    \"font_color\": \"white\"\n",
    "}\n",
    "node_color1 = [\"red\" if i in sep_node else \"blue\" for i in range(n)]\n",
    "node_color2 = [\"red\" if list(S[0].nodes)[i] in sep_node else \"blue\" for i in range(len(S[0].nodes))]\n",
    "node_color3 = [\"red\" if list(S[1].nodes)[i] in sep_node else \"blue\" for i in range(len(S[1].nodes))]\n",
    "\n",
    "fig, ax = plt.subplots(1, 3, figsize=(15, 4))\n",
    "for i, a in enumerate(ax):\n",
    "    a.axis('off')\n",
    "    a.margins(0.20)\n",
    "nx.draw_networkx(G, pos=nx.circular_layout(G), ax=ax[0], **options, node_color=node_color1)\n",
    "nx.draw_networkx(S[0], pos=nx.circular_layout(S[0]), ax=ax[1], **options, node_color=node_color2)\n",
    "nx.draw_networkx(S[1], pos=nx.circular_layout(S[1]), ax=ax[2], **options, node_color=node_color3)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "值得提醒的一点是，我们的例子中 $k=9$，``大图分割``得到的两个子图的顶点数都小于或等于 $k$，那么两个子图的最大割问题可以直接被``量子近似优化算法``解决。但如果得到的子图的顶点数依然大于 $k$，那我们将对子图重复之前的做法，直至所有的子图顶点都小于或等于 $k$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 图形重构\n",
    "\n",
    "当``量子近似优化（分治）算法``被应用到分离的子图上之后，所有的顶点会被分成两个部分，即 $S_0$ 和 $S_1$。我们需要将子图的最大割进行整合，得到母图的最大割。因为两个子图有共同的顶点，即分离顶点，我们要确保它们所在的最大割集合吻合，即 $S_0$ 还是 $S_1$ 需要吻合。比如，如果对于一个子图来说，分离顶点在它的最大割当中所在的分割集合都是 $S_0$，而另一个子图的最大割中，分离顶点们在的分割集合是 $S_1$，那么相应的两个最大割将不能被整合。所以为了解决这一问题，对于每个子图，我们将提供多个可能的最大割，从而在这些可能的最大割当中寻找可以整合的且可能性最高的进行整合，从而得到母图的最大割。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-16T03:41:46.108438Z",
     "start_time": "2021-05-16T03:41:45.970323Z"
    }
   },
   "outputs": [],
   "source": [
    "def GR(str_cnt1, str_cnt2):\n",
    "    com_cnt = []\n",
    "    n = len(str_cnt1[0][0])\n",
    "    com_index = []\n",
    "    for i in range(n):\n",
    "        if str_cnt1[0][0][i] != \"x\" and str_cnt2[0][0][i] != \"x\":\n",
    "            com_index.append(i)\n",
    "\n",
    "    for (str1, cnt1) in str_cnt1:\n",
    "        for (str2, cnt2)  in str_cnt2:           \n",
    "            # 检查分离顶点在两个子图所在的集合是否一致\n",
    "            validity = [str1[i] == str2[i] for i in com_index]\n",
    "            if False not in validity:\n",
    "                com_str = [[0]] * n\n",
    "                for i in range(n):\n",
    "                    if str1[i] != \"x\":\n",
    "                        com_str[i] = str(str1[i])\n",
    "                    else:\n",
    "                        com_str[i] = str(str2[i])\n",
    "                com_cnt.append((\"\".join(com_str), min(cnt1, cnt2)))\n",
    "\n",
    "    # 将{最大割：频率}按频率从大到小排列\n",
    "    com_cnt.sort(key=lambda tup:tup[1])\n",
    "    return com_cnt[::-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们将延续上述10个顶点的圆的例子对``图形重构（graph reconstruction, GR）``进行说明。对于所分得的两个子图，我们先用``量子近似优化算法``求解最大割，再用``图形重构``将子图的最大割整合，得到原图的最大割。下面所给的代码实现了这一步骤。代码中的参数 $t$，代表想要保留最有可能的最大割的数量。如果 $t$ 大于 $2^n$，那么所有可能的最大割，即所有可能的顶点分类，都将被保留用于整合。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-16T03:42:41.303385Z",
     "start_time": "2021-05-16T03:41:47.071053Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "第一个子图的最大割：\n",
      "{'01101010xx': 0.07865697145462036, '10010101xx': 0.07865697145462036, '01010101xx': 0.07865694910287857, '10101010xx': 0.07865694910287857, '01010010xx': 0.04094246029853821, '10101101xx': 0.04094246029853821, '01011010xx': 0.04005919396877289, '01010110xx': 0.04005919396877289, '10101001xx': 0.04005919396877289, '10100101xx': 0.04005919396877289}\n",
      "第二个子图的最大割：\n",
      "{'1xxxxxx010': 0.4556591808795929, '0xxxxxx101': 0.4556591808795929, '0xxxxxx011': 0.025223204866051674, '1xxxxxx100': 0.025223204866051674, '0xxxxxx110': 0.010825536213815212, '1xxxxxx001': 0.010825536213815212, '0xxxxxx111': 0.002283714711666107, '1xxxxxx000': 0.002283714711666107, '1xxxxxx011': 0.00228371424600482, '0xxxxxx100': 0.00228371424600482}\n",
      "母图的最大割：\n",
      "{'1010101010': 0.07865694910287857, '0101010101': 0.07865694910287857, '1010010100': 0.025223204866051674, '1010100100': 0.025223204866051674, '0101011011': 0.025223204866051674, '0101101011': 0.025223204866051674, '1010110100': 0.025223204866051674, '0101001011': 0.025223204866051674, '1001010100': 0.025223204866051674, '0110101011': 0.025223204866051674}\n"
     ]
    }
   ],
   "source": [
    "# 我们利用 量子近似优化算法 计算上面例子两个子图的最大割\n",
    "# 在下一小章中，我们将使用 量子近似优化分治算法 计算子图的最大割，因为子图顶点数量有可能超过量子比特的限制。\n",
    "import paddle\n",
    "from paddle_quantum.QAOA.maxcut import find_cut\n",
    "\n",
    "# 设定 量子近似优化算法 中的参数\n",
    "p = 3     # 量子电路的层数\n",
    "ITR = 100 # 训练迭代的次数\n",
    "LR = 0.5  # 基于梯度下降的优化方法的学习率\n",
    "# 设定 图形重构 中的参数\n",
    "t = 10    # 想要保留最有可能的最大割的数量\n",
    "paddle.seed(999)  # 固定随机种子\n",
    "\n",
    "# 图形重构完整过程\n",
    "S_str_cnt = []\n",
    "for si in S:\n",
    "    siv = list(si.nodes)\n",
    "     \n",
    "    # 计算子图的最大割\n",
    "    tmp, si_str_cnt_relabeled = find_cut(si, p, ITR, LR)\n",
    "    \n",
    "    # 填充子图的最大割结果，使它们和原图的顶点数量和顺序吻合\n",
    "    si_str_cnt = []\n",
    "    for str_relabeled in si_str_cnt_relabeled:\n",
    "        strr = \"\"\n",
    "        for i in range(len(G.nodes)):\n",
    "            if i in siv:\n",
    "                strr += str_relabeled[siv.index(i)]\n",
    "            else:\n",
    "                strr += \"x\"\n",
    "        si_str_cnt.append((strr, si_str_cnt_relabeled[str_relabeled]))\n",
    "    si_str_cnt.sort(key=lambda tup:tup[1])\n",
    "    S_str_cnt.append(si_str_cnt[::-1][:t])\n",
    "\n",
    "# 当子图的最大割被找到之后，我们开始图形重构这一步\n",
    "print(\"第一个子图的最大割：\\n\" + str(dict(S_str_cnt[0])))\n",
    "print(\"第二个子图的最大割：\\n\" + str(dict(S_str_cnt[1])))\n",
    "out_cnt = GR(S_str_cnt[0], S_str_cnt[1])\n",
    "print(\"母图的最大割：\\n\" + str(dict(out_cnt[:t])))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "就以上例子来说，对于第一个子图而言，最有可能的几个最大割将包括 {'01010101xx', '10010101xx', '01101010xx', '10101010xx'}，而第二个子图最有可能的最大割将包括 {'0xxxxxx101,'1xxxxxx010'}。这些字符串中的 'x' 代表不在这个子图却在母图的顶点。\n",
    "\n",
    "从这个例子中我们看到，分离顶点 0 和 7 在第一个子图中可能的最大割，'01010101xx' 中分别属于 $S_0$ 和 $S_1$，它们在第二个子图的最大割，'0xxxxxx101'，中也分别属于 $S_0$ 和 $S_1$，所以我们可以整合这两个最大割并得到母图的最大割，'0101010101'，如下图第三张图所示。\n",
    "\n",
    "以下为图形展示，前两个图为两个子图的最大割实例，最右的图为母图的最大割。红色点和蓝色点分别表示被分在在 $S_0$ 和 $S_1$ 中的顶点，虚线表示被切割的边。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-16T03:42:41.647686Z",
     "start_time": "2021-05-16T03:42:41.309407Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA1MAAADnCAYAAAD7CwxiAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAABKBklEQVR4nO3dd5xcZfXH8c832XRC6KF3ECkSsCBICdKrCJEeQFCE0KXZ6CAgCCJVftJBFJAqCgLSLVQR6R2kSgtJNj3n98dzYza7M7uzk5m5U77v12tf4p07d85mZu/cc5/nOUcRgZmZmZmZmfVOn7wDMDMzMzMza0ROpszMzMzMzMrgZMrMzMzMzKwMTqbMzMzMzMzK4GTKzMzMzMysDE6mzMzMzMzMyuBkyszMzMzMrAxOpszMzMzMzMrgZMrMzMzMzKwMTqbMzMzMzMzK4GTKzMzMzMysDE6mzMzMzMzMyuBkyszMzMzMrAxOpszMzMzMzMrgZMrMzMzMzKwMTqbMzMzMzMzK4GTKzMzMzMysDE6mzMzMzMzMyuBkyszMzMzMrAxOpszMzMzMzMrgZMrMzMzMzKwMTqbMzMzMzMzK4GTKzMzMzMysDE6mzMzMzMzMyuBkyszMzMzMrAxOpszMzMzMzMrgZMrMzMzMzKwMTqbMzMzMzMzK4GTKzMzMzMysDE6mzMzMzMzMyuBkyszMzMzMrAxOpszMzMzMzMrgZMrMzMzMzKwMTqbMzMzMzMzK0JZ3AJYfiVWAPYFlgcHAR8CDwG8iGJ9nbGbWuiSGArsC6wLzA+3Aq8BlETyXZ2xmVr8klgL2Bj4PDAU+AR4DrojgozxjK5k0EBgFbAwsCEwG3gSuJuKxPEOzwhQRecdgNSQhYHvgh8DKQD9mT6rHk0YsrwJ+FsGrNQ/SzFqSxHLA0cDuwAxgSIeHpwLTgH8DpwI3R+AvMDNDYiPgR8A6pGuY/h0ebs+23QL8NIJ/1T7CEkiLAocD3822DO3w6AxgEvAGcDopsZpe2wCtGCdTLUSiDbiUlEwN6WH3qaS7IdtGcG+1YzOz1iaxMXATMJCeZ01MAK4D9o1gWrVjM7P6lN0gPhH4PmmGTXemk65rvhPBtdWOrVekNYG7Sddm/XvYewJpFtH2REysdmjWMydTLSI74VwLbEPPJ5yO2oHNInioKoGZWcuTWB/4E70/N90EjPYIlVlrkjgFOISebxB31A7sFcH11Ymql6RVgL8BcwEq8VkTgUeAjYnwDaWcOZlqERJjgJ/RuxPOTJ8BS0fwSWWjMrNWJzEf8DqzT2kp1QTg8Ah+VdGgzKzuSWwJXE/vbsLM1A6MiOClykbVS1J/0tS94ZSeSM3UDpxLxA8qHpf1iqv5tQCJPsBPKJBIXXUVvPMOjB0LL7wA++xT8BBtpEIVZmaVtg/Qt9ADK60E99wDn34KL70E223XZZchwDHZyLuZtZbjKJBIlXhd0w84tLrhlWQ70nls9nNY//7w61/D66/DZ5/BE0/A5pt3fu5g4ACkQbUI1IpzMtUaNiYNH3dx6qmw9NIwbBhsuy2cfDKsuWaX3QYDR/qCxcwqKbvRU3CtQ9++cMst8Ic/wHzzwb77wtVXwwordDnMMGDD6kdrZvVCYiVgtUKPlXhd0w/YSyprtk4l/YBCo/JtbfDWW7DBBukXOeYYuO46WGqpQsfYsdpBWvecTLWGQymSTD37LEyZkv47Iv0st1zBYwwF1qtOeGbWojagyNTjlVaCRReFs8+GGTPg3nvh4Ydh9Oguuw6hPu4wm1nt7EeRQjW9uK6ZAexQpfh6Jq0IrFTwsfZ2OOEEeOON9Avcfju89hp88Yud95yLdEPKcuRkqjWsRDdzcc8/HyZMSMPh774Lf/xjwd36AMtXKT4za00rUGSKnwqcsSRYddWum0k9ZcysdXyBNLpUUInXNXOR73XN8sCUkvZcaCFYcUV45plCjy5dwZisDE6mWkO3izMPOACGDoV114Ubb4TJkwvu1gbMXY3gzKxlDaXI3eXnn4cPPoAjj0wzXjbZJM14GVz4bJb3VB0zq61uC9aUeF0DPL2mpOjwsy9Ap223Zdtu67g927Zvp323kbRop20XZ/s+3mHbO8Bck1IriO61tcE118AVV6TssKuej2FV5WSqNUzoaYcZM9IUmsUXh/33L7jLNGBspQMzs5b2GRTuEzVtWio4sdVW8N57cPjhacnAf/5T8DjjqxijmdWfz3raoYTrGmC1xyNCHX4uBui0bZts2zYdt2fbLu60720R8U6nbftm+36xw7ZFgXEDUyPe4qRUUWPKFDjwwGJ7uddUzpxMtYR4Nk267VlbW9G5xQG8WMmozKzlvUhat1DQ00/DyJGwwAKpkNWyy8Ijj3TZLYBnqxeimdWhf1LiFLlurmvGk+91zYv01KD3kktg+HDYYYd0h6mwVysdmPWOk6kmJmkJSfPDdbcUGpxacEHYaScYMgT69IFNN4VddoG//KXQ0cZOhT6HS/qmpAFVD97MWsEDdDPivdpqMGAADBqURqYWWQQuv7zLbhOAs6oXopnVoQspcCOmd9c1ANxYzSC7FfEK8HTRxy+8ED7/edhmG5hUdABrHPDzKkRnveBkqslIGiJpL0n3kO7cfBmeuwSGvNN534g09P2f/8Ann8CZZ8Khh8Ktt3Y57ASY9lOI20mdxt+SNFTSIKnQMnEzs55FEMCZpOaTXYwenRaPf/ABbLRRWjc1peu96I+AB6sbqZnVkwhehniiwPZSr2umAJdE5D5F7mekhGh2Sy4J++0HI0akec7jxqWfXXedbbdsytEN1Q/TuqMobfaX1TFJfUm9pF4BJgPnA1cCf4iISWkfvgucTXkLtT8FlopIc5QlLRwR70k6BhgNXAVcHRGvzenvYmatRWIeiNdBw3r/7OmToO+YCC6rdFxmVr/Sjdy/7gRrXA0DC1YE7UE7sFpEzlPkpDbgdWARejnAMRmmnQMTjoZREXF3NcKz0nhkqoFJWkDSmcBbwEnAIhHxVkRsGxE3zEykMr8GrqfIHeButAObzUykACLivew/TyYlU8OB+7NRsSWkci6KzKwVRfAp3D0aphRdEFDYtMlwNdD2cTXiMrP6I6mPpEOBSyLW/i0MPJ4Simx1MhHYNfdECiBiGrARaf1Wb0Y3Jg6Ae06AXYCLJC1SlfisJB6ZajCSFgZ2Bf5Bmmt7NGlU6Lmen0tf0qjV7vQ8QjWFVGVmywgeLiGuPhExIzvJHQ/cQRoduzMipvf0fDNrPZJWIJ3D9oX4GnA7MICeFmWni6fLYfCVMPFmYLuI6FqawsyahqTlgMtIAwF7RcTLEiKdQ44BBtFNT01S5dApwO4R3FTteHtFWhW4l9T7qqdS5xOAPwO7EDFZUltETJN0LHB/RNxf5WitE49MNQhJi0j6E/AcsCrwWUR8FhE/LiWRAohgOrA/sCNpjcEkulbDGZf9nA+sWkoilY4dM7L//QWwLHAfcCDQR9JXJK3h9VVmNpOkr5IKUPw9ImZE8CDp3HYB6S5t53LnM2/w3A98K4IDI9ofAdYAHpX0OUn+TjNrMh2uHTYGbgE2iIiXIa27jOA0YFPSzZhJdC03PoE0GnUl8MW6S6QAIv4NrExaQ/UJXddRTSP9Dk8AewOjiJicnhozR/X/CVwr6ReSuu0vapXlkak6lV0UrA/sQRrluQnYAbg1Ino7Va/Ia7AcaZRqGdJI1X+BvwHXR/TQ+6BXr6M9gBNIJ7QrgbMjYmqljm9mjUXS0sAjpLvLf+z6OIOAbwFfBRYknTteBa6KoMvazOxi6w7gQ2DvyC4yzKyxSVoSuBQ4PSLu6nl/FiEtP/gcMIxUoOZJ4DcdlyvUNakfsC0wkrSMYhLwJnAtEc90/1TND5wLPBkRZ1Q5Uss4maozWRK1EGka36ek5OOaDuuUGlL2e30N2AL4MbA9MBi4KSLccNOsRUhaLiJekbR4RBRuwVvecQcD15AuoLaPiE8rdWwzq63sBsnewGmk0t9ndhiBsR5k11zrkJKyYzutobcK85SIOpAVkjhQ0iPAwcD7wJYRsXpE/LzREylI0wAj4sGI+FGkDH4csBPwH0lXKFW0MbMmlS0cPw24KZvjX7FECiAbsR9FGl2ft5LHNrPayRKBvsDawIYRcZoTqd7Jll68CCwHPC7pSzmH1NQ8MlVI+kPeDDgK+DJpUeM00jzWS4ELmMMLgazx7SCgDXgJ+CNpFOqeVjppSFqIdLL8naSjgPmBK6OHoewSDtyHVCHnSNIJeTAwnfQeXk56D9+Yo9cws5Jk57tLSVOKt42ID6v8egIuAs6LiOJNMc2sbmR/t7sDhwJrtdK1ULVk/6Y7A2OAkS4IVh1OpjqTdiMNKQ8GhhbYY+ZQ6f3At4l4t/RDS6QL+z1Id1CPiYgLJQ2KiLwbx+VO0ueBPYHdSOXe1wUievshlb4F/IL0/s1F1+o+k0klSB8mvYdvzVHgZtYtSQsCxwJH1epcJ2kX4Bxg54j4Sy1e08zKI2k48CtSAas9I+LJnENqKtn1Zz/gCtL6s3/mG1FzcTLVkXQS8H1SItWTmSNV6xHxQveH1bKkKZUfkkpfXkdaB/XmnAXcnLImxCtHxNOSfgUsThq1u7XHCzHpR6Q1WaW+h2OBkVklHTOrIEmLA8cBB0RE58qhtXj9DYHfke7IPlvr1zeznmXT/Fcj3WQ+0QVkqiNLqPYAziAVqTjNxcAqw8nUTKk/0imUdhE+U5Aq4K1Op3VNkgaSPrR7ACsC34+IqysTbOuQNAT4JunfcRnSv+V8wCczy7F32Hlf4Gx6/x5+DIyY06mbZjaLpNVIpYp/Cfy81yPMlYtjUeBdYHng5bziMLPZSVqA1ArhmYg4Ie94WkV2k+v/gFMi4qG842kGTqYApCVIC/V6apRWyFTgFiK+pVTOcnPSaMffSR/WG4A7nP3POUlzRcR4SReR/p2vAq6KiBdJUwRep7z3cBpwFxFbVi5as9aVTdn5F3BIRPy2DuLpQ5rW+wRwsNcNmOVL0nbAhaQKnMd4qUNtSVJEhKTDSWv3z/R5sXyu5peMofuu2bD88jBxIlx1VedH+gVsvYx0MfA2qRP3kIiYEhF7RsRtTqQqo0MJ9f2B7Ui9sS6RpOfgmIK3Bfr3h1//Gl5/HT77DJ54AjbfvPNebcCGpDvYZjYHJC0dEe8DX66HRAr+V9lqc1Lvmd+7oaVZPiT1z/5zWeBbEXGEE6na6zBC/3tSwbWHJH0ux5Aamkem0h/2B6TeJMXdeScMGgRvvAGjR8/2UMDEG+AvO6a7sK9UL1grSOo7AcYNSdURZzd4MBx5JFx+Obz5Jmy5JVx7Lay2WnovZ5kEnEnEMTWK2qypZPPxjwT2BVatx74m2YXcaaRph2/nHY9Zw5GWI/2Nr0Iq8jSWNOL7f/TwNyVpS9Jo1Prharp1Ixu53x/4XEQc3PP+DCUVCtuEVIF5EvAGcBnwjwhaLrFwMiVtBNwIzF10n512gu23h2efTSNUnZKpzMtErFClKK070jrAHRSuvtjVU0/BCSfAjTd2fuQ/RCxR4ejMml5WNOYcYD1Sj7y6TlSyeC8AfuYbYGYlkDYFjgG+RJrV1L/DozNvnNwHnEjE32Z/qoaSKuxuCOwdEfdVOVorU1Yw7UJgTOdzo8QywI9IidQM0uygmWYAE0nrU08DLo+gZaYNepofLER3U/yGDoUTT4TDD+/pOPNXMijrleFQ4p2QhRaCFVeEZwq2sXKjT7PyDCVdXK1f74kUQLY24J/Ag5K+nHM4ZvVLEtLJwE2kdiUDmT2RIts2kDRd7G6kMR2ePoj0/fwesLoTqbr3BnAn8HdJY7JRKyTWB54C9iLNAhrS6Xl9sm3Lk26s/UHqVTGwhuZkKtXdL55MnXQSXHIJ/KfHQm9tlQzKeqVfSXu1tcE118AVV8ALBavZ+z006wVJC2QFYSZHxL4RMTbvmEoVERcC+wF/lLRU3vGY1amTSE10S7kwVrbfGR9LB2fnhusjYnxE/DgixlUxTquAiJgeEWeRzTIA5pVYC/gT6aZZKddJQ4ANSAlVS1xXOZlKvaJmFHxk9dVh443h7LNLOY5PEvn5mJ5GpqRUPGTKFDjwwGJ7jS/2gJnNTmntxF9Jf391tz6qFBFxK7BmRLwhaZm84zGrK2lq32F0HYXoyeBB8ItNYGHSlDBrMBHxfERsDTEJxj9I71rOQBq9WovUZ7DpOZmCfwADCj4yciQsvXQqXPDuu3DEEbDDDvD44533nAbcXdUorTuPU+w9nOmSS2D48PT+TZtWaI8ZpIbKZtYDScOAB4CzI+JHjdy7KSLeypqG3ibppKyQhpmlNVLFL6KLVzlmAMSfYXwjjVZbQbvAoC4VqQ84AB59FCZNgssuK/rcwcDBUg/XZ03ABSgApJuAbemcXA4aBHN3qEtxxBEpudp/f/jww457tgPrEPFU1WO1wqSrgZ2Bvl0eu/BCGDEijTJOmFDsCBOAjYj4R9ViNGsCkpbIEpBlI+LVvOOpFEkLAbcBzwHfdUsLa2lp5PnfdNe7sZsqx5lJwKJEfFKdIK2aJETqwbp858e++U2YMQM22yx9BL797aKHGQd8L4Jrqxdp/jwylZxJqkIyu4kT4f33Z/2MH5/S8NkTKUiV/JxI5essYHKXrUsuCfvtl5Kp996DcePSz667dt7zHeCR6odp1rgkfY+0MHnuZkqkACLiA+DrpJtj8+QbjVnu9qW7a8SddoJPP4V77unuGDOAXSobltXQCGCRQg/cdBPccgt89FGPxxhKmira1FpiYVgJ/gr8jVmVago74YRCWycCh1QlKitdxBNId5P6HszqN/Xmm2m9VPcmAgfhYVqzgrKpbyeRRn9HRsRnOYdUFRExARgjqb+kXwEnRMQ7ecdlloNV6Fq1L5lZ5XijjWCffbo7xmBgxSrEZrWxLFSkvHnTr0f1yBSQXURvB7xA7xZSTwT2w6U+68VOpGkJvemm3g4cRsSd1QnJrCkMBhYD1omIl/IOpgamAq8Bf5W0ct7BmOWgeN/G0qscA8xXsYis1uaiMnnCoJ53aWxOpmZKdyTXAe6dDpMKliiYZUL2szMRV1Y/OCtJxCRgfVID33ZSYZBiJmT77EXEr2oQnVnDkTS3pPOAvhHx7WwqXNOL5DTgJ8BfsvVUZq2kcOGI3lU5Buh5IpjVq3EUq3bdO+0VOEZdczLVUUQ7EVveCtu9k5qWTSKdUGb+TABeB44EFiGV1bV6EjGJiO2BrwJXkkapOr6H44G3LoF71kzJ8PX5BWtWvyQtSqrY15cW+DIsJCKuBr4aER9IWjLveMxq6AkKzdQpvcoxpO/bp6sapVXT81RmOdBzFThGXXM1v06yXiP9IuJFUvnfL5AWI08mdfB+2mtrGog0N+k9nBeYArwPPCUYDewRERvnGZ5ZPZI0iDRl9v+A0xu59HklSBoIPAucRyoH39L/HtYCpMWAl+m8jrz0KseQbsIslM38sQYk8U9g9c7b+/aFtjY47jhYfHH47ndT15npXVdYjQN2j6CpBx+cTHUi6UrguYg4Ne9YrHok9SN9UYyKiEfzjsesXkhaNCLekbRCi6yPKomkJYA/kXoKHh4RlViYbVa/pD8BmwHFqzgdd1zqN9W1NPpU4BIi9q9egFZtErsAv6LTGrrjjoPjj5993+OPL1in7UNg4YiKFLKoW06mOpC0FGloe7mI+DTncKzKJH0XmBxe92YGgKQdgV8Cq0XEf/OOp95ImofUSuMIf0dY05PWJt08KN64t7h2YAS+IdPQJPqTivEsTO+XBk0Ajomg5AV2jcrJVAeSzgamRMTRecditSOpT0RUYpGlWUPKSp8flv1sFRH/yjmkuiZpMCmpOiYivMDempc0BjiD3iVUE4Fdibi5KjFZTUl8DngEZgyFPj32msm0A7cCu0bQ9ImGC1DM7kTg9LyDsNqRtBNwUd5xmOWsP6lB4zpOpEoyibQW4OFsna1Zc4q4gHSTpZ2eew5NzfZzItVEIngBdj0TPp0BUUr7oAnAb4HRrZBIgZOp/5G0M7BQRHycdyxWU3cDoyQtnncgZrUmaZCks4AhEbFHRLyVd0yNICJmZDMYzgMeVCpWZNacIi4mtY757WSIGV17OY4nJVGXkKb23VzjCK2KJH0Rrj0Y9lsXdAppHdS42feKKekeU/vfgG8B34notj1NU/E0P0DSUOBVYO2IeDnveKy2sovJiIjD847FrFYkzQ/cArwF7BURk3MOqSFJWi4iXpG0WES8nXc8ZtX0D2nBtdLF8oqkKrkfkSp//s5V+5pP9j3xGHBUZK1kJPoCWwJfI62lagfehCv/HLHHE7kFmyMnU4Ck7wNrRcROecditZeNSo2KiF/kHYtZLWTVLJ8gVaf7gdcMzhmlFgzPAsdGxKV5x2NWDUrrp+6PiGfyjsWqT1Jf4Hbg6Yg4soT9BwHfiYhzqx5cnWn5ZCpbeP0I8L2IaMmM2hJJi0TEu3nHYVZNkoZHxPuSPh8RTd9MsVYkrUhKTq8ETnQvKmsmkvoD7wBrRsSbecdj1SfpRGA9YJOI6HHKnqQ+wBvAFhHx72rHV09afs1U9oW3jhOp1iZpaeCfWZUus6YkaQvgaUlLOJGqrIh4kbSuZDnKKyVtVs82I/XgdCLVAiRtA3wb2LmURArSWlJS4YldqhlbPWrpZEpSX0nXAHPlHYvlKyJeBx4G9sk5FLOqkLQPcBmwnQtNVEdEvB8RewB9JJ0jyd8t1iw2BX6TdxBWfZKWJxUT2TEi3u/l038D7JjN+moZLZ1MAdsBywOf5huG1YnTgSOy9SRmTSOb+z4S2CAi/ppzOK1gIjAIuF/SwnkHY1YBBwO/zjsIq65sds6NwPER8bcyDvFP4GutNs25ZZOpLGv+AXBaq73pVlhE/AM4KO84zCpFUj9JpwILRMToiHgh75haQTYt5nvAzcBD2cJss4YkaRNg24iYmncsVj3ZdfHFpITownKOkV1PD5b0rQqGVvdaNpkCFiQtprwl70CsrtwGbJwtpDRrWNkUs1uBL5CaKFoNRXISsFVETPQIlTWwg4G58w7Cqu4AYDVgvzkcZOgHnCuprTJh1b9WvmD8MCK+4ZLAVsDJwNZ5B2FWruxmwJ2kHlLfiIjxOYfUsiLiBUkLAk9J2iHveMx6I+sztD5plNWalKR1gGOB7SOifU6OFREvkb57NqxEbI2gJZMpSV8C/px3HFZ/srsxpwM/bLUFlNYcJC2Y3STal9TyoWW60NeriPgvsDlwjqRD8o7HrBc2BO6IiHF5B2LVkY2aXwd8OyJeqdBhfwPsWKFj1b2W7DMl6XrgYTdptUKyxfovAKPLXIBplgtJ6wI3ACMj4vm847HZSVoK+Cmwd0RMzjses1JI6h8RU/KOwyovK7h1N3BfRBxXwePORbo/3RJTzFtuZCprrDgSV6WxIiJiOulu3D/yjsWsVNkUshuBPZxI1aeIeCMidgOGSDpD0sC8YzIrRtJikn7oRKqpnQa0AydW8qDZ1PI1JX21ksetVy2XTJGaKR7hNQTWnawPz46SVs07FrOeZFNStwU2iwhPYa5/7cDSwJ2S5s05FrNidia1j7EmJGlH4JvAbtlN5EpbCTi8CsetOy01zU/SMGBKREzMOxarf5KOBNaIiF3zjsWskKzQxI+ByyLiP3nHY6XL3rszgY2AL7nstNUbSY8BP4iIu/OOxSpL0srA/cCmEfFklV5jPuA1YImI+Kwar1EvWm1k6idAxeaEWtP7FbCppGXzDsSsM0kDSIt8NyGNdFgDiYgZEfF9YJeImCppobxjMptJ0iKkFjL35h2LVZakuYGbgCOrlUgBRMTHpIRtm2q9Rr1omZGpbCrFK8CIiHgz73isMUg6Bfg4In6edyxmM2XT+m4HxpPWSE3KOSSbA5KWBB4Ddvc0TasXLjzRfLLvjt8DH0TEfjV4vQWAT6o0jbButFIy9WNghYjYK+9YrHFIanNpaasn2dSJT0jNFf/tXnnNQdJ6pEqMR0XEFXnHY60ru+A+FTjZ68ubi6SjgB2A9WtVUVTSHqTy+h/U4vXy0ErT/O4ATso7CGssETFN0ubZCcgsV5JGAP8C1oyIfzmRah4R8SCp0uymWXsGs7ysCXwLaImy1q1C0teBw4BRNW7NsBnp89S0WiKZkvQV4PUKNiOz1vICcFRWwMQsF5I2ITUbPywiHs87Hqu8iHguK52+gKSTJLXlHZO1pF2Aa6NVpi61AElLANeQphK/VeOX/w3Q1IW8mj6ZyhqSXQeskHcs1pgi4jXgTuB7ecdiLW1nYIeIuD7vQKzq2oGvADdLGpJ3MNZyNiddAFsTyIoV3QD8IiLuySGEu4DPSVo8h9euiaZfMyVpN+C7ETEy71iscUn6AvC9iDgg71isdWRrFw4Dbo6IV/OOx2onuxF4ManPzwae0mm14sITzUXShcBw0s24XC76JS0cEe/l8dq10NQjU9mFyBGkDs9mZcvWpxzgtQxWK9kUr4uA3QH3xmsxWd+pvYEDImKGpPnzjsman6T9cKPepiFpL+DrwF45T9scK2lMjq9fVa0wMrU08Ibn/tqcyj5Lt5AW/zd1mU/Ln6TfAPMB34qIcXnHY/mR9HlSv59vRsTf8o7HmpOk/sA7pO84t5BpcJLWIK2z3SAins05lj7Am8BmEfFMnrFUQ7OPTB1O6hHkRMoq4Q1SX58d8g7EmpekebJR9dOBbZxIWUQ8RxqlulXSdjmHY81rU+B5J1KNL2uh8XvSyHauiRSkJuXAtaTiJk2naZMpSesCY0gLec3mWJaUnwb8ILvYNasoSSsCj5PuJD6VTfUyIyL+CGwB7ODzj1WJC080gWwU6Brgpoi4Lu94OrgW2KkZz19NMc1PYgAwGPgsgulpm24D/hARv8o1OGsq2UnqGOBnETExbWMQMID0+fMicZslfV7mBiaTfV6K76q1gZuAH0fEJbUIzxqTpMWAPYHTui1MkdZ4zg20U9u+MlbnJAQMAvoB4yKYkV3ktvkmTmOTdAKpZ93G9fReZp+v4RHxHum/h5AGdcbR4MlIw45MSSwjcZbEWNLo03vAVInXpLd/APOsDLiLvFVURMyIiBPghq9JXC4xERgHvE/6/D0tsXuW4FsrkgYijUb6NzCV9NkYhzQR6VKk1Yo8cw9gbydSVoJJwFbAVVnZ41mkYUgHIb1O+vy9B7QjjUX6OWntp7UoiTUkriYVtfkM+ACYKo19Ga74GUTTjRq0EklbA/sAO9VTIgUQwN0w8k3pcWAK8AnwITAV6V6kLbIbkA2n4UamJBYiDV+uS0oG+xfYbQJEH9AFwNEzR6vM5pTEihC/g0mrw4AZ0KdQdb+Za1yOAX4ZQWP9kVl5ZpUxPz7bMrTAXtNIF7jPATsR8bKkfYH7I+KFmsRpTUHSINJ34QBg64C+wBmkfngzSHd9O5tMuqZ5ENiViA9rFK7lTGJl4LfAcqTPTIHvrimToP8U4AcRXFjTAG2OSVoO+BuwXUT8Ne94ZiONBK6YAQsAg4tkTOOBCcB3iPhDrUKrhIZKpiSWBv5KejP6lfCUdtKXxjYR1FWGbo1H4svA3cBclDaq204aHT3ACVWTS4nUzDLmg0t4xoyAcdvDzTfD2sDmWXNos5JlrRpWfQmeWxL+3B++TGmfvymkO8Jr42IDTU9iHVLj+SFAKSNP7aTz2RH+7moMkgaTro9/HRHn5R3PbKQdgctJ00pLMRH4PhEXVS2mCmuYZEpiPuBJYDEK3lEpqh24FdjVJwUrl8RypMIAw3r51AnAzyI4sfJRWd2QTiKNShUaDShqHEz/E3x5x4gnqxOYNT1J78Fdw+Drg0q7UJ5pOvAWsAYRn1YnOMubxErAIxQeKe/OBOCECM6ofFRWSdlapCtIN3lH11UFa2lD4HZKT6RmmgjsRsRNlQ+q8hppbuKxpA7OsyVS994LEyfCuHHp5/nnuzxvMLA1qWmZWbkuosCX0QEHwKOPwqRJcNllBZ83BPhhNqpqzShNrTicQonUvPPCjTfC+PHw+uuwy+xVYecCdoRTaxGmNa1NFoavFkyklloKbr8dPv4Y3n0Xzj0X+v7vK7QvsAhpOrI1r19T4NxUwrXTEOBEicVqEKPNmf2B1YF96yyRmllVsGsi1cN3Y/acy+m8JrRONUQylVVL2wcKL+o/8EAYOjT9rLRSwUMMAY6oXoTWzCSWBNajwN/LO+/AySfDpZd2fwjgwOpEZ3XgIIqNlp9/PkyZAsOHw267wYUXwsor/+9hpeeNJFVnMyvHkRSb2nfBBfDBB7DIIjBiBGywAYwZ03GPAcB3G+WCxXpHYnngixS51ivh2glgvyqFZxWQVYE9HtghIuqtFdAmpHuGXfXw3ZgRDdLXsyGSKWBHmKMpegJG+g6LlWlMsQduugluuQU++qjb5w8A9nWFvyaUigDsQ6FCOIMHww47wDHHwIQJ8PDDcOutMHp05z2DdGfRrHekJUnFmApP71tmGbjuOpg8Gd5/H+64A1ZZpdCeo6oYpeWn+I2e0gwEDpBKWqNuNSZpOHAdsE9EvJx3PAUcRaFkqvTvxqHA0TWIc441SjI1mm7m+556Kvz3v/DQQ+nGWxEzgG2qEJs1v10oMiraC0G66LHmsh4U6S224oowfTq89NKsbU89VehidiCwW5Xis+a2Dd3daDznHNh5Zxg0CBZdFLbYIiVUsxtKKstvzWcnuinWVeK1U1/gK1WIzeaApDZSdcbLI+K2vOPpQuoPbEChGz2lfzcCfA5poSpFWTGNkkwNL/bA0UfDssvCYovBxRfDbbel/1/AQFIVQLPemrdCx/Hnr/ksSLFRgbnmgrFjZ982dmyaU9PVPBWOy1rDgqTvtsLuvz9doHz2Gbz9Njz2WKof2VXdX6xYWYoWTOrFtVPg7656dCqp1cHxOcdRzLxQpIp2774bp9AAn79GSaaKxvnII2n92pQpcOWVabRwyy0L7qrujmPWjUp8bvz5a059KJZMjR8Pc889+7a5506rvQsfx6y3in9uJLjzzrTIe8gQmH/+tOj79NN7dxxrZL52akKSRpGm5u4WEfXaR7UPxUbNe/fdGDTA56/uA8x0vyKlg4j0HVLAZFK3ZbPeKvgX3ksz8OevGX0MRZqCv/gitLXB8svP2rb66vDMM4X2/qwawVnT+5h057ar+eaDJZeE885LV8wff5xKjha+Yv64mkFabsaXumM3106Bv7vqhqTPAxcCoyKi5GvjHHxCseURvftu7E8DfP4aJZm6idTzYDbDhsGmm8KAAana6667wvrrp5txBQRwV5XjtOZ0OzCt0AN9+876/HX87wL6kxrqWXN5mGJfGO3taVTgxBPTgtt11oFvfAOuuqrznlOBhur2bnXjLool8x99BK++Cvvvn05Kw4bBnnumtQmzmwDcWOU4LR93UODz0ctrp37Ao1WO00ogaSjpb/XoiHg873i6FTEJ+FfBx0r/bgR4H3inipFWRKMkU5dToCJNv36pLPV//wsffggHHQTbbZeS3gKejqBrJwWznv2CInN/f/KT1GPqhz9MhWgmTUrbOpkGXBfh0Yemk5qd/p5iF7RjxqTF/x98ANdemy5sn322817TgHOqGqc1p4hngBeKPr799rD55ulL8uWXYdo0OOywznv1Aa6sYpSWn7NIs3Jm04trp6nAFRFdb2ZbbWWNeS8DHoiI7pux1I/TKTazp7TvxgnAmdRT76wi1AAxAiBxNbAz5ZX5HA/sFcHvKxuVtQqJJ4A1ynx6O7BOBF1uCVsTkNYEHqRYr5+ePULEWhWMyFqJtBOpMWvhfi7dmwZcQ8ReFY3J6obEs8Dny3z6RGCNiG4SdqsJSUeQ2gStFxFdEuS6lCr6/ReYu6ddi5gILExE3d+IbpSRKYCf0Iv5vx1MBp4BbqlsONZixsCUglP9etAO3OREqolFPAHcRnqve6sdN3S2OXPjOHizzKur8cBxFY3G6s1+pIvS3moHrnEilT9JGwKHk9ZJNUYiBRAxhdTrrJzvxgnATxohkYIGSqYieB3YlDRkWOpw2iTgNWDziMJrXsx6ImkY6HF49GCI3nwptQN/B75dpdCsfuxBWlfQmy+NdmAXIrwewcomGPZa6ufyBuk7rxRB+i7dhIg3qhac5S6CB0jfQb397noANxPPnaTFgWuA3SPizbzj6bWIK0ll3Hv73XgpcHZVYqqChkmmACJ4BFgbeItuk6ppAdOmAvcDX4ng0xqFaE1G0pKkIgOjIr52IWgriE9gfOFGrclk0kXNb4HNIor0WrDmke7AbULqRj+JAusUOhhHqk60BRG31iA6a0KS+kg6DbhxdfhoAHwBeIh00Vzs5uHMJOpNYC0iHqtNtJanCH4HbAeMpdvqtNOnks5fVwBb+yZ0viQNAG4AfhkR9+QdT9kiTgYOBtpndJ9UtZM+f8cDhzTCWqmZGmbNVEcSfUgXLkcBXyNduMysRd8G798G91wYset9+UVpjU7S6qQqa2dFxNmzti+wLWz7S7jkY9DnSaWJg7SebwapbOn5EbyVR9yWM2kpYAxpek0fUnEKkSo6PgOcBtxChJNsK0t2kXUpsCywTUR82OHBVYDDgF1JSdUM0udvAGm04QzgHiK6uyFkTUhiALA98ANgRWb77poieOIP8NXDI3g7zzgtkXQ+sCiwfTTixXpn0tAn4chl4MB50vlo5ndgG6k9yJnAZUTUfSn0zhoymepIYkHSh20w6a7LGxFMkLQiMG9E/CPXAK1hSToWeD4iruu0/QHgwoi4VmJRYDjpxPAp8GpEkb4v1lrS4ttlgXlIN3zeJ6LuS7xa/ZO0EvBj4HsRUfhOrzQEWAoYRrrj+zYdky5raRKLAwsxq4/Pq6BpQJ86bgTbMiTtQfob/0pEjM07nkqR1DfSDZ6lgflJNxw/Bl5t5Bs8DZ9MFSNpW+BY4MtNkdFbzUgaDbweEQ8WeOxrwFXAihHhKRBmVjPZ+om9gZP8vWaVJuliUuntq/OOpZVJGkHqITcyUvuDpiBpBVKfrC802/mrodZM9dIfgEHARnkHYo1ByY+Ak4BincWPBs5wImVmtSRpNVLj73Iqs5mV4n5gl7yDaGWS5iX1LjyomRKpzM7Afc2WSEETj0zB/4ZJR0XEtnnHYvVP0vHAN4CtosB0LEmrAncDy0T0qqqfmVnZJH2O1MvskIi4Nu94rDlJmgt4G1guPCW05iT1IbXZeDEiunTXbmRZ0+Fngb0j4m95x1NpzZ5M9QMGN9N8U6s8pbUF04HFgP9Gkb4Gkq4EnouIU2sZn5m1LknzkdZjrhoR/8o5HGtyko4Gbo4I95eqMUnHkWZTbRRNVqBI0mBS8aVDPDLVgCQtAewWEaflHYvVH0kLke4EXRoRv+pmv6WAJ0h37D6tUXhm1qKyO7lHkabGfDEaeHG2NRZJfV2EorYkbQlcDHwpIt7LO55Ka/bPVDOvmZrpY+D7WfUjs//JFkP+FbiDdBLrzuHAr51ImVm1SeoLnEcqb761EymrlSyJfybrsWg1IGlZ4DJg5yZNpPoAz2aDG02p6ZOpiJhA+lI6Mu9YrO5sB5weEcd1N+wsaUFgd+AXNYrLzFrbkqSy1etHhHv+WM1k34UPADvlHUsrkDSIVHDilIh4KO94quRrwJSIaNrem00/zQ9A0vzAX0j1+ifnHY/lKyubPzEi7ipx/xOB4RHxvepGZmatTNICpIbPJ3s0yvIiaUNSs/o18o6lmWWjgJcB/YDdm3EtEYCkC4E3m3m9edOPTAFExEfACCdSJml/4CJSk8JS9h8K7A+cUc24zKy1SVqONO14INCUF1XWMB4A/ippQN6BNLnvAV8E9m3WRCrzLvDbvIOoppYYmYL/zUH/I7BLRHycdzxWe5IOJd313TwiXi3xOd8H1ooIT3kws6rI1qf8AzgxIi7MOx4zaP6iAXmStBap+NXXIuKlvOOpllb5DLXEyBRA9ma+DRyQdyxWW5L6Z2U5bwHW6UUiNQD4Pqmcp5lZxUmaB3gL2MaJlNWLrCjCP7OpaFZBWRXh64HvNHMilblU0rfyDqLaWiaZypwBHJT1FbIWIGkY8CfgwIh4rZeNCHcD/h0RT1YnOjNrZZK+B/wd6BsRj+Udj1kHr5GmnH4p70CaiaQ20pS3KyPi1rzjqabsJvY3SNNGm1pLJVMR8RxwOdC05RltFkmLAw8CzwE/7+Vz+wJH41EpM6swJSeTqsxuExHT8o7JrKNsDc9vgF3yjqXJnAJMA47LO5Aa2Bp4JCLezzuQamvLO4Bai4ijJLVJavMXWNP7BnA1cEYZizu3IxWpuL/SQZlZy1sYGEGadvxBzrGYFXMNsEPeQTQLSTuQSs5/qRXWEZGSxnPzDqIWWqYARUeSrgL+HBFX5R2LVV5W1nVwRNxe5vMFPELq+3BzJWMzs9YlaW7gYODUFrmYsibQKkUEqknSSqTpblu2wpTebHbPjCavUvg/LTXNr4OrgKOzrszWRCTtCvwOaJ+Dw3wdmAto6vnMZlY7khYlXUwtBnhRvzUESbsBF+QdRyPLWqzcCPywFRKpzF7AOXkHUSutmkzcBUwBtso7EKscSd8mrXHaKCLunYND/QA43U0zzawSJC1I6iH1W2CMp5hbA3kAGOWeU+XJZrpcAjwcEZfkHU8N7UILLZNoyWl+AJJGApMi4u85h2JzKBtOHgjMR1o3+585ONaXgJuA5SJiSoVCNLMWlU3tG0fqV+fvG2s4kh4Azmz26nPVkPWq3AVYLyIm5R1PLUhaBHgWWDQiJuYdTy206sgUEXEf8LQkV/ZrYFnpzd8DP4qIt+YkkcocDfzciZSZzSlJOwL/BAY6kbIG9ou8A2hEkjYAjgJGtUoilZmftOa8JRIpaOGRKQBJ+wDbR4Sn+zUgSQuQOoi/Auw9pwmQpBWBh4FlImJ8BUI0sxaUTe05LPvZKiL+lXNIZnMk+0z3cSGK0khaDHgU2DMi7so7nlpqxYIlLTsylbkaGCHpC3kHYmXZGrgPGF2hkaQjgfOdSJnZHJoH2IxU+tyJlDWDi4Cd8w6iEUjqD1wPnNeCidTywBNZ8t0yWnpkCkDSUcCIiNg171isNJK+DCweETdV8JiLAU8DK0bEh5U6rpm1DkmDgENJ60um5hyOWcVkVf12iYit846l3kk6F1iCNPOppQpZSfoJsHBEHJh3LLXU6iNTkO62nJF3EFYaSVsDfwQqPYR8KHClEykzK4ek+UmVYr+Av1ut+dwCrJdNr7ciJO1OGpXeswUTKQG7Ab/JO5Zaa/kTfkR8Brwuadu8Y7HuZd3D/w/YppJVhSTNC+wDnFWpY5pZ68gq9j2c/ewWEZNzDsmsorLp76cBTqaKkLQ6cDawQ0SMzTueHAwG/gL8Le9Aaq3lp/kBSBoOPAd8PiLezzsem112t2MwMBQYGhEvVfj4PwZWiIi9KnlcM2t+kuaKiPGS1o2Ih/KOx6yaTpD6HgfrA8uRmtt/Rrp++jstfEGZ3ZR9FDgmIq7NO55qk1gR+CppfegU4F34110RX2jPNbCcOJnKSDofGBsRP8o7FptFUj/SaNS4iDioCscfDLwGbBgRz1b6+GbWvCRtDlwMrNaid6KtVUjzB+zzIZwyP0zOpjW1AdOAAD4EfgZcTcS43OLMgaQ+pGmQr0TEoTmHUzUSbcA2pHLvq5OWW7QBMyCmQftcMPEyWODUCF7JM9ZaczKVkbQMaWhyKU/RqA/Z1JkbgMnAzhExoQqvcQCwSURsV+ljm1nzkrQ38FPSIvO/5h2PWdVIXwduBvqSZokUM4H0fb0JEU/UILK6IOkY0jqpDZu18IzEQsA9wNKkEclippKSrB9EcE4NQqsLTqY6kDRfRHycdxyWSBoFbAwcGBHTqnD8fsBLpETNDTXNrCSShpB63O0fES/kHY9Z1aTR1xuBQSU+I0hJ1deJeLRqcdWJbHT6EuBLEfFu3vFUg8SCwJPAQkC/Ep/WDpwewYlVC6yOOJnqQFJf0jD1j1usW3VdkbQysEpEXF/l19kN+G5EjKzm65hZc8huwBwCnOsZDNb0pJWAx4AhZTz7U+DzRLxX0ZjqSDaj6e/AqIh4MO94qkGiDymRWgno38untwN7RnBDxQOrMy1fza+jrGPzSsAeecfSqiStD9wLDKzy6wj4AXBqNV/HzJqDpLmAW4ENSesEzJrdj+nuu3inneDZZ2H8eHj5ZVh33Y6PDgSattdQ1lPuBuCnzZpIZTYFlqFAIrXSSnDPPfDpp/DSS7Dddl2eOxg4Q6LpG/g6merqNOAoSX2RhLQg0gpIS5KKFViVSNqUdHLaLSKuqswxkcQCEstLLCX97w7blqSFs3+uxOuYWfOSNBC4D3gL+EY11m+a1RVpHmAUaZ1UVxtvDKefDt/+NgwdCuuvD6++2nGPgcABpNHcppLdjD0feBH4Zc7hVNtRpErKs+nbF265Bf7wB5hvPth3X7j6alhhhS7PXwBYt8vWJuNpfp1I0sJw9x3wz9VhF2A+0oI6keaK3kNq8ntfK5cBraTsxDSIdBdj0Yj415wfk3mAPYEjgAWZ9R72B+6FHRaF206JmPLbOX0tM2tekgZHRLukkcD94fO+tQLpEFKBlcI3kR9+GC65BC69tLujjAP2JqKppnlJ2hc4GPhq1n+rKUksCbxAgdHJVVaBv/895dEz3Xkn/OMfcOyxs+0awG0RfKO60ebLI1MdSX0CTnsH1lkd9gMWAQaQKpcMIV2Ib06a6vEa0ojcYm0S2Tq1s4GLIuLDOU2kspGoE4B3gVOAxZn9PewHsQlcsQpMPlPiy3P4K5hZk5K0LvCCpIUi4j4nUtZCNqBYItWnD3zpS7Dggml+11tvwbnnwsAu19xDgbWqHGdNSfoKcDKpimfTJlKZNUg9pLpQgYl7Eqy6atfNNNlnoBAnUzOli/obgAOUsvBiU/pEujBfEngIaYMaRdh0sjnHvwNGkBZ1z+Hx6ANcAxxOeg+LLJqVYC6BFgPuk9h0Tl/bzJqLpB1IVcy+ExEf5B2PWY3NV/SR4cOhf38YNQrWWw9GjIA11oCf/KTQ3gtWK8Bak7QgcD2pcNWLecdTA8Mokic8/zx88AEceSS0tcEmm8AGG8DgwlfO5RQwaShOpmY5j7TQrtQ3Xdm+f0BapWpRNbcNSHc9NouITypwvDOAbendH+5g4EaJERV4fTNrApL6kxbPbxYRd+Ydj1kOJhZ/JHvo3HPhvffgo4/grLNgyy0L7d0U6wsltQHXAtdExC15x1Mjk0jT9LqYNi0VnNhqq/QROPxwuO46+M9/Ch6n4OhWM3EyBWTJ0J4UuwjvvmLNEFIiZiWStLSkXSLiDlKxiTkuMSyxHDCGTu/huHGz/0ybBr/sulx0MPCrOY3BzBqbpD6SDiZV6/t6RDyZd0xmOXmV1Hy1q08/TVP7ep71Ohl4rbJh5eYkUmJxTN6B1NDb3T349NMwciQssABsvjksuyw88kjBXZu2PP5MTqaSQynWiKznijUCvoq0dNWjbAKSvgg8DMwPUME1CAdRoOrQ0KGzfoYPTzfUru/avUrAahIrVSgWM2swWcW+a0kVzAZ4fZS1uEtIyVBhl10GBx2U1k3NMw8cemgq7Ta7IP1NNTRJ3yQVJNsla6HTKv5G6hVV0GqrwYABMGhQGplaZBG4/PIuu02gBQYcnExJQ4HdKNY35IQT4MQTU4mSCHjnnfQzuz40cT+FSpG0DvAn4MCIqNgfl8QgYB966Mw9alSa4/tg4Y4QbVRg3ZaZNZ5sCs8dpBsrm1Zo2rFZ44p4gu5GlU46CR59FF58EZ57Dp58Ek45ZdbTUyJ1HxHdjm7UO0krkmaufCsiPsw7nlqKYAZwFswoOOVz9Gh49910XbXRRmnd1JSuE/r6AFdXOdTcuTS6tAXwW2DuLo/16ZOGMo49Fr7znVSp5uab04q7SZM67/0mEUtVP+DGlN31HQisGBGFB4LLPjYbAjdT6D3s4J574IEHUn5cxAcRDK9kbGZW3yQNjIhJkjYC7o2IGXnHZFYXpN1IiUSvCwi0Q3wCWy6WpvM3pKxR9z+AX0TE/+UdTx6kL4+GB66AQeU03p0EXBPBdyodV73xyFSablb4Q9K7ijXDqhhjw1JyLHBtRHxa6UQqM39POyyxRKo0c8UV3e7WpTGdmTUvpfYWz0taKiLucSJlNpvfAH+ku2IUhbX3hV8uDndKOj4b3WkoWf/LXwN/a91ESt+Hx46F239C7z8D04A3gcMqH1n9cTLVnV5UrPkUhkk6HkDSO5Ii+3k823Zxh20haVFJ23Tatm+2b8dtt2Xbbuu4Pdu2b6d9t8mO23Hbxdm+j3fY9k627fhO+34x++m4bY5+J+ABUoW97ar1O8Go6+GzbhOhPfaAhx6C118v76NgZs1F0ibAn4EjI+KNvOMxqztp6tLuwJ2UXpVvAnDlAPh+9v8/BP4q6VBJjXTNeQiwPC24hEPSlpIWIU3PGxEx6qfA/pSeUE0CXgE2iGBclcKsK57m1900P4A334Qf/xiuuir9/+23TyNTa67ZZU9P85udpPWAI4Fdq9ncrpRpfi+8AKedltbMdsPT/MxaQNYs/M/A8RFReBWlmSUpCToY+CEwiK6zOIKURH0EHEvElbM/XcsDlwMXRMRvqh7vHMquXa4HvhoRr+ccTs1IGgacDWwI7BBp3VyHx1kPOBNYjbTOvPM69fGkmV6XAj+KoNmbGv+Pk6lUgOJ90gmiqxNOgC22SMX0p06FW2+F++5L66hmmQKcS8QRVY+3AUhaGNgoIq6RpGpXxcoKUHxAaqbcxdprw113wcILp+r2RUwFLolg/+pEaWZ5y6bufJdUYWy8K/aZ9UJKqjYjVUBenrSWajzwb+As4EGK/E1lNzAANgeWAi6qx2m1khYFHgW+HRF/zjueWsmK8PyLNJvoyIgoOqKUVT4+BPg66Sb2FFL58wuB30X0ekpgw3MyBSD9H7AXhSr6tbXBOefArrumohPXXQdHHQWTZ6sYOgn4PC10B6MYSZ8jVey7LCJOqt3r8gtSn6kuFf0uuih15d5jj24PMRFYI4IXqhKgmeUqu1g4H/gKsEVENH3vE7N6I2kl4ApgHLB3RLyZc0j/o9Ss+17gjxFxSk/7N4OsyMaOEXGppEUjoku5auuZkymY2bT3UYqNTnUvgPuJ2LCyQTUeSauT5lb/MCK6n1BX8ddmOdLdsYFlPD2ARyNYq7JRmVk9yNZq3AwMAEZ1d9fVzKoru7FxJLB+RGyRdzwzSToHWAbYrh5HzSpN0gbAZcD9wL4RMTXnkBqWk6mZpAuB0fS+BOh4YC0inq18UI1D0gDSqNAXI+L+fGLg58D36P17OAFYN4J/VjwoM8uVpAERMVnSpqTS575gMKsD2dS/IaR1OsdGjj2pJO0KnAh8KSI+zSuOWpG0MWmE8HsR0aXbsvVOI1VWqbYDSQuSS61YM3PB5dZOpHQw8IeIGJ9XIpU5EriVbjp2F9AOfNOJlFnzyUoy/1vSyhHxZydSZvUjIqaTpti/CTwpaXS2rrGmJH0BOAfYvtkTKUnrSNqQNJ1xNSdSleFkaqb0Rz0KOI+0BqrYBXmQRqPeBNYl3+QhV5L6SDqTVDLzu3nHk3Xr3o1UbWYixRPjme/hf4CREdxVmwjNrFYkrU1aTH16tPgNL7N6FRFTI+IEUmGKw4AVavn6kuYBfg8cGhH/quVr15KkgZJ+RvpdB0fE9Ij4OO+4moWn+RUizQt8Gzic1BB2Kinx7AfcBZxBWifV0v94ktYkJS6j6u2PUmIYsCdptGohUrWZme/hX0jv4V8iaOn30KwZZXe3/wT8MiL+mHc8ZtazmdV/JR0HPB8Rv6vy681cS/l6RBxczdfKm6TfAn2BMRHx37zjaTZOprqTvpDnB+YBJgMfEdGbKWRNSSnZ3DoirqpF6fM5ISFgPmBeUkL1UUTJUznNrMFI2h24Hfi0ns9NZlaYpK+Q1vM8Tbr4/7BKr/NjYEtgw4iYUo3XyFO2lv0Q4AJSteqxPidWh6f5dSciiPiQiJeJeMuJFEhaEngIWKPeEymACCKCjyJ4OYI3nUiZNads2vFpwDHA3PV+bjKzwiLiEWBN0nKKg6rxGllBmjHAt5o0kRpBqlL9NWBgRPjmUhV5ZKqVSYNJd2UWI5UUHws8RsRjhXfXCqRFiz+PiLNrFqeZtZRsRPlLwBeBYaR1rG8DtxdqCJlN67uc1Eh024j4qHbRmlm1ZH/ba5IaBR/S05ICiX6kxsLLkCoFfgY8Azwwc1q/pKWBv5P6Kz1QteDnRGrZ8zXSzKipwPvA7USM7fmpWhh4EjgauMpJVPV1bVJrzS8lRYeQGhXPAPqT5tJOBQLpLeB04LdETExPUX9SwYa9W6kruJnVjsRgYGfSRcBizFrnOJ00TVcSlwLnRvByeo76R8QUSdcAD0Z2zjKzxpetoXoe+AR4WtK+EXF75/0kFiMVwzqAdN7oT7rGnUo6f3wqcSZcdy1wA6kwTX0lUlI/4Juk89/nScWy+pOu0yYDbUjXAWdRoFiGpFWBDSLifEnLR4Rn4tSIR6ZajXQAqfhCX9IfaTHjgY+BkYL1SP2b1vUdDjOrhqzx9n2kO7FzdbPrFNLF0fdBt5PWR30nmxpkZk1K0kjgWGCLiJg8azvbAdeQkqiB3RxiAoxvg2/eD3dvXlfXM9JCwD3A0nR//ptGShDPBI4jJZttwBGkomk/iIhLqhytdeJkqpVIRwHHAYNL2T1g+kSY8gX46BXYNCKeq26AZtaKJJYFHiNN6StxLe/0SXDsJPjpycBZdXVhZGZVk1XhuxG4AGIe4DJKvK5JgzyaABoZQcElDTUnLUialrcQaSS+FBOAy4g4SNIRpCUbe0fE69UJ0rrjZKpVSFsB1wODevO06RABb7fB8nS4E2RmVgkSA4GXgEXpdVGkaVOg7RsR3FGF0MysTqUCEl+5Ah5YAAaUs2TlE2ClCD6odGy9ktaEPQ6sQvezhbqYClMegZ+tCycDUyNiRjVCtJ65ml/rOJ1CidS888KNN8L48fD667DLLrM93BfUlqbd7FCLIM2s5exIOsfM9n00btzsP9OmwS9/2fmpbf2B02oTppnVi7R2+4EnoV/fzo+Vdu5gIGn5Qt42JDUq7ppILbUU3H47fPwxvPsunHsu9J316/aD/mvB/gHTnEjly8lUK0jNdZcp+Nj558OUKTB8OOy2G1x4Iay8cue95iItiDQzq7SjKbBGYOjQWT/Dh8PEiXD99QWfv4LEF6odpJnVD4mFYcCG0EedHyvx3DEIOESiSzJWY0eSqg52dcEF8MEHsMgiMGIEbLABjBkz2y5tKQnbrOpRWrecTLWGQ4EBXbYOHgw77ADHHAMTJsDDD8Ott8Lo0YWOsTySL1jMrGIk1iAtuO7WqFHpmuLBBws+3B84rLKRmVmd+24pO5Vw7tiqkkH1irQoMBLokhACsMwycN11MHkyvP8+3HEHrLJK572GAkdVNU7rkZOp1rA2FLj7suKKMH06vPTSrG1PPVXojxXSqs01qhSfmbWmNUnlf7u1555w5ZVFH24jnePMrHWsR/eV+4Aezx1zke91zWqkkueFnXMO7LwzDBoEiy4KW2yREqquVq9WgFYaJ1OtYWjBrXPNBWM79X8bOzaNjXfVRlrXYGZWKcPooXrVEkuk2S1XXNHtcQqf48ysWc3b0w4lnDsELFDJoHppGMVGpQDuvz/d3P7sM3j7bXjsMbj55kJ7lljJ0KrFyVRrKHznY/x4mHvu2bfNPXdasdnVDKC90oGZWUubSOoZVdQee8BDD6X6ON2YVMGYzKz+9Xg9Utq54+YRAJLekRTZz+PZtos7bAtJi0raptO2fbN9O267Ldt2W8ft2bZ9Z/7/beB3UwvNGko7wp13pgJhQ4bA/POngmGnn15o7yk9/VtYdTmZag1vFtz64ovQ1gbLLz9r2+qrwzPPFNp7GvCfagRnZi3rLVIDyqL22KPHUSkodo4zs2b1Cukmb1ElnDvaYbvfAETEohGh7OeL2bZ9O2xTRLwTEbd12nZxtm/Hbdtk27bpuD3bdvHM/38brFF0WH6++WDJJeG881KRsI8/hssugy23LLT3+93+llZ1TqZaw3lA1+Gm9vZ01+PEE1MxinXWgW98A666qtAxZgB3VzlOM2stf+7uwbXXhsUWK1rFb6ZxpHOcmbWOX5FGtgsq8dzRB7iuwnH1xlNQpM/VRx/Bq6/C/vuncujDhqUFYE891XnPduD8KsdpPXAy1RpuotgdnDFj0uLGDz6Aa69Nf7jPPtt5r8nA+UR0ewfZzKw3IpgCXEiRqch77jmrDV43pgO3Vj46M6tjjwDvFHuwhHPHDODWCD6qQmyliQhSD9AJBR/ffnvYfHP473/h5ZdTw6zDuhQu7QNcXtU4rUdK76U1Pelk4PsUatzbs4nACkS8XdmgzKzVSSwJPE/556YzIjiuslGZWb2T2Is0Kl24T1P32oGRETxa0aB6S5oLeJcCvfZKMBm4jog9KhuU9ZZHplrHicC/6K4MZ2HtwN5OpMysGiJ4E/gevS9wMxl4Ejil4kGZWSO4AvgT3Uz3K2ICcEruiRRAxHhgO3r/O0wjrRU9sNIhWe85mWoVEVNIXbKfpPQ/2onAIUT8tmpxmVnLi+Aq0sh5qeemduBxYItsqqCZtZgIAtgNuINiU+W6agd+AZxapbB6L+IeYBdSbKVMF5sEvAysT8Rn1QzNSuNkqpVEjAU2AE4DPqFQUYpUWWsi8DdgCyJ+XbsAzaxVRfArYEvgH6RzUKE1muOAj0gXQiMj8IWEWQvLbqaMAo4mraEaR9eEZDopUXkG2C2Cn2SJWP2IuIXUiPgeUrJUaBbRuOznfODLRLxXuwCtO14z1aqkNmAbYAywBKmT+FjgQeCXRLyYY3Rm1sIkPgccAnyN1NhyEmlKy/nA7RFMyzE8M6tDEgK+DhwMrEBqZjsOeAI4J4IncgyvdNISwAGk2UTzkG4svQtcDNxARG+Xa1iVOZkyMzMzMzMrg6f5mZmZmZmZlcHJlJmZmZmZWRmcTJmZmZmZmZXByZSZmZmZmVkZnEyZmZmZmZmVwcmUmZmZmZlZGZxMmZmZmZmZlcHJlJmZmZmZWRmcTJmZmZmZmZXByZSZmZmZmVkZnEyZmZmZmZmVwcmUmZmZmZlZGZxMmZmZmZmZlcHJlJmZmZmZWRmcTJmZmZmZmZXByZSZmZmZmVkZnEyZmZmZmZmVwcmUmZmZmZlZGZxMmZmZmZmZlcHJlJmZmZmZWRmcTJmZmZmZmZXByZSZmZmZmVkZnEyZmZmZmZmVwcmUmZmZmZlZGZxMmZmZmZmZlcHJlJmZmZmZWRmcTJmZmZmZmZXByZSZmZmZmVkZnEyZmZmZmZmVwcmUmZmZmZlZGZxMmZmZmZmZlcHJlJmZmZmZWRmcTJmZmZmZmZXByZSZmZmZmVkZnEyZmZmZmZmV4f8BjSjK7aMjSBYAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 1080x288 with 3 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 计算出的两个子图的最大割\n",
    "strr1 =  '01010101xx'\n",
    "strr2 = '0xxxxxx101' \n",
    "strr = '0101010101'\n",
    "\n",
    "# 图形示例展示\n",
    "options0 = {\n",
    "    \"node_color\": [\"red\" if strr1[i] == '0' else \"blue\" for i in S[0].nodes],\n",
    "    \"style\": [\"solid\" if strr1[u] == strr1[v] else \"dashed\" for (u, v) in list(S[0].edges)]\n",
    "}\n",
    "options1 = {\n",
    "    \"node_color\": [\"red\" if strr2[i] == '0' else \"blue\" for i in S[1].nodes],\n",
    "    \"style\": [\"solid\" if strr2[u] == strr2[v] else \"dashed\" for (u, v) in list(S[1].edges)]\n",
    "}\n",
    "options2 = {\n",
    "    \"node_color\": [\"red\" if strr[i] == '0' else \"blue\" for i in range(n)],\n",
    "    \"style\": [\"solid\" if strr[u] == strr[v] else \"dashed\" for (u, v) in list(G.edges)]\n",
    "}\n",
    "\n",
    "fig, ax = plt.subplots(1, 3, figsize=(15,4))\n",
    "for i, a in enumerate(ax):\n",
    "    a.axis('off')\n",
    "    a.margins(0.20)\n",
    "nx.draw_networkx(S[0], pos=nx.circular_layout(S[0]), ax=ax[0], **options, **options0)\n",
    "nx.draw_networkx(S[1], pos=nx.circular_layout(S[1]), ax=ax[1], **options, **options1)\n",
    "nx.draw_networkx(G, pos=nx.circular_layout(G), ax=ax[2], **options, **options2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 量子近似优化分治法\n",
    "\n",
    "为了找到一个大图 $G$ 的最大割，我们采用``量子近似优化分治法``。这个方法像上面描述的一样，先递归性地利用``大图分割``分割图形，再利用``图形重构``递归性地整合两个子图的最大割。\n",
    "\n",
    "首先如果输入图形的顶点数大于量子比特数量限制 $k$，它将被``大图分割``分成两个子图。反之，可以直接求解它的最大割（不用拆分）。每一个子图将递归性地被输入进``量子近似优化分治法``，直到它的最大割被返回。最大割被返回说明在某一步，它某些递归的子图的顶点数量小于$k$，直接被``量子近似优化分治法``解得，再一层一层地经历``图形重构``，直到返回这个子图所在层。\n",
    "\n",
    "下面是利用``图形重构``和``大图分割``完成的``量子近似优化分治法``的代码。``量子近似优化分治法``将返回最有可能的最大割和前 $t$ 个最有可能的最大割。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-16T03:44:13.784486Z",
     "start_time": "2021-05-16T03:42:41.653981Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最有可能的 t 个图形 G 的最大割: {'1010100100': 413, '1010101100': 405, '0101010011': 390, '0101011011': 379, '0100101011': 255, '1001010100': 253, '1011010100': 245, '0110101011': 230, '1010110100': 214, '0101010101': 212}\n",
      "量子近似优化分治算法找到的图形 G 的（最有可能的）最大割: 1010100100\n"
     ]
    }
   ],
   "source": [
    "def DC_QAOA(g, p, t, s, k, ITR, LR):\n",
    "    if len(g.nodes) > k:\n",
    "        # 利用 大图分割 得到两个子图\n",
    "        S = NaiveLGP(g, k)\n",
    "\n",
    "        S_str_cnt = []\n",
    "        for si in S:\n",
    "            siv = list(si.nodes)\n",
    "            # 递归性地计算子图的最大割\n",
    "            _, si_str_cnt_relabeled = DC_QAOA(si, p, t, s, k, ITR, LR)\n",
    "            # 填充子图的最大割结果，使其和母图的顶点吻合\n",
    "            si_str_cnt = []\n",
    "            for str_relabeled in si_str_cnt_relabeled:\n",
    "                strr = \"\"\n",
    "                for v in g.nodes:\n",
    "                    if v in siv:\n",
    "                        strr += str_relabeled[siv.index(v)]\n",
    "                    else:\n",
    "                        strr += \"x\"     \n",
    "                si_str_cnt.append((strr, si_str_cnt_relabeled[str_relabeled]))\n",
    "            si_str_cnt.sort(key = lambda tup:tup[1])\n",
    "            S_str_cnt.append(si_str_cnt[::-1][:t])\n",
    "\n",
    "        # 利用 图形重构 整合子图最大割\n",
    "        out_cnt = GR(S_str_cnt[0], S_str_cnt[1])\n",
    "    else:\n",
    "        if len(g.nodes) == 1:\n",
    "            return [(\"0\", 99999), (\"1\", 99999)]\n",
    "        _, out_cnt = find_cut(g, p, ITR, LR, shots=3000)\n",
    "        # 将词典格式转成列表格式，易于排序\n",
    "        out_cnt = [(k, v) for k, v in out_cnt.items()]\n",
    "        # 将{最大割：频率}按频率从大到小排列\n",
    "        out_cnt.sort(key=lambda tup:tup[1])\n",
    "        out_cnt = out_cnt[::-1]\n",
    "\n",
    "    # 只保留最有可能的t个最大割\n",
    "    out_cnt = out_cnt[:t]\n",
    "    # 等比例调节频率的显示\n",
    "    cnt_sum = sum(cnt for (str,cnt) in out_cnt)\n",
    "    out_cnt = [(k, int(s * v / cnt_sum)) for (k, v) in out_cnt]\n",
    "\n",
    "    return out_cnt[0][0], dict(out_cnt)\n",
    "\n",
    "# 设定 量子近似优化算法 中的参数\n",
    "p = 2     # 量子电路的层数\n",
    "ITR = 100 # 训练迭代的次数\n",
    "LR = 0.5  # 基于梯度下降的优化方法的学习率\n",
    "\n",
    "# 设定 量子近似优化分治算法 中的参数\n",
    "s = 3000  # 等比例调节频率的比例\n",
    "t = 10    # 想要保留最有可能的最大割的数量\n",
    "k = 5     # 量子比特的数量限制\n",
    "\n",
    "# 量子近似优化分治算法使用\n",
    "max_cut, out_cnt = DC_QAOA(G, p, t, s, k, ITR, LR)\n",
    "print(\"最有可能的 t 个图形 G 的最大割: \" + str(out_cnt))\n",
    "print(\"量子近似优化分治算法找到的图形 G 的（最有可能的）最大割: \" + str(max_cut))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 应用范围\n",
    "\n",
    "**以上表述的``量子近似优化分治法``可以估计一个图形的最大割，当且仅当，它和它递归出来的顶点数量大于 $k$，且子图的伪连接度（pseudo-connectivity）都小于 $k$**。伪连接度的定义为：一个连接图变成不连接的两个子图所需要移除的最小的顶点数量。\n",
    "\n",
    "当 $k > 1$ 的时候，圆圈就是一个例子。因为只需要移除两个点，圆圈就会被拆成两条不相连的子图，所以所有圆圈的伪连接度都是2。我们拿六个顶点的圆 $C_6$ 并且 $k=4$ 举例。``大图分割``会将它分成 $P_5$（顶点数量为5的子图）和 $P_2$，$P_2$ 的顶点数量在 $k$ 之下，可以直接使用``近似优化算法``计算。而子图 $P_5$ 是一个链状结构，他的伪连接度是 $1 < k$。所以``大图分割``将继续分割 $P_5$，并把它分成了 $P'_4$ 和 $P'_2$。新的子图的顶点数量都小于或等于 $k$，我们都不再需要考虑他们伪连接度。\n",
    "\n",
    "``量子近似优化分治法``不可解的图包括顶点数量大于 $k$ 的完全图（complete graph）。对于完全图来说，无论怎么移除顶点，剩余的图都是连接图。有些图是否适用决定于 $k$ 的大小，我们以下给了个这样的例子。\n",
    "\n",
    "最左的图就是实例图，这个图的伪连接度是2。如果 $k=2$，那么分离点的数量只能为1个，如果分离点是4,那么这个图被拆分成三部分而不是两部分（下图中间所示）；如果分离点是其他的几个，这个图仍然连在一起，没有被拆开。此外，该图的伪连接度为2并不小于 $k$，不满足条件，所以``量子近似优化分治法``并不适用于这个例子。但如果 $k=3$，伪连接度是 $2 < k$，这个图可以进行拆分成两个子图，其中一个的顶点数量小于等于 $k$，另一个的伪连接度显而易见是 $1<k$（移除顶点4）。``量子近似优化分治法``在这种情况下可以解决这个图。于是我们移除顶点0和4（如下图最右所示），剩下的图将是两个不相连的子图。我们再将分离顶点0和4加回去，并在这两个子图上计算最大割。``量子近似优化分治法``最终可以成功给出最大割。\n",
    "\n",
    "![limitations-connectivity](./figures/dcqaoa-fig-applicability_example.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "读者可以在以下代码中自己调试 $k$，利用``量子近似优化分治法``试验上述的示例图的最大割，从而感受这个方法的适用范围。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-16T03:44:54.150187Z",
     "start_time": "2021-05-16T03:44:13.788802Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最有可能的 t 个图形 G 的最大割：{'00101': 532, '11010': 511, '10110': 508, '00001': 490, '01001': 480, '11110': 479, '11111': 0, '11101': 0, '11011': 0, '11001': 0}\n"
     ]
    }
   ],
   "source": [
    "G = nx.Graph()\n",
    "G.add_nodes_from([0, 1, 2, 3, 4])\n",
    "G.add_edges_from([(0, 4), (1, 2), (1, 4), (2, 4), (3, 4)])\n",
    "k = 3\n",
    "_, out_cnt = DC_QAOA(G, p, t, s, k, ITR, LR)\n",
    "print(\"最有可能的 t 个图形 G 的最大割：\" + str(dict(out_cnt)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法测试效果\n",
    "\n",
    "下面，我们比较量子近似优化分治法所得到的最大割和半正定规划（SDP）方法得到的理论上界进行比较。这里，我们用的例子是10个顶点的随机图，量子比特数量限制 $k=5$。\n",
    "\n",
    "为了能正确运行以下测试代码，用户首先应该安装 cvxpy：`pip install cvxpy`。**Windows 如果直接使用 pip 安装，在运行时可能会出现报错，建议新建 conda 环境后使用 conda 安装 cvxpy。** 更多详情请参考 [https://www.cvxpy.org/install/](https://www.cvxpy.org/install/)。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-11T07:06:44.690385Z",
     "start_time": "2021-05-11T07:06:44.433742Z"
    }
   },
   "outputs": [],
   "source": [
    "import cvxpy as cvx\n",
    "import networkx as nx\n",
    "\n",
    "def sdp_solver(G):\n",
    "    \"\"\"\n",
    "    通过半正定规划 SDP 来找到最大割问题的理论上界。\n",
    "    \"\"\"\n",
    "    n = len(G)\n",
    "    adj_mat = nx.adjacency_matrix(G).toarray()\n",
    "    Y = cvx.Variable((n, n), PSD=True)\n",
    "    cut_size = 0.25 * cvx.sum(cvx.multiply(adj_mat, 1 - Y))\n",
    "    problem = cvx.Problem(cvx.Maximize(cut_size), [cvx.diag(Y) == 1])\n",
    "    opt_val = problem.solve(cvx.SCS)\n",
    "\n",
    "    return opt_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-11T07:16:56.698522Z",
     "start_time": "2021-05-11T07:06:44.697731Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "顶点数量 = 10\n",
      "顶点编号 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "\n",
      "随机图形 1\n",
      "边 = [(0, 2), (0, 4), (0, 5), (1, 4), (1, 8), (2, 3), (2, 5), (2, 6), (2, 8), (3, 4), (3, 9), (4, 5), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (6, 8), (6, 9), (8, 9)]\n",
      "半正定规划找的最大割的上限: 16.325182392614767\n",
      "量子近似优化分治算法找到的最大割分类: 1101011010, 最大割 = 15.0\n",
      "\n",
      "随机图形 2\n",
      "边 = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 6), (0, 7), (0, 8), (0, 9), (1, 3), (1, 4), (1, 8), (1, 9), (2, 4), (2, 8), (3, 8), (3, 9), (4, 7), (4, 8), (5, 9), (6, 8), (7, 8), (8, 9)]\n",
      "半正定规划找的最大割的上限: 16.480274420284523\n",
      "量子近似优化分治算法找到的最大割分类: 1001110010, 最大割 = 16.0\n",
      "\n",
      "随机图形 3\n",
      "边 = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 8), (0, 9), (1, 2), (1, 8), (1, 9), (2, 4), (2, 9), (3, 5), (3, 7), (4, 5), (4, 7), (5, 6), (5, 8), (5, 9), (6, 8), (6, 9), (7, 8)]\n",
      "半正定规划找的最大割的上限: 17.39937016574631\n",
      "量子近似优化分治算法找到的最大割分类: 0110010100, 最大割 = 15.0\n",
      "\n",
      "随机图形 4\n",
      "边 = [(0, 2), (0, 5), (0, 6), (0, 8), (1, 4), (1, 5), (1, 7), (2, 8), (2, 9), (3, 6), (3, 9), (4, 5), (4, 7), (4, 9), (6, 8), (6, 9), (7, 8), (7, 9)]\n",
      "半正定规划找的最大割的上限: 14.551833331333285\n",
      "量子近似优化分治算法找到的最大割分类: 1001100011, 最大割 = 13.0\n",
      "\n",
      "随机图形 5\n",
      "边 = [(0, 3), (0, 4), (1, 2), (1, 4), (1, 5), (1, 8), (2, 3), (2, 5), (2, 7), (2, 9), (3, 5), (3, 6), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (5, 6), (5, 8), (7, 8), (7, 9)]\n",
      "半正定规划找的最大割的上限: 16.10769704836696\n",
      "量子近似优化分治算法找到的最大割分类: 1100010101, 最大割 = 15.0\n"
     ]
    }
   ],
   "source": [
    "n = 10\n",
    "iter = 5\n",
    "print(\"顶点数量 = \" + str(n))\n",
    "print(\"顶点编号 = \" + str([i for i in range(n)]))\n",
    "\n",
    "value_dc_qaoa_ls = []\n",
    "ubound_sdp_ls = []\n",
    "for i in range(iter):\n",
    "    print(\"\\n随机图形 \" + str(i+1))\n",
    "    # 生成随机图形\n",
    "    G = nx.erdos_renyi_graph(n, 0.1, 100 * i, directed=False)\n",
    "    while nx.is_connected(G) == False:\n",
    "        G = nx.erdos_renyi_graph(n, 0.5, directed=False)\n",
    "    print(\"边 = \" + str(list(G.edges)))\n",
    "    \n",
    "    # 半正定规划（SDP）方法找最大割的上限\n",
    "    ubound_sdp = sdp_solver(G)\n",
    "    ubound_sdp_ls.append(ubound_sdp)\n",
    "    print(\"半正定规划找的最大割的上限: \" + str(ubound_sdp))\n",
    "\n",
    "\n",
    "    # 设定 量子近似优化算法 中的参数\n",
    "    p = 2      # 量子电路的层数\n",
    "    ITR = 100  # 训练迭代的次数\n",
    "    LR = 0.5   # 基于梯度下降的优化方法的学习率\n",
    "    # 设定 量子近似优化分治算法 中的参数\n",
    "    s = 3000   # 等比例调节频率的比例\n",
    "    t = 10     # 想要保留最有可能的最大割的数量\n",
    "    k = 5      # 量子比特的数量限制\n",
    "\n",
    "    try:\n",
    "        cut_dc_qaoa, out_cnt = DC_QAOA(G, p, t, s, k, ITR, LR)\n",
    "        cut_dc_qaoa1 = [\"solid\" if cut_dc_qaoa[u] == cut_dc_qaoa[v] else \"dashed\" for (u, v) in list(G.edges)]\n",
    "        value_dc_qaoa = cut_dc_qaoa1.count(\"dashed\")\n",
    "        value_dc_qaoa_ls.append(value_dc_qaoa)\n",
    "        print(\"量子近似优化分治算法找到的最大割分类: \" + str(cut_dc_qaoa) + \", 最大割 = \" + str(float(value_dc_qaoa))) \n",
    "    except Exception as e:\n",
    "        value_dc_qaoa = 0\n",
    "        value_dc_qaoa_ls.append(value_dc_qaoa)\n",
    "        print(\"量子近似优化分治算法找最大割失败，错误信息：'\" + str(e) + \"'\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-11T07:16:56.935061Z",
     "start_time": "2021-05-11T07:16:56.704158Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAEWCAYAAABhffzLAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAABLK0lEQVR4nO3dd3hU1dbA4d9KIISETugt1AAJECCAShdQVETFi4hKR2xYruXzWgH7tVx7B6QpVkSaWFBRikJCD70XgYQAAUICJFnfH2eCQ0iZlJmTmdnv88zDzKlrToY1Z/bZZ21RVQzDMAz/EWB3AIZhGIZnmcRvGIbhZ0ziNwzD8DMm8RuGYfgZk/gNwzD8jEn8hmEYfsYkfsNwAxGJEJHVInJSRO6zOx7DcGYSv1FgIrJbRM6KSFi26WtEREUk3E377SgiC0TkuIgcFZEVIjLCxXWniMhz+SyjIpIiIqdE5ICI/E9EAgsZ7v8Bv6lqeVV9q5DbMAy3MInfKKxdwOCsFyLSCijrrp2JyKXAL8BioAlQFbgLuKqYd9VGVcsBvYBbgNsLGGcpx9MGQHxhAnDahmG4hUn8RmFNB4Y6vR4GTHNeQESucTR3nBCRfSIy3mneIBHZKSIVHK+vEpFDIlItl/29AkxV1f+q6hG1xKnqTY71h4vIkmz7VxFpIiJjgFuB/3Oczc/N782p6mbgDyDKsa1+jl80x0VkmYi0dtrPbhF5VETWASki8gvQE3jHsb9mIlJRRKaJSKKI7BGRJ0UkwCn2pSLyuogcBcY7fqG8JyLfO7axVERqisgbInJMRDaLSFunGP4jIjscTUsbReQGp3nDRWSJiLzqWHeXiFzlNL+KiHwiIn875s92mned432fcGy/r2N6RRGZJCIHHb+OnivCryPD01TVPMyjQA9gN9Ab2AK0AAKBfVhnuQqEO5brAbTCOsFoDRwGrnfazqfAFKyz97+BfrnsLwTIAHrmEdNwYEm2aQo0cTyfAjyXz/tyXr4lcAgYBbQDEoBOjvc6zHEMyjgdjzVAPaCsY9pvwGinbU8DvgPKA+HAVmCUU+zpwL1AKaxfTlOAI0B7IBjr184urC/bQOA54Fen7Q8EajuO9SAgBajltP1zWL9eArF+Kf0NiGP+fOALoDJQGujumN4RSAb6OLZbB2jumDcb+BAIBaoDK4A77P5smoeL/4ftDsA8vO/BP4n/SeBFoC/wkyNpnU/8Oaz3BvC60+tKwF5gPfBhHvur49hu8zyWKa7EfwI4BuxwJNcA4H3g2WzLbnFKkLuBkdnmn0/8jmR7BmjpNP8OrGsAWbHvzbb+FOBjp9f3ApucXrcCjufxXtYA1zltf7vTvBDHe60J1AIygco5bOND57+X0/QajvdT1mnaYJy+iMyjZD9MW6JRFNOB34GGZGvmARCRTsBLWM0lQUAZ4Kus+ap6XES+Ah4EbnRa73HgccfLGY75mVhJarM73oiTdqq63XmCiDQAhonIvU6Tg7DOsLPsy2ObYY7l9zhN24P1hZbX+oednqfm8LqcU4xDsY5TuGNSOcd+sxzKeqKqp0Uka5kqwFFVPZbD/usBC3KY3gDrl8FBx3bA+oLM6xgYJYhp4zcKTVX3YDU/XA3MymGRz4A5QD1VrQh8AJzPFCISDYwEZgLne76o6guqWs7xuFNVTwPLcfpyyEEK1pls1rZrZg+3AG8tu33A86payekRoqozXdz+EaymlgZO0+oDB4ojPscX08fAWKCqqlYCNuB0rPOwD6giIpVymdc4l+lngDCn41FBVSMLE7/heSbxG0U1CrhcVVNymFce62wyTUQ6YvWSAUBEgrHO5h8HRgB1ROTuPPbzf8BwEXlERKo6ttFGRD53zF8LRIpItGPb47OtfxhoVPC3B1hJ9U4R6SSWUMeF6/KurKyqGcCXwPMiUt6RqB/Eev/FIRTriyMRwNHFNcrF2A4C3wPviUhlESktIt0csycBI0Skl4gEiEgdEWnuWOdH4DURqeCY11hEuhfT+zHczCR+o0hUdYeqxuYy+27gGRE5CTyNlfyyvAjsV9X3VfUMcBvwnIg0zWU/y4DLHY+djt4vH+FoilDVrcAzwM/ANmBJtk1MAlo6euXMLuB7jMW6MPoOVvv/dqx284K4F+tXyU5HbJ8Bkwu4jdzi2wi8hvWr6DBW+//SAmxiCNYvks1YF7EfcGx3BdaX8utYF3kX88+vlqFYzVcbsY7J11hNcYYXyLqqbxiGYfgJc8ZvGIbhZ0ziNwzD8DMm8RuGYfgZk/gNwzD8jFfcwBUWFqbh4eF2h2EYhuFV4uLijqjqRfWvvCLxh4eHExubW49BwzAMIycisien6aapxzAMw8+YxG8YhuFnTOI3DMPwM17Rxm8YRuGcO3eO/fv3k5aWZncohhsFBwdTt25dSpcu7dLyJvEbhg/bv38/5cuXJzw8HKcSyoYPUVWSkpLYv38/DRs2dGkd09RjGD4sLS2NqlWrmqTvw0SEqlWrFuhXnUn8huHjTNL3fQX9G5vEbxiFlbAZVk2DzEy7IzGMAjGJ3zAK6sTf8N1YeP9SmHMvrJ2Z/zp+LDAwkOjoaCIjI2nTpg3/+9//yHT6slyxYgXdunUjIiKC5s2bM3r0aE6fPp3jtmbPnk3r1q1p3rw5UVFRfP311xfMT09PJywsjMcee+yC6cnJyQwdOpTGjRvTuHFjhg4dSnJy8gXL3H///dSpU+eC2HyVSfyGURA7f4O32sHaz6HTnRBxNZQOtjuqEq1s2bKsWbOG+Ph4fvrpJxYsWMCECRMAOHz4MAMHDuS///0vW7ZsYdOmTfTt25eTJ09etJ21a9fy8MMP891337F582bmzp3Lo48+Slxc3PllfvzxRyIiIvjyyy9xHmtk1KhRNGrUiB07drBjxw4aNmzI6NGjz8/PzMzk22+/pV69evz+++9uPBolhN2jvbvyaN++vRqGbc6lqR7Zbj1PO6E6537Vo7vsjMhlGzdutDsEDQ0NveD1jh07tEqVKpqZmalPPfWUPvXUUy5t57bbbtNJkyZdMG3ixIk6ePDgC5b54osvtEePHrps2TJVVd22bZuGh4drenr6+eXS09M1PDxct2+3/q4///yzXnXVVTplyhQdM2ZMod6n3XL6WwOxmkNONd05DSM3mZmw4Wv45VkILAP3/AVlysO1b1y4XEY6xE6G8M5Qo+SONz5hbjwb/z5RrNtsWbsC464t2Htu1KgRmZmZJCQksGHDBoYNG+bSevHx8Tz88MMXTIuJieHtt98GIDU1lUWLFvHhhx9y/PhxZs6cyaWXXsrGjRuJjo4mMDDw/HpZzU/x8fE0btyYmTNnMnjwYK677joef/xxzp0753KfeG9kmnoMIyc7foGPusOs2yG4Ilz1XwgIzHnZMyfgtxdhwSNghjJ1iRbiOKnqRb1XnLczb948evbsSUhICDfeeCPffvstGRkZOa7nvL2zZ8+yYMECrr/+eipUqECnTp348ccfC/6mvIg54zeM7Lb+CJ8NhEr1YcDHEPUvCMjjHCmkCvR6GuY9ABu+gVb/8lioBVHQM3N32blzJ4GBgVSvXp3IyEji4uK47rrrLlruyiuv5PDhw8TExDBx4kQiIyOJjY2ldevW55dZtWoVMTExAMycOZOlS5eSVcI9KSmJX3/9lcjISFavXk1mZiYBjr9jZmYma9eupUWLFixcuJDk5GRatWoFwOnTpwkJCeGaa65x85GwUU7tPyXtYdr4Dbc7ult120/W84x01bipVtu+qzLSVT/opvpqhHUdoIQoaW38CQkJ2qdPH3366adVVfXQoUNav359/fPPP88vM336dD148OBF21m9erU2adJEd+3apaqqu3bt0latWunmzZs1OTlZq1Wrpmlp//zNJk+erCNHjlRV1RtuuEEnTJhwft6ECRN0wIABqqp6880362effXZ+3qlTp7RatWqakpJSDO/ecwrSxm97UnflYRK/4TYpSarfP6b6TJjqay1U088Vflt7V6iOq6D6w5PFF18RlYTEHxAQoG3atNGWLVtq69at9ZVXXtGMjIzz85ctW6ZdunTRZs2aafPmzXXMmDG5Jt1vvvlGo6KitGnTplq6dGldsmSJqqp+8sknOmjQoAuWTUpK0rCwME1LS9OjR4/qrbfeqo0bN9ZGjRrprbfeqseOHdOUlBStXLmyJicnX7DuDTfcoJ9//nkxHwn3KkjiF/WCNsmYmBg1A7EYxepcKvz5Pix5A86ehOhboMfjULFO0ba7+BWo3wkadiuWMItq06ZNtGjRwu4w3OI///kPf/31Fz/88ANBQUF2h2O7nP7WIhKnqjHZlzVt/IZ/OhAHiyZAs6ug9zioXkzJsfsjxbMdI18vvfSS3SF4LZP4Df+gClt/gKTtcNlYCO8Cdy6FmlHFv69zqfDLc1D/EmhxbfFv3zCKyHTnNHzf/liYcg3MHARrPoWMc9Z0dyR9gIDS1h2+Cx+DszmXHjAMO5nEb/iu43vhy6EwsRcc2QbXvAZ3/A6Bbr4xJ7AUXP0KJO+DJf9z774MoxBM4jd8V/pZ68y7x2Nw32roMNr9ST9Lg8ug1U2w9E1I2uGZfRqGi0ziN3zHmZPw64swa4z1OqwJPLgZevwHypTzfDx9noHAIPjpac/v2zDy4LbELyKTRSRBRDY4TftCRNY4HrtFZI279m/4kYxzsOJjeKstLH4J0tOss32AoBD74qpQC274AHpPsC+GEuD5558nMjKS1q1bEx0dzV9//QVAjx49iIiIOF9meezYsRw/fvz8eln1dKKiohg4cGCupZrt1KNHDzzZ1Xz37t1ERRX92pQ7z/inAH2dJ6jqIFWNVtVo4Btglhv3b/iDQ+vh3U6w4GEIawajF8FN06BUCenX3eJa65cH+OWALcuXL2fevHmsWrWKdevW8fPPP1OvXr3z8z/99FPWrVvHunXrKFOmzAWlG7LKOW/YsIGgoCA++OADO97CBTIyMuwOoVi4LfGr6u/A0ZzmiVUx6SbAjGBhFM4ZR732CnWgXHUY/AUMnw91L7pXxX7pZ+HzW+GP1+yOxOMOHjxIWFgYZcqUASAsLIzatWtftFxQUBAvv/wye/fuZe3atRfN79q1K9u3b79oerly/zThff311wwfPhyA4cOHc+edd9K1a1eaNWvGvHnzAJgyZQrXXXcdffv2JSIi4vy4AAAzZsygY8eOREdHc8cdd5xP8uXKlePpp5+mU6dOLF++/KIYZsyYwWWXXUZUVBQrVqwA4OjRo1x//fW0bt2aSy65hHXr1gEwfvx4Xn311fPrRkVFsXv3bnbv3k2LFi24/fbbiYyM5IorriA1NRWAuLg42rRpw6WXXsq7776bx9F2nV1t/F2Bw6q6LbcFRGSMiMSKSGxiYqIHQzNKtMMb4bNB8MlV1hl0SBUYuRAi+kJJHVu2VJBV2fOP16yeRnb65JqLHys+tuadPZ3z/NWfWvNTki6el48rrriCffv20axZM+6++24WL16c67KBgYG0adOGzZs3XzA9PT2d77///nwRNVft3r2bxYsXM3/+fO68887zg5GvWLGCTz/9lDVr1vDVV18RGxvLpk2b+OKLL1i6dClr1qwhMDCQTz+13ndKSgpRUVH89ddfdOnS5aL9pKSksGzZMt577z1GjhwJwLhx42jbti3r1q3jhRdeYOjQofnGu23bNu655x7i4+OpVKkS33zzDQAjRozgrbfeyvFLp7DsSvyDyedsX1U/UtUYVY2pVq2ah8IySqzkA/DdPfBBZ9izHCIHgHrRz+4rnrf+/eEJe+PwsHLlyhEXF8dHH31EtWrVGDRoEFOmTMl1eecSMqmpqURHRxMTE0P9+vUZNWpUgfZ90003ERAQQNOmTWnUqNH5L5Q+ffpQtWpVypYty4ABA1iyZAmLFi0iLi6ODh06EB0dzaJFi9i5cydgfSHdeOONue5n8ODBAHTr1o0TJ05w/PhxlixZwpAhQwC4/PLLSUpKumiox+waNmxIdHQ0AO3bt2f37t0kJydz/PhxunfvDnB+m0Xl8Tt3RaQUMABo7+l9G15q30qY2g80EzrdBd0ets70vUmletDtIeuO3h2/QOPL7YljxPzc5wWF5D0/tGre83MRGBhIjx496NGjB61atWLq1Knnm2ScZWRksH79+vP1ZrLa+PPiXGc/64w+p3nOr3OarqoMGzaMF1988aJ9BAcHXzCIS14xOG8vp+VKlSp1wZi+zjFnNYeBdcxSU1NzHUugqOw44+8NbFbV/Tbs2/AW6WfgcLz1vFYbiBkFY2Oh7wvel/SzXHovVG4Iv/3X7kg8ZsuWLWzb9k+L7po1a2jQoMFFy507d47HHnuMevXqXVBvPz81atRg06ZN58fMdfbVV1+RmZnJjh072LlzJxEREQD89NNPHD16lNTUVGbPnk3nzp3p1asXX3/9NQkJCYDVRr9nzx6XYvjiiy8AWLJkCRUrVqRixYp069btfFPRb7/9RlhYGBUqVCA8PJxVq1YB1lgCu3btynPblSpVomLFiixZsgTg/DaLym1n/CIyE+gBhInIfmCcqk4CbsZc1DVyk5kJ67+yzowzzsL9a63BzPu+YHdkRVc6GAZNty5I+4lTp05x7733cvz4cUqVKkWTJk346KOPzs+/9dZbKVOmDGfOnKF379589913Bdr+Sy+9RL9+/ahXrx5RUVGcOnXq/LyIiAi6d+/O4cOH+eCDDwgODgagS5cuDBkyhO3bt3PLLbecH8jlueee44orriAzM5PSpUvz7rvv5vgllV3lypW57LLLOHHiBJMnTwasi7gjRoygdevWhISEMHXqVABuvPFGpk2bRnR0NB06dKBZs2b5bv+TTz5h5MiRhISEcOWVVxbo+OTGlGU2So7ti+DncVYXzZqtrRugGve0Oyr3yMyAsykQXMGtu/Hlssx5GT58OP369eNf/7pwNLQpU6YQGxvLO++8Y1Nk7mPKMhveZ+9fMGOAY7jDiRB1Y97DHXqzzEyrV1Kl+nDjRLujMfyQSfyGfY7thr9XQ+QNUK8j3DjJuuGpVJl8V/VqAQHQsDv8/jK0H26ViDaKVW49h4YPH57jhWV/46OnVEaJlpJklSx+OwbmPWjVrxexBin39aSfpcu/oWJ9WPAIZKS7dVfe0JxrFE1B/8Ym8Ruec/a0dRPTW9Hw1wfQ5ma4aymULmt3ZJ4XFGJdsE7YCCvd19wTHBxMUlKSSf4+TFVJSko6f/HaFaapx/CcY7tg0bPQrC/0Hg/Vm9sdkb2a94PGvaxeTJ3ucMudx3Xr1mX//v2Yu999W3BwMHXr1nV5edOrx3AfVdi60BoBq9dT1rQj2/8pWmbAqUQIrlhyisoZPiW3Xj2mqcdwj30r4ZOrYebNsPE7q+simKSfXblqVtI/cwqO7rQ7GsNP5Jv4RWSgK9MMA7Bq6nwxBCb1tgY2v+Z/cPdyCAq1O7KSSxWmXQdfDbf69xuGm7lyxv+Yi9MMf5bVZBhYGvb9BT0edwx3OMpzwx16KxG49G44uBbiptgdjeEHcr24KyJXAVcDdUTkLadZFQD39j8zvMeZk7Dsbdi/Em6bZdXGf2C9/3TLLC6RAyD2E/jlWeu+Bm+tR2R4hbzO+P8GYoE0IM7pMQconoIRhve6YLjD/0KZCv+045ukX3AicNXLkHYCFj1jdzSGj8v1jF9V1wJrReRTVTVn+MY/ErfCzEHWxcgGXazRr+qaKttFVqOl1a0zYZN1U1eg6W1tuIcrn6xtInJRn09VbeSGeIyS7PRRqwmiUj2o0gj6vgRNryi5I195o94TrGsi5pgabuRK4nfuAxoMDARMA6Q/ORwPP4+HxM1WTfzSZeG2b+yOyjdl9ec/vs+64a1hN3vjMXxSvr16VDXJ6XFAVd8AbBo+yPCo5P0w+254v7NVPTNmpN0R+Y85Y+GrEZB63O5IDB+U7xm/iLRzehmA9QugvNsiMkqGw/Hw8eXWcIeX3gNdHzI9TTypzzPwUQ/47UW4yn9G7DI8w5WmntecnqcDu4Gb3BKNYQ9Vq1vmqQRIPQb1OkD1ltD5foi+FSrnPwqRUcxqtbF+Ya34CNoOgZpRdkdk+BBTq8eXnT0NJw9CSqKV1E8dhtNJ0P1R6+Lhb/+FNTOsejHpqdY6QeXh3xugbCVbQzewLqa/3R6qNYcRC8wFX6PACjwCl4g8CCQ7xsl1nn4vEOho6zc87expq598QCAkboHdSxyJ/bAjuSfArV9C2crwx6tWGeQLiNV0U6Y8lK8J9S+F0GrWjVflakBYU5P0S4qQKtBnglXkLj3NP8tXG26R6xm/iGwA2qnq2WzTywArVbW1B+ID/OCM/1zqP0k7JQHqdrSKd+39E5a/Y52RnzpsJfizp+DOJVCzlVXHff5D1jZCqkJodWu9Gz6ECrWt0a0SNllJPdSR2EOqmv7hhuEnCjPmrmZP+o6JZ0TMb06XnEu1BtrISupZib3NzVCnvXW2PnMwnDlx4Xq3fAXNrrDuhE3caiXuOu2sxB1aDULCrOVaDYSIayA0LOd6OLXbWg/D++2Pg4OrocNouyMxfECep34iUkNVD2ef5t6QSrD0s9ZZd2CQdWadlmyVLTjf1JJoJfbL7oN2QyBph9UzxlmZilCvk5X4K9SB6FscTS01HGfm1azmFoAmvWDsitzjCa5oPQzfF/cJrJ0J4V2hWoTd0RheLq/E/wowX0QeAlY5prUHXgZedXdgHpORbiXuFKez8kr1rBtn0s/AjBv/OVNPPWat0+VB6D3O6ur4y7NWnZqs5F29hZXAAao0hMGfO5pZHEm9tNPwaFUamq56hmt6j4dNc+D7/4Mhs82FXqNI8qrVM01EEoFngChAgXhgnKp+76H4im7XH9aNSFlt5KcOW8m5q6Nt/OVGcCb5wnXaDLYSf2CQ9R+sWgQ07PpPAq/juLUhuBI8cSj3i25BoRBxldvemuFHQsOg55Pw/SPWwDaR19sdkeHF8mzqcSR470nyOZn/EBzZYj0vHWIl7rJONyL1fMzRdFPdqbnFccYuAsPm5r5tEdPTwvCcmJGwair88AQ07WMGtzEKzfe7dwz8BEoFW0m9TLmL519yl+djMozCCCwFV78Ke5ZCgO//1zXcx/c/PTUi7Y7AMIpPg0uth2EUgRls3TC80eb5MOe+f4a8NIwCcGWw9ekiUtHpdQMRWeTesAzDyNPRXVZ7/9aFdkdieCFXzviXAH+JyNUicjvwE/CGW6MyDCNvne6AsAj4/lE4l2Z3NIaXcaUe/4fAaOA7rK6d3VQ1j64uhmG4XWBpuPplOL4Hlr1ldzSGl3GlqWcIMBkYCkwBFohIGzfHZRhGfhr1gJbXW4X4TvxtdzSGF3GlV8+NQBdVTQBmisi3wFQg2p2BGYbhgiufh+b9oHwtuyMxvEi+iV9Vr8/2eoWIdHRbRIZhuK5iXWg90HqemQkBpqOezziXapWFccONeq4MvRgMjAIisQZbz2IGYDWMkmL1p9ZoXaN++mfAdsN7pSXDZ4OsOmC3fFHstZlcOT2YDtQErgQWA3WBk8UahWEYRVOuOhxcA3++Z3ckRnEoFQxB5awS7m4oyOdK4m+iqk8BKao6FbgGaJXfSiIyWUQSHAO6OE+/V0S2iEi8iLxcuLANw7hA0z7W2AyLXzYXer3Z0V3WkJulysCtX0HUALfsxpXEf87x73ERiQIqAuEurDcF6Os8QUR6AtcBrVU1El8q72wYduv7AmSmw49P2R2JURiH1sOkK+DbO63Xbiy97Uri/0hEKgNPAXOAjVg1+fOkqr8DR7NNvgt4SVXPOJZJKFi4hruoKj9vPMybP2/jyKkzdodjFEblcOjyb9jwDRzZZnc0RkHsWQafXGPdn9HnGbfvLtcxd4tl4yLhwDxVjXK8XoN1I1hfIA14WFVX5rLuGGAMQP369dvv2bPHbXH6ux2Jp5gwdyO/b00EoHxwKf7duxlDL21AqUDTS8SrnEuFQxugXge7IzFcteV7+Go4VKwHQ761BoIqJrmNuZvXYOsP5rVBVf2fCzsN58LEvwH4Bbgf6AB8ATTSfL59fH6wdZucOpPO279sY/KSXQSXCuSBPs3o3KQqz8/fxB/bjhBRozzj+0dyaeOqdodqFEbqMShb2e4ojLxknIN3O0FwBbj1a2vAnWJUmMHWXwXWYA3EcgYojgan/cAsR6JfISKZQBiQWAzbNlykqny35m9eWLCJhJNn+Ff7ujzatznVypcBYNrIjvwQf5hn521k8Md/ck3rWjxxdQtqVzKDzniNlZNg0TMwduU/Q4EaJUtmptW0M+RbCKkCZcp7bNd5Jf52wM1YvXjigJnAovzOzvMxG7gc+E1EmgFBwJEibM8ooPi/kxk/J56Vu4/Rum5FPhjSnnb1LzwrFBH6RtWkR0Q1Pli8g/d/28EvmxK4p2djRndtRHDpQJuiN1zWsDucTYGfxsEN79sdjeFMFRZNgJQj0P9tqNzA4yHk2oCrqmtU9T+qGg1MwuqNs1FE+ruyYRGZCSwHIkRkv4iMwqr508jR5PM5MKyIXySGi46fPsuTs9dz7dtL2JGYwksDWjH77s4XJX1nwaUDeaB3M35+sDvdmoXx6o9bufKN31m06bAHIzcKJawJXDYW1n4Ge/+yOxojS2YGzL0PlrwOAYHWnbk2yPfirohUA24CBmJ17XxKVf/0QGznmTb+wsvIVD5fuZdXf9hCcuo5hl4azr97N6NiSOkCb+uPbYmMnxPPjsQUekZU4+lrI2kYZsZ9LbHOnIJ3O0JIVRjzm5VoDPucS4NZo2HTXOj6MFz+pFu7bELhLu6OAAZhlWn4GvjSru6XJvEXTtyeo4ybE8+GAyfo2LAKE/pH0qJWhSJt82x6JlOX7ebNRds4m57JqK4NGduzCaFlfH8UT6+0YRbMvgtGLoTabe2Oxr/NHAxbFkDflzw21ndhEn8msB7Y65h0wYKq6lKTT3Ewib9gEk6k8dL3m5m1+gA1KwTz+DUtuLZ1LaQYzy48sQ+jGKjCyUNQwVTvtN32RVa7fptBHttlYRJ/97w2qKqLiym2fJnE75rsZ+OjuzbkHjefjcftOcrT38UT//cJOjWswvhi+FVhuIGqdWdordZ2R+Jfju+FPcs9muydFTjxlyQm8efPuf398ubVeapfS4+1v2ddR3jlhy2cSD3HkEsa8GCfiEJdRzDcZOUkmP8Q3P4L1GlndzT+IWETTB8A6alw32pb7qkwid9H7Tt6mufmb+SH+MM0qBrC0/1a0qtFDVtiOX76LK/9uJVP/9pDpZAgHrkygpti6hEYYJp/bJeWDG/HQKX6VulmU7ffvfathE//ZVXZHDILakTaEoZJ/D4m7VzG+T72ASKMvbwJo7o0LBF97LPfKzChfyRt8+g2anjI2s/h2zug/zvQbojd0fiubT/Dl0OgXA0YOtuqoWQTk/h9hKryQ/xhnpu/kf3HUunXuhaPl8C7avO7O9iwgSpM7gtJ2+DeOFPOwV2WvQPrPofbZtl+13RhLu7OJVtPHmemV4/nbU84xYS58efr6Izr35LLGhdvbY/ilr0e0P29mzLssnBKm+Jv9ji4zhrZadB0qHtRPjCK4uQhKF/Ten4uDUoH5728B5hePV7sZNo53lq0jU+W7qZsUCAP9mnGkEu8q3LmjsRTPDN3I4u3JtK0ejkm9I/ksiYl+0vLZ6WfNcMzFidV+O0la/Sz23+17pouIUxTjxdSVb5dfYAXv9/MkVNnuKl9PR7pG0FYOe9sLlFVft6UwDPz4tl3NJWrW9XkiWtaUqeENVP5hYxzED8bWv3L7XeP+rTMTPj+/2DlxxB9G1z7JgSWnJsZC1OdM2vFpsCLQEucBltX1UbFGqFxgQ0Hkhk3J564PcdoU68SE4fG0KZeJbvDKhIRoU/LGnRtGsZHv+/kvd+288vmBO7u0YQx3UzxN4/a+J1VPgCF1jfZHY13Sj8Ls++0Br657D5rABUv+RJ1pVbPEmAc8DpwLTDCsd4494dn8acz/mMpZ3nlxy3MXLGXKiFBPHpVc/7Vri4BPtglcv+x07ywYBML1h+iXpWyPN0vkt4tqpu7fz0hMxMm9oITB2BsrFUP3iiYpW/BT09ZCb/z/XZHk6NCN/U4VmwvIutVtZVj2h+q2tVNsV7EHxJ/Rqby2Yq9vPbjFk6mpTP00gY80LsZFcv6/k1QS7cfYdyceLYnnKJ7s2qMu7YljaqVszss33cgDj7uBZfeA1c+b3c03if9LOxabA10X0LllvhduTqYJiIBwDYRGSsiNwBmZIditHL3Ua59ewlPzd5Ai5oVWHBfV8ZdG+kXSR+gc5Mwvr+/K09e04JVe45x5Ru/8+L3mzh1Jt3u0HxbnfZWf/6/PoCEzXZH4x2SD8Dnt1o1d0oFleiknxdXrkI8AIQA9wHPYg2kMsyNMfmNwyfSeHHBJmav+ZtaFYN555a2XNPKPwudlQ4MYHTXRvSPrs3LC7fw4eKdzF59gMeuasF10bX98ph4RK9xkLQT0tPsjqTkO7INpt8Aqcfh6K5iHybRk0yvHhucTc/kk6W7eGvRNs5lKGO6NeLuno0JCSo5vQHstmrvMcZ9F8/6A8l0DLeKv7WsbdqhDZscWGWVYJAAuO0bqNXG7ohcUpQ2/hjgCaABTr8QVNVjZf58KfEv3prIhLnx7ExMoXcLq5hag6pmMJOcZGQqX8bu45UftnD89Flu7dSAh65oRqUQ0we92KUeh2VvQ9cHIch8Hi+w9y+YMcAaF3fIbKja2O6IXFbo7pzAp8AjWLX57RknzAfsO3qaZ+Zt5KeNh2kYFsonIzrQM8JcKslLYIAwuGN9ro6qxf9+2sL0P/cwb93fPHxlBDd3qG+KvxWnxM3wx6uAQq+n7Y6mZKnSCBr1gKtf9ZlxDVzqzqmqXTwUT468+Yw/9WwG7/+2nQ9+30mpAOHey5sysks4ZUqZPusFtengCcbNiWfFrqNE1anAhP5RtG9g6s0Um1l3QPwsuPtPrzqrdZutP0LjnhDovZ0sitLU0wsYDCwCzmRNV9VZxR1kbrwx8asqCzcc4rn5mzhwPJX+bWrz+NUtqFnR/vod3kxVmbvuIC/M38ShE2kMaFeH/1zVnOrlzXEtspOHrNLN9S+BW7/ympuRip0q/PEa/PIsXPmC1d3VSxWlqWcE0BwozT9NPQp4LPF7m22HTzJ+bjxLtyfRvGZ5vhhzCZ0aVbU7LJ8gIvRvU5tezavzzq/bmfjHTn6MP8z9vZoyvLMp/lYk5WtCj//Aj0/A1oUQcZXdEXleZib8+CT8+S60HgQdx9gdkVu4csZ//sYtu3jLGf+JtHO8+fM2pi7bTUhQIA9fGcEtHet7VTE1b7PrSArPzI3n1y2JNK4Wyvj+kXRtWs3usLxXxjlY+BhcerfVtu1PMs7Bd2Otksqd7oQrX/T6AWuK0tTzMfC6qm50V3D5KemJPzNTmbX6AC99v5mklDPc3KEeD18RQVUvLabmjRZtOswz8zayJ+k0fSNr8sQ1LahXJcTusAxvkrgVPr7cKr/Q7WGfaOoqSuLfBDQGdmG18QugpjunZf3+ZJ6es4HVe4/Ttn4lJvSPpHXdSnaH5ZfSzmUw8Y+dvPvrDjJVuatHY+7s3tgUfyuM4/vgh8fhiuegcgO7o3Ev59r5zjX1fUBR2vj7uiEer3c05Syv/LCZz1fuo2poGV4d2IYBbev4ZDE1bxFcOpCxlzdlQLu6PL9gE2/8vI2v4/bz5DUtuTKyhrn7tyBEYPvPoJlw86d2R+M+Jw9ZA6K3vdW6iOtDST8vuTZgiUjWbZInc3n4pfSMTKYt302PV37lq9j9jOzckF8e7s6/2vtmBU1vVLtSWd69pR2f3d6J0KBS3DkjjqGTV7A94ZTdoXmPinWh2yOweZ71BeCLju6ESVfAsd1QvaXd0XhUXiNwzVPVfiKyC6sXj3NWU0/W4y8pTT1/7Uxi3Jx4Nh86SecmVRl/bSRNa5S3OywjD+kZmUz/cw//+2krqWczGNmlIfde3oTywd7bN9tj0s/Ae5daz+9eDqV86JrVofXWmX5mOtz2tVWwzgeZEbiK4FByGi8s2MSctX9Tp1JZnrymBX2japqmAy9y5NQZXlm4hS9i91GtfBkev7o510fXMX/D/Gz/GWbcaLX1X3av3dEUj9NH4a22EFQOhnwL1ZrZHZHbFOXi7iJV7ZXfNHeyK/GfSc9g0pJdvPPLdtIzlTu7N+au7o0pG2QuFnqrNfuOM+67Dazdn0xMg8qM7x9JVJ2KdodVssVNgZbXQVkfukt67RcQ3tlq0vJhhRlsPRirHPOvQA/+aeqpAHyvqi3cE+rF7Ej8v25J4Jm5G9l1JIUrWtbgqX4tTfdAH5GZqXwdt5//LtzM0dNnuaVjfR6+IoLKoab4W54yM727X/uaz6yLt40vtzsSjylMr547sGrx1wZWOU0/AbxbrNGVIHuSUnh23kZ+3pRAo7BQpo7sSPdm5oYgXxIQINzUoR5XRtXk9Z+2Mv3PPcxff5CHrrBuuDPF33JwdBd8MQT6vgANu9kdTcFlDZPYvJ9fJf7cuNLUc6+qvu2heHLkiTP+1LMZvPfbdj78fSelA4T7ejVlROeGBJXy4jMcwyVbDp1k3JwN/LnzKC1rVeCZ6yKJCa9id1gly7lUeLcTlC4Ldy7xnsJlqvDzeFj6BrS8HgZ85FsXqfNRlDb+ssBdQBes3j1/AB+oqseG7HFn4ldVFqw/xPPzN/J3cho3tLWKftWoYIp++RNVZf76gzw/fxMHHZ+Dx65qTnXzOfjH5gXw+WDvKVyWmQFz74fV0yFmpFVWOcC/rs8VJfF/idVvf4Zj0mCgsqoOLPYoc+GuxL/18EnGfRfP8p1JtKxVgQnXRdLBnOn5tdNn03nv1x189PtOSgeaX34XUIVPB8LeP+HeOChfw+6I8qZq1d6pUBt6Pu4TJRgKqiiJf62qtslvmjsVd+JPTj3HGz9vZdryPZQPLmXado2L7D5iXetZtDmBRtVCGXdtpLnWA5C0A967BC65G/pMsDuanKWdgNRjVqkJVb9M+FmKUrJhtYhcoqp/OjbUCVha3AF6Qmam8vWq/by8cDNJKaY3h5G78LBQJg3vwK+bE5gwN55hk1eY3l1gDdAydA7UvSiXlAynEq1hEs+lWjedecu1CA9ztUhbBLDXMak+sAmrNn+uxdpEZDLQD0hQ1SjHtPHA7UCiY7HHVXVBfkEWxxn/2n3HGTcnnjX7jtO+QWUmmP7bhouc7+fIyFTuMPdzWNJOWOPzlpR282N7YPr1cOIgDJoOTfvYHZHtitLUk2dpPlXdk8t63YBTwLRsif+Uqr7qYtxA0RJ/0qkzvLxwC1/G7SOsXBkeu6o5N7Q1d2waBXcwOZUXF2w+fwf3U/1acGWkn97BnbzfKmHc7RHoeLvd0cDhjY4z/dNwy1dQv5PdERULVS3S5yu3xO/KFatGwLVYZ++NVHWP8yOPgH8HjhY64mLwxcq99Hz1N75ZtZ/buzbil4e6M6BdXf/8j2oUWa2KZXlrcFs+H3MJ5YNLceeMVQz7ZCWnzqTbHZrnVagD1SKs4QlTjtgdDfzkGCB+xEKfSfoJJ9IY9OGfbD1c/DUx86rOWUdE/gLGYyX/JsB4EVkhInWKsM+xIrJORCaLSK73gIvIGBGJFZHYxMTE3BbL08m0dNrUq8TCB7rx+NUtTGEuo1hc0qgq8+7twrhrW7J0+xHum7majMySX/OqWInAVa/A2RRY9Ix9cWS1WAz4CEb+ADV8o8pm6tkMRk+LZcPfyaRnFP9nK6+SDd8C36nqlGzThwI3qup1+W5cJByY59TUUwM4gnU/wLNALVUdmd92CtvUk5mpiGDO8A23mf7nHp6avYGRnRvy9LW+kXQK5IcnYPm7cPsiz1e4XPcVrPvCGi/Ah27KysxU7v50FT9sPMTHQ2Lo3bLw3WYL09TTMnvSB1DVaViDrxeYqh5W1QxVzQQ+BjoWZjuuCggQk/QNtxpySQNGdA5n8tJdzPgz15ZP39X9UShXHTbM8ux+//oQZo2G9DTIOOvZfbvZqz9uYWH8IZ64ukWRkn5e8urOmeOlehEJyG1efkSklqoedLy8AdhQmO0YRkny5DUt2ZN0mnFz4qlfJYRu/tTfP7gCjFnsuZGrVOHXF+D3l626OzdO+mfYRB/wVew+3vttB4M71mdUl4Zu209eZ/xzReRjEQnNmuB4/gGQbxdMEZkJLAciRGS/iIwCXhaR9SKyDugJ/Lto4RuG/QIDhLcGt6Vp9XLc8+kqtrnhYlyJVqGW1eZ/bI9145Q7/fKclfTbDoGBU30q6f+5M4nHv11PlyZhPHNdpFtbK/Jq4y8NvAgMB/Zgtcs3AKZi9b/32O8ruwdiMQxXHDieynXvLKVsUACz7+5M1XK+0+6cr9NH4Y1WEH0LXP2K+/ZzOB42zoEe//GpO3J3HUnhhveWUjU0iFl3d6Zi2eLpiFLgNn5VPaeqDwP1sJL/SKCBqj7syaRvGN6iTqWyTBwWQ8KJM9wxPY4z6Rl2h+Q5IVWgzWBYOdEa1rA4nTllDQajCjUioedjPpX0j58+y6gpKxFg8vAOxZb085JvP35VTVXV9aq6TlVPuz0iw/Bi0fUq8dpNbYjdc4z/fLMebxjatNhc/oQ1SteCR/7pZllUKUkwrT/Me9A62/cx5zIyuWvGKvYfS+WjoTE0qBqa/0rFwJQcNIxi1q91bR7q04xvVx/gnV+22x2O55StDL3Hw97lsO7Lom8veT980hcObYBBM6BmVNG3WYKoKk/N3sDynUm8OKCVRysDu1KkzTCMAhp7eRN2HUnhtZ+20rBaKP1a17Y7JM+Ivg1WTYOkIn7hJW6F6TfAmRPWgOjhnYsnvhLk4z928vnKfYzt2YQb23t27N9cE7+ItMtrRVVdldd8w/BnIsKLN7Zi37HTPPTlWupUKkvb+j40WHluAgJg+AIoVcSKt0e2gmbA8PlQK8c6kF7th/hDvPj9Zq5pVYsH+zTz+P7z6tXzq+NpMBADrMUacL018JeqdvFIhJhePYb3OppyluvfXcrps+nMvqczdSv7UUnnfSsguBJUK0BiSzkCoWHW87MpVvVPH7PhQDIDP1hOs5rl+WLMJQSXdl9108L06umpqj2xunK2U9UYVW0PtAX8qOHSMAqvSmgQk4fHcCY9k1FTYjmZds7ukDzjbAp8dhPMf9D1C73x31pdQncutl77YNI/lJzG6KmxVA4pzcdD27s16efFlYu7zVX1fP8sVd0ARLstIsPwMU2ql+f9W9uzPfEU981cTXpGpt0huV9QKPR8Anb/YSX0/KycBF+NgJqtfbJpB6xhPUdPW8nJtHNMGt6B6uXtu/nMlcS/SUQmikgPEekuIh9jDcRiGIaLujS17sb8dUsiz833k/8+MSOhZiv48UmrL35OVGHxK9Yvg6ZXWBdyy/retZDMTOWBz9ew8e8TvH1LW1rUqmBrPK4k/hFAPHA/8ACw0THNMIwCuLVTA0Z1aciUZbuZvny33eG4X0AgXP0qnDgAf7yW8zLbfoJfn4PWg6wqm0G+eQ3k5R+28OPGwzx5TUsub27/IPX5dudU1TQR+QBYoKpbPBCTYfisx69uwe4jKYyfu5H6VUN9fwD3+pdAh9H/XLDNrmkfq+ZOi/5WjyAf9GXsPj5YvINbO9VnROdwu8MBXDjjF5H+wBpgoeN1tIjMcXNchuGTAgOENx0F3cZ+usotoyuVONe8Bpfe88/rs6dh1h1wZJtVeiHyep9N+st3JPH4rPV0bRrG+P7uLbxWEK4c7XFYdfOPA6jqGiDcbREZho8rV6YUk4d3IDgokJFTVnLk1Bm7Q3I/VVj/tfWYfr01gMoB374VaGfiKe6cEUd4WCjv3NKO0oEl58vNlUjSVTXZ7ZEYhh+pXaksE4fGkHjyDGOmxZJ2zscLumVmwO+vwjej4O/VMHAKtBlkd1Ruc/z0WUZNjSUwQJg8zDOF1wrClcS/QURuAQJFpKmIvA0sc3NchuHz2tSrxOuDolm19zj/9/U63y7oFlgKrn0DqreEW760mnd81Nn0TO6cEceBY6l8NKQ99auWvAvWriT+e4FI4AzwGZCM1cPHMIwiurpVLR65MoI5a//mrUU+fl9k/Uvg7uXQuKfdkbiNqvLk7PX8ufMoL/+rNTEeLLxWEK4UabtGVZ8AnsiaICIDga/cFpVh+JG7ezRmZ2IKr/9sFXTr38ZPCrr5oA9/38mXsfu57/ImXN+2jt3h5MqVM/7HXJxmGEYhiAgvDIiiY3gVHv5qLXF73Dx8oeEWCzcc4r8LN9OvdS3+bUPhtYLINfGLyFWO9vw6IvKW02MKkO6xCA3DD5QpFcgHQ9pTq2IwY6bFsu+oGfPIm6zfn8wDX6ymTd1KvDqwTYnptpmbvM74/wZigTQgzukxB7jS/aEZhn+pEhrEpGEdOJeRyaipK/2noJuXO5ScxuhpK6kaWoaPh8bYVnitIPKqzrlWVacCTVR1qtNjlqqa36KG4QZNqpfj/dvaszMxhbGf+UlBNy+WciadUVNXknImg0nDY6hWvozdIbnElTb+cBH5WkQ2isjOrIfbIzMMP9W5SRjPXh/F4q2JPDtvo93hGLnIyFQe+GINmw5ahdea17S38FpBuNKr5xOsu3dfB3piFWgr2Q1YhuHlBnesz46EU0xcsotG1cox7LJwu0Mysvnvws38tPEw469tSc+I6naHUyCunPGXVdVFWKN17VHV8cDl7g3LMIzHrm5B7xY1mDA3nl+3JNgdjuHk8xV7+ej3nQy5pIFXfim7kvjTRCQA2CYiY0XkBsC7vt4MwwsFBghv3hxN85oVuPez1Ww55AcF3bzAsu1HeHL2Bro1q8a4a1uW+B48OXEl8T8AhAD3Ae2BIcAwN8ZkGIZDaJlSTBoeQ4ijoFviST8o6FaC7XAUXmsYFso7t7SlVAkqvFYQ+UatqitV9ZSq7lfVEao6QFX/9ERwhmFArYplmTgshqSUM4yZ7gcF3UqoYylnGTllJaUDA5g8vAMVgktW4bWCyPXirojMBXKtGqWq/d0SkWEYF2ldtxJvDIrmzhmreOTrdbx1c7RXNjF4q7PpmdwxI46DyWnMvL0T9aqUvMJrBZFXr55XPRaFYRj56htVi//rG8HLC7fQKCy0xJcF8BWqyuPfrmfFrqO8eXM07RuUzMJrBZFr4lfVxZ4MxDCM/N3VvTG7ElN4c9E2GlUL5broklsIzFe8v3gHX8ft5/5eTX3meOfbj19EdpFDk4+qNnJLRIZh5EpEeP6GVuw5eppHvlpH3cplfeIMtKT6fv1BXl64hf5tavNA76Z2h1NsXLkkHQN0cDy6Am8BM9wZlGEYuQsqFcCHt7WndqVgxkyLMwXd3GTd/uP8+8s1tKtfiZf/1dqnrqm40qsnyelxQFXfwNzAZRi2qhwaxKThVkG3kVNWcsIUdCtWB5NTGT01lqqhZfhwiHcUXiuIfBO/iLRzesSIyJ1AeQ/EZhhGHhpXK8cHQ9qz60gK93y6yhR0KyYpZ9IZNSWW02czmDy8g9cUXisIV5p6XnN6vAi0A25yZ1CGYbjmssZhPHd9FH9sO8KEuRt9e9xeD8jIVO7/fDWbD53gnVvaElHTN89x8724q6q+O0CmYfiAmzvWZ+eRFD76fSeNqoUyonNDu0PyWi8u2MTPmxJ45rpIenhZ4bWCcKWp5wURqeT0urKIPOfCepNFJEFENuQw72ERUREJK3DEhmFc5NG+zenTsgbPztvIL5sP2x2OV/rsr71MXLKLYZc2YOil4XaH41auNPVcparHs144BmG52oX1pgB9s08UkXpAH2CvayEahpGfrIJuLWpZBd02Hzphd0heZen2Izz93QZ6RFTjqX4t7Q7H7VxJ/IEicv7qhoiUBfK92qGqvwNHc5j1OvB/5FEOwjCMggsJKsWkYR0oF1yKUVNiSTiZZndIXmF7glV4rXG1crw92HsLrxWEK+9wBrBIREaJyEjgJ2BqYXYmIv2BA6q61oVlx4hIrIjEJiYmFmZ3huF3alYMZuLQDhxNOcuYaXGmoFs+jjoKr5UpFcDEYTGU9+LCawXhSj/+l4HngRZAJPCsY1qBiEgI8ATwtCvLq+pHqhqjqjHVqlUr6O4Mw2+1qluR1wdFs3b/cR76ai2ZmebHdU7OpGdw5/Q4Dp1I48MhMV5feK0gXBl6EVX9Hvi+iPtqDDQE1jrugKsLrBKRjqp6qIjbNgzDSd+omjzatzkvfb+ZxmGhPHhFhN0hlSiqymOz1rNi91HeGtyW9g0q2x2SR+VVlvkkObfDC6CqWqCRhVV1PU4jd4nIbiBGVY8UZDuGYbjmjm6N2Jl4ird+2U7DaqHc0Lau3SGVGO/9toNZqw7w797N6N+mtt3heFyuTT2qWl5VK+TwKO9K0heRmcByIEJE9ovIqOIM3DCMvIkIz13fiksaVeHRr9ezcndOfS38z/x1B3nlhy1cH12b+3o1sTscW7h8+VpEqotI/axHfsur6mBVraWqpVW1rqpOyjY/3JztG4Z7BZUK4IPb2lOnclnumB7H3iT/Lui2Zt9xHvxyDe0bVOalG32r8FpBuHIDV38R2QbsAhYDuyl6e79hGB5SKSSIycM7kJGpjJy6kuRU/yzoduC4VXitWvkyfDikvc8VXisIV874nwUuAbaqakOgF7DUrVEZhlGsGoaF8sFt7dl9JIWxn63inJ8VdDt1Jp1RU1Zy5lwGnwzvQFg53yu8VhCuJP5zqpoEBIhIgKr+CkS7NyzDMIrbpY2r8sINrfhj2xHGz4n3m4JuGZnKfTNXsy3hFO/e2o6mNXyz8FpBuNKd87iIlAN+Bz4VkQQg3b1hGYbhDjd1qMeOI6f4cPFOGlUrx6guvl/Q7fn5m/hlcwLPXh9Ft2bmniBw7Yz/OuA08G9gIbADuNadQRmG4T6PXtmcKyNr8Nz8jSza5NsF3Wb8uYfJS3cx/LJwhlzSwO5wSoxcE7+INBGRzqqaoqqZqpquqlOBNUAlTwVoGEbxCggQXh8UTWTtCtw3czWbDvpmQbc/tiUybk48Pf2k8FpB5HXG/wZwMofppx3zDMPwUiFBpZg4NKug20oSTvhWQbftCSe5+9NVNK1ejrdvaUdggH9228xNXok/XFXXZZ+oqrFAuNsiMgzDI2pWDGbSsA4cO32O26fFknrWNwq6JZ06w4gpKylTKpCJw2IoV8alyjR+Ja/EH5zHvLLFHYhhGJ4XVacib94czboDyTz01RqvL+h2Jj2DO6bHkXDiDB8PbU/dyv5TeK0g8kr8K0Xk9uwTHaUX4twXkmEYnnRFZE0eu6o5C9Yf4n8/bbU7nEJTVf7zzXpi9xzjtZva0La+fxVeK4i8fgM9AHwrIrfyT6KPAYKAG9wcl2EYHnR710bsSEjhnV+30zAslBvbe19Bt3d+2c63qw/wUJ9m9Gvtf4XXCiLXxK+qh4HLRKQnEOWYPF9Vf/FIZIZheIyI8Oz1Uew9epr/zFpHvSohdGxYxe6wXDZv3d+89tNWBrStw9jL/bPwWkG4MhDLr6r6tuNhkr5h+Kisgm71Kodwx/RYdh9JsTskl6zee4yHvlxLTIPKvHhjK78tvFYQvj+4pGEYLqsYUppJwzugYBV0O12yC7rtP3aa26fFUqNCMB8OaU+ZUv5beK0gTOI3DOMCWQXd9h09zd2fxZXYgm4n084xemosZ9IzmTw8hqp+XnitIEziNwzjIpc0sgq6Ld2exNPflbyCbukZmecLr71/a3uaVDeF1wrC3NlgGEaOBsbUY+eRFN7/bQeNq4Uyumsju0M677n5m/h1SyLPXR9Fl6ZhdofjdUziNwwjV49cEcGuxBSeX7CJ8Kqh9G5Zw+6QmL58N1OW7WZk54bcZgqvFYpp6jEMI1dZBd2ialfkvs9XE/93sq3xLN6ayPi5G+nVvDpPXNPC1li8mUn8hmHkqWyQVfOmYtnSjJ4aa1tBt62HTzLWUXjtzcFtTeG1IjCJ3zCMfNWoEMzEYTEkp55jtA0F3Y6cOsPIKSsJDgpk8vAOpvBaEZnEbxiGSyJrV+TNm9uy/kAy//7CcwXd0s5ZhdcST57h46Ex1K5kakQWlUn8hmG4rE/LGjx+VQsWxh/i1R+3uH1/qsqj36wjbs8xXh8UTXS9Sm7fpz8wv5cMwyiQ0V0bsvPIKd77bQcNw0IZGFPPbft6a9F2vlvzN49cGcHVrWq5bT/+xpzxG4ZRICLCM9dF0blJVR7/dj1/7kxyy37mrP2b13/eyo3t6nJ3j8Zu2Ye/MonfMIwCKx0YwHu3tKdelRDunBHHrmIu6Ba35xgPf7WWjuFVeGFAlCm8VsxM4jcMo1AqhpRm8rAOAIyaUnwF3fYdPc0d02OpVTGYD0zhNbcwid8wjEILDwvlw9vas+/Yae76tOgF3bIKr51Nz2TSsA5UCQ0qpkgNZybxG4ZRJJ0aVeWlAa1ZtiOJp2ZvKHRBt/SMTMZ+tpodiad4/7b2NKlerpgjNbKYXj2GYRTZje3rsvPIKd79dQeNqoUyplvBL8Y+O28ji7cm8uKAVnRuYgqvuZNJ/IZhFIuH+kSw60gKL36/mfCqoVwRWdPldacu283U5XsY3aUhgzvWd2OUBpimHsMwiklAgPDawGha16nI/Z+vYcMB1wq6/bYlgQlz4+ndogaPXW0Kr3mCSfyGYRSbskGBfDw0hsohVkG3Q8l5F3TbcugkYz9bTfOaFXjz5mhTeM1DTOI3DKNYVa8QzMRhHaweOtNWcvpseo7LJZ60Cq+FBAUyaXgMoabwmseYxG8YRrFrWbsCbw1uS/zfJ3jg84sLuqWdy2DM9FiSUs4wcVgMtSqawmueZBK/YRhu0atFDZ64ugU/bjzMyz/8U9BNVXnk63Ws3nucNwZF07puJfuC9FNuS/wiMllEEkRkg9O0Z0VknYisEZEfRaS2u/ZvGIb9RnVpyC2d6vPB4h18GbsPgDd+3sbctX/zf30j6BtlCq/ZwZ1n/FOAvtmmvaKqrVU1GpgHPO3G/RuGYTMRYUL/SLo2DePxWet5fv5G3ly0jYHt63JXd1N4zS5uS/yq+jtwNNu0E04vQwHPjORgGIZtSgcG8M4t7WhQNYSP/9hFx4ZVeP6GVqbwmo08fhldRJ4HhgLJQM88lhsDjAGoX9/c0GEY3qxi2dJMGdGRqct2c0/PJgSVMpcX7SSFravh0sZFwoF5qhqVw7zHgGBVHZffdmJiYjQ2NtYNERqGYfguEYlT1Zjs0+382v0MuNHG/RuGYfgljyZ+EWnq9LI/sNmT+zcMwzDc2MYvIjOBHkCYiOwHxgFXi0gEkAnsAe501/4NwzCMnLkt8avq4BwmT3LX/gzDMAzXmEvrhmEYfsYkfsMwDD9jEr9hGIafMYnfMAzDz7j1Bq7iIiKJWL2ACiMMOFKM4RQXE1fBmLgKxsRVMCU1LihabA1UtVr2iV6R+ItCRGJzunPNbiaugjFxFYyJq2BKalzgnthMU49hGIafMYnfMAzDz/hD4v/I7gByYeIqGBNXwZi4CqakxgVuiM3n2/gNwzCMC/nDGb9hGIbhxCR+wzAMP+MziV9E+orIFhHZLiL/yWG+iMhbjvnrRKRdCYmrh4gkOwagXyMibh+HWEQmi0iCiGzIZb5dxyq/uDx+rBz7rSciv4rIJhGJF5H7c1jG48fMxbjs+HwFi8gKEVnriGtCDsvYcbxcicuWz5hj34EislpE5uUwr3iPl6p6/QMIBHYAjYAgYC3QMtsyVwPfAwJcAvxVQuLqgTVKmSePVzegHbAhl/keP1YuxuXxY+XYby2gneN5eWBrCfl8uRKXHZ8vAco5npcG/gIuKQHHy5W4bPmMOfb9INYAVRftv7iPl6+c8XcEtqvqTlU9C3wOXJdtmeuAaWr5E6gkIrVKQFwep6q/A0fzWMSOY+VKXLZQ1YOqusrx/CSwCaiTbTGPHzMX4/I4xzE45XhZ2vHI3ovEjuPlSly2EJG6wDXAxFwWKdbj5SuJvw6wz+n1fi7+D+DKMnbEBXCp4+fn9yIS6eaYXGHHsXKVrcdKrHGk22KdLTqz9ZjlERfYcMwczRZrgATgJ1UtEcfLhbjAns/YG8D/YQ1SlZNiPV6+kvglh2nZv8ldWaa4ubLPVVj1NNoAbwOz3RyTK+w4Vq6w9ViJSDngG+ABVT2RfXYOq3jkmOUTly3HTFUzVDUaqAt0FJGobIvYcrxciMvjx0tE+gEJqhqX12I5TCv08fKVxL8fqOf0ui7wdyGW8Xhcqnoi6+enqi4ASotImJvjyo8dxypfdh4rESmNlVw/VdVZOSxiyzHLLy67P1+qehz4DeibbZatn7Hc4rLpeHUG+ovIbqzm4MtFZEa2ZYr1ePlK4l8JNBWRhiISBNwMzMm2zBxgqOPq+CVAsqoetDsuEakpIuJ43hHrb5Lk5rjyY8exypddx8qxz0nAJlX9Xy6LefyYuRKXHcdMRKqJSCXH87JAb2BztsXsOF75xmXH8VLVx1S1rqqGY+WIX1T1tmyLFevxctuYu56kqukiMhb4AasnzWRVjReROx3zPwAWYF0Z3w6cBkaUkLj+BdwlIulAKnCzOi7ju4uIzMTqvRAmIvuBcVgXumw7Vi7G5fFj5dAZGAKsd7QPAzwO1HeKzY5j5kpcdhyzWsBUEQnESpxfquo8u/8/uhiXXZ+xi7jzeJmSDYZhGH7GV5p6DMMwDBeZxG8YhuFnTOI3DMPwMybxG4Zh+BmT+A3DMPyMSfyGVxGRDLGqJm4QkblZ/bKLYbvDReSd4thWtu2WEpEXRGSb/FPx8Yli3P4UEflXcW3P8A8m8RveJlVVo1U1Cqug2z12B5SP54DaQCtHqYCuOO5NcOa4Mcf8fzQ8wnzQDG+2HEehKhHpKCLLxKpnvkxEIhzTh4vILBFZ6DjrfjlrZREZISJbRWQx1s1QWdMbiMgiseqeLxKR+o7pU0TkfbFq4O8Uke5ijSGwSUSmZA9OREKA24F7VTUNrCqaqjreMT/cse57WDVi6jm2HyvZ6sWLyG4R+a9Y9eRXiEgTp111c7znnebs33CFSfyGV3LcfdmLf0pgbAa6qWpb4GngBafFo4FBQCtgkFgDmNQCJmAl/D5AS6fl38Eqgdsa+BR4y2leZeBy4N/AXOB1IBJoJSLR2cJsAux1lEzOTYRjX21VdQ/whKrGAK2B7iLS2mnZE6ra0RHfG07TawFdgH7AS3nsyzAAk/gN71PWUZ4gCagC/OSYXhH4SqzRu7KScZZFqprsOOveCDQAOgG/qWqiY6yEL5yWvxRrQAyA6VhJNctcxy3864HDqrpeVTOBeCA8r8AdvzDWiMg+EckquLXHUV89y00isgpY7XgPzl9IM53+vdRp+mxVzVTVjUCNvGIwDDCJ3/A+qY628gZYo5pltfE/C/zqaPu/Fgh2WueM0/MM/qlR5Wq9EuflsraVmW27mVxc+2o7UF9EygOo6ieO2JOxajcBpGQtLCINgYeBXo5fG/OzvQ/N5blzHDmV7zWMC5jEb3glVU0G7gMeFqs0cUXggGP2cBc28RfQQ0SqOtYf6DRvGVaVRIBbgSWFjPE0VvXMd0QkGM43UQXlskoFrC+CZBGpAVyVbf4gp3+XFyYmwwAfqc5p+CdVXS0ia7GS9MtYlRcfBH5xYd2DIjIeK4EexLq4mnUWfh8wWUQeARIpWiXEJ7B+jWwQkZNYFR+nYtVSr50tprUishqr2WgnsDTbtsqIyF9YJ2yDixCT4edMdU7D8AJiDdIRo6pH7I7F8H6mqccwDMPPmDN+wzAMP2PO+A3DMPyMSfyGYRh+xiR+wzAMP2MSv2EYhp8xid8wDMPP/D9ZWI5XcsfXlQAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.plot(value_dc_qaoa_ls, label=\"DC-QAOA\")\n",
    "plt.plot(ubound_sdp_ls, label=\"SDP upper bound\", linestyle=\"--\")\n",
    "plt.title('Max-Cut Performancce')\n",
    "plt.xlabel('Random Graph')\n",
    "plt.ylabel('Calculated Optimal Max Cut')\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从上面的线形图中，我们可以说明``量子近似优化分治法``找到的最大割和理论上限接近。\n",
    "\n",
    "## 应用\n",
    "\n",
    "最大割问题属于应用范围很广的二次无约束二值优化（quadratic unconstrained binary optimization, QUBO）问题。此类问题的应用范围十分广泛，上至为NP-困难问题创建模型，下到找自旋玻璃的基态 [5]。同时最大割问题本身也有很广泛的应用。\n",
    "\n",
    "最大割问题和很多领域都有紧密的联系，比如超大规模集成电路（VLSI circuit）设计，统计物理。减少超大规模集成电路设计所用的孔和寻找自选玻璃基态都可以归约到最大割问题 [6]。更重要的是，最大割问题给很多算法或者技术提供了一个测试台。比如适用于最大割问题的半正定规划方法被后续用在了数据集合设计 [7] 和相位检索上 [8, 9]。\n",
    "\n",
    "更多关于最大割的应用可以在 [10-12] 里找到。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## 参考文献\n",
    "\n",
    "[1] Akshay, V., et al. \"Reachability deficits in quantum approximate optimization.\" [Physical Review Letters 124.9 (2020): 090504.](https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.124.090504)\n",
    "\n",
    "[2] Li, Junde, Mahabubul Alam, and Swaroop Ghosh. \"Large-scale Quantum Approximate Optimization via Divide-and-Conquer.\" [arXiv preprint arXiv:2102.13288 (2021).](https://arxiv.org/abs/2101.03717)\n",
    "\n",
    "[3] Goemans, Michel X., and David P. Williamson. \"Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.\" [Journal of the ACM (JACM) 42.6 (1995): 1115-1145.](http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf)\n",
    "\n",
    "[4] Burer, Samuel, and Renato DC Monteiro. \"Local minima and convergence in low-rank semidefinite programming.\" [Mathematical Programming 103.3 (2005): 427-444.](https://link.springer.com/article/10.1007/s10107-004-0564-1)\n",
    "\n",
    "[5] Kochenberger, Gary, et al. \"The unconstrained binary quadratic programming problem: a survey.\" [Journal of Combinatorial Optimization 28.1 (2014): 58-81.](https://link.springer.com/article/10.1007/s10878-014-9734-0)\n",
    "\n",
    "[6] Barahona, Francisco, et al. \"An application of combinatorial optimization to statistical physics and circuit layout design.\" [Operations Research 36.3 (1988): 493-513.](https://www.jstor.org/stable/170992?seq=1)\n",
    "\n",
    "[7] Poland, Jan, and Thomas Zeugmann. \"Clustering pairwise distances with missing data: Maximum cuts versus normalized cuts.\" [International Conference on Discovery Science. Springer, Berlin, Heidelberg, 2006.](https://link.springer.com/chapter/10.1007/11893318_21)\n",
    "\n",
    "[8] Candes, Emmanuel J., et al. \"Phase retrieval via matrix completion.\" [SIAM review 57.2 (2015): 225-251.](https://epubs.siam.org/doi/10.1137/110848074)\n",
    "\n",
    "[9] Waldspurger, Irene, Alexandre d’Aspremont, and Stéphane Mallat. \"Phase recovery, maxcut and complex semidefinite programming.\" [Mathematical Programming 149.1 (2015): 47-81.](https://link.springer.com/article/10.1007/s10107-013-0738-9)\n",
    "\n",
    "[10] Deza, Michel, and Monique Laurent. \"Applications of cut polyhedra—I.\" [Journal of Computational and Applied Mathematics 55.2 (1994): 191-216.](https://www.sciencedirect.com/science/article/pii/0377042794900205)\n",
    "\n",
    "[11] Deza, Michel, and Monique Laurent. \"Applications of cut polyhedra—II.\" [Journal of Computational and Applied Mathematics 55.2 (1994): 217-247.](https://www.sciencedirect.com/science/article/pii/0377042794900213)\n",
    "\n",
    "[12] Poljak, Svatopluk, and Zsolt Tuza. \"Maximum cuts and largest bipartite subgraphs.\" [DIMACS Series 20 (1995): 181-244.](https://arxiv.org/pdf/1810.12144.pdf)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Raw Cell Format",
  "interpreter": {
   "hash": "3b61f83e8397e1c9fcea57a3d9915794102e67724879b24295f8014f41a14d85"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.13"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}