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": 14,
   "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": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-16T03:41:44.839484Z",
     "start_time": "2021-05-16T03:41:44.455664Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA1MAAADnCAYAAAD7CwxiAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAABKwElEQVR4nO3dd5hcdfXH8fcnvRBCr0rviFQLvWNCl04ggFKkKr0oSO8ISBeB0Kt0aSKCVGkiICDlh9RQAyFl03N+f3xvJNmd2TKZmTvl83qefZSdO3fOZmfv3PMt5ygiMDMzMzMzs67plncAZmZmZmZm9cjJlJmZmZmZWQmcTJmZmZmZmZXAyZSZmZmZmVkJnEyZmZmZmZmVwMmUmZmZmZlZCZxMmZmZmZmZlcDJlJmZmZmZWQmcTJmZmZmZmZXAyZSZmZmZmVkJnEyZmZmZmZmVwMmUmZmZmZlZCZxMmZmZmZmZlcDJlJmZmZmZWQmcTJmZmZmZmZXAyZSZmZmZmVkJnEyZmZmZmZmVwMmUmZmZmZlZCZxMmZmZmZmZlcDJlJmZmZmZWQmcTJmZmZmZmZXAyZSZmZmZmVkJnEyZmZmZmZmVwMmUmZmZmZlZCZxMmZmZmZmZlcDJlJmZmZmZWQmcTJmZmZmZmZXAyZSZmZmZmVkJnEyZmZmZmZmVwMmUmZmZmZlZCZxMmZmZmZmZlcDJlJmZmZmZWQmcTJmZmZmZmZXAyZSZmZmZmVkJeuQdgBUmMSewO7AaMDswGngDuCqC9/OMrbMkugE/AbYB5gMC+AS4A3g4gqk5hmdmNUpiADAEWAuYE2gB3gWGRfBGnrGZWfOSELAmsDOwIOk++nPgfuDuCCblGJ7lRBGRdww2HYnvA78GtgKmAv2me3hi9r2ngdMieKT6EXYsuxHaHzgU6AsMmO7hAMaSksPfAZdFMLbqQZpZzZFYHDgK2JV0res/3cOTgMnAv4HTgbsi8AeYmVWcRC/g58CRwNyke7PpV3eNBqYAFwHnRzCi6kFabpxM1RCJnYArgd5A9w4ObwHOBX5bSzcUEgsCj5FGbPp2cPg44D1ggwg+rWxkZlbLJDYC7gT60PGqibHArcA+EUyudGxm1rwkBgIPACsy4wB3IeOBkcB6EbxZ4dCsRjiZqhES2wPX0HECMr2xwO8j+E1louoaibmAfwHz0vklpJOA4cDKEXxdodDMrIZJrEO6WenoRmV6LaTka2gtDSiZWeOQ6As8AyxDGujujKnAN8AqEbxXodCshrgARQ2QWBK4mq4lUpCWwBwssWnZgyrN7aTp767sxesJzE8aZTazJiMxB/BnupZIkR2/NbBPuWMyM8tcAixF5xMpSPfWswJ/yfZYWYNzMlUbDiYlFW1cdx0MHw7ffANvvgl77tnmkH7A8ZUNr2MSywE/AHpN//1eveCKK+C992DUKHjpJRg0qM3TewFrSSxRlWDNrJbsSZFlzZ24/vUHjvMNi5mVW1YIbCcKDHQvsww88giMHAlvvw1bb93m6d1JA8XrVzhMqwFOpnIm0R/YgyLJ1OmnwyKLwMCBsOWWcMopsMoqbQ77vsQyFQ20YwdT4Gfo0QM+/BDWXTf9DMceC7feCgsv3Ob53YGDKh+mmdWKrOLnoRSZlerk9W8gvmExs/L7ObStOty9O9x9N/z5zzDHHLDPPnD99bDkkm2e3x84ogpxWs6cTOVvWwr8sU7z+uswcWL6/xHpa/HF2xzWHdivQvF1SKI3sAsFlve1tMCJJ8L776fY77sP/vtfWHXVNqfpCewpuVy/WRNZlxkr9s2gk9e//qTBHDOzcvoVBQZ6llkGFlgAzjsPpk6FRx+Fp56CoUPbPF/A+hLzVCFWy5GTqfwtSTs3EwAXXwxjx6ZlLp98Avff3+aQnsD3KhRfZ3T6QjHPPLDUUvDaawUf7k7qqWVmzWFJOqhc2onrn4BlKxSfmTWhbOnw/F04nu8VvgsbD7Rdi2MNxclU/uaA9tf7H3AADBgAa60Fd9wBEyYUOuqFDSRFHl+w7AcwqsPN4z16wA03wDXXpBujAqYwY08qM2tsA+igYE3nrn/tD0iZmXVRHyhcJfTNN+Hzz+GII9J9zcYbp60M/YrfBfm+psE5mcrfCIr8wU5v6tQ0jfyd78B+BRf0rfZIRCiPL3jjuzBrS3vxS2kz+cSJcOCBRQ/rDozq6N/CzBrGKOi4T1TH1z/GlDswM2tq4yky0D15cio4sdlm8OmncNhhaS/4Rx8VPZfvaxqc96fk703SjUCnRi569Ci4Z2AS8HJ5w+qSzzs64MorYd55YdNN04WoiEngXlNmTeQtmBqdHdcrfP2LAF7vYILfzKzTIgiJj4CFCj3+6quw3nrf/vdTT6VVNwX0BveaanSemcrfHRS5C5h7bthxR+jfH7p1g002gZ13TuU4W5kCXFrhOIuKYCKpT9akQo9feiksuyxssQWMH1/0NBOBP0YwpSJBmlnNkNRb0rbQ7RD4tODimM5f/1qAQStKOlrSdysevJk1i/OAsYUeWGEF6N0b+vZNM1Pzzw9XX93msAAejuDLyoZpeXMylbMIxkFcCVPazNdEpCUtH30EX38N55wDBx8M997b5jQvRvBONeJtxwUUWK6z0EKw776w0kppOnz06PQ1ZEjrI6cGcFEV4jSzHChZXdKlwHDgQIi7od+vSRnRDDp//ev3AfxtKLAY8LKkv0raXZL3KZjZzLiaIgVyhg5NBXE+/xw23DDtm5pWeXQ6Y4FzKhui1QJFdLhdxypI0tyw4jXw9CDoV8o6lRbgpxH8pdyxdZXEX4G16FqncGDSZPjbVBi0L3B1+E1p1jAkLQbsCgwlzaJfC9wQEe+nx5mNtAxmYAmnHwscFMGw7LX6AFsAuwFrA/dmr/e3iPCst5l1icQfYPIe0KNX1545ZSp0+w/oexEd74u3+uaZqRxJ2gZ4BV5+DSZsD4zr4ilagDNqIZHKbA98QpHlfkVMhJ7vwanrk3o63CNpgUoEZ2bVIWk2SXtLegJ4FpgbGAIsGxGnTUukACIYCQymwOxUB1qAm0mjx9m5YnxE3BYRWwBLAc8DpwMfSDpL0goz8WOZWRORJBj4PrwKTC1cR7SgmAKjp8Jyb4O6mIRZPXIylQNJc0i6ATgT2C4ijoiY/XZS49sWOq5uFdlxJwOnVDTYLojga+DHwNt07saoBXgDWD3i8aeBHwIvAf+StEu6kJlZPZDUU9Lmkm4F3gd+ApwNLBgRB0XE88VmnSN4BhgEjCbtn+zIWGAYsE+xUd+I+DwiLoiI1YCNSbNi90t6SdIhkubr8g9pZk1BUnfgIhi1I5z8Pej2DEX2T7UyDjQcPloB/jMZeEjSbBUN1nLnZX5VJmkz4HLgT8AxEdEy4+MsAxwB7AxMZcb+KdPKN/yVNCP1VOUj7jqJfsCepJ9jdtLPMC0xmkpKor4EzgKGRTB+xudrNeAaUqXDfSOiw2qBZlZ92YDHKqRldTsB75CW1d0aEV2uzCmxEHAIsFf2rVmme3gi6frxLHBmBA+UEG93YN0s3q2AZ7J4746Irq4MMLMGJKkfcCPp3mXbiBgl0YM04H0ksAhpO8P0+6lGk1YXnQdcFsFISd2A35EGcwZHxIfV+ymsmpxMVYmkgaQ/svWBn0XEY+0fz6ykZTErA3MC35CSi+si+KSy0ZZH1kF8XWBLYNoo8KfAncCT7a0jzvY+nADsARwUEbdVNFgz67Ssat4upKSkDykhuT4iylIIR6Ivadnwj0lLBMcC75Kuf/8tz2uoP7A16Wf4Aem6dC3wRERMLcdrmFl9kTQXaa/l28BeEdFmplxiVWAHYEGgJ+m+5i/Ag4UqEks6BDgU2CwiXqlg+JYTJ1NVIGkT4ArgPuDIiBidc0h1Q9KPSbNULwEHRMSInEMya0pZdbxtSMnHSqTZ9euAp+q9aEy2T3MIsDup59/1wHUR8WaugZlZ1UhaHHgAuBU4rpzXNUnbAxcDO0dE2wY3VtecTFVQdvNxNrApsGdEPJxzSHVJUl/gVNIyon0j4p6cQzJrCtmyuA1Jlfi2AB4nJVD3RkTxrnF1Klu2uCLp5x0CfECarbrZAzlmjUvSD4C7gRMj4g8Veo21SYNQh0fEdZV4DcuHC1BUiKT1gVdIU8ArOJEqXUSMi4hDgR2B8yRdK2n2vOMyy4PEIhLnSHwuMVFiisRoiQclNsyW187ka2gFSWeRkolTgeeAJSNiy6xaXsMlUgCR/CsiDgO+CxwPrAn8n6Q7JW0jqYutH9qS+K7E6RKfSkzIfodjJB6R+Inkz2azapG0OWnl0C8qlUgBRMQTpK0eJ0s6xkW2GodnpsosW4d/Omk5zC8i4r6cQ2ookmYhVUHcEtg7Ih7MOSSzqpBYGLgKWIM0ENa65G6Q9hZ9A/wygju6dn7NRyp8sxswF98udXt9JkOve5JmBbYl/dusANxGmrH6R1eWAkksSPodrkMqylMoMRtN+j0eGsFNMxm6mbVD0i9I+7O3iojnqvSaC5CSt3+Q9oR3VMHZapyTqTKStCap58mzwC8j4qt8I2pckjYErgQeBg6LiFE5h2RWMRLfBx4lNbbt3sHhkCpmnhDB2e2fV31JVe12A1YnLXO5FnjMRRgKk7Qw3xbf6E5a9nhdRLRbGENiWdIyydmAHp14qRbgrAhOnKmAzayNbFboZNKKl8HlKp7ThdcfQFryN4G0j6ozZdetRjmZKoPshuRk0gfs/hFxZ84hNYVstHha2dE9vanTGlFWLvwlUpuBriwLaSHNUF054/nUDViblAxsQxr8uQ64yx/onZfdjK3Gt2Xh3yD9O94WESNnPJYFgH+RZvy6+js8KoKLyhCymQGSegF/BJYGtoiIL3KKoyepVc5yWRxuA1OnnEzNJEk/JFWbe5VUbS6XP8pmJmkQ6cJ4D3BURIzJOSSzspH4C7ABnZuRam08sFAEX0hamlRYYVdgFGkG6saIGF62YJtUdnM2mPTvuzHwICmxeigiJkncBWxG52akWhsPLBHBx2UK16xpZYOwfyL1hNq5da/PHOIRaZnhLsCgas+QWXl4k2uJJPWWdCqpH8EJEbGDE6l8ZPumViA1+HxZ0jo5h2RWFhLfJc0iFU2kllgCxo2D6wrWhpoacMcfJT0LPAb0Je0N+H5EnONEqjwiYmJE3B0R2wGLkpZkHgN8JC19OUwdTKtEqlcvuOIKeO89GDUKXnoJBg0q+hL7VjB8s6aQ7VV6nNRcfJu8Eyn4X9Gb40l7wZ+Q9KO8Y7Kua9qZKYl5gJ+TmkLOTtrw+x/gjxG80f5ztTJpNupdUqnuTyscrnWSpC2BS0l9In4dEeOKH0svUtPOnwLzAlOBT4CbKdJ8z6yaJE4HDqFwoQIAHnoI+vaF99+HoUMLHTFyAiy4DbT8xRudq0vSEnDT5bDVetB3huV9/frBEUfA1VfDBx/AppvCTTfBCiuk32UrXwPzRjCpOpGbNRZJy5OKPlwGnFmLvfEkbQYMIzULdguYOtJ0yZTEysBxpCUZQRqpnWYyMAl4DTg1grtmfK56Ar8GDgAOA66vxT/IZidpTuAiYBVg94j4x4yPMwdwOLAfacR/QKtTjCYtrTkPuCAC7yOxXEgMB+Yv9viOO8I228Drr6cZqsLJFKOBjSN4tkJhWjsk3iXNVnXo5ZfhxBPhjrZ1GEcBW0XwWHmjM2t8ktYlDbAeFhHX5x1PeyStRtqycHJEXJp3PNY5TbXMT2Jn4ElS9ao+zJhIQVqG0Ze0qfh6iYultLxG0vdIZSx/BKwcEdc5kapNETEiInYGfgPcJelMSX0AJJYg9f86lFRVq3UiRfa9uUlJ9wsS81UlcLO2Ziv2wIABcNJJcOihHZ5jKjBPGWOyrpmjMwfNMw8stRS89lrRQ+YuW0RmTULSjqRWBkNqPZECiIgXgLWAgyWd7l5U9aFpkimJ7UiltPvRuZ+7P7AHTLlE6n4MaQ38JcBmEeGNwHUgIv4EfB9YAnhR+vlg4BnSSH9nGm/2zZ77jFT8ptasgorulTr5ZLjySvi446uRSM3DLR8dFp3o0QNuuAGuuQbefLPgIaJtXzEzK0LJocDZwEb1VO03It4lNQtfF7g2K3BjNawpkimJRUl7nFrPRHWkH0zcC/YdAqwWEVd6Nqq+ZKVGt4Nup8Jh98CUOeja+74HKfm6oSIBmrWv4BLTFVeEjTaC887r1DmCtOfG8jG6vQelVDxk4kQ48MCih03Fv0OzTpHUnbRM/2fAGhHxSs4hdVlEfAlsSBrYv1/SwJxDsnY0RTIF/JJ2Rgfbr4bVtxtc1D0i2m4JtrqQEuAp/wfLToTuM7znDzgAnn8exo+HYcOKnqI3sIHEIhUO1ay1v5NupGew3nqwyCKpcMEnn8Dhh8O228KLLxY8Ry/gnxWN0trzCBQvZnPllTDvvOn3N7l4eZA+wHMViM2soWR9P28BVgTWjoiPcg6pZFkBre1JPeyekPSdnEOyIho+mZLoC+xFO0skLr443VC3c5aFJVYrd2xWVYdBtz6tvzl8OJxyClx1VYfPF7B/JQIza8c5pH4oM7j8clh8cVhppfR12WVw333wk5+0ef5k4NYIvql4pFbMucCEQg9ceiksuyxssUUa0CliKnBPBF9WKD6zhpAVn3oYmEjq2TQy34hmXkRMIU0IXAc8ne3ftxrT8MkUsCVpmUtBO+4II0fCI+2vpu1NquBndUhiAOl90Ob9fuedcPfdMGJEh6fpDewr4c2gVk1PA5+1/ua4cfDZZ99+jRmTbsa/bHu7PZG03MVyEsE/gfdaf3+hhWDffVMy/OmnMHp0+hoypM0pxgG/q3igZnVM0qLAU6QiY7tGRMEBjHqU9aI6GzgK+Juk9fOOyWZUSjf2erM4qehEG9OqYW2wAey1V7vn6A4sW4HYrDrmJ91UdqboRHv6kNYvj5npiMw6IYKQOAj4E+3s+TzxxILfHkfql/ZyZaKzLvglqcH7/36HH3yQ9kt1YBypyaiX+JkVIWlVUjnx0yLi4rzjqZSIuEnSp8DNkg6OiJvyjsmSZpiZGkCRilhdqIY17TxWn2ahndnJLpiM3wdWZRHcT+qL1tKFp40DXgbaznNY1UXwCGl1Q9Em4gWMIzWS3y6iLNcvs4YjaTDwAHBAIydS00TEo6TCFGdIOsKl02tDM8xMfUO6CZ7hZ51WDWvllTt9nlFljsuqZzTlGTjoid8HloMILpEYATEMxvdOhXEKmkyahb0f2DWi8F4dq74IhkmMBK4nDe70L3zkJKDbeOj+CLBDRJcSMLOmIWlP4BRgq4h4Ju94qiUi/i1pDdJ1fqFslqpokRurvGZIpt4gjfDNMKMwfTUsgFlmge7dYbnlYNVV25xjMvBSpQO1ivmYdvr1dMEoujY7YFY2EdwirTIZNr0QTpkKGsiMVeJ6kUr4nx9B8davlpsI7pSYHxgKHAHMRfp8maYXvPwqHD464rEtcgnSrMZlszHHk/6O1o2It3IOqeoi4mNJ6wC3A3+SNCSr/mc5UKO3TZLoSdrAPfv03+/bF2ad9dv/PvzwlFztt1/BTdzjgFUjeKOiwVrFSFwJ7EarAYTu3VPDzOOPh+98B/beO5UnntJ2jGcccGYEhXenmFWBpMeAP0LcSCr9Oy8pifoaeDmi/Z5GVjuyYjYrAPOR9nOOBF4BTQL+S7pJ/E9+EZrVHkk9gT+Q/nY2j4g2BXqaSdbQ9ypgMWDLrD+VVVnDJ1MAEieRRgHblMae5vjjU7+poUMLPvx8BD+sUHhWBRIrAM/SahP/8cfDCSfMeOwJJxTc0D8eWDSCTysVo1l7JK0O3AgsGRHFOxJZ3ZN0HLBIROyZdyxmtULSAOA20mzujhFRsKl5s8lm6k4FtiOVhH8355CaTrMkU/MDb5EKEXRVC2kD8APljcqqTeIx4Md0varfOOCOCHYte1BmnSTpLuDhZthk3ewkzQG8DaxYz01HzcpF0vzAfcALwP4eUGpL0n7AcaQ9ZO12T7XyaoZqfkTwCanPUFf3u7SQlnY5kWoMPwU+LbiIr7jxwJukxs9muZC0HGkgoOP20lb3IuIrYBhwaN6xmOVN0jKknnu3A79wIlVYRFwK7AvcJ2mzvONpJk2RTAFE8CgpoRpDqnbVnqmkROok4OQKh2ZVEsHXsOUB8HbA1M5s1BwLPA+sG8H4Codn1p4jgQu8wbipnAfsIWnOvAMxy4uktYDHgBMi4tRohuVUMyEi7gG2AK6QtHfe8TSLpljmNz2JhYFfQcsvoeck6Dn9PqpxgEjlJs+K4NlcgrSKkDQf8AJ85yD4cB7SDeq8pKbO03o1TIHxggkfwsDjgJsjmJRTyGZIWohUTXTxiBiZczhWRZKuAD6IiJPyjsWs2iRtC1wK7BoRf8k7nnoiaUlS/60bgeOdhFZW0yVTAJLmhT5vwvBDYfblgLlJ/aj+D7gxgi/yjdDKLasA9FfgsYg4Pn0PAWsAg4D5STOSw2FoL7h+4YjYJbeAzTKSfg9MiIgj847FqkvS0sATwKLebG/NRNKvSIXDNo+If+UcTl2SNA9wL6lF0N4R4YHhCmnWZOpA4EcRUbh2nzUcSecAy5MuzO3umZI0N2nz94K+gbE8SZqLVDznexExPO94rPok/Ql4PCIuyDsWs0qT1A04GxgMDI6I93MOqa5J6g/cRKpmvV1EjMo5pIbUNHumWhlCenNZE5C0A7ANsEtnuoRHxBfAM6R1x2Z5Ogj4kxOppnYmcFg2u27WsCT1Id2brQas6URq5mUDwtuQVl79XdICOYfUkJoumZK0KLAk8HDesVjlZVXQLga2zSpkddaNpKTbLBeSZgH2J43SWpPKShy/DeycdyxmlSJpduCh7D9/EhFf5xlPI8mqH+4P3AI8nd0XWRk1XTIF7EQa6fXa0QYnaVbgDuCIiHipi0+/C1g36/diloe9gUcj4u28A7HcnQEclS2BMmsokhYGniL1kNo5Ilw9t8wiOYPUh+pRSWvnHVMjacYL8xDSrIM1sKwj+DBSwYmru/r8iBhNGiXbtsyhmXVIUi9Sj6Ez847FasIjpGqzm+cdiFk5SVqJlEhdHhGHRcTUnENqaBFxHbALcLuk7fOOp1E0VTIlaQVgIOkP1xrbEcB3gF/NxDluwkv9LB+7AG9ExIt5B2L5y8oanwEckw0UmdU9SZsAfwEOjojzcw6naUTEX4GNgXMlHZJ3PI2gqZIp0przmz3y0dgkbQAcQqpcM2EmTvUAsKKkBcsTmVnHsqVcR5Funs2muROYE/DyHKt7knYHrgW2iYg/5R1Ps4mIl0mtYfaUdL6k7nnHVM+aJpnKRvN2xkv8Gpqk7wI3kCr3fTgz58rWbd8F7FiG0Mw6aytgFPBo3oFY7cgqkZ4FHJ13LGalUnIscAKwXkQ8mXNITSu7R1oLWBG4RVLfnEOqW02TTAE/BsYDL+cdiFWGpN7AbcB5EfG3Mp32RlxFy6okG/Q5GjjDHeutgOtIs+Ur5R2IWVdJ6gH8AfgpsHpE/CfnkJpeRIwEBgGTgIdddKs0zZRM7Qzc6BuUhnY+MJzylpJ+FPiupCXLeE6zYtYj7eu8K98wrBZly5bPIy0DNasbWfPYu4CFSDNSn+YbkU2TXVd2AZ4GnpK0SL4R1Z+mSKay0ZAdcaPehiVpD2ADYI9yJszZ0ppb8OyUVcfRwFne12ntuBzYWNLieQdi1hmS5gUeAz4Htsiq5VoNiYipEXEkcAkpoVol75jqSVMkU6Sb7Pcj4p28A7Hyk7QyaTbqpxExqgIvcSMwxFW0rJKyD6/lSXv+zArKrnGXAYfnHYtZRyQtRZrxuA/Y0z0+a1tEXAgcCDwoaVDe8dSLZkmmXHiiQWXre28HDoiI1yv0Ms8BPYGVK3R+M0hLt86dyQqU1hwuAHaUNF/egZgVI2l14O/AaRFxgrdZ1IeIuBPYGrha0s9zDqcuqNHf25L6AJ8Ay0fE8LzjsfLJSkjfB7weEYdV+LVOAXpHxBGVfB1rTtmevKeBxbwExjpD0kXA6Ig4Ju9YzFqTtDVpSeruEfFAzuFYCSQtDdxPKmF/kpPh4pphZmpT4J9OpBrSb4F+VKdU8E3ATlkCZ1ZuhwOXOpGyLvgdsI+kgXkHYjY9SQcAFwODnUjVr4h4k9SLagvgj5J65hxSzWqGG8MhuPBEw5G0GbAXsGM11mBHxGvAV6SeDGZlI2l+YHvgwrxjsfoREf8lNRbfN+9YzCCtFpF0BnAQsFZEvJh3TDZzIuIzUpXZBYC7Jc2Sb0S1qaGX+UmaFfgQWCQivs47HiuPrIrV06SCE09X8XWPJr2XfPNiZSPpTKBvRPwy71isvkhaAfgLsGjWZNwsF1mfx6uARYAtI2JEvhFZOWVVsS8FVgE2c2n7GTX6zNRPgcecSDUOSf1IBSdOrmYilbkZ2FZSryq/rjUoSbORZlh/l3MoVoci4lXgBWD3vGOx5pVdxx4A+gAbOZFqPBExGdiH1Cvs6Ww/lWUaPZlyFb8GkpUmvwz4N2k9dlVFxHvAW8DG1X5ta1j7A3+OiPfzDsTq1hnAkdnIsVlVSfou8ATwKrBDRIzLOSSrkEhOBk4C/i5pzbxjqhUNm0xJmgf4MXBv3rFY2ewLrAjsk2NVmRtJ+/DMZoqkvsAvgbPyjsXqV0Q8BQwHts07Fmsukr5PWnI/DDg4a3JvDS4iribNht8pydcdGjiZIm3o/nNEtOQdiM28rF/FicC2Of9ObwM2k9Q/xxisMfwMeDYrbmI2M84AjnZjcasWSRsAfwUOj4hzXTa7uUTEQ8BPgAskNf1+30ZOpobgJX4NQdK8wK2k7unv5BlLRHwO/INUKtSsJNmSrCNIN8FmM+t+oAfp5sasoiTtQqqSvH1E3JJ3PJaPiHgJWBPYT9LZzdw6piF/cEmLAEsBD+ccis2k7KbzZuDqiKiVJZs3kfbjmZVqB+CDiHgm70Cs/mWzAmdQnZ571qSUHA2cBmwQEX/POybLV7aXfE3Stpobs6qOTachkylgJ+BP1eg/ZBV3OjABOCHnOKZ3J7CepDnyDsTqT7YU62g8K2XldQuwcLYk2qysJHUnFX7aCVjdy5Ntmoj4ilSYqzvwkKTZcw6p6hoimZLoLTG7RPfsW27U2wAkbQdsB+xSSxtbI2IUqbfLNgBIfZFmo4mnuK0wiW4Ss0n0ne7bg4EAHswpLGtAWenic4Cjpn1Ponv22diUo8XWDklI/ZAGdvTZlbUkuQNYElgnIoZXJUarG1mfux2BfwJPSlqoveMlJDGLxKwSdb/Xs25v/iQWlThX4hugBfgUmCRN+BgO+y6893LOIdpMkLQsqUHcdrXYs+IX8PRdcDLSOGA08BkwCelVpF1p0qluA4k+EkMl/g1MIr03RkuMk7gKfnwScIY3bFsFDIPZ1pBeOUXiPdL771OgReIbid9JLJJrhJYvaWWk64FxwCjgc9Jn10tIO9Gqj6KkuYG/ASNJzVpHVTtkqw8RMTUiDgWuIPWiWmn6x7MEan2J+4CJwNfAl8AkiUclBkv1mZeo3j7PJeYBbgDWIiWDBRqoTpgEvScDlwBHRVAzsxrWMUkDgOeAsyPiqrzjmYG0FHBLwNKToW/PwkeNzv73OOAC6u2PzEqSja4dwrdLUge0PWrqFJjQDXr/C7rtEEGuBVWscUj0AM6GSQfCFKBPob5TE0izok8AQyL4spoxWo6k5Uj7jxcHesP/VvJMbzTp/XE0EZdKWoLUjPcW4DgPAFlnSdqetCx0l4h4WGI94BpgDqA/FJyNGgOMBfaK4M/VirUc6iqZykbUngbmAorcx86ghfShsUUE3j9VB7L9JLcBIyLiF3nHMwPpB6RSsLPQuVndFtLF4wAnVI0tS6QuA3YF+nXiKVNJNy4bRvBiJWOzxifRi1TRb3U69/6bSBoRXj2CDyoZm9UAaQ3gIYrfxLbW8hbctQxsEHBCRPyhsgFaI5K0NvAnuOg2OODnMMNy9/aMAw6N4LLKRVdedZNMScwBvAQsSOERlWJagHtIo3D18cM2MUmHkyqdrR0RE/KO53+kxYEXgYFdfOZY4CwiTip/UFYrJE4mzUp1tf/YSGCVCP5b9qCsKWSJ/C3A5nT+ZgXS9NWHwMoRjKxAaFYLpGVIKz0KzJQXNxbiWbh6g4ifVyYwawbSHbvD4GHQt6v7osYBu0RwZyXiKrd6Wpv4W2BeWiVSjz4K48bB6NHp6z//afO8fqQPmQ2qEqWVTNL6wOGkfVK1k0gll1How2j22eGOO2DMGHjvPdi5TcX0/sAxpHL91oAkFgcOo0Ai1Ynr0wDS3kCzUm0MbEqrROqAA+D552H8eBg2rODzugPzk5YjW+O6gkKDPB18dvUHbQA7Iy1YnTCt0aT9T9ucXiiRWnhhuO8++Oor+OQTuPBC6D7jNElf4Op6KZ5TF8lUVglrTyj8j3rggTBgQPpaZpmCp+hPukm3GiXpO6S9cLtGRG0tO0lVadam0N/LxRfDxIkw77ywyy5w6aWw3HJtzgAcWPlALScH0c5seQfXp+7AehK+YbFSHUGBpX3Dh8Mpp8BV7e867Q3sXS83LNZFac/TqpT+2QWwb4WjtMa1MWlbRBuXXAKffw7zzw8rrQTrrgv779/mMAHbVjbE8qiLZIq07GtmlugJ37DUrKzJ223ABRHx17zjKaDtnzhAv36w7bZw3HEwdiw89RTccw8MHdr6yN7APq7w13imG+gpUAin0wLYrzwRWTORWIhUjKnNyO+dd8Ldd8OIztVC3a7MoVltKDzQ0/nPrj7AAUid2aNu1tqRFEmmFl0Ubr0VJkyAzz6DBx+E5Zdvc9gApmv1UMvqJZkaSjvrfU8/Hb74Ap58MmW3RUwFtqhAbDbzziWV7z0z70CK2JlCs6JLLQWTJ8Pbb3/7vZdfLnhFIN0wr1Wh+Cw/a5OuLUV14vrUB9ilArFZ49uCmRtohPTZulsZYrHasyOFinV17bOrO/DDCsVnDSorirMuRQqenH8+7LQT9O0LCywAgwenhKqApbMq3jWtXpKpeYs9cNRRsNhisOCCcPnlcO+96b8L6EOqAmg1RNJuwEbAHjVcdrVwN+9ZZoFRrVpufPNNWs9VmN9/jWdu2qmO1YXr02wVis8a29ykz7aZVfM3K1aSwgWTuvbZFfizy7pudiheRfvxx1PuPmoUfPwxvPAC3HVXwUMnUgfvv3pJporG+dxzaf/kxIlw7bVptnrTTQseqvbOY9WXNXT7HbBNRHyTczjtKfy+GTMGZp11xu/NOmuqNNCW33+NqRvtJFNduD75vWGlKNf7xu+/xuTPLstLN4rMmktpFuqOO6B/f5hzzlQP5czCa5OCOnj/1XyAmc6t+gYi0i+qgAmkbstWAyTNDtwOHBQRr+UdTwcKfsLw1lvQowcsscS331txRXit4I8zFb//GtFX0Pmm4O1cn0YV/K5Z+74ijdyW4zzWeMYU/G7XPrsCf3ZZ131NkaJxc8yRqvlddFEaaPzqq1RxtMhAYy/q4P1XL8nUnaR+PTMYOBA22QR6904lFYcMgXXWKbruMoCHKxyndYKkbsD1wD0RcXPe8XTCfcDkNt9taUlDKyedlDb0rrEGbLUVXHddoXP0IjWctsbyFEU+MLpwfZoE9dXt3WrGwxRJ5rt3//a9N/3/L2AscEcFY7T8PEih90fXPrt6As9XOE5rMBGMB14p9NiIEfDuu7DffumaNHAg7L47vFLwaD4Dhlcw1LKol2TqagpUpOnZM5V+/eIL+PJLOOgg2HrrGfdUTufVCNp2ebE8HEva9Hxk3oF00vkUW/u7//5pB+Xnn8NNN6Wrw+uvtz5qMnArEZ59aDBZs9PbKXDD0oXr02Tg95WO1RpPBK8BbxZ67NhjU4+pY45JRdrGj0/fK6AbcG0Fw7T8nEtaldNW5z67JgHXENFmMNusE86kyMqebbaBQYPS5+M778CkSXDIIW0OGwucEzHTRXYqTrW7539GEtcDO9FOP5d2jAH2iOD28kZlXSVpMPBHYLWI+DTveDpN+iewconPbgHWIOLlMkZkNUJiFeAJCvT66aTnIvhRGUOyJiKxI6kxa8ESxB2YDNwQwR5lDcpqh/Q6sGyJzx4HrExEwYTdrD1ZRb8vgFk7OraIccB8EbW/DL5eZqYgzWYUXv/bvgnAa8Dd5Q3HukrSYqRZxp3qKpFK9iclRV3VAtzpRKpxRfBP4F5Kf3+4obPNjDvgy0+LTUB0YAxwfJnjsdqyL+mmtKtagBucSFmpIpgIHxwD49ttH1LEWODYekikoI6SqQjeAzYhTRl2djptPPBfYFBEgT0vVjWS+pKWQ50aEU/mHU+XRfwD2JWufSi1AP8AflaRmKyW7EbaV9CVhKoF2DnC+xFsZmgvWHoWmPoh6TOvM4L0WbpxBO9XLjbLXcTjpM+grn52PY6bidtMkLQ4LHww3P4ERFc/G68CzqtMZOVXN8kUQATPAasDH9JuUjVlKunC8Xfgh9m+BsuJJAGXAq8DF+YcTuki7gQ2A76OYhX+kgmkm5qbgZ8QUbTXgjWGNALHxsCtpN99O9MEY6dCfA0MjuCeqgRoDUdSN0mnAwfDV2tC3+8BT6bdB5OLDThOS6I+AH4UwQtVCtfyFHELsDXwDe1/do3Pvq4BNifCg9BWEkk/IC1/Pzdil/VAvyQlSe3tv2shvf9OAH5VD3ulpqmbPVPTk+hGunE5EliTdOOS1aKf0gtuboEd1oro2WY3pVWfpH2BA4AfRyNsZJV63QzHfR8OXS4NSEwkvf+6k0qgXwpcTMSHeYZp+ZBYmLQsdF/S+2MKqVdLL4jXYI954N5fRHz1QJ5xWv2S1Is0crsosGVEjMi+3wNWehfueBkW3ZC0J2oq6f3XmzTbcDbwSASlLL2xeib1BrYBjgaWYsbPrsnAxcClRHycW4xW9yRtTro+7RkR9377fQaQVvgcRWo4Pm2guQepPcg5wLCI2i+F3lpdJlPTk5gbWIC0+fsb+OJ9mOffwNbhfSq5k/Qj0n6SNSOicJ3FOiTpSuD1gJuAeUk3KiOBd4koR98Xq3PZ5tvFgNlIAz6fRTBc0lDgZxGxQZ7xWX2SNJBUyvwbYJeIGDfdYzsBB0TE2hL9gYWBgaQR348j+DKPmK0GSd8B5uHbPj7vehWFzSxJvyDNLG0VEc8VPgYBiwBzkgYcvwLerecBnrpPpgqRdBrQPSKOyjuWZiZpHuAF4MCIaJjlTEqje58A34+Ij/KOx+qLpJ7AO8AOEfFs3vFY/VC6Ab6ftIT94IiYMt1jAl4CfhMR9+UUopk1oez6czKwIzA4It7JOaSqqqs9U11wE7BT1hzWcpCWm3AzcG0jJVKZwcArTqSsFJFGf88hLXUw6xRJK5Aaf18L/HL6RCrzE9JyrfurHZuZNa9s2fHVpO03azRbIgUNmkxFxKuk9Zdr5B1LEzuVtAa7EcvuDgFuzDsIq2tXAmtKKrX/izURSRsAjwBHRsQ5UXhJydHAGUUeMzMrO0mzAvcBswPrR8QXOYeUi4ZMpjI3kW56rcokbUua6h1SYPS0rkkaQBoBdgNoK1lEtAAXAUfkHYvVNklDSJ9nO0TEzUWOWZ20P+qWasZmZs1L0gKkojZvA9tkn2tNqSH3TAFIWhR4FlgwvKmyaiQtQ/rj2jQiGq7sblY8YIeI2CLvWKy+SZqDtHdqxXDlR2sl24NwBKkS6qYR8Vo7x94FPBwRF1cpPDNrYpKWJ81IXQac2ewz4g07MxUR/wX+D9go71iaRTZrcwdwTCMmUpmd8RI/K4OI+AoYBhySdyxWWyR1J/Xk24W0B6G9RGo54Mek95KZWUVJWhf4G3BsRHhpMQ08MwUg6SDgBxGxW96xNLpsFPUW4JuI2DvveCpB0tyk6ewFG6JfluUuq872CrDktF5B1twk9SMN2MwCbBsR33Rw/NXAWxFxWhXCM7MmJmlH0kDPzhHxSN7x1IqGnZnK3ApsmX04WWUdQuqpc1DegVTQdsD9TqSsXLKKkHeSlnJZk5M0F6nQxGjS0r6OEqmFgC2AS6oQnpk1KSWHkSrRbuREakYNnUxFxGfAc8BmecfSyLIp3yNJo6jj846ngqZtBDcrp7OBAyX1zzsQy4+kxUmlz/8G7Bada/59KHBlRIysZGxm1ryyZcfnAz8jLTt+Jd+Iak9DJ1MZV/WrIEkLkv6Nh0bE+3nHUynZCPCywEN5x2KNJSL+AzwB7Jl3LJYPST8gvQfOjYjfdGYPQjaLtRvpJsfMrOwk9SVt4fg+sJaLJRXWDMnUHcAGkmbLO5BGkzVquw24KCIezjueCtsJuL2To8VmXXUGcJiknnkHYtUlaXNSVaxfRMRlXXjqgcCfImJ4ZSIzs2YmaU7gYWAiMMgz4MU1fDKVrTn/K7BN3rE0oN8BX5BuBBudl/hZxUTE86TiJjvnHYtVj6R9gD8Cm0fEvV143izA/qQlomZmZZW1F3oKeBLYNSIm5BxSTWv4ZCrjpX5lJmlXYBCwe0RMzTueSspKD89FWoZjVilnAEdLapbrctPKNnOfTOojtXZEPNfFU+wNPBYRb5c/OjNrZpJWJSVRF0bE0Y1+j1cOzfKhfR+wqqT58w6kEUhaETiP1PF6ZM7hVMPOwC0RMSXvQKyhPQK0kKqzWYPKlkdfDWxC2sz9TgnPPxQ4s/zRmVkzkzQYeBA40E3AO68pkqmIGAfcA+yQdyz1TtLswO3ALyPi1bzjqbSsf5Yb9VrFZUUHzgCOyd531mAkzQr8GZgdWD8ivijhNLsAb0TEi2UNzsyamqQ9Sc2/t4yIO/OOp540RTKVuRHvR5gp2fKja4H7IqJZ9g/9AJgK/DPvQKwp3AnMAayTdyBWXpIWAB4H3iHN6reUcI5uwFE0xz5VM6uCbNnxCcCvgXUi4pmcQ6o7zZRMPQIsmvXysNL8hjSienjegVTRzsCNnSlVbDazsqWkZwFH5x2LlY+k5Uk9pG4GDoiIySWeaitgFPBouWIzs+aVVZC9ktSPdY2IeCvnkOpS0yRT2YfXbaQS19ZFkgYB+wLbR8SkvOOphqxR3Y64ip9V13XA9yWtlHcgNvOypuZ/A46NiDNKHZjJln4eDZR8DjOzaSQNAO4F5gHWi4jPcg6pbjVNMpW5CdjF+xG6JiuReQ2wU0R8knc8VbQu8ElEvJl3INY8shK055GWc1kdk7QDaRBvSERcP5OnWw8YCNw1k+cxsyaXFWT7O/ABsHVEjM05pLrWbMnUM0A/Uidn64Ss+/WfgNMjotlKgw/BhScsH5cDG3tZcn3K9iAcSurFt1FEPFKG0x4NnOkyxWY2MyQtS1p2fAepWXipy44to2ZbLSDpdNLP7T0JHchm8K4E+pJGVpvmzSKpNzAcWDEiPso7Hms+kk4B5oyI/fKOxTovWx78O2AjYHBEfFiGc64C3A0sHhETZ/Z8ZtacJK1Fqsh8VERcnXM4DaPZZqYgLfXb2Y0xO2Vv4IfA3s2USGUGAa86kbIcXQDsKGm+vAOxzslm8m8BVgTWKkcilTkKONeJlJmVStK2pNmooU6kyqsZE4pXgdHA6nkHUssk/RA4hVTCd0ze8eRgCC48YTmKiM9Jy0x/lXcs1jFJcwIPA5OAQeVqaC5pSWAD4I/lOJ+ZNR9JvwJ+D2wSEX/JO55G03TL/AAk/QZYICIOyDuWWiRpbuAF4FcRcVfO4VRdVuHmI2CxiBiRdzzWvLLiLy+Q3ovf5B2PFZb9nh4gLcU7ppz7miT9Afg0Io4v1znNrDlkq7DOBgaTlh2/n3NIDalZk6nFgH/Al1vAnMuRKiSNBd4H/hZB027Gk9QDeBB4LiJ+nXc8lSYxP7A+qVFqAF/CCrPBvzePiC1yDc4MkHQ9acnpmXnHYm1JWhW4h1Sk56Iyn3t+4DVgqYj4spznNrPGJqkPqRLzfKSKfV/nHFLD6pF3ANUm0RdiXXhvAAz8OzCZ9O8wJfuaKHEBcHkEn+YZa05OJiUVx+UdSKVICFiH1Hx4Y2Ai0JP0c0+GF/vD/z0rsVoEL+QYqhnAmcBfJP0+IsbnHYx9S9Jg0s3KLyLizgq8xMHAdU6kzKwrJM1BaqPwCfATf3ZUVlPNTEksDTwGzJJ9FTOOdGM9JIK7qxBaTZD0U+B8YLWI+CLncCpCog+p78v6pDL5RXqOxRTQBNKelX0jmFKtGM1ak/Rn4N6I+EPesVgiaU/gVOCnEfFMBc4/G/B/wCpemmNmnSVpYdKy4weAI9xOofKaJpmSWBb4BymJ6mzhjXHAzyK4pWKB1QhJSwNPAJtFxPN5x1MJEr1IyfRKpHLvndEC/AXYNgJfkCwXWTnba4Cl3RMkX1nLiOOBoaQ9CG9V6HWOAZaJiN0rcX4zazySVgL+DJwTEefnG03zaIpqfhIDSTfRA+jaz9wXuEriB5WIq1ZImoVULvM3jZpIZa4klSzubCIFafZqY1JlQ7NcRMSTpOUa2+YdSzOT1JN0HdkMWKOCiVRfUhXHsypxfjNrPJI2IQ3+HuxEqrqaIpkC9iDNSBVc0rXjjvD66zBmDLzzDqy11gwP9yXtI2pI2SjrFaRZuytyDqdiJBYGtiMlRzNYZhl45BEYORLefhu23rrN0/sDB0vMWuk4zdpxOnB09jdrVZZV+bwXmBdYPyI+q+DL7QE8GxGvVfA1zKxBSNoduJbUzuZPecfTbBo+mcqKDRxBgZtogI02gjPPhJ/9DAYMgHXWgXffnfEUwLoS36l8tLn4FbAkcGCDN+bdnwLJdPfucPfd8Oc/wxxzwD77wPXXw5JLtnn+VGDXKsRpVsz9pGI5mwBI9JdYWGIJibmya51VQFZV7+/AB8BWZeu9J/VDWghpSaS5kZRVVD0COKMsr2FmDStdMnQscAKwXraKwaqs4fdMSaxPKltbsODEU0/BlVfCVVe1e5rxwLkR/Kb8EeZH0jrArcCPI+K9nMOpGImewJfQdmZp+eXhH/9IifQ0Dz0Ezz4Lv/1tm1O9H8EilYvUrH1Sr11h68Ph1i+AdUmVKINUjfJzUj+RayNwT6oykbQMaSP3lcCpMz3olGYW1yclTBsy4+9wxL3wyJ6w+OcRa87U65hZQ8sGXi4BVgM2jYhmrEBdExp+Zor0Jutd6IFu3WC11WDuudPyrg8/hAsvhD592hzah3Tj0jAkLQDcDOzeyIlU5rtA984eLMH3vlfwoe9k1QDNqk7iRzDhTLjq+xAbkm6++5MGinqT3uenA59IHO+ZqpmXFf54DDgxIk4pQyK1CvAeqbnvT2j7O1xgI9jlE1gN6TRSw00zsxlke93vBhYC1nUila9muFDPTvrAamPeeaFXL9huO1h7bVhpJVh5ZTj22ILnma1yIVaXpF6k8uCXRMRDecdTBQOhcGnzN9+Ezz+HI46AHj1g441h3XWhX8FFoUykgd4HVj8kBgF/Ay0Asyil/AX1J+3zPAK4xglV6SRtSyrMs1tEXF2GE25Aqpi6EO3s4e0L3bpDL+CXwK1OqMxsepLmBR4FPgO2iIjROYfU9JrhIj0OCpe0Hjcu/e+FF8Knn8KIEXDuubDppkXP0yjOBkYAp+UdSJWMp8iNy+TJqeDEZpul98Bhh8Gtt8JHHxU8T3ca631gdUBiFeB2iuz7LKI/sA3ed1MSSb8Cfk9qdvmXMpxwBdIocld/h4OyOMzMkLQU8DRwH7BnREzKOSSjOZKpjyhyAzxyZFraN/3CjSKLOIK0NKPuSRpCKuu7WxM1cvuUNNJb0KuvwnrrwVxzwaBBsNhi8NxzBQ8NwCNAVm1/pMhNeAeVSPsDv5S8z6+zJHWT9DvgF8CaEfFSmU59Cen38a3Ro2f8mjwZLrig9fP6A3uS9m2ZWROTtDqpEM5pEXFCgxcNqyvNkEzdSTv7ZYYNg4MOSvumZpsNDjkkVXZrZQxwWeVCrA5J3yeNcm4TESNzDqdqIvgaeJKUDLWxwgrQuzf07ZtmpuafH66+us1hk4Eb3bjXqklieWDZQo91ohIppGv8gRUOsyFI6gPcBPwAWCsi3i/TiRcHVqX17PiAAd9+zTdfWipx222FztCDtOTPzJqUpK1Js9s/j4grcw7HWmn4ZCqCkaT9QQX3zJx8Mjz/PLz1FrzxBrz0Epx6apvDRgF/q2igFSZpNtJSoUMi4pWcw8nD2RBjCz0wdCh88knaO7Xhhmnf1MSJbQ6bCJxf4RjNWjuYIns+TzwRTjopVZ6MgOHD01crvYB9pMJFeCyRNDvwECnh2SQivirj6Q8iJUTFbbttugA98UShR3sCuyP1L/SgmTU2SQcAFwODI+KBvOOxthq+NDqAxErAU3RtvXqmJeCKp+BXg8vWW6TKlDYw3wW8HxEH5RxOLqR+P4J3n4R5epQwhjAFeDmCVSsQmllREl8Ac7X+frduaSLjt7+FvfZKFUjvuisVUhk/vs1pRgGbR1DwTr3ZSVqYVPr8AeCIsi9/lj4CFmz3mEcegccfTxlyYd8AO1CO/VtmVheye7fTga1IidR/cw7Jimj4mSmACP4FnAwUnJlox3jo8Tgc9l/gX5LWLntw1XEMMCdwWN6BVJuk3pJOhXH3wAm/gW5dfQ8E6WZ02wqEZ9aRAYW+2cVKpEH6+7dWJK1EGmi7PCIOq9A+0oHtPrrQQqmE6DXXtHdUN2COcgZlZrVLUm/gemAt0v5NJ1I1rCmSqcyZpGVaLZ08vgV4BnptFjFpN+BQ4BZJ50nqW6EYy07SJsABwPYR0XbxWgOTtDLwPPA9YMWIy84CBpOKSHTmpmkK8BWwXkRjFCCxxtC1SqQjB8LWd0oKf834BbxEmjU6r1KvMbpIw/j/GToUnnwS3nuvrO8RM6tP2baMB0i95zaKiBH5RmQdaZpkKoKI4FhgN+Bt0ixVoRvq0aQb6NOATSLSbFZE3AOsAMxHmqX6cVUCnwmSFgGuBXaOiLa7KRqUpJ6SjiftgTgb2HpaQ7tsqdMPgAeBCaSy6a21ZN+/HVgpgmbcY2a1oWD1yC5UIgVmGwV3rRMR8lf6AvYAPgcq/u8yAD5u9ze8224dzUpB+qwq5z4uM6tBkr5L6kf3KrBDRLgdSx1oij1TrWWNLH9Amm1albSUZhyp/PnvgT9HMLn487UdcBFwNXBCRBS6Ic9VVpnqSeCGiDgv73iqRdL3gGtIN0p7RUTRGxmJBUglkLcjNeOdCnwNXAdcFYFHgyxXEn8k3fi3KWBw4okweHDqkTZpEtxzDzz2WNpH1cpoYO4IJlQ63lonScBvgD2BTSPijSq86PnA/hQqJLL66vDww6ma35h2t+S2APMQhYvomFn9yyou3wecB5zn0uf1oymTqXKQNA+pXPrSpJ5NL+Yc0gwkXUFKEndqhj9IST2AI0gJ8tHAVc3wc1tjy0qjPw+0WVrcowf8/vcwZEgqOnHrrXDkkTBhxpRpInBhBIdXJ+LalV0jLgFWAzaLiE+q9MKLA/8G+rR57LLLoF+/NDtV3CTgCiL2r0yAZpY3SRuSWjMcFBG35B2PdY2TqZmQjXLuTBpF+ANwSi3sS5K0Fymp+GG9ViDsCqWGlleT+oHtGeXqD2NWAyReBFYp8enjgWWbfc+fUlnxW0gzfNtHRHWbb0tPAGvSutdU54wDVibizfIGZWa1QNKuwO9Iy/r+nnc81nVNs2eqEiK5EViZdLPzrKQV84xJ0g9I+71+2uiJlKTukg4lLWe8ltQfxomUNZq96XzhnOmNBS5wIqV5gcdIS3+3qHoilexH16vJkj3nSidSZo1HyTHAqcAGTqTql5OpMsiKO2wBXAD8VdKx2ZKSqpI0F6lB8S+iwT98JS1BukHaGvhRRFwSlSlrbJarCP5JKs3flYRqLHAHaclr05K0FPA0aR/CnhExKZdAIv4NbEnXEqqxpIpev6pITGaWG0ndSY14dwRWj4jXcg7JZoKTqTLJZqmGkWao1gaekbRctV4/+8O8Cbg5Iu6s1utWm6Rukg4E/kGqtrdeRPxfzmGZVVQEDwIbkCrDjSH1jipkLGlZ2FnA7hFFj2t4klYHHgdOi4gTct9DGfEosA7wAe3/DqdVE70A2BEPEpk1FEn9SINdS5IqijZNteVG5T1TFZDtpdqHNHV7FvC7iJhS4dc8Ffgx8JOIKFqJsJ5lpd6vIm3G36PRZ9/MWpPoBmwIHAmsSypOMBXoBXxKagVwbQSjcguyBkjaGvgjqTjQAzmHM6P0+bAeqWDORnz7O+wJjCD9Dq8mYmROEZpZhUiaG7gXeBPYuxb22dvMczJVQZIWJd389ybd/L9VodfZCrgQWC0iPq/Ea+QpS073JiWnZ1OF5NSs1kn0B+YkJVJfA18180zUNJIOAH4NbFlrVVbbSCPUc5I+I0YCI/CHsllDyrYnPADcDPw299lyKxsnUxUmqRtwAHA8cDJwYTn39mR7Ap4ENo+I58p13loh6TvAFcBcwO5eV2xmhWTX2tOBrYDBEfHfnEMyMwNA0o+Au0i9Sf+QczhWZk6mqkTSkqTy3ZOBn0XEux09gbS+fnlgVtJeiPeAB8k2UWflfp8lJWg1+ccp8R1gE2CO7FsjgIciaHeNcDYbtTtpmeQFwJm5bR43s+pKf/+rkZqqDyTtIfoYuI+IcQUO7w0MAxYmzUi54baZVYY0J7ApMDfQnbQy4DEi3il8uLYEriTd+/25anFa1TiZqqKsSMTBwDHAccAf2sxSSQOBPYDDgdlIf6g9SUnYRNLa+ovHwaX90pK3CcDPa2m6WEKkfR1HkBLCyaRlLJDi7Qk8ApwDPNZ6aZKk+YHLgYVIex5erlLoZpantOxtJ+AoYEFSkaSewBTS9U+kpdMXTrtxkTQbaTP3SGCXKJBsmZnNNOmHwGGkypyTSPc13Uj3Nd2BF0kDwPeRbUWQtC9pZdJWjbh6yBInUzmQtCxwDTCKlAh9kD2wCvAw6Q+0fzunGD8Juv0cProevldLNw8SfUjl2dcj/QzFmlQGqWrVQ8CQCCa0aoJ8OXCyN2eaNQlpcVK7g9mAWdo5ciIpuTpUqeT5/cCjwCHeS2lmZZcGwi8CdgP60H4l7DHAqyNh8OypUND2pGXHrjrcwJxM5STrQ3UkcAhw9CR4uUe6IWgvAZnBVBjfDfYg4pYKhtppEr1IP8PKpIp7ndECPA8rDYGXLwSWIRXreL5CYZpZrZEWA14gLenrVMuOKTD+tzD+NDgFOLeWZufNrEGkQd6bgM1pf5D7fwImDIcJ34P/jEz72b+oZIiWPydTOZO0wvxww5uwzIC0nKWrWoC1ifhnuWPrKolhwA5Av649c/IEuHYK7HkRcHxEjK9AeGZWi6Q+wNvAAnSx9+FkmNgDtiLiwYrEZmbNTfo1qTpopxKpaSbC1G7wWI+IDSsTmNUSN+3NWUS8+j7c3qfQbNTo0TN+TZ4MF1zQ+qi+pPW4uZJYgLTXoU0itfDCcN998NVX8MkncOGF0L379Ef06A179IA4x4mUWdPZgbS0r+3n0eyzwx13wJgx8N57sPPOMzzcI5WFP6MKMZpZs5H6kva4z5hIdeLerBd06wE/Rvp+9QK2vDiZypvUvScc1BN6tHlswIBvv+abD8aNg9tua3MGYBOk+aoRbjv2LfbAJZfA55/D/PPDSivBuuvC/vu3PqrbFGCvSgZoZjXpKIrtkbr4Ypg4EeadF3bZBS69FJZbrvVRS/qGxcwqYHso0Luvc/dmkAZ7Dq5siFYLnEzlb1PSH1z7tt02ZSRPPFHsiH3KGVRXSHQHDiRtzGxj0UXh1lthwgT47DN48EFYfvk2h/UFDpH8njRrGtLKwCIFH+vXL133jjsOxo6Fp56Ce+6BoUNbH9mLtPfUzKycjgQGtHtE+/dmPYCdkNo/h9U937jmb1Xar1yV7L47XHttsUf7AGuVMaaumpciiRTA+efDTjtB376wwAIweHBKqAoYSFruY2bNYRUKjfwCLLVUWj7z9tvffu/llwuNxPQAVq9QfGbWjFLhiWU6PK79ezNIJdSXLFNUVqOcTOVvLjqq3rfQQmlt3DXXtHfU7OUMqosGknpJFfT44+n+Z9Qo+PhjeOEFuOuugodOys5lZs1hIMUK78wyS7poTO+bb9LSmrY88mtm5VR0gPh/OndvFvi+puE5mcrf6A6PGDoUnnwybcAu4u+wmqTI4wsWeR3GFLyZkdIs1B13QP/+MOecaU/5mWcW/DG6ATXTM8vMKm4cqWdUW2PGwKyzzvi9WWdNG77bcuEaMyunCXR0j9yJe7OM72sanJOp/H1AKm9e3G67dTTyMXVdGBYRyuML3usPs0woFNgcc6RqfhddlPaRf/UVDBsGm25a8OfoBnzVuX82M2sAH5JmpNt66y3o0QOWWOLb7624Irz2WqGjP6hEcGbWpCKmAl+3e0zH92YAvYGPyxSV1SgnU/m7lfZ+D6uvDgsuWKxSzDTjgD+UOa5Oi6AFuB+Y2vqxESPg3Xdhv/1SOfSBA9MS41deaXOaKcDtEUysfMRmViP+UvSRlpY0pX3SSakYxRprwFZbwXXXtT5yNHBRJYM0s6b0R9IMVVuduzcDeIWID8sdmNUWJ1N5ixgB3EOBRARImce0PivFDQeeK39wXXIORaayt9kGBg2CL76Ad96BSZPgkLa1tyYA51Y4RjOrJRETgUspdsOy//6pcs3nn8NNN6VRmddfb33UFNI11MysnC6hWIGczt2bjQbOqkBcVmMUUfh9YlUkrQb8nQINbzthLHAQEcPKG1TXSAh4g1S1pqtJ+hTg9QjcK8as2UgLAf8htUfoqnHA2UTk3rjczBqQ9CCwAcUK5bTvS2ABIgovZbaG4ZmpWhDxAnAaKTHqinHAg8DV5Q6pqyIIYAug3WGaQk8ljd5sVfagzKz2RXwA/IKO9o62NQF4CTi17DGZmSVDSUlR4UI5xbUAmzqRag5OpmrHacD5dP6GYiwpkRpCjUwvRvA2sB5p02ZnLjyTSQUn1o3gvxUMzcxqWcR1wKF0vupVC/AiMDhbKmhmVn4RXwBrkLZTdOZaE6RB5c2JeL6SoVntcDJVKyKCiGOBXYDXSDcLrROSabM4w4GjgO1q7UYigpeAlUiFNcZTODkcmz12E7BiBG3LUZhZc4n4A7Ap8CwpqSo0ojsaGAGcDqxHxKgCx5iZlU/Ee6T7mqtI9y+FVuCMz77uBX5IxKPVCs/y5z1TtUpaBfgVsAqpIWUL8A5wAfBIrcxGtUdidmAPYAgwBykZHAHcCFwTwcjcgjOz2iUtTbr+rUlqeDmeVP78YuA+Ioo2CTczqxipP7AT8HNgHqA7MBK4G/gDEZ/mF5zlxcmUmZmZmZlZCbzMz8zMzMzMrAROpszMzMzMzErgZMrMzMzMzKwETqbMzMzMzMxK4GTKzMzMzMysBE6mzMzMzMzMSuBkyszMzMzMrAROpszMzMzMzErgZMrMzMzMzKwETqbMzMzMzMxK4GTKzMzMzMysBE6mzMzMzMzMSuBkyszMzMzMrAROpszMzMzMzErgZMrMzMzMzKwETqbMzMzMzMxK4GTKzMzMzMysBE6mzMzMzMzMSuBkyszMzMzMrAROpszMzMzMzErgZMrMzMzMzKwETqbMzMzMzMxK4GTKzMzMzMysBE6mzMzMzMzMSuBkyszMzMzMrAROpszMzMzMzErgZMrMzMzMzKwETqbMzMzMzMxK4GTKzMzMzMysBE6mzMzMzMzMSuBkyszMzMzMrAROpszMzMzMzErgZMrMzMzMzKwETqbMzMzMzMxK4GTKzMzMzMysBP8PRq1rtrcBITYAAAAASUVORK5CYII=\n",
      "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": 16,
   "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": 17,
   "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",
      "{'01010101xx': 0.07887396513978905, '10010101xx': 0.07887396513978903, '01101010xx': 0.078873965139789, '10101010xx': 0.078873965139789, '10101101xx': 0.040906327139884305, '01010010xx': 0.0409063271398843, '01010110xx': 0.04004434869249364, '10100101xx': 0.04004434869249363, '01011010xx': 0.040044348692493625, '10101001xx': 0.040044348692493625}\n",
      "第二个子图的最大割：\n",
      "{'0xxxxxx101': 0.4556003303152275, '1xxxxxx010': 0.45560033031522745, '1xxxxxx100': 0.0254542520553071, '0xxxxxx011': 0.025454252055307092, '0xxxxxx110': 0.010740876742244158, '1xxxxxx001': 0.010740876742244157, '1xxxxxx000': 0.0022930869455346486, '0xxxxxx111': 0.002293086945534646, '0xxxxxx100': 0.002293086945534642, '1xxxxxx011': 0.002293086945534638}\n",
      "母图的最大割：\n",
      "{'0101010101': 0.07887396513978905, '1010101010': 0.078873965139789, '1010100100': 0.0254542520553071, '1010010100': 0.0254542520553071, '1010110100': 0.0254542520553071, '1001010100': 0.0254542520553071, '0101101011': 0.025454252055307092, '0101011011': 0.025454252055307092, '0101001011': 0.025454252055307092, '0110101011': 0.025454252055307092}\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": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-16T03:42:41.647686Z",
     "start_time": "2021-05-16T03:42:41.309407Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA1MAAADnCAYAAAD7CwxiAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAABKA0lEQVR4nO3dd5xcZfXH8c832XRC6L03KSIBUaQH6VUkSA8gKiX0jkovAoIUAVF+0kEQkCqKAtJVuoKA9CZVasqmkvP747kxm92Z3dnJzNwp3/frtS/xzp07ZzOzd+65z/Oco4jAzMzMzMzMeqdP3gGYmZmZmZk1IidTZmZmZmZmZXAyZWZmZmZmVgYnU2ZmZmZmZmVwMmVmZmZmZlYGJ1NmZmZmZmZlcDJlZmZmZmZWBidTZmZmZmZmZXAyZWZmZmZmVgYnU2ZmZmZmZmVwMmVmZmZmZlYGJ1NmZmZmZmZlcDJlZmZmZmZWBidTZmZmZmZmZXAyZWZmZmZmVgYnU2ZmZmZmZmVwMmVmZmZmZlYGJ1NmZmZmZmZlcDJlZmZmZmZWBidTZmZmZmZmZXAyZWZmZmZmVgYnU2ZmZmZmZmVwMmVmZmZmZlYGJ1NmZmZmZmZlcDJlZmZmZmZWBidTZmZmZmZmZXAyZWZmZmZmVgYnU2ZmZmZmZmVwMmVmZmZmZlYGJ1NmZmZmZmZlcDJlZmZmZmZWBidTZmZmZmZmZXAyZWZmZmZmVgYnU2ZmZmZmZmVoyzsAy4/ESsAewFLAYOBj4CHgNxGMyzM2M2tdEkOBXYB1gLmBduA14PIIXsgzNjOrXxKLA3sBKwBDgU+BJ4ArI/g4z9hKJg0Etgc2AuYFJgFvAdcQ8USeoVlhioi8Y7AakhCwHfBDYEWgHzMn1eNII5ZXAz+N4LWaB2lmLUliaeBoYDdgGjCkw8NTgKnAv4DTgVsj8BeYmSGxIfAjYC3SNUz/Dg+3Z9tuA34SwTO1j7AE0kLA4cAPsi1DOzw6DZgIvAmcSUqsvqhtgFaMk6kWItEGXEZKpob0sPsU0t2QbSK4r9qxmVlrk9gIuAUYSM+zJsYDNwB7RzC12rGZWX3KbhCfDBxGmmHTnS9I1zXfj+C6asfWK9JqwD2ka7P+Pew9njSLaDsiJlQ7NOuZk6kWkZ1wrgO2pucTTkftwKYRPFyVwMys5UmsB/yR3p+bbgFGeYTKrDVJnAYcTM83iDtqB/aM4MbqRNVL0krA34DZAJX4rAnAY8BGRPiGUs6cTLUIidHAT+ndCWe6McASEXxa2ajMrNVJzAW8wcxTWko1Hjg8gl9VNCgzq3sSWwA30rubMNO1A8MjeLmyUfWS1J80dW9+Sk+kpmsHLiDimIrHZb3ian4tQKIPcCwFEqmrr4Z334XPP4cXX4Tvfa/gIdpIhSrMzCrte0DfQg8svzzcey989hm8/DJsu22XXYYAx2Uj72bWWk6gQCJV4nVNP+CQ6oZXkm1J57GZz2H9+8Ovfw1vvAFjxsDTT8Nmm3V+7mBgf6RBtQjUinMy1Ro2Ig0fd3H66bDEEjBsGGyzDZx6Kqy2WpfdBgNH+oLFzCopu9FTcK1D375w223w+9/DXHPB3nvDNdfAsst2OcwwYIPqR2tm9UJieWDlQo+VeF3TD9hTKmu2TiUdQ6FR+bY2ePttWH/99IsceyzccAMsvnihY+xQ7SCte06mWsMhFEmmnn8eJk9O/x2RfpZeuuAxhgLrVic8M2tR61Nk6vHyy8NCC8G558K0aXDfffDIIzBqVJddh1Afd5jNrHb2pUihml5c10wDRlYpvp5JywHLF3ysvR1OOgnefDP9AnfeCa+/Dl/9auc9ZyPdkLIcOZlqDcvTzVzciy6C8ePTcPh778Ef/lBwtz7AMlWKz8xa07IUmeJXiARf/nLXzaSeMmbWOr5CGl0qqMTrmtnI97pmGWBySXvONx8stxw891yhR5eoYExWBidTraHbxZn77w9Dh8I668DNN8OkSQV3awNmr0ZwZtayhlLk7vKLL8KHH8KRR6YZLxtvnGa8DC58Nst7qo6Z1Va3BWtKvK4Bnl1NUnT42Rug07Y7sm13dNyebdu7075bS1qo07ZLsn2f7LDtXWC2iakVRPfa2uDaa+HKK9OJsauej2FV5WSqNYzvaYdp09IUmkUWgf32K7jLVODzSgdmZi1tDBTuEzV1aio4seWW8P77cPjhacnAf/5T8DjjqhijmdWfMT3tUMJ1DbDykxGhDj+XAHTatnW2beuO27Ntl3Ta946IeLfTtr2zfb/aYdtCwNiBqRFvcVKqqDF5MhxwQLG93GsqZ06mWkI8nybd9qytrejc4gBeqmRUZtbyXiKtWyjo2WdhxAiYZ55UyGqppeCxx7rsFsDz1QvRzOrQPyhxilw31zXjyPe65iV6atB76aUw//wwcmS6w1TYa5UOzHrHyVQTk7SopLnhhtsKDU7NOy/suCMMGQJ9+sAmm8DOO6dSxF19PgX6HC7p25IGVD14M2sFD9LNiPfKK8OAATBoUBqZWnBBuOKKLruNB86pXohmVocupsCNmN5d1wBwczWD7FbEq8CzRR+/+GJYYQXYemuYWHQAayzwsypEZ73gZKrJSBoiaU9J95Lu3HwNXrgUhrzbed+INPT9n//Ap5/C2WfDIYfAHXd0Oex4mPoTiDtJncbfljRU0iBJLpduZmWJIICzSc0nuxg1Ki0e//BD2HDDtG5qctd70R8DD1U3UjOrJxG8AvFUge2lXtdMBi6NyH2K3E9JCdHMFlsM9t0Xhg9P85zHjk0/u+wy027ZlKObqh+mdUdR2uwvq2OS+pJ6Sb0KTAIuAq4Cfh8RE9M+/AA4l/IWan8GLB6R5ihLWiAi3pd0HDAKuBq4JiJen9Xfxcxai8QcEG+AhvX+2V9MhL6jI7i80nGZWf1KN3L/uiOseg0MLLkiaAftwMoROU+Rk9qAN4AF6eUAxySYej6MPxq2j4h7qhGelcYjUw1M0jySzgbeBk4BFoyItyNim4i4aXoilfk1cCNF7gB3ox3YdHoiBRAR72f/eSopmZofeCAbFVtUKueiyMxaUQSfwT2jYHLRBQGFTZ0E1wBtn1QjLjOrP5L6SDoEuDRizeth4ImUUGSrkwnALrknUgARU4ENSeu3ejO6MWEA3HsS7Az8UtKCVYnPSuKRqQYjaQFgF+BR0lzbo0mjQi/0/Fz6kkatdqPnEarJpCozW0TwSAlx9YmIadlJ7kTgLtLo2J8i4ouenm9mrUfSsqRz2N4QawN3AgPoaVF2uni6AgZfBRNuBbaNiK6lKcysaUhaGricNBCwZ0S8IiHSOeQ4YBDd9NQkVQ6dDOwWwS3VjrdXpC8D95F6X/VU6nw88GdgZyImSWqLiKmSjgceiIgHqhytdeKRqQYhaUFJfwReAL4MjImIMRHx41ISKYAIvgD2A3YgrTGYSNdqOGOzn4uAL5eSSKVjx7Tsf88DlgLuBw4A+kj6uqRVvb7KzKaT9A1SAYq/R8S0CB4indt+QbpL27nc+fQbPA8A34nggIj2x4BVgcclfUmSv9PMmkyHa4eNgNuA9SPiFUjrLiM4A9iEdDNmIl3LjY8njUZdBXy17hIpgIh/ASuS1lB9Std1VFNJv8NTwF7A9kRMSk+N6aP6/wCuk3SepG77i1pleWSqTmUXBesBu5NGeW4BRgK3R0Rvp+oVeQ2WJo1SLUkaqfov8Dfgxogeeh/06nW0O3AS6YR2FXBuREyp1PHNrLFIWgJ4jHR3+Q9dH2cQ8B3gG8C8pHPHa8DVEXRZm5ldbN0FfATsFdlFhpk1NkmLAZcBZ0bE3T3vz4Kk5QdfAoaRCtQ8Dfym43KFuib1A7YBRpCWUUwE3gKuI+K57p+quYELgKcj4qwqR2oZJ1N1Jkui5iNN4/uMlHxc22GdUkPKfq+1gc2BHwPbAYOBWyLCDTfNWoSkpSPiVUmLREThFrzlHXcwcC3pAmq7iPisUsc2s9rKbpDsBZxBKv19docRGOtBds21FikpO77TGnqrME+JqANZIYkDJD0GHAR8AGwREatExM8aPZGCNA0wIh6KiB9FyuDHAjsC/5F0pVJFGzNrUtnC8TOAW7I5/hVLpACyEfvtSaPrc1by2GZWO1ki0BdYE9ggIs5wItU72dKLl4ClgSclrZ5zSE3NI1OFpD/kTYGjgK+RFjVOJc1jvQz4BbN4IZA1vh0EtAEvA38gjULd20onDUnzkU6Wv5V0FDA3cFX0MJRdwoH7kCrkHEk6IQ8GviC9h1eQ3sM3Z+k1zKwk2fnuMtKU4m0i4qMqv56AXwIXRkTxpphmVjeyv9vdgEOANVrpWqhasn/TnYDRwAgXBKsOJ1OdSbuShpQHA0ML7DF9qPQB4LtEvFf6oSXShf3upDuox0XExZIGRUTejeNyJ2kFYA9gV1K593WAiN5+SKXvAOeR3r/Z6FrdZxKpBOkjpPfw7VkK3My6JWle4HjgqFqd6yTtDJwP7BQRf6nFa5pZeSTND/yKVMBqj4h4OueQmkp2/dkPuJK0/uwf+UbUXJxMdSSdAhxGSqR6Mn2kal0iXuz+sFqKNKXyI1LpyxtI66DemrWAm1PWhHjFiHhW0q+ARUijdrf3eCEm/Yi0JqvU9/BzYERWScfMKkjSIsAJwP4R0blyaC1efwPgt6Q7ss/X+vXNrGfZNP+VSTeZT3YBmerIEqrdgbNIRSrOcDGwynAyNV3qj3QapV2ETxekCnir0Gldk6SBpA/t7sBywGERcU1lgm0dkoYA3yb9Oy5J+recC/h0ejn2DjvvDZxL79/DT4Dhszp108xmkLQyqVTxz4Gf9XqEuXJxLAS8BywDvJJXHGY2M0nzkFohPBcRJ+UdT6vIbnL9H3BaRDycdzzNwMkUgLQoaaFeT43SCpkC3EbEd5TKWW5GGu34O+nDehNwl7P/WSdptogYJ+mXpH/nq4GrI+Il0hSBNyjvPZwK3E3EFpWL1qx1ZVN2ngEOjojr6yCePqRpvU8BB3ndgFm+JG0LXEyqwHmclzrUliRFREg6nLR2/2yfF8vnan7JaLrvmg3LLAMTJsDVV3d+pF/AVktKlwDvkDpxD4mIyRGxR0Tc4USqMjqUUN8P2JbUG+tSSXoBjit4W6B/f/j1r+GNN2DMGHj6adhss857tQEbkO5gm9kskLRERHwAfK0eEin4X2WrzUi9Z37nhpZm+ZDUP/vPpYDvRMQRTqRqr8MI/e9IBdcelvSlHENqaB6ZSn/YH5J6kxT3pz/BoEHw5pswatRMDwVMuAn+skO6C/tq9YK1gqS+42HskFQdcWaDB8ORR8IVV8Bbb8EWW8B118HKK6f3coaJwNlEHFejqM2aSjYf/0hgb+DL9djXJLuQO4M07fCdvOMxazjS0qS/8ZVIRZ4+J434/h89/E1J2oI0GrVeuJpu3chG7vcDvhQRB/W8P0NJhcI2JlVgngi8CVwOPBpByyUWTqakDYGbgdmL7rPjjrDddvD882mEqlMylXmFiGWrFKV1R1oLuIvC1Re7+uc/4aST4OabOz/yHyIWrXB0Zk0vKxpzPrAuqUdeXScqWby/AH7qG2BmJZA2AY4DVifNaurf4dHpN07uB04m4m8zP1VDSRV2NwD2ioj7qxytlSkrmHYxMLrzuVFiSeBHpERqGml20HTTgAmk9alnAFdE0DLTBj3ND+ajuyl+Q4fCySfDYYf1dJy5KxmU9cr8UOKdkPnmg+WWg+cKtrFyo0+z8gwlXVytV++JFEC2NuAfwEOSvpZzOGb1SxLSqcAtpHYlA5k5kSLbNpA0XewepNEdnj6I9P38PrCKE6m69ybwJ+DvkkZno1ZIrAf8E9iTNAtoSKfn9cm2LUO6sfZ7qVfFwBqak6lUd794MnXKKXDppfBOj9cHbZUMynqlX0l7tbXBtdfClVfCiwWr2fs9NOsFSfNkBWEmRcTeEfF53jGVKiIuBvYF/iBp8bzjMatTp5Ca6JZyYaxsv7M+kQ7Kzg03RsS4iPhxRIytYpxWARHxRUScQzbLAJhTYg3gj6SbZqVcJw0B1iclVC1xXeVkKvWKmlbwkVVWgY02gnPPLeU4Pknk5xN6GpmSUvGQyZPhgAOK7TWu2ANmNjOltRN/Jf391d36qFJExO3AahHxpqQl847HrK6kqX2H0nUUoieDB8F5G8MCpClh1mAi4t8RsRXERBj3EL1rOQNp9GoNUp/BpudkCh4FBhR8ZMQIWGKJVLjgvffgiCNg5Eh48snOe04F7qlqlNadJyn2Hk536aUw//zp/Zs6tdAe00gNlc2sB5KGAQ8C50bEjxq5d1NEvJ01Db1D0ilZIQ0zS2ukil9EF69yzACIP8O4RhqttoJ2hkFdKlLvvz88/jhMnAiXX170uYOBg6Qers+agAtQAEi3ANvQObkcNAhm71CX4ogjUnK1337w0Ucd92wH1iLin1WP1QqTrgF2Avp2eezii2H48DTKOH58sSOMBzYk4tGqxWjWBCQtmiUgS0XEa3nHUymS5gPuAF4AfuCWFtbS0sjzv+iud2M3VY4zE4GFiPi0OkFaNUmI1IN1mc6PffvbMG0abLpp+gh897tFDzMW2CeC66oXaf48MpWcTapCMrMJE+CDD2b8jBuX0vCZEylIlfycSOXrHGBSl62LLQb77puSqfffh7Fj088uu3Te813gseqHada4JO1DWpg8ezMlUgAR8SHwTdLNsTnyjcYsd3vT3TXijjvCZ5/Bvfd2d4xpwM6VDctqaDiwYKEHbrkFbrsNPv64x2MMJU0VbWotsTCsBH8F/saMSjWFnXRSoa0TgIOrEpWVLuIppHtIfQ9m9Jt66620Xqp7E4AD8TCtWUHZ1LdTSKO/IyJiTM4hVUVEjAdGS+ov6VfASRHxbt5xmeVgJbpW7UumVzn+5jfh+9/v7hiDgeWqEJvVxlJQkfLmTb8e1SNTQHYRvS3wIr1bSD0B2BeX+qwXO5KmJfSmm3o7cCgRf6pOSGZNYTCwMLBWRLycdzA1MAV4HfirpBXzDsYsB8X7NpZe5RhgropFZLU2G5XJEwb1vEtjczI1XbojuRZw3xcwsWCJghnGZz87EXFV9YOzkkRMBNYjNfBtJxUGKWZ8ts+eRPyqBtGZNRxJs0u6EOgbEd/NpsI1vUjOAI4F/pKtpzJrJYULR/SuyjFAzxPBrF6NpVi1695pr8Ax6pqTqY4i2onY4nbY9t3UtGwi6YQy/Wc88AZwJLAgqayu1ZOIiURsB3wDuIo0StXxPRwHvH0p3LtaSoZvzC9Ys/olaSFSxb6+tMCXYSERcQ3wjYj4UNJiecdjVkNPUWimTulVjiF93z5b1Sitmv5NZZYDvVCBY9Q1V/PrJOs10i8iXiKV//0KaTHyJFIH72e9tqaBSLOT3sM5gcnAB8A/BaOA3SNiozzDM6tHkgaRpsz+H3BmI5c+rwRJA4HngQtJ5eBb+t/DWoC0MPAKndeRl17lGNJNmPmymT/WgCT+AazSeXvfvtDWBiecAIssAj/4Qeo680XXFVZjgd0iaOrBBydTnUi6CnghIk7POxarHkn9SF8U20fE43nHY1YvJC0UEe9KWrZF1keVRNKiwB9JPQUPj4hKLMw2q1/SH4FNgeJVnE44IfWb6loafQpwKRH7VS9AqzaJnYFf0WkN3QknwIknzrzviScWrNP2EbBAREUKWdQtJ1MdSFqcNLS9dER8lnM4VmWSfgBMCq97MwNA0g7Az4GVI+K/ecdTbyTNQWqlcYS/I6zpSWuSbh4Ub9xbXDswHN+QaWgS/UnFeBag90uDxgPHRVDyArtG5WSqA0nnApMj4ui8Y7HakdQnIiqxyNKsIWWlzw/NfraMiGdyDqmuSRpMSqqOiwgvsLfmJY0GzqJ3CdUEYBcibq1KTFZTEl8CHoNpQ6FPj71mMu3A7cAuETR9ouECFDM7GTgz7yCsdiTtCPwy7zjMctaf1KBxLSdSJZlIWgvwSLbO1qw5RfyCdJOlnZ57Dk3J9nMi1UQieBF2ORs+mwZRSvug8cD1wKhWSKTAydT/SNoJmC8iPsk7Fqupe4DtJS2SdyBmtSZpkKRzgCERsXtEvJ13TI0gIqZlMxguBB5SKlZk1pwiLiG1jrl+EsS0rr0cx5GSqEtJU/turXGEVkWSvgrXHQT7rgM6jbQOauzMe8XkdI+p/W/Ad4DvR3TbnqapeJofIGko8BqwZkS8knc8VlvZxWRExOF5x2JWK5LmBm4D3gb2jIhJOYfUkCQtHRGvSlo4IkrqYmrWqB6V5l0jXSwvR6qS+zGp8udvXbWv+WTfE08AR0XWSkaiL7AFsDZpLVU78BZc9eeI3Z/KLdgcOZkCJB0GrBERO+Ydi9VeNiq1fUScl3csZrWQVbN8ilSd7hivGZw1Si0YngeOj4jL8o7HrBqU1k89EBHP5R2LVZ+kvsCdwLMRcWQJ+w8Cvh8RF1Q9uDrT8slUtvD6MWCfiGjJjNoSSQtGxHt5x2FWTZLmj4gPJK0QEU3fTLFWJC1HSk6vAk52LyprJpL6A+8Cq0XEW3nHY9Un6WRgXWDjiOhxyp6kPsCbwOYR8a9qx1dPWn7NVPaFt5YTqdYmaQngH1mVLrOmJGlz4FlJizqRqqyIeIm0rmRpyislbVbPNiX14HQi1QIkbQ18F9iplEQK0lpSUuGJnasZWz1q6WRKUl9J1wKz5R2L5Ssi3gAeAb6XcyhmVSHpe8DlwLYuNFEdEfFBROwO9JF0viR/t1iz2AT4Td5BWPVJWoZUTGSHiPigl0//DbBDNuurZbR0MgVsCywDfJZvGFYnzgSOyNaTmDWNbO77CGD9iPhrzuG0ggnAIOABSQvkHYxZBRwE/DrvIKy6stk5NwMnRsTfyjjEP4C1W22ac8smU1nWfAxwRqu96VZYRDwKHJh3HGaVIqmfpNOBeSJiVES8mHdMrSCbFrMPcCvwcLYw26whSdoY2CYipuQdi1VPdl18CSkhuricY2TX04MlfaeCodW9lk2mgHlJiylvyzsQqyt3ABtlCynNGlY2xex24CukJopWQ5GcAmwZERM8QmUN7CBg9ryDsKrbH1gZ2HcWBxn6ARdIaqtMWPWvlS8YP4qIb7kksBVwKrBV3kGYlSu7GfAnUg+pb0XEuJxDalkR8aKkeYF/ShqZdzxmvZH1GVqPNMpqTUrSWsDxwHYR0T4rx4qIl0nfPRtUIrZG0JLJlKTVgT/nHYfVn+xuzJnAD1ttAaU1B0nzZjeJ9ia1fGiZLvT1KiL+C2wGnC/p4LzjMeuFDYC7ImJs3oFYdWSj5jcA342IVyt02N8AO1ToWHWvJftMSboReMRNWq2QbLH+i8CoMhdgmuVC0jrATcCIiPh33vHYzCQtDvwE2CsiJuUdj1kpJPWPiMl5x2GVlxXcuge4PyJOqOBxZyPdn26JKeYtNzKVNVYcgavSWBER8QXpbtyjecdiVqpsCtnNwO5OpOpTRLwZEbsCQySdJWlg3jGZFSNpYUk/dCLV1M4A2oGTK3nQbGr5apK+Ucnj1quWS6ZIzRSP8BoC607Wh2cHSV/OOxaznmRTUrcBNo0IT2Guf+3AEsCfJM2ZcyxmxexEah9jTUjSDsC3gV2zm8iVtjxweBWOW3daapqfpGHA5IiYkHcsVv8kHQmsGhG75B2LWSFZoYkfA5dHxH/yjsdKl713ZwMbAqu77LTVG0lPAMdExD15x2KVJWlF4AFgk4h4ukqvMRfwOrBoRIypxmvUi1YbmToWqNicUGt6vwI2kbRU3oGYdSZpAGmR78akkQ5rIBExLSIOA3aOiCmS5ss7JrPpJC1IaiFzX96xWGVJmh24BTiyWokUQER8QkrYtq7Wa9SLlhmZyqZSvAoMj4i38o7HGoOk04BPIuJnecdiNl02re9OYBxpjdTEnEOyWSBpMeAJYDdP07R64cITzSf77vgd8GFE7FuD15sH+LRK0wjrRislUz8Glo2IPfOOxRqHpDaXlrZ6kk2d+JTUXPFf7pXXHCStS6rEeFREXJl3PNa6sgvu04FTvb68uUg6ChgJrFeriqKSdieV1/+wFq+Xh1aa5ncXcEreQVhjiYipkjbLTkBmuZI0HHgGWC0innEi1Twi4iFSpdlNsvYMZnlZDfgO0BJlrVuFpG8ChwLb17g1w6akz1PTaolkStLXgTcq2IzMWsuLwFFZAROzXEjamNRs/NCIeDLveKzyIuKFrHT6PJJOkdSWd0zWknYGrotWmbrUAiQtClxLmkr8do1f/jdAUxfyavpkKmtIdgOwbN6xWGOKiNeBPwH75B2LtbSdgJERcWPegVjVtQNfB26VNCTvYKzlbEa6ALYmkBUrugk4LyLuzSGEu4EvSVokh9euiaZfMyVpV+AHETEi71iscUn6CrBPROyfdyzWOrK1C4cCt0bEa3nHY7WT3Qi8hNTnZ31P6bRaceGJ5iLpYmB+0s24XC76JS0QEe/n8dq10NQjU9mFyBGkDs9mZcvWp+zvtQxWK9kUr18CuwHujddisr5TewH7R8Q0SXPnHZM1P0n74ka9TUPSnsA3gT1znrb5uaTROb5+VbXCyNQSwJue+2uzKvss3UZa/N/UZT4tf5J+A8wFfCcixuYdj+VH0gqkfj/fjoi/5R2PNSdJ/YF3Sd9xbiHT4CStSlpnu35EPJ9zLH2At4BNI+K5PGOphmYfmTqc1CPIiZRVwpukvj4j8w7EmpekObJR9TOBrZ1IWUS8QBqlul3StjmHY81rE+DfTqQaX9ZC43ekke1cEylITcqB60jFTZpO0yZTktYBRpMW8prNsiwpPwM4JrvYNasoScsBT5LuJP4zm+plRkT8AdgcGOnzj1WJC080gWwU6Frgloi4Ie94OrgO2LEZz19NMc1PYgAwGBgTwRdpm+4Afh8Rv8o1OGsq2UnqOOCnETEhbWMQMID0+fMicZshfV5mByaRfV6K76o1gVuAH0fEpbUIzxqTpIWBPYAzui1MkdZ4zg60U9u+MlbnJAQMAvoBYyOYll3ktvkmTmOTdBKpZ91G9fReZp+v+SPifdJ/DyEN6oylwZORhh2ZklhS4hyJz0mjT+8DUyRel945BuZYEXAXeauoiJgWESfBTWtLXCExARgLfED6/D0rsVuW4FsrkgYijUL6FzCF9NkYizQB6TKklYs8c3dgLydSVoKJwJbA1VnZ4xmkYUgHIr1B+vy9D7QjfY70M9LaT2tREqtKXEMqajMG+BCYIn3+Clz5U4imGzVoJZK2Ar4H7FhPiRRAAPfAiLekJ4HJwKfAR8AUpPuQNs9uQDachhuZkpiPNHy5DikZ7F9gt/EQfUC/AI6ePlplNqskloP4LUxcBQZMgz6FqvtNX+NyHPDzCBrrj8zKM6OM+YnZlqEF9ppKusB9AdiRiFck7Q08EBEv1iROawqSBpG+CwcAWwX0Bc4i9cObRrrr29kk0jXNQ8AuRHxUo3AtZxIrAtcDS5M+MwW+uyZPhP6TgWMiuLimAdosk7Q08Ddg24j4a97xzEQaAVw5DeYBBhfJmMYB44HvE/H7WoVWCQ2VTEksAfyV9Gb0K+Ep7aQvja0jqKsM3RqPxNeAe4DZKG1Ut500Orq/E6omlxKp6WXMB5fwjGkBY7eDW2+FNYHNsubQZiXLWjV8+WV4YTH4c3/4GqV9/iaT7giviYsNND2JtUiN54cApYw8tZPOZ0f4u6sxSBpMuj7+dURcmHc8M5F2AK4gTSstxQTgMCJ+WbWYKqxhkimJuYCngYUpeEelqHbgdmAXnxSsXBJLkwoDDOvlU8cDP43g5MpHZXVDOoU0KlVoNKCosfDFH+FrO0Q8XZ3ArOlJeh/uHgbfHFTahfJ0XwBvA6sS8Vl1grO8SSwPPEbhkfLujAdOiuCsykdllZStRbqSdJN3VF1VsJY2AO6k9ERqugnArkTcUvmgKq+R5iYeT+rgPFMidd99MGECjB2bfv797y7PGwxsRWpaZlauX1Lgy2j//eHxx2HiRLj88oLPGwL8MBtVtWaUplYcTqFEas454eabYdw4eOMN2HnmqrCzATvA6bUI05rWxgvANwomUosvDnfeCZ98Au+9BxdcAH3/9xXaF1iQNB3ZmtevKXBuKuHaaQhwssTCNYjRZs1+wCrA3nWWSE2vKtg1kerhuzF7zhV0XhNapxoimcqqpX0PCi/qP+AAGDo0/Sy/fMFDDAGOqF6E1swkFgPWpcDfy7vvwqmnwmWXdX8I4IDqRGd14ECKjZZfdBFMngzzzw+77goXXwwrrvi/h5WeN4JUnc2sHEdSbGrfL34BH34ICy4Iw4fD+uvD6NEd9xgA/KBRLlisdySWAb5KkWu9Eq6dAPatUnhWAVkV2BOBkRFRb62ANibdM+yqh+/GjGiQvp4NkUwBO8AsTdETMMJ3WKxMo4s9cMstcNtt8PHH3T5/ALC3K/w1oVQE4HsUKoQzeDCMHAnHHQfjx8Mjj8Dtt8OoUZ33DNKdRbPekRYjFWMqPL1vySXhhhtg0iT44AO46y5YaaVCe25fxSgtP8Vv9JRmILC/VNIadasxSfMDNwDfi4hX8o6ngKMolEyV/t04FDi6BnHOskZJpkbRzXzf00+H//4XHn443XgrYhqwdRVis+a3M0VGRXshSBc91lzWhSK9xZZbDqZOhZdfnrHtn/8sdDE7ENi1SvFZc9ua7m40nnce7LQTDBoECy0Em2+eEqqZDSWV5bfmsyPdFOsq8dqpL/D1KsRms0BSG6k64xURcUfe8XQh9QfWp9CNntK/GwG+hDRflaKsmEZJpuYv9sDRR8NSS8HCC8Mll8Add6T/X8BAUhVAs96as0LH8eev+cxLsVGB2WaDMWNm3vb552lOTVdzVDguaw3zkr7bCnvwwXSBMmYMvPMOPPFEqh/ZVd1frFhZihZM6sW1U+Dvrnp0OqnVwYk5x1HMnFCkinbvvhsn0wCfv0ZJporG+dhjaf3a5Mlw1VVptHCLLQruqu6OY9aNSnxu/PlrTn0olkyNGwezzz7zttlnT6u9Cx/HrLeKf26kNAp1880wZAjMPXda9H3mmb07jjUyXzs1IUnbk6bm7hoR9dpHtQ/FRs17990YNMDnr+4DzHS/IqWDiPQdUsAkUrdls94q+BfeS9Pw568ZfQJFmoK/9BK0tcEyy8zYtsoq8NxzhfYeU2ijWQ8+Id257WquuVI1vwsvTFfMn3ySSo4WvmL+pJpBWm7GlbpjN9dOgb+76oakFYCLge0jouRr4xx8SrHlEb37buxPA3z+GiWZuoXU82Amw4bBJpvAgAGp2usuu8B66xWaEg6kE8LdVY7TmtOdwNRCD/TtO+Pz1/G/C+hPaqhnzeURin1htLenUYGTT04LbtdaC771Lbj66s57TgEaqtu71Y27KZbMf/wxvPYa7LdfOikNGwZ77AHPPNN5z/HAzVWO0/JxFwU+H728duoHPF7lOK0EkoaS/laPjogn846nWxETgS4nG6A3340AHwDvVjHSimiUZOoKClSk6dcvlaX+73/ho4/gwANh221nXtPWwbMRdO2kYNaz8ygy9/fYY1OPqR/+MBWimTgxbetkKnBDhEcfmk5qdvo7il3Qjh6dFv9/+CFcd126sH3++c57TQXOr2qc1pwingNeLPr4dtvBZpulL8lXXoEpU+DQQzvv1Qe4qopRWn7OIc3KmUkvrp2mAFdGdL2ZbbWVNea9HHgwIrpvxlI/zqTYzJ7SvhvHA2dTT72zilADxAiAxDXATpRX5nMcsGcEv6tsVNYqJJ4CVi3z6e3AWhH8s4IhWb2QVgMeolivn549RsQaFYzIWom0I6kxa+F+Lt2bClxLxJ4VjcnqhsTzwAplPn0CsGpENwm71YSkI0htgtaNiC4Jcl1KFf3+C8ze065FTAAWIKLub0Q3ysgUwLH0Yv5vB5OA54DbKhuOtZjRMLngVL8etAO3OJFqYhFPAXeQ3uveascNnW3W3DwW3irz6moccEJFo7F6sy/porS32oFrnUjlT9IGwOGkdVKNkUgBREwm9Tor57txPHBsIyRS0EDJVARvAJuQhgxLHU6bCLwObBZReM2LWU8kDQM9CY8fBNGbL6V24O/Ad6sUmtWP3UnrCnrzpdEO7EyE1yNY2QTDXk/9XN4kfeeVIkjfpRsT8WbVgrPcRfAg6Tuot99dD+Jm4rmTtAhwLbBbRLyVdzy9FnEVqYx7b78bLwPOrUpMVdAwyRRABI8BawJv021SNTVg6hTgAeDrEXxWoxCtyUhajFRkYPuItS8GbQnxKYwr3Kg1mUS6qLke2DSiSK8Fax7pDtzGpG70EymwTqGDsaTqRJsTcXsNorMmJKmPpDOAm1eBjwfAV4CHSRfNxW4eTk+i3gLWIOKJ2kRreYrgt8C2wOd0W532iymk89eVwFa+CZ0vSQOAm4CfR8S9ecdTtohTgYOA9mndJ1XtpM/ficDBjbBWarqGWTPVkUQf0oXLUcDapAuX6bXo2+CDO+DeiyN2uT+/KK3RSVqFVGXtnIg4d8b2ebaBbX4Ol34CWoFUmjhI6/mmkcqWXhTB23nEbTmTFgdGk6bX9CEVpxCpouNzwBnAbUQ4ybayZBdZlwFLAVtHxEcdHlwJOBTYhZRUTSN9/gaQRhvOAu4lorsbQtaEJAYA2wHHAMsx03fXZMFTv4dvHB7BO3nGaYmki4CFgO2iES/WO5OGPg1HLgkHzJHOR9O/A9tI7UHOBi4nou5LoXfWkMlURxLzkj5sg0l3Xd6MYLyk5YA5I+LRXAO0hiXpeODfEXFDp+0PAhdHxHUSCwHzk04MnwGvRRTp+2KtJS2+XQqYg3TD5wMi6r7Eq9U/ScsDPwb2iYjCd3qlIcDiwDDSHd936Jh0WUuTWASYjxl9fF4DTQX61HEj2JYhaXfS3/jXI+LzvOOpFEl9I93gWQKYm3TD8RPgtUa+wdPwyVQxkrYBjge+1hQZvdWMpFHAGxHxUIHH1gauBpaLCE+BMLOaydZP7AWc4u81qzRJl5BKb1+TdyytTNJwUg+5EZHaHzQFScuS+mR9pdnOXw21ZqqXfg8MAjbMOxBrDEp+BJwCFOssfjRwlhMpM6slSSuTGn+XU5nNrBQPADvnHUQrkzQnqXfhgc2USGV2Au5vtkQKmnhkCv43TLp9RGyTdyxW/ySdCHwL2DIKTMeS9GXgHmDJiF5V9TMzK5ukL5F6mR0cEdflHY81J0mzAe8AS4enhNacpD6kNhsvRUSX7tqNLGs6/DywV0T8Le94Kq3Zk6l+wOBmmm9qlae0tuALYGHgv1Gkr4Gkq4AXIuL0WsZnZq1L0lyk9Zhfjohncg7Hmpyko4FbI8L9pWpM0gmk2VQbRpMVKJI0mFR86WCPTDUgSYsCu0bEGXnHYvVH0nykO0GXRcSvutlvceAp0h27z2oUnpm1qOxO7lGkqTFfjQZenG2NRVJfF6GoLUlbAJcAq0fE+3nHU2nN/plq5jVT030CHJZVPzL7n2wx5F+Bu0gnse4cDvzaiZSZVZukvsCFpPLmWzmRslrJkvjnsh6LVgOSlgIuB3Zq0kSqD/B8NrjRlJo+mYqI8aQvpSPzjsXqzrbAmRFxQnfDzpLmBXYDzqtRXGbW2hYjla1eLyLc88dqJvsufBDYMe9YWoGkQaSCE6dFxMN5x1MlawOTI6Jpe282/TQ/AElzA38h1euflHc8lq+sbP6EiLi7xP1PBuaPiH2qG5mZtTJJ85AaPp/q0SjLi6QNSM3qV807lmaWjQJeDvQDdmvGtUQAki4G3mrm9eZNPzIFEBEfA8OdSJmk/YBfkpoUlrL/UGA/4KxqxmVmrU3S0qRpxwOBpryosobxIPBXSQPyDqTJ7QN8Fdi7WROpzHvA9XkHUU0tMTIF/5uD/gdg54j4JO94rPYkHUK667tZRLxW4nMOA9aICE95MLOqyNanPAqcHBEX5x2PGTR/0YA8SVqDVPxq7Yh4Oe94qqVVPkMtMTIFkL2Z7wD75x2L1Zak/llZztuAtXqRSA0ADiOV8zQzqzhJcwBvA1s7kbJ6kRVF+Ec2Fc0qKKsifCPw/WZOpDKXSfpO3kFUW8skU5mzgAOzvkLWAiQNA/4IHBARr/eyEeGuwL8i4unqRGdmrUzSPsDfgb4R8UTe8Zh18DppyunqeQfSTCS1kaa8XRURt+cdTzVlN7G/RZo22tRaKpmKiBeAK4CmLc9oM0haBHgIeAH4WS+f2xc4Go9KmVmFKTmVVGV264iYmndMZh1la3h+A+ycdyxN5jRgKnBC3oHUwFbAYxHxQd6BVFtb3gHUWkQcJalNUpu/wJret4BrgLPKWNy5LalIxQOVDsrMWt4CwHDStOMPc47FrJhrgZF5B9EsJI0klZxfvRXWEZGSxgvyDqIWWqYARUeSrgb+HBFX5x2LVV5W1nVwRNxZ5vMFPEbq+3BrJWMzs9YlaXbgIOD0FrmYsibQKkUEqknS8qTpblu0wpTebHbPtCavUvg/LTXNr4OrgaOzrszWRCTtAvwWaJ+Fw3wTmA1o6vnMZlY7khYiXUwtDHhRvzUESbsCv8g7jkaWtVi5GfhhKyRSmT2B8/MOolZaNZm4G5gMbJl3IFY5kr5LWuO0YUTcNwuHOgY4000zzawSJM1L6iF1PTDaU8ytgTwIbO+eU+XJZrpcCjwSEZfmHU8N7UwLLZNoyWl+AJJGABMj4u85h2KzKBtOHgjMRVo3+59ZONbqwC3A0hExuUIhmlmLyqb2jSX1q/P3jTUcSQ8CZzd79blqyHpV7gysGxET846nFiQtCDwPLBQRE/KOpxZadWSKiLgfeFaSK/s1sKz05u+AH0XE27OSSGWOBn7mRMrMZpWkHYB/AAOdSFkDOy/vABqRpPWBo4DtWyWRysxNWnPeEokUtPDIFICk7wHbRYSn+zUgSfOQOoi/Cuw1qwmQpOWAR4AlI2JcBUI0sxaUTe05NPvZMiKeyTkks1mSfab7uBBFaSQtDDwO7BERd+cdTy21YsGSlh2ZylwDDJf0lbwDsbJsBdwPjKrQSNKRwEVOpMxsFs0BbEoqfe5EyprBL4Gd8g6iEUjqD9wIXNiCidQywFNZ8t0yWnpkCkDSUcDwiNgl71isNJK+BiwSEbdU8JgLA88Cy0XER5U6rpm1DkmDgENI60um5ByOWcVkVf12joit8o6l3km6AFiUNPOppQpZSToWWCAiDsg7llpq9ZEpSHdbzso7CCuNpK2APwCVHkI+BLjKiZSZlUPS3KRKsV/B363WfG4D1s2m11sRknYjjUrv0YKJlIBdgd/kHUuttfwJPyLGAG9I2ibvWKx7Wffw/wO2rmRVIUlzAt8DzqnUMc2sdWQV+x7JfnaNiEk5h2RWUdn09zMAJ1NFSFoFOBcYGRGf5x1PDgYDfwH+lncgtdby0/wAJM0PvACsEBEf5B2PzSy72zEYGAoMjYiXK3z8HwPLRsSelTyumTU/SbNFxDhJ60TEw3nHY1ZNJ0l9T4D1gKVJze3HkK6f/k4LX1BmN2UfB46LiOvyjqfaJJYDvkFaHzoZeA+euTviK+25BpYTJ1MZSRcBn0fEj/KOxWaQ1I80GjU2Ig6swvEHA68DG0TE85U+vpk1L0mbAZcAK7fonWhrFdLcAd/7CE6bGyZl05ragKlAAB8BPwWuIWJsbnHmQFIf0jTIVyPikJzDqRqJNmBrUrn3VUjLLdqAaRBToX02mHA5zHN6BK/mGWutOZnKSFqSNDS5uKdo1Ids6sxNwCRgp4gYX4XX2B/YOCK2rfSxzax5SdoL+Alpkflf847HrGqkbwK3An1Js0SKGU/6vt6YiKdqEFldkHQcaZ3UBs1aeEZiPuBeYAnSiGQxU0hJ1jERnF+D0OqCk6kOJM0VEZ/kHYclkrYHNgIOiIipVTh+P+BlUqLmhppmVhJJQ0g97vaLiBfzjsesatLo683AoBKfEaSk6ptEPF61uOpENjp9KbB6RLyXdzzVIDEv8DQwH9CvxKe1A2dGcHLVAqsjTqY6kNSXNEz94xbrVl1XJK0IrBQRN1b5dXYFfhARI6r5OmbWHLIbMAcDF3gGgzU9aXngCWBIGc/+DFiBiPcrGlMdyWY0/R3YPiIeyjueapDoQ0qklgf69/Lp7cAeEdxU8cDqTMtX8+so69i8PLB73rG0KknrAfcBA6v8OgKOAU6v5uuYWXOQNBtwO7ABaZ2AWbP7Md19F++4Izz/PIwbB6+8Auus0/HRgUDT9hrKesrdBPykWROpzCbAkhRIpJZfHu69Fz77DF5+GbbdtstzBwNnSTR9A18nU12dARwlqS+SkOZFWhZpMVKxAqsSSZuQTk67RsTVlTkmkphHYhmJxaX/3WHbgrRw9s+VeB0za16SBgL3A28D36rG+k2zuiLNAWxPWifV1UYbwZlnwne/C0OHwnrrwWuvddxjILA/aTS3qWQ3Yy8CXgJ+nnM41XYUqZLyTPr2hdtug9//HuaaC/beG665BpZdtsvz5wHW6bK1yXiaXyeStADccxf8YxXYGZiLtKBOpLmi95Ka/N7fymVAKyk7MQ0i3cVYKCKemfVjMgewB3AEMC8z3sP+wH0wciG447SIydfP6muZWfOSNDgi2iWNAB4In/etFUgHkwqsFL6J/MgjcOmlcNll3R1lLLAXEU01zUvS3sBBwDey/ltNSWIx4EUKjE6utBL8/e8pj57uT3+CRx+F44+fadcA7ojgW9WNNl8emepI6hNwxruw1iqwL7AgMIBUuWQI6UJ8M9JUj9eRhucWa5PI1qmdC/wyIj6a1UQqG4k6CXgPOA1YhJnfw34QG8OVK8GksyW+Nou/gpk1KUnrAC9Kmi8i7nciZS1kfYolUn36wOqrw7zzpvldb78NF1wAA7tccw8F1qhynDUl6evAqaQqnk2bSGVWJfWQKokEX/5y18002WegECdT06WL+puA/ZWy8GJT+kS6MF8MeBhp/RpF2HSyOce/BYaTFnXP4vHoA1wLHE56D4ssmpVgNoEWBu6X2GRWX9vMmoukkaQqZt+PiA/zjsesxuYq+sj880P//rD99rDuujB8OKy6Khx7bKG9561WgLUmaV7gRlLhqpfyjqcGhlEkT3jxRfjwQzjySGhrg403hvXXh8GFr5zLKWDSUJxMzXAhaaFdqW+6sn1/j7RS1aJqbuuT7npsGhGfVuB4ZwHb0Ls/3MHAzRLDK/D6ZtYEJPUnLZ7fNCL+lHc8ZjmYUPyR7KELLoD334ePP4ZzzoEttii0d1OsL5TUBlwHXBsRt+UdT41MJE3T62Lq1FRwYsst00fg8MPhhhvgP/8peJySR7calZMpIEuG9qDYRXj3FWuGkBIxK5GkJSTtHBF3kYpNzHKJYYmlgdF0eg/Hjp35Z+pU+HnX5aKDgV/Nagxm1tgk9ZF0EKla3zcj4um8YzLLyWuk5qtdffZZmtrXcdZr4Rmwk4DXKx9aLk4hJRbH5R1IDb3T3YPPPgsjRsA888Bmm8FSS8FjjxXctWnL40/nZCo5hGKNyHquWCPgG0hLVD3KJiDpq8AjwNwAFVyDcCAFqg4NHTrjZ4EF0g21G7t2rxKwssTyFYrFzBpMVrHvOlIFswFeH2Ut7lJSMlTY5ZfDgQemdVNzzAGHHppKu80sSH9TDU3St0kFyXbOWui0ir+RekUVtPLKMGAADBqURqYWXBCuuKLLbuNpgQEHJ1PSUGBXivUNOekkOPnkVKIkAt59N/3MrA9N3E+hUiStBfwROCAiKvbHJTEI+B49dOYeOTLN8X2ocEeINiqwbsvMGk82hecu0o2VTSo07discUU8RXejSqecAo8/Di+9BC+8AE8/DaedNuPpKZG6n4huRzfqnaTlSDNXvhMRH+UdTy1FMA04B6YVnPI5ahS89166rtpww7RuanLXCX19gGuqHGruXBpd2hy4Hpi9y2N9+qShjOOPh+9/P1WqufXWtOJu4sTOe79FxOLVD7gxZXd9BwLLRUThgeCyj80GwK0Ueg87uPdeePDBlB8X8WEE81cyNjOrb5IGRsRESRsC90XEtLxjMqsL0q6kRKLXBQTaIT6FLRZO0/kbUtao+1HgvIj4v7zjyYP0tVHw4JUwqJzGuxOBayP4fqXjqjcemUrTzQp/SHpXsWZYFWNsWEqOB66LiM8qnUhl5u5ph8UWS5Vmrryy2926NKYzs+al1N7i35IWj4h7nUiZzeQ3wB/orhhFYe194eeLwJ8knZiN7jSUrP/lr4G/tW4ipcPgiePhzmPp/WdgKvAWcGjlI6s/Tqa604uKNZ/BMEknAkh6V1JkP09m2y7psC0kLSRp607b9s727bjtjmzbHR23Z9v27rTv1tlxO267JNv3yQ7b3s22ndhp369mPx23zdLvBDxIqrC3bbV+J9j+RhjTbSI0ahQ8/DC88UZ5HwUzay6SNgb+DBwZEW/mHY9Z3UlTl3YD/kTpVfnGA1cNgMOy//8R8FdJh0hqpGvOg4FlaMElHJK2kLQgaXre8IjtfwLsR+kJ1UTgVWD9CMZWKcy64ml+3U3zA3jrLfjxj+Hqq9P///a34bjjYLXVuuzpaX4zk7QucCSwSzWb25Uyze/FF+GMM9Ka2W54mp9ZC8iahf8ZODEiCq+iNLMkJUEHAT8EBtF1FkeQkqiPgeOJuGrmp2sZ4ArgFxHxm6rHO4uya5cbgW9ExBs5h1MzkoYB5wIbACMjrZvr8DjrAmcDK5PWmXdepz6ONNPrMuBHETR7U+P/cTKVClB8QDpBdHXSSbD55qmY/pQpcPvtcP/9aR3VDJOBC4g4ourxNgBJCwAbRsS1klTtqlhZAYoPSc2Uu1hzTbj77lTNb1zxP+0pwKUR7FedKM0sb9nUnR+QKoyNc8U+s15ISdWmpArIy5DWUo0D/gWcAzxEkb+p7AYGwGbA4sAv63FaraSFgMeB70bEn/OOp1ayIjzPkGYTHRkRRUeUssrHBwPfJN3Enkwqf34x8NuIXk8JbHhOpgCk/wP2pFBFv7Y2OP982GWXVHTihhvgqKNg0kwVQycCK9BCdzCKkfQlUsW+yyPilNq9LueR+kx1qej3y1+mrty7797tISYAq0bwYlUCNLNcZRcLFwFfBzaPiKbvfWJWbyQtD1wJjAX2ioi3cg7pf5Sadd8H/CEiTutp/2aQFdnYISIuk7RQRHQpV209czIF05v2Pk6x0anuBfAAERtUNqjGI2kV0tzqH0ZE9xPqKv7aLE26OzawjKcH8HgEa1Q2KjOrB9lajVuBAcD23d11NbPqym5sHAmsFxGb5x3PdJLOB5YEtq3HUbNKk7Q+cDnwALB3REzJOaSG5WRqOuliYBS9LwE6DliDiOcrH1TjkDSANCr01Yh4IJ8Y+BmwD71/D8cD60Twj4oHZWa5kjQgIiZJ2oRU+twXDGZ1IJv6N4S0Tuf4yLEnlaRdgJOB1SPis7ziqBVJG5FGCPeJiC7dlq13GqmySrUdQFqQXGrFmukLLrdyIqWDgN9HxLi8EqnMkcDtdNOxu4B24NtOpMyaT1aS+V+SVoyIPzuRMqsfEfEFaYr9W8DTkkZl6xprStJXgPOB7Zo9kZK0lqQNSNMZV3YiVRlOpqZLf9TbAxeS1kAVuyAP0mjUW8A65Js85EpSH0lnk0pm/iDveLJu3buSqs1MoHhiPP09/A8wIoK7axOhmdWKpDVJi6nPjBa/4WVWryJiSkScRCpMcSiwbC1fX9IcwO+AQyLimVq+di1JGijpp6TfdXBEfBERn+QdV7PwNL9CpDmB7wKHkxrCTiElnv2Au4GzSOukWvofT9JqpMRl+3r7o5QYBuxBGq2aj1RtZvp7+BfSe/iXCFr6PTRrRtnd7T8CP4+IP+Qdj5n1bHr1X0knAP+OiN9W+fWmr6V8IyIOquZr5U3S9UBfYHRE/DfveJqNk6nupC/kuYE5gEnAx0T0ZgpZU1JKNreKiKtrUfp8VkgImAuYk5RQfRxR8lROM2swknYD7gQ+q+dzk5kVJunrpPU8z5Iu/j+q0uv8GNgC2CAiJlfjNfKUrWU/GPgFqVr15z4nVoen+XUnIoj4iIhXiHjbiRRIWgx4GFi13hMpgAgigo8jeCWCt5xImTWnbNrxGcBxwOz1fm4ys8Ii4jFgNdJyigOr8RpZQZrRwHeaNJEaTqpSvTYwMCJ8c6mKPDLVyqTBpLsyC5NKin8OPEHEE4V317KkRYs/i4hzaxanmbWUbER5deCrwDDSOtZ3gDsLNYTMpvVdQWokuk1EfFy7aM2sWrK/7dVIjYIP7mlJgUQ/UmPhJUmVAscAzwEPTp/WL2kJ4O+k/koPVi34WZFa9qxNmhk1BfgAuJOIz3t+qhYAngaOBq52ElV9XZvUWvNLSdHBpEbF04D+pLm0U4BAehs4E7ieiAnpKepPKtiwVyt1BTez2pEYDOxEughYmBnrHL8gTdOVxGXABRG8kp6j/hExWdK1wEORnbPMrPFla6j+DXwKPCtp74i4s/N+EguTimHtTzpv9Cdd404hnT8+kzgbbrgOuIlUmKa+EimpH/Bt0vlvBVKxrP6k67RJQBvSDcA5FCiWIenLwPoRcZGkZSLCM3FqxCNTrUban1R8oS/pj7SYccAnwAjBuqT+Tev4DoeZVUPWePt+0p3Y2brZdTLp4ugw0J2k9VHfz6YGmVmTkjQCOB7YPCImzdjOtsC1pCRqYDeHGA/j2uDbD8A9m9XV9Yw0H3AvsATdn/+mkhLEs4ETSMlmG3AEqWjaMRFxaZWjtU6cTLUS6SjgBGBwKbsHfDEBJn8FPn4VNomIF6oboJm1IomlgCdIU/pKXMv7xUQ4fiL85FTgnLq6MDKzqsmq8N0M/AJiDuBySryuSYM8Gg8aEUHBJQ01J81LmpY3H2kkvhTjgcuJOFDSEaQlG3tFxBvVCdK642SqVUhbAjcCg3rztC8gAt5pg2XocCfIzKwSJAYCLwML0euiSFMnQ9u3IrirCqGZWZ1KBSS+fiU8OA8MKGfJyqfA8hF8WOnYeiWtCXsSWInuZwt1MQUmPwY/XQdOBaZExLRqhGg9czW/1nEmhRKpOeeEm2+GcePgjTdg551nergvqC1NuxlZiyDNrOXsQDrHzPR9NHbszD9Tp8LPf975qW39gTNqE6aZ1Yu0dvvBp6Ff386PlXbuYCBp+ULeNiA1Ku6aSC2+ONx5J3zyCbz3HlxwAfSd8ev2g/5rwH4BU51I5cvJVCtIzXWXLPjYRRfB5Mkw//yw665w8cWw4oqd95qNtCDSzKzSjqbAGoGhQ2f8LLAATJgAN95Y8PnLSnyl2kGaWf2QWAAGbAB91PmxEs8dg4CDJbokYzV2JKnqYFe/+AV8+CEsuCAMHw7rrw+jR8+0S1tKwjatepTWLSdTreEQYECXrYMHw8iRcNxxMH48PPII3H47jBpV6BjLIPmCxcwqRmJV0oLrbo0cma4pHnqo4MP9gUMrG5mZ1bkflLJTCeeOLSsZVK9ICwEjgC4JIQBLLgk33ACTJsEHH8Bdd8FKK3XeayhwVFXjtB45mWoNa0KBuy/LLZfGv19+eca2f/6z0B8rpFWbq1YpPjNrTauRyv92a4894Kqrij7cRjrHmVnrWJfuK/cBPZ47ZiPf65qVSSXPCzvvPNhpJxg0CBZaCDbfPCVUXa1SpfisRE6mWsPQgltnmw3GjJl52+efp7HxrtpI6xrMzCplGD1Ur1pssTS75coruz1O4XOcmTWrOXvaoYRzh4B5KhlULw2j2KgUwIMPppvbY8bAO+/AE0/ArbcW2rPESoZWLU6mWkPhOx/jxsHss8+8bfbZ04rNrqYB7ZUOzMxa2gRSz6iiRo2Chx9O9XG6MbGCMZlZ/evxeqS0c8etwwEkvSspsp8ns22XdNgWkhaStHWnbXtn+3bcdke27Y6O27Nte0///1vDb6cUmjWUdkyjUDffDEOGwNxzp4JhZ55ZaO/JPf1bWHU5mWoNbxXc+tJL0NYGyywzY9sqq8BzzxXaeyrwn2oEZ2Yt621SA8qidt+9x1EpKHaOM7Nm9SrpJm9RJZw72mHb3wBExEIRoeznq9m2vTtsU0S8GxF3dNp2SbZvx21bZ9u27rg923bJ9P9/B6xadFh+rrlSNb8LL0xFwj75BC6/HLbYotDeH3T7W1rVOZlqDRcCXYeb2tvTXY+TT07FKNZaC771Lbj66kLHmAbcU+U4zay1/Lm7B9dcExZeuGgVv+nGks5xZtY6fkUa2S6oxHNHH+CGCsfVG/+EIn2uPv4YXnsN9tsvlUMfNiwtAHvmmc57tgMXVTlO64GTqdZwC8Xu4IwenRY3fvghXHdd+sN9/vnOe00CLiKi2zvIZma9EcFk4GKKTEXeY48ZbfC68QVwe+WjM7M69hjwbrEHSzh3TANuj+DjKsRWmogg9QAdX/Dx7baDzTaD//4XXnkFpkyBQ7sULu0DXFHVOK1HSu+lNT3pVOAwCjXu7dkEYFki3qlsUGbW6iQWA/5N+eemsyI4obJRmVm9k9iTNCpduE9T99qBERE8XtGgekuaDXiPAr32SjAJuIGI3SsblPWWR6Zax8nAM3RXhrOwdmAvJ1JmVg0RvAXsQ+8L3EwCngZOq3hQZtYIrgT+SDfT/YoYD5yWeyIFEDEO2Jbe/w5TSWtFD6h0SNZ7TqZaRcRkUpfspyn9j3YCcDAR11ctLjNreRFcTRo5L/Xc1A48CWyeTRU0sxYTQQC7AndRbKpcV+3AecDpVQqr9yLuBXYmxVbKdLGJwCvAekSM6Wlnqz4nU60k4nNgfeAM4FMKFaVIlbUmAH8DNifi17UL0MxaVQS/ArYAHiWdgwqt0RwLfEy6EBoRgS8kzFpYdjNle+Bo0hqqsXRNSL4gJSrPAbtGcGyWiNWPiNtIjYjvJSVLhWYRjc1+LgK+RsT7tQvQuuM1U61KagO2BkYDi5I6iX8OPAT8nIiXcozOzFqYxJeAg4G1SY0tJ5KmtFwE3BnB1BzDM7M6JCHgm8BBwLKkZrZjgaeA8yN4KsfwSictCuxPmk00B+nG0nvAJcBNRPR2uYZVmZMpMzMzMzOzMnian5mZmZmZWRmcTJmZmZmZmZXByZSZmZmZmVkZnEyZmZmZmZmVwcmUmZmZmZlZGZxMmZmZmZmZlcHJlJmZmZmZWRmcTJmZmZmZmZXByZSZmZmZmVkZnEyZmZmZmZmVwcmUmZmZmZlZGZxMmZmZmZmZlcHJlJmZmZmZWRmcTJmZmZmZmZXByZSZmZmZmVkZnEyZmZmZmZmVwcmUmZmZmZlZGZxMmZmZmZmZlcHJlJmZmZmZWRmcTJmZmZmZmZXByZSZmZmZmVkZnEyZmZmZmZmVwcmUmZmZmZlZGZxMmZmZmZmZlcHJlJmZmZmZWRmcTJmZmZmZmZXByZSZmZmZmVkZnEyZmZmZmZmVwcmUmZmZmZlZGZxMmZmZmZmZlcHJlJmZmZmZWRmcTJmZmZmZmZXByZSZmZmZmVkZnEyZmZmZmZmVwcmUmZmZmZlZGf4fpfjM8bFtWsUAAAAASUVORK5CYII=\n",
      "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": 19,
   "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 的最大割: {'1010101100': 419, '0101010011': 382, '0101011011': 368, '1010100100': 351, '0110101011': 303, '0101001011': 251, '1001010100': 247, '1010101010': 229, '0100101011': 227, '1011010100': 218}\n",
      "量子近似优化分治算法找到的图形 G 的（最有可能的）最大割: 1010101100\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": 20,
   "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 的最大割：{'01001': 531, '00001': 504, '11110': 501, '10110': 494, '00101': 489, '11010': 481}\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": 21,
   "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": 26,
   "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, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 8), (1, 2), (1, 4), (1, 5), (1, 6), (1, 8), (1, 9), (2, 3), (2, 8), (3, 9), (4, 5), (4, 6), (5, 7), (5, 8), (6, 8), (7, 8)]\n",
      "半正定规划找的最大割的上限: 16.366014900074795\n",
      "量子近似优化分治算法找到的最大割分类: 0010100011, 最大割 = 14.0\n",
      "\n",
      "随机图形 2\n",
      "边 = [(0, 2), (0, 3), (0, 4), (0, 5), (0, 8), (1, 4), (1, 8), (1, 9), (2, 5), (2, 6), (2, 8), (3, 4), (3, 5), (3, 6), (3, 9), (4, 6), (4, 7), (4, 8), (5, 7), (6, 8), (7, 9), (8, 9)]\n",
      "半正定规划找的最大割的上限: 17.401823913484183\n",
      "量子近似优化分治算法找到的最大割分类: 1100111001, 最大割 = 16.0\n",
      "\n",
      "随机图形 3\n",
      "边 = [(0, 1), (0, 2), (0, 3), (0, 5), (0, 7), (0, 8), (1, 3), (1, 5), (1, 6), (1, 8), (2, 3), (2, 4), (2, 6), (2, 7), (2, 8), (3, 4), (3, 5), (3, 7), (3, 8), (5, 6), (5, 7), (6, 7), (7, 8), (8, 9)]\n",
      "半正定规划找的最大割的上限: 17.481389612347442\n",
      "量子近似优化分治算法找到的最大割分类: 0111000101, 最大割 = 17.0\n",
      "\n",
      "随机图形 4\n",
      "边 = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (1, 4), (1, 5), (1, 7), (2, 3), (2, 4), (2, 6), (2, 7), (2, 8), (2, 9), (3, 6), (3, 8), (3, 9), (4, 5), (5, 6), (5, 7), (5, 9), (6, 9), (8, 9)]\n",
      "半正定规划找的最大割的上限: 19.247444317293844\n",
      "量子近似优化分治算法找到的最大割分类: 1110010000, 最大割 = 18.0\n",
      "\n",
      "随机图形 5\n",
      "边 = [(0, 3), (0, 5), (0, 6), (0, 7), (1, 3), (1, 5), (1, 7), (1, 8), (2, 7), (2, 9), (3, 4), (3, 6), (3, 7), (3, 8), (3, 9), (4, 6), (4, 7), (4, 8), (4, 9), (5, 7), (5, 8), (5, 9), (6, 7), (6, 9), (8, 9)]\n",
      "半正定规划找的最大割的上限: 18.715743968566105\n",
      "量子近似优化分治算法找到的最大割分类: 1111110000, 最大割 = 17.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": 27,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-11T07:16:56.935061Z",
     "start_time": "2021-05-11T07:16:56.704158Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAEWCAYAAABhffzLAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAABEbUlEQVR4nO3dd3hUZfbA8e8hJITeQm8hJIDUAKFY6OpacLGCiFIFK+rPdXddt7i67uq6ugp2mohSrIsr6loCIiC9d5LQayCQAIGElPP7405gCClDyGQymfN5nnmYW+beMzfMue9973vfV1QVY4wxgaOcrwMwxhhTsizxG2NMgLHEb4wxAcYSvzHGBBhL/MYYE2As8RtjTICxxG+MF4hIKxFZKyInReQxX8djjDtL/OaSicguETkrImG55q8RERWRcC/tt5uIfCMiySJyTESWi8hIDz87TUReKGQdFZFUETklIvtF5N8iElTEcH8HzFfVqqo6oYjbMMYrLPGbotoJDMmZEJH2QCVv7UxErgTmAQuASKA28BBwYzHvqqOqVgH6A/cAYy4xzvKut82ATUUJwG0bxniFJX5TVB8Cw9ymhwPT3VcQkZtdVwEnRGSviPzVbdlgEdkpItVc0zeKyCERqZPP/v4FfKCq/1TVo+pYpaqDXJ8fISKLcu1fRSRSRMYCQ4HfuUrzXxX25VR1K7AQaOfa1gBX1U2yiPwiIh3c9rNLRH4vIuuBVBGZB/QF3nTtr6WIVBeR6SJyRER2i8ifRKScW+yLReQ1EUkC/uq6QnlbRL51bWOxiNQXkddF5LiIbBWRTm4xPC0iCa6qpc0icpvbshEiskhEXnF9dqeI3Oi2vJaIvC8iB1zL57gtG+j63idc27/BNb+6iEwRkYOuq6MXLuPqyJQ0VbWXvS7pBewCrgW2AVcAQcA+nFKuAuGu9foA7XEKGB2Aw8CtbtuZAUzDKb0fAAbks79KQBbQt4CYRgCLcs1TINL1fhrwQiHfy339NsAhYDTQCUgEuru+63DXMajgdjzWAk2Aiq55PwH3u217OvAlUBUIB7YDo91izwTGAeWBiq54jwJdgFCcq52dOCfbIOAFnKqknO3fBTR0HevBQCrQwG37GThXL0E4V0oHAHEt/xr4GKgJBAO9XfO7ASnAda7tNgJau5b9B3gPqAzUBZYDD/j6/6a9PPwN+zoAe/nfi/OJ/0/Ai8ANwA+upHUu8efxudeB19ymawB7gA3AewXsr5Fru60LWKe4Ev8J4DiQ4Equ5YB3gL/lWnebW4LcBYzKtfxc4ncl27NAG7flDwA/ucW+J9fnpwGT3KbHAVvcptsDyQV8l7XAQLftx7stq+T6rvWBBkA2UDOPbbzn/vdym18PSMd1knPNG4LbichepftldYnmcnwI/Aw0J1c1D4CIdAdewqkuCQEqAJ/mLFfVZBH5FHgSuMPtc88Az7gmP3Itz8ZJUlu98UXcdFbVePcZItIMGC4i49xmh+CUsHPsLWCbYTgl6d1u83bjnNAK+vxht/dn8piu4hbjMJzjFO6aVcW13xyHct6o6mkRyVmnFnBMVY/nsf8mwDd5zG/m+j4HXdsB5wRZ0DEwpYjV8ZsiU9XdONUPNwFf5LHKTOC/QBNVrQ68C5zLFCISDYwCZgHnWr6o6j9UtYrr9aCqngaW4HZyyEMqbjeXRaR+7nAv4avlthf4u6rWcHtVUtVZHm7/KE5VSzO3eU2B/cURn+vENAl4FKitqjWAjbgd6wLsBWqJSI18lrXIZ346EOZ2PKqpatuixG9KniV+c7lGA/1UNTWPZVVxSpNpItINp5UMACISilOafwYYCTQSkYcL2M/vgBEi8lsRqe3aRkcRme1avg5oKyLRrm3/NdfnDwMRl/71ACepPigi3cVR2XXjuqonH1bVLOAT4O8iUtWVqJ/E+f7FoTLOieMIgKuJazsPYzsIfAu8LSI1RSRYRHq5Fk8BRopIfxEpJyKNRKS16zPfA6+KSDXXshYi0ruYvo/xMkv85rKoaoKqrsxn8cPA8yJyEvgLTvLL8SKwV1XfUdV04F7gBRGJymc/vwD9XK8dInIMmIirKkJVtwPPAz8CccCiXJuYArRxtcqZc4nfcSXOjdE3cer/43HqzS/FOJyrkh2u2GYCUy9xG/nFtxl4Feeq6DBO/f/iS9jEfThXJFtxbmI/4drucpyT8ms4N3kXcP6qZRhOdddmnGPyGU5VnPEDOXf1jTHGBAgr8RtjTICxxG+MMQHGEr8xxgQYS/zGGBNg/OIBrrCwMA0PD/d1GMYY41dWrVp1VFUv6v/KLxJ/eHg4K1fm12LQGGNMXkRkd17zrarHGGMCjCV+Y4wJMJb4jTEmwPhFHX9eMjIy2LdvH2lpab4OxXhRaGgojRs3Jjg42NehGFNm+G3i37dvH1WrViU8PBy3rmFNGaKqJCUlsW/fPpo3b+7rcIwpM/y2qictLY3atWtb0i/DRITatWvbVZ0xxcxvEz9gST8A2N/YmOLn14nfGONHTh+D5ZNg58+QYVdxvmSJ/zIEBQURHR1N27Zt6dixI6+++irZ2dnnli9fvpxevXrRqlUrOnXqxP3338/p06fz3NacOXPo0KEDrVu3pl27dnz22WcXLM/MzKROnTo8/fTTF8xPSUlh2LBhREZG0qJFC4YNG0ZKSsoF6zzxxBM0atTogtiMKXFBwbDkLfjgFvhnM5g+EBb+G45s93VkAccS/2WoWLEia9euZdOmTfzwww98++23PPfccwAcPnyYu+66i3/+859s27aNNWvWcMMNN3Dy5MmLtrNu3TqeeuopvvzyS7Zu3cpXX33F73//e1atWnVunR9++IGWLVvy6aef4j6GwujRo4mIiCA+Pp6EhASaN2/O/ffff255dnY2//nPf2jSpAkLFizw4tEwJh8H1kD6KahQFR5YAEM+hi4j4VQixD4Hcd856+VcERyNBxsnxLt8Pdq7J68uXbpobps3b75oXkmrXLnyBdMJCQlaq1Ytzc7O1j//+c/65z//2aPt3HvvvTplypQL5k2ePFmHDBlybvq+++7Tjz/+WPv06aOLFy9WVdW4uDgNDw/XzMzMc+tlZmZqeHi4xsfHq6pqbGys3njjjTpt2jQdM2ZMkb6nr5WGv7Upok1zVP9WV3Xuk3kvP3FINTXJeb9lruqz1ZzXq1eofvGg6tpZqmeSSy7eMgZYqXnkVL9tzunuua82sfnAiWLdZpuG1Xj2lksbOzoiIoKsrCwSExPZuHEjw4cP9+hzmzZt4qmnnrpgXkxMDG+88QbgtGD68ccfee+990hOTmbWrFlcddVVbN68mejoaIKCgs59Lqf6adOmTbRo0YJZs2YxZMgQBg4cyDPPPENGRoa1iTclY8nb8N0z0Lgr9Hkm73Wq1jv/vtVNMG417FwAO36C7d/CupnOvNDqsG8lnDoM4dc406bIrKrHD8ydO5e+fftSsWJF7rjjDubMmUNWVlahnzt79izffPMNt956K9WqVaN79+589913JRCxCWjZWfDt0/DdH+CKATD8v1C5duGfE4HaLSBmFAyaDr/dAQ8shFoRzvIVU2D2PfDPcJjUH2Kfhx0LrFqoCMpEif9SS+besmPHDoKCgqhbty5t27Zl1apVDBw48KL1fvWrX3H48GFiYmKYPHkybdq0YdWqVXTs2PHcOqtWrSImJgaAWbNmsWjRInK6pk5KSmLevHm0adOGtWvXkp2dTblyzjk8OzubtWvX0qZNG7777juSk5Np3749AKdPn6ZixYoMGDDAy0fCBLRTibDxM+jxCFz/NygXVPhn8lKuHDTocH76lteh01An2e/4CRa9Dlu+gkdXOMs3/xeqN4YGHYu+z0CRV/1PcbyAqUAisNFtXkdgCbAB+Aqo5sm2/KGOPzExUa+77jr9y1/+oqqqhw4d0qZNm+rSpUvPrfP555/roUOHLtrOmjVrNDIyUnfu3Kmqqjt37tT27dvr1q1bNSUlRevUqaNpaWnn1p86daqOHDlSVVVvu+02fe65584te+655/T2229XVdUhQ4bozJkzzy07deqU1qlTR1NTU4vh25ec0vC3Nh44fVw1K8t5f/Kw9/d3JkX10CbnfVaW6otNnfsDLzZVnT1UddlE1aQd3o+jFCOfOn5vJv5eQOdciX8F0Nv1fhTwN0+2VVoTf7ly5bRjx47apk0b7dChg/7rX//SrJz/+Kr6yy+/6DXXXKMtW7bU1q1b69ixY/NNup9//rm2a9dOo6KiNDg4WBctWqSqqtOmTdPBgwdfsG5SUpKGhYVpWlqaHjt2TIcOHaoREREaERGhQ4cO1ePHj2tqaqrWrFlTU1JSLvjsbbfdprNnzy7mI+FdpeFvbQpxNF719Y6qsS/4LoYTh1TXfaL6n4dV/93WOQl87xTENCNNde1s1RMHfRefD+SX+EW9WD8mIuHAXFVt55pOAWqoqopIE+A7VW1T2HZiYmI090AsW7Zs4YorrvBC1L739NNPs2zZMr777jtCQkJ8HY7PleW/dZmwZxnMutupox/yMTTp6uuInHr/YzugfAWn+mfnQvjAVcVZpzVE9IHmvaF5L6hQxaehepOIrFLVmNzzS7qOfxMwEJgD3AU0KeH9+4WXXnrJ1yEY45nNX8LnY6B6Ixj6mXNztjTIuVGco9nVMHbB+RZDqz6AZe/CqO+haXfnIbJTh6BJd+dkUcaVdOIfBUwQkT8D/wXO5reiiIwFxgI0bdq0ZKIzxnjuxEEn6TfoCENme9Zyx1fKlYOG0c7r6schMx32LodGnZ3lq96HpW9D+YrQtIdzRRDRGxpEOyeRMqZEE7+qbgWuBxCRlsDNBaw7EZgITlVPiQRojCmcqpMMqzWAez+HxjEQXNHXUV2a8hWgec/z033+4FT75LQY+vFZqFQbnop3vuuuRVClvnMVUQZOBCWa+EWkrqomikg54E/AuyW5f2PMZTp7Gr4YA21vg/Z3Xpg8/VloNWh1o/MCOHnYuUfgaibNl4/A8V1QrbFzJZBzj8D9ATQ/4rUHuERkFk7TzVYisk9ERgNDRGQ7sBU4ALzvrf0bY4rZqSPODdKtX8OZ476Oxruq1oNmV56fvvcLGPAaNO4C275xTn6xzzvLVGH7d5CWkve2SiGvlfhVdUg+i8Z7a5/GGC85Gg8z7oCTh2DwR84TuYGkdovzTxVnZ8Oh9VA+1Fl2ZCvMHAQS5NwzaO66ImjSrdTeKLYuGy7D3//+d9q2bUuHDh2Ijo5m2bJlAPTp04dWrVqd62b50UcfJTk5+dzncvrTadeuHXfddVe+XTX7Up8+fcjdhNabdu3aRbt27Upsf+YSnEqEKddB+kkYPjfwkn5uOTeK67Z2pmu1gBFfQ88nAYFFrzlXRnE/OMtPHHB6KM0uvJuVkmKJv4iWLFnC3LlzWb16NevXr+fHH3+kSZPzrVNnzJjB+vXrWb9+PRUqVLig64ac7pw3btxISEgI777r+1sdnvT9YwJUlbpOUrv/x9LRRr+0KR/idBzX709w/w/w+11OK6fmvZzl62bBxD7wcgR8fB+smAxJCT7tY8gSfxEdPHiQsLAwKlRwLuXCwsJo2LDhReuFhITw8ssvs2fPHtatW3fR8p49exIfH3/R/CpVzj9U8tlnnzFixAgARowYwYMPPkhMTAwtW7Zk7ty5AEybNo2BAwfSp08foqKizo0LAPDRRx/RrVs3oqOjeeCBB84l+SpVqvCb3/yGjh07smTJkoti+PDDD89dmSxfvhyAY8eOceutt9KhQwd69OjB+vXrAfjrX//KK6+8cu6z7dq1Y9euXezatYsrrriCMWPG0LZtW66//nrOnDkDcK5/oo4dO/LWW28VcLRNiVOFpe84JVWAq8ad7yzNFCznRnFoNWe6031w+yRoPQD2r4avfwNv94BM1yhkhzY4VWglqEx00gbA+3m0DG17K3Qb47REmHHXxcuj73E6fUpNgk+GXbhs5NcF7u7666/n+eefp2XLllx77bUMHjyY3r1757luUFAQHTt2ZOvWrRd0xJaZmcm3337LDTfcUNi3u8CuXbtYvnw5CQkJ9O3b99yJY/ny5WzcuJFKlSrRtWtXbr75ZipXrszHH3/M4sWLCQ4O5uGHH2bGjBkMGzaM1NRUunfvzquvvprnfk6fPs3atWv5+eefGTVqFBs3buTZZ5+lU6dOzJkzh3nz5jFs2DDWrl1bYLxxcXHMmjWLSZMmMWjQID7//HPuvfdeRo4cyZtvvkmvXr347W9/e0nHwHhRdhb872lYPhG63g8NO/k6Iv9WpS50GOS8cp4oPrL1fBPYuf8H+1Zc+ERx+NVe7Xq67CT+ElalShVWrVrFwoULmT9/PoMHD+all146VzLPzb1rjDNnzhAdHQ04Jf7Ro0df0r4HDRpEuXLliIqKIiIigq1btwJw3XXXUbu28xDN7bffzqJFiyhfvjyrVq2ia9eu5/Zdt25dwDkh3XHHHfnuZ8gQ5/58r169OHHiBMnJySxatIjPP/8cgH79+pGUlMSJEwWPhdC8efNz37dLly7s2rWL5ORkkpOT6dXLuRy+7777+Pbbby/pOBgvOHsaPr8ftn3tlPKvfd7XEZUtOU8Uuz9VfNMrzrMDOxecf6K45Y1wz2yvhVF2En9BJfSQSgUvr1y70BJ+XoKCgujTpw99+vShffv2fPDBB3km/qysLDZs2HCuv5mcOv6CiNtDImlpafkuc5/Oa76qMnz4cF588cWL9hEaGnrBIC4FxZDXtLvy5ctfMKave8w51WHgHLOcqh5Typw5Dh/d4VTv3Pgv6D7W1xEFhpwniq954vwTxUHe7aPL6viLaNu2bcTFxZ2bXrt2Lc2aNbtovYyMDP7whz/QpEkTOnTocNHy/NSrV48tW7acGzPX3aeffkp2djYJCQns2LGDVq1aAc64vMeOHePMmTPMmTOHq6++mv79+/PZZ5+RmJgIOHX0u3fv9iiGjz/+GIBFixZRvXp1qlevTs+ePZkxYwYAP/30E2FhYVSrVo3w8HBWr14NwOrVq9m5c2eB265RowY1atRg0aJFAOe2aXwopCpUa+Q017Sk7xs5TxQ37e7d3Xh162XYqVOnGDduHMnJyZQvX57IyEgmTpx4bvnQoUOpUKEC6enpXHvttXz55ZeXtP2XXnqJAQMGUKdOHWJiYjh16tS5ZU2bNqVbt26cOHGCd999l9BQpz1xt27duOOOO9i3bx/33nvvuYFcXnjhBa6//nqys7MJDg7mrbfeyvMklVtoaCidOnUiIyODqVOnAs5N3FGjRtGhQwcqVarEBx98AMAdd9zB9OnTadu2Ld27d6dly5aFbv/9999n1KhRiAjXX3/9JR0fU4z2Loea4U5d9OAPfR2NKQFe7Za5uARat8wFGTFiBAMGDODOO++8YP60adNYuXIlb775po8i855A/VuXiE3/gS8ecNrm3znV19GYYpZft8xW1WNMIFKFxRPg0xFOq52bXin0I6bssKoePzNt2rQ8548YMSLfFkXGXCA7C779PayYBG1uhdveg+BQX0dlSpBfl/j9oZrKXB77G3tB+knYMd9prnnn+5b0A5DflvhDQ0NJSkqidu3aBTYzNP5LVUlKSjp389pcptSjUKEqVKwBY+aff7LUBBy/TfyNGzdm3759HDlyxNehGC8KDQ2lcePGvg7D/x2Nc9roN+8FA9+0pB/g/DbxBwcH07x5c1+HYUzpt/sXmDUEgoIhZqSvozGlgF/X8RtjCrHxc5g+ECrXcXrXbNTF1xGZUqDQxC8iF/Vultc8Y0wpc+a40wFYoxgY/b3zkJYxeFbi/4OH84wxpUF2ltNOv2JNZ4CQ+/4DlWr5OipTiuRbxy8iNwI3AY1EZILbompAprcDM8YUwdlU+GwUNLsKrn4c6rf3dUSmFCqoxH8AWAmkAavcXv8FfuX90Iwxl+TkYZh2M8R9D8GVfB2NKcXyLfGr6jpgnYjMUFUr4RtTmh3ZBjPudNrq3z3TGQHKmHx40pwzTkQuenxSVW0cNmNKg7QUeP9GkHJOnX6jzr6OyJRyniR+957dQoG7ALtTZExpEVodbngJmnSzljvGI4W26lHVJLfXflV9HchjgFtjTIlRhUWvw/bvnekOgyzpG48VWuIXEffrxnI4VwB++8SvMX4vKxO+/S2snAqdh0FLG8TGXBpPEvirbu8zgV3AIK9EY4wpWPopp7lm3Hdw9RPQ/1lfR2T8UKGJX1X7lkQgxphCpJ+EaQPg0Hq4+d/QdbSvIzJ+qqAHuJ4EUlR1Sq75o4Gqrrp+Y0xJCakCTbpDnz9Aqxt8HY3xYwWV+IcCPfKY/yHOg12veyMgY0wuuxZBlXoQFgU3vezraEwZUFCrnvKqmpF7pqqeBQod+UREpopIoohsdJsXLSJLRWStiKwUkW5FC9uYALH+U/jwNvjuGV9HYsqQghJ/ORGpl3tmXvPyMQ3IfT36MvCcqkYDf3FNG2NyU4WF/4Yv7ofG3eD2ib6OyJQhBSX+fwFfi0hvEanqevUB5gKvFLZhVf0ZOJZ7Nk4nbwDVcfoDMsa4y8p0ulOOfQ7a3Qn3feH0tOnnEo6cYtrinRxMOePrUAJeQX31TBeRI8DzQDucpL0J+IuqflvE/T0BfCcir+CcdK7Kb0URGQuMBWjatGkRd2eMH8rOhMQtcM2T0O/PUM6/x0uKTzzJG/Pi+WrdAbIV/vHNVgZ1bcxDfSJpVKOir8MLSKJ6UTc8xbdxkXBgrqq2c01PABao6uciMggYq6rXFradmJgYXblypdfiNKZUOHkYyldwBkPPTHfe+7Hth08yITaOrzccpGJwEPdd2YxbOjRk5vI9fLpyLwB3xTTh4T4taFzTehP1BhFZpaoxF80v4cSfAtRQVRURwWkuWuioz5b4TZmXuNXpXbNeO7hntq+juSxbD53gjdh4vtl4kErBQQy7KpwxPSOoVTnk3Dr7k8/wzk/xfLJiH9mq3NmlMY/0jaRJLTsBFKf8En9Jd71wAOgN/AT0A+JKeP/GlD47F8LsoRAcCn1+7+toimzzgRNMiI3jf5sOUaVCeR7pE8noa5pT0y3h52hUoyIv3NqeR/pG8u5PCcxasZfPVu3j9s6NeKRvJM1qV/bBNwgcXivxi8gsoA8QBhwGngW2AeNxTjhpwMOquqqwbVmJ35RZ6z+FOQ9BrQi49zOo4X/3szbuT2FCbBzfbz5M1QrlGXl1OKOuaU6NShcn/PwcSknj3QUJzFq+h8xs5dboRjzaL5LmYXYCuBxFruoRkQ+BR1U1xTXdDJiqqv29EmkeLPGbMunsaXjL1ZXy4A/9ruXOhn0pjI/dzo9bEqkWWp5R1zRn5NXNqV4xuMjbTDyRxns/72DGst2czczm1uhGPNIvkhZ1qhRj5IHjchL/A8D/AU8CjYDfAr9R1a+8EWheLPGbMiUrE0SgXBAc2wnVGvrVjdy1e5OZEBvHvK2JVK8YzP3XNGf41eFUCy16ws/tyMl0Jv6cwEdL95CemcUtHRsyrl8kkXWrFts+AsFl3dwVkWuA+cBRoJOqHir+EPNnid+UGekn4dORTin/5kIfhylVVu85zvgf41iw/Qg1KgUzpmcEw65sRtViTPi5HT2VzqSFO/hwyW7OZGQxoENDHusXSVQ9OwF44nJK/PcBf8apo++AM9D6SNeYvCXCEr8pE04chJmD4PAmGPBv6DLC1xF5ZOWuY4yPjWNh3FFqVQ5hTM8I7ruyGVUqlFzbkGOpZ5m0cAfTf9nF6YwsbmrXgHH9I2ldv9BGgQHtchL/HJz29omu6W7ARFe3CyXCEr/xe4lb4KM7IS0Z7poGUdf5OqJCLd95jPGx21kcn0TtyiGM7RXBvT2aUbkEE35ux1PPMmXRTqb9sotT6Znc2K4+4/pF0aahnQDyUqzt+EUkxNVZW4mwxG/8WsYZGB/tvB/6CTTo6NNwCrMkIYnxsdtZuuMYYVUq8GDvCO7p3pRKIaVn4L3k02eZumgn7y/excn0TK5vU4/H+kfRrlF1X4dWqlxOiT8UGA20xRlsHQBVHVXcQebHEr/xe/GxENYSajTxdSR5UlWWJCTxemwcy3ceo07VCjzYuwX3dGtKxZAgX4eXr5QzGby/eCdTF+3kRFom115Rl8f7t6R9YzsBwOUl/k+BrcA9OP32DAW2qOrj3gg0L5b4jd9RhYWvQOW60GW4r6PJl6qyKP4oE2LjWLHrOPWqVeCh3i24u1tTQoNLb8LP7URaBtMW72LKop2knMmgX+u6PNY/iugmNXwdmk9dTuJfo6qdRGS9qnYQkWBgoarmNUiLV1jiN34lKwO+fhJWT4fooTDwLaf5Zimiqvwcd5TxP25n9Z5kGlQP5aE+LRgU08SvEn5uJ9MymL5kN5MW7iD5dAa9W9bh8Wuj6NzUv56RKC6X02VDzmAsySLSDjgE1C3O4IwpM9JPwifDISEWej4F/f5UqpK+qvLTtiOMj41j7d5kGlYP5YVb23FXTGMqlPffhJ+jamgwj/SNZPhV4UxfsotJP+/g9rd/oWdUGE9cG0WXZrV8HWKp4EmJ/37gc5ymnO8DVXC6Zn7X++E5rMRv/EJmOky+1tVc87VSVcWjqszbmsiE2DjW7UuhUY2KPNI3kju7NCakvH93+1yQ1PRMPlq6m4k/7yAp9SxXR9bm8f4t6dY8ME4APumds7hY4jd+Y9HrTg+bUYX2Nl4iVJUfNh9mwrw4Nu4/QZNaFXm0byS3dSrbCT+302czmbF0D+/9nMDRU2e5MqI2j18bRY+I2r4OzasuOfGLyJMFbVBV/11MsRXKEr8p1XYsgKAQaHalryM5Jztb+X7zYSbExrH54Ama1a7EI30jua1TI4KDAifh53bmbBYzl+/h3QUJHDmZTrfmtXiifxRXtqiNlKIqueJSlMSfDawFvgXSyTXAuqo+V/xh5s0Svym11s2GLx+FJt1gxNc+r8/Pzlb+t+kQE2Lj2HroJM3DKvNo30gGRjekfAAn/NzSMrKY5ToBHD6RTtfwmjzevyVXR5atE0BREn9HYAjOgOmrgFlArPqgbsgSvymS7GzIPOM8QJVxGkKrO6+0FNi3wjXftSzjDEReC2FRcGQ7LHvH6T0zZ1nGGbjuOWgcA9u/hy8fduadPQXhPWHwR87IWT6Sla18s+Egb8yLY/vhU0TUqcy4fpHc0sESfkHSMrL4ZOVe3vkpgYMpaXRpVpPH+kfRKyqsTJwALrlVj6svnnXA0yJyFc5J4A0R+b2q/td7oZqAkJXhllRd/4ZWh+qNnWVb51647OxpaNodIvrAmePw9VMXLs84DT0eguh74Gg8vHuNk/TdDXgdYkbCsR3w0R0Xx3T7JCfxnzkGW+ZCcEUIrnT+X8121qvWAFoPgJDKTs+aXcdAec/7ni9OWdnK3PUHeGNePPGJp2hRpzLj745mQIeGBJXz/8TlbaHBQQy7MpzBXZvw6cp9vD0/nuFTlxPdpAaPXxtFn5Z1ysQJIDdPWvXUAQYBd+E07fyzqi4tgdjOsRK/D5w5DmdTL0yuwRXPdzew4TNIPXph4q3TCjoPc5Z/OsK13K1U3fpm+NXfnYebnq91PpHm6PYA3PSy0zrmhTxaDPf8DfT/ixPbpH5uSdmVmKOHQptfw+ljsPh1KF/xwuTdtIeT2M+mOi1vcif2kCoQVHq6JShIZlY2c9c7JfyEI6m0rFeFcf2iuKl9A0v4l+FsZjafrdrHW/Pj2Z98ho6Nq/NY/yj6ta7rlyeAolT1jMJJ+KHAZ8AnOR21lTRL/CXg0Aan+iPG1RPHO1fD4Y0XrtO8Fwx3DcMwPhqO7zy/LLiSk9jvmOxMT78VMtMuTKzhV5/vkXLRa1Au+MLkWzsS6rdzTgyJWyCk0vll5Sv6TVL2psysbL5ce4A358ez82gqretX5bH+UdzQtj7lLOEXm7OZ2fxnzT7enB/P3mNnaN/IOQFce4V/nQCKenN3I7DbNeuCFVX118UdZH4s8XtR4lb46UXYPAcq1YbH10OFKrDxC+dhpOBKrgRcESrXgfrtnc+dPAxBrsRdPtTnNzXLuoysbOas2c9b8+PZlXSaKxpU4/H+kVzfxhK+N2VkZfMf13HfnXSaNg2q8Vj/KK5vU88vjntREn/vgjaoqguKKbZCWeL3gpR9EPs8rP/Eqavu/iBc9ajfDf9X1mVkZfPF6n28NT+BPcdO07ZhNR7vH8V1ber5VcnT3/nrlZY9wGUc2dlQrhwc3w3v9nSeLr36Cahcth9k8TdnM7P5fLVT17zv+Bk6NK7OY/2i6O9nVQ1lTWZWNl+5bqbvOJJKq3pVGdc/kpvaNSiVJwBL/IHuxAH4+RU4eRCGzHLmnU11Svum1EjPzOLTlft456cE5+Zikxo80T+KPq3KZusSf5XTmmpCrHNzPapuFR7tF1nqWlNZ4g9UpxKdG6krpjitaDrfBze+7NTPm1IjLSOLT1fu5W1Xe/JOTWvweP8oepfR5oRlRe7nJ1rUqcy4flHc0rF0nAAs8QeihPkw+x6neWT0EOj1O6jZzNdRGTdpGVnMXr6Hdxfs4NCJNGKa1eTxa6O4JrJsPEAUKLKzlW83Ok9Mbzt8koiwyjzaL5Jfd/TtA3RFubn7Fbla8rizVj2l1Jlkp1qnXhvnCdXv/+TU4ddu4evIjJu0jCxmLNvDewsSSDyZTrfwWjx+bRRXldE+YwKF00fSIcbHxrPl4AnC3fpI8sUJwFr1lHXpJ2Hpu/DLG1C9ETz0izWxLIVOn81k5jKnhH/0VDo9ImrxeP+WXNnCbq6XJdnZyg9bnE7yNh04QdNalZxeUTuXbCd5VtVTVp09DSsmOd0BnzkGrW6CPn+ABh18HZlxc/psJh+6RoY6euosV7WozeP9o+hexrsFDnSqSuyWRMbHxrFhfwqNazrjINzRuWS6xb6coRejgBeBNlw42HpEcQeZH0v8BVg7C+Y86HQw1vcZaNTF1xEZN6npmeeGAjyWepaeUWE81j+KruGBMRCIceSMfPZ6bBzr9ibTqEZFHu7bgju7eHfks8tJ/IuAZ4HXgFuAkUA5Vf2LNwLNiyV+N5lnYc2HztOynYZCViYcWANNuvo6MuMmZ+zXyQt3cPx0Br1a1uHx/lF0aWYPyAUyVWXBdmfoyzV7nKEvH+rTgkFdm3jlBHA5iX+VqnYRkQ2q2t59XrFHmQ9L/DgJft0s+PllSN7j9A559wxfR2VyOZGWwQeLdzF50U5SzmTQt1UdHusfRacAHezb5E1VWRR/lPE/xrFy93HqV3NOAIO7Fu9g95cz2Hq6iJQD4kTkUWA/zri7he1wKjAASFTVdq55HwOtXKvUAJJVNdqjbxDI4mPhm6ec7oQbdoKbX4PI/r6OyrhJOZPB+4t3MnXRTk6kZdK/dV0e6x9FxyY1fB2aKYVEhJ5RdbgmMoxfEpIY/2Mcz/53E2/Nj+fB3i24p3vTYj0B5OZJ4n8cqAQ8BvwN6Ad4Mor0NOBNYHrODFUdnPNeRF4FUi4h1sCSnQ1Z6U4naFLO6Szt7lnQ6kZrrVOKpJzOYMrinby/eCcn0zK5rk09Hu8fRbtG1X0dmvEDIsLVkWFcHRnGkoQkxsdu5/m5m3n7pwQe7B3B0O7NqBjihSogb7bqEZFwYG5Oid9tvgB7gH6qGlfYdgKqqkcVtn0L8/8BzXvCDS8681SdPnZMqXA89SxTFu3kg192cTI9kxva1mdc/0jaNrSEby7Psh1JjI+N45eEJMKqhDDh7k5cFRlWpG0VuapHRGKAPwLN3NdX1ctpL9gTOFxQ0heRscBYgKZNm17GrvyEqlOlM//vcGA11IpwhvkDp4RvpfxS4VjqWSYv3MEHv+wi9WwWN7Wvz7h+UVzRoJqvQzNlRPeI2syMqM2KXcd4e348EXUKrVm/ZJ7c3N0G/BbYAJwbMklVd+f7ofOfDSfvEv87QLyqvupJkAFR4p//D1jwT6jeFHr/DjoOsYFHSpGkU+lMXLiDD5fs5kxGFje3b8C4flG0ql/V16EZk6/Lubl7pDjH2BWR8sDtgDU437MUKoVBWCS0uxOq1IVOw3w2fqu52JGT6Uz8OYGPlu4hLTOLWzo0ZFy/SKLqWcI3/suTxP+siEwGYoH0nJmq+kUR93ktsFVV9xXx8/5v/2qnSif+R4i+F259C+q0dF6mVEg8mcZ7C3YwY9luzmZmMzC6EY/0jSSybvFfdhtT0jxJ/COB1kAw56t6FCgw8YvILKAPECYi+4BnVXUKcDcwq6gB+7VDG50qnW1fQ8VacO1z0G2Mr6Mybg6fSOPdBQnMXLaHzGxlYHRDHu0b6ZV6VmN8xZPE31VVWxW+2oVUdUg+80dc6rbKjPUfw65F0PdP0P0BCLUbgqXFwZQzvPtTArNW7CUrW7m9k1PCDw+zgWpM2eNJ4v9FRNqo6mavR1PWJCU4N2w7DHYeuOr5G+j5pI1rW4ocSD7DOz8l8PGKvWSrckfnxjzSN5KmtSv5OjRjvMaTxN8DWCsiO3Hq+AXQy2zOWbYd3+10rbB2FgSFQJPuzvyKNXwaljlv3/HTvP1TAp+u3AvAnV2a8HCfFjSpZQnflH2eJP4bvB5FWTL/H7Dw3067+25j4JonoWo9X0dlXPYeO83bP8Xz2SqnbcGgmCY81KcFjWtawjeBI9/ELyLVVPUEcLIE4/FPpxKd6pugYKha3xnXtudTzoAoplTYnZTKW/Pj+WL1fsqJMKRbUx7s3YKGNSr6OjRjSlxBJf6ZOJ2srcJpxeP+6KgCJdYff6mVmgS/jIflk5yuFbqMgJhRvo7KuNl5NJU358UzZ+1+gsoJ9/ZoxoO9W1C/emjhHzamjMo38avqANe/zUsuHD9xJhmWvAlL34GzqdD+Lgjv6euojJuEI6d4y5Xwg4PKMfzKcB7sHUHdapbwjfGkr55YVe1f2LyAMnso7F4EbW51hjms29rXERmX+MSTvDEvnq/WHSCkfDlGXd2csb0jqFvVEr4xOQqq4w/F6Y45TERqcr6qpxoQWJXXZ1Nh5VTodK9Tl3/ts84IWDaubakRd/gkE+bFM3f9AULLBzGmZwRjekUQVqWCr0MzptQpqMT/APAE0BBY7Tb/BE4/+2VfRhqset9ppZPquoHb6V5o0s3XkRmXrYdO8EZsPN9sPEjF4CAe6NWCMT2bU9sSvjH5KqiOfzwwXkTGqeobJRiT76k6JfyfX4GTB5z6+8EfQtMevo7MuGw5eIIJsXF8u/EQVSqU5+E+LRh9TQS1KlsHd8YUxpN2/JNF5EngGpzWPAuBd1U1zauR+YLq+b7vt38HNZrC7e9B816+jsy4bNyfwoTYOL7ffJiqFcozrl8ko69pTo1KlvCN8ZQnif8DnLb8OaX+e4APgbu8FVSJy86CDZ/BwlfhntnOICh3ToGQKjYASimxYV8K42O38+OWRKqGlufx/lGMuro51SsF+zo0Y/yOJ4m/naq2cZueLyJlo9+e7GzY8iXMfxGOboN67ZymmgAVrL/10mDt3mQmxMYxb2si1SsG8+R1LRl+VTjVK1rCN6aoPEn8q0Wkh6ouBRCR7oD/D4eVlQlTrnOGOQxrBXdNgysG2ri2pcTqPccZ/2McC7YfoUalYJ663kn4VUMt4RtzuTxJ/F1weujc45puCmwTkQ34W2dtqk6ib9TFGdaw9c3Q/UFofyeUK/6R7M2lW7X7GK//GMfCuKPUrBTM725oxbArw6lSwYahNKa4BE4nbTt/hnl/h71LYdT30LQ79HrK11EZl+U7jzE+djuL45OoXTmEp29szX09mlHZEr4xxc6TX1UE0Nb1fpOqzvdiPMVvz1KY9wLsWghVG8LN/4aGnXwdlXFZuiOJ8T/GsWRHEmFVQvjjTVcwtEdTKoVYwjfGWwp6crcRzvCKaTgdtQHcJSL/BG5T1f0lEN/lOXsaZg52+sS/4SXoMhKC7dF9X1NVliQk8XpsHMt3HqNO1Qr86eYrGNq9GRVDrMrNGG8rqFj1JvCOqk5znykiw4C3gYFejKt4hFSCoZ9BvTYQYkPo+Zqqsjg+ifGx21mx6zh1q1bg2VvaMKRbU0KDLeEbU1IKSvxtVPW23DNVdbqI/NGLMRWvJl19HUHAU1V+jjvK+B+3s3pPMvWrhfLcr9syuGsTS/jG+EBBiT/Pdo0iUg6wX6splKry07YjjI+NY+3eZBpWD+Vvt7ZjUExjKpS3/0LG+EpBiX+uiEwCnlDVVAARqQy8BnxTEsEZ/6SqzNuayITYONbtS6FRjYr8/bZ23NnFEr4xpUFBif93wIvAbhHZ7ZrXFKcLh2e8HZjxP6rKD5sPM2FeHBv3n6BxzYq8dHt7bu/cmJDy9mCcMaVFQb1zZgBPicifgUjX7ARVPV0ikRm/kZ2tfL/5MBNi49h88ATNalfi5Ts7cFunRgQHWcI3prQptLG0qp4BNpRALMbPZGcr/9t0iAmxcWw9dJLw2pV45a6O3BrdkPKW8I0ptewpGXPJsrOVbzYe5I3YeLYdPklEWGVeG9yRWzpYwjfGH1jiNx7Lylbmrj/Am/PiiUs8RYs6lRl/dzQDOjQkqJx1X22Mvyjoyd3OBX1QVVcXtNyUHZlZ2cxdf5A35sWRcCSVqLpVmDCkEze3b2AJ3xg/VFCJ/1XXv6FADLAOZ8D1DjjdMl9Z0IZFZCowAEhU1XZu88cBjwBZwNeq+rsiR2+8KjMrmy/XHuDN+fHsPJpKq3pVeeueztzYrj7lLOEb47cKatXTF0BEvgA6q+oG13Q74K8ebHsaTrcP03NmiEhfnK4eOqpquojULXLkxmsysrKZs2Y/b82PZ1fSaVrXr8o7Qzvzq7aW8I0pCzyp42+Vk/QBVHWjiFxR2IdU9WcRCc81+yHgJVVNd62TeCnBGu/KzMrm89X7eGt+AnuOnaZtw2q8d18XrruiniV8Y8oQTxL/ehGZDHzkmh4KrC/i/loCPUXk7zi9fj6lqiuKuC1TjNIysnjoo1XM33aE9o2qM3lYDP2vqIvYmMPGlDmeJP6ROCX1x13TPwPvXMb+agE9gK7AJyISoaqae0URGQuMBWjatGkRd2c8kZaRxQMfrmLB9iP8bWBb7u3RzBK+MWWYJw9wpYnIu8A3qrrtMve3D/jCleiXi0g2EAYcyWO/E4GJADExMRedGEzxSMvIYsz0lSyKP8o/72jP4K52kjWmrCv0aRsR+TWwFvifazpaRP5bxP3NAXJuGrcEQoCjRdyWuUxnzmZx/wc5Sb+DJX1jAoQnj1k+C3QDkgFUdS3QvLAPicgsYAnQSkT2ichoYCoQISIbgdnA8LyqeYz3nTmbxegPVrA44Sj/urMjg2Ka+DokY0wJ8aSOP0NVU3LV+RaarFV1SD6L7vUkMOM9p89mMmraCpbvPMard3Xk9s6NfR2SMaYEeZL4N4nIPUCQiEQBjwG/eDcs4y2p6ZmMnLaClbuO8e9B0dzaqZGvQzLGlDBPqnrGAW2BdGAmkML5Fj7Gj5xKz2Tk+07Sf22wJX1jApUnJf6bVfWPwLlxdkXkLuBTr0Vlit2p9ExGTF3Omr3JjL+7E7d0bOjrkIwxPuJJif8PHs4zpdTJtAyGTVnGmr3JTLCkb0zAK6h3zhuBm4BGIjLBbVE1INPbgZnicSItg+FTl7NhXwpvDunEje0b+DokY4yPFVTVcwCnF85fA6vc5p8E/s+bQZnikXImg2FTl7Npfwpv3tOZG9rV93VIxphSoKDeOdcB60Rkpmv8XeNHUk5ncN/UZWw5eIJ37u3CdW3q+TokY0wp4cnN3XAReRFog9M3PwCqGuG1qMxlST59lvumLGfboZO8e28X+l9hSd8Yc54nN3ffx+mULROnu4XpnO+p05Qyx1PPMnTyMrYdOsl791nSN8ZczJPEX1FVYwFR1d2q+lfgZu+GZYriWOpZ7pm8jLjEU0wc1oW+rW2cG2PMxTyp6kkXkXJAnIg8CuwHqng3LHOpkk6lM3TyMnYeTWXSsBh6t6zj65CMMaWUJyX+x4FKOF01dAHuA4Z7MyhzaY6eSueeSU7Snzzckr4xpmCe9MefM0LWKZxBWUwpcuRkOkMnL2XPsdNMHdGVqyPDfB2SMaaUK+gBrq8ooBdOVf21VyIyHks8mcY9k5ax77iT9K9qYUnfGFO4gkr8r5RYFOaSJZ5IY8ikpRxITmPayG70iKjt65CMMX6ioAe4FpRkIMZzh0+kMWTiUg6dSGPayK50t6RvjLkEhdbxi8hO8qjysQe4fONQilPSTzyRxgejutE1vJavQzLG+BlPmnPGuL0PBe4CLNv4wMGUMwyZuJSjp84yfXQ3ujSzP4Mx5tIV2pxTVZPcXvtV9XXsAa4SdyD5DHdPXEqSJX1jzGXypKqns9tkOZwrAE+uFEwx2Xf8NEMmLSU5NYPpo7vRqWlNX4dkjPFjniTwV93eZwI7gUHeCcfktveYk/RTzmTw0f3d6dikhq9DMsb4OU8e4OpbEoGYi+09dpq7Jy7lZFoGM+7vTofGNXwdkjGmDCi0jl9E/iEiNdyma4rIC16NyrAn6TSD31vCqfRMZo7pYUnfGFNsPOmr50ZVTc6ZUNXjOEMyGi/ZdTSVwROXcDojixn3d6ddo+q+DskYU4Z4kviDRKRCzoSIVAQqFLC+uQw7j6Zy98SlpGVkMfP+Hpb0jTHFzpObuzOAWBF53zU9EvjAeyEFroQjp7hn0lIyspSZY3pwRYNqvg7JGFMGeXJz958ish7o75r1N1X9zrthBZ74RCfpZ2Urs8b0oFX9qr4OyRhTRnnUHl9VvwW+9XIsASs+8SR3T1wGwOyxPYiqZ0nfGOM9BXXLfJK8u2UWQFXV6iGKQdzhkwyZtBQRYdaY7kTWtaRvjPGufG/uqmpVVa2Wx6uqJ0lfRKaKSKKIbHSb91cR2S8ia12vgG4dtO3QSe6euJRyIswe28OSvjGmRHjSqgcAEakrIk1zXh58ZBpwQx7zX1PVaNfrG0/3X9ZsOXiCIZOWUj7ISfot6tgwxsaYkuHJA1y/FpE4nK4aFgC78KC+X1V/Bo5dboBl0eYDJ7hn0lJCgsoxe+yVRFjSN8aUIE9K/H8DegDbVbU5TuuepZexz0dFZL2rKijf3sZEZKyIrBSRlUeOHLmM3ZUuG/encM/kpYQGBzF7bA+ah1X2dUjGmADjSeLPUNUkoJyIlFPV+VzYR/+leAdoAUQDB7mwA7gLqOpEVY1R1Zg6deoUcXely8b9KQydvIzKIeX5eOyVhFvSN8b4gCfNOZNFpArwMzBDRBKB1KLsTFUP57wXkUnA3KJsxx+t35fMvZOXUTU0mNlje9CkViVfh2SMCVCelPgHAqeB/wP+ByQAtxRlZyLSwG3yNmBjfuuWJev2JjN08jKqVbSkb4zxvYLa8UcC9VR1sWtWNvCBiFwD1ACSCtqwiMwC+gBhIrIPeBboIyLROM8H7AIeuLzwS781e44zbMpyalQOZtaYHjSuaUnfGONbBVX1vA78IY/5Ka5lBZb6VXVIHrOneBpYWbBq93GGT11O7SohzBrTg4Y1Kvo6JGOMKbCqp56qbsg90zUv3GsRlRGrdh9j+NTlhFUJYfZYS/rGmNKjoMRfo4BllsUKsGLXMYZNWU7dqhWYPfZKGlS3w2WMKT0KSvwrRWRM7pkicj+wynsh+bdlO5IYPnU59aqHMmtsD+pXD/V1SMYYc4GC6vifAP4jIkM5n+hjgBCcFjkml6U7khj5/goa1ghl1pge1K1mSd8YU/rkm/hdbe6vEpG+QDvX7K9VdV6JROZnfkk4yuhpK2lcsyIzx/SgTlUbpMwYUzp5MhDLfGB+CcTitxbHH2X0BytoWqsSM8f0IKyKJX1jTOnlce+cJm8L444watoKwmtXZpYlfWOMH/BoBC6TtwXbjzBm+koiwiozc0wPalUO8XVIxhhTKEv8RTR/WyIPfLiKyDpVmHF/d2pa0jfG+AlL/EUwb+thHvxwNVH1nKRfo5IlfWOM/7A6/kv04+bDPPDhKlrVr8rM+3tY0jfG+B1L/Jfg+02HeGjGKto0qMZH93eneqVgX4dkjDGXzBK/h/638RAPz1hN24bVmT66O9UrWtI3xvgnq+P3wLcbDjJu1hraN67OB6O6US3Ukr4xxn9Zib8QX68/yKOz1tCxSQ2mW9I3xpQBVuIvwFfrDvDEx2vp1KQG00Z1o0oFO1zGGP9nJf58fLl2P4/PXkOXpjUt6RtjyhTLZnmYs2Y/T36ylq7htZg6oiuVLekbY8oQy2i5fLF6H099uo7uzWszZUQMlULsEBljyhar6nHz2ap9/ObTdfSIqM3UEV0t6RtjyiTLbC6frNjL779Yz9Utwpg0LIaKIUG+DskYY7zCSvzA7OV7+N3n67kmMozJwy3pG2PKtoBP/DOX7eHpLzbQu2UdJg2LITTYkr4xpmwL6MT/0dLdPPOfDfRtVYf37utiSd8YExACto5/+pJd/OXLTfRvXZe37+1MhfKW9I0xgSEgE/+0xTv561ebufaKerw1tJMlfWNMQAm4xD910U6en7uZ69vU4817OhNSPqBru4wxASigEv/khTt44est3NC2Pm/c04ngIEv6xpjAEzCJf+LPCfzjm63c1L4+4++2pG+MCVxey34iMlVEEkVkYx7LfiMiKiJh3tq/u3d+cpL+zR0aWNI3xgQ8b2bAacANuWeKSBPgemCPF/d9zlvz4/nn/7ZyS8eGjB8cbUnfGBPwvJYFVfVn4Fgei14Dfgeot/ad46358fzru20MjG7Ia4M6Ut6SvjHGlOwDXCIyENivqus8WHesiKwUkZVHjhwp0v6ah1Xmri6N+fegaEv6xhjjUmI3d0WkEvAMTjVPoVR1IjARICYmpkhXBze1b8BN7RsU5aPGGFNmlWQxuAXQHFgnIruAxsBqEalfgjEYY0zAK7ESv6puAOrmTLuSf4yqHi2pGIwxxni3OecsYAnQSkT2ichob+3LGGOM57xW4lfVIYUsD/fWvo0xxuTPmroYY0yAscRvjDEBxhK/McYEGEv8xhgTYETV6z0nXDYROQLsLuLHw4DS2GTU4ro0FtelsbguTWmNCy4vtmaqWif3TL9I/JdDRFaqaoyv48jN4ro0FtelsbguTWmNC7wTm1X1GGNMgLHEb4wxASYQEv9EXweQD4vr0lhcl8biujSlNS7wQmxlvo7fGGPMhQKhxG+MMcaNJX5jjAkwZSbxi8gNIrJNROJF5Ok8llcQkY9dy5eJSHgpiWuEiBwRkbWu1/0lENNUEUkUkY35LBcRmeCKeb2IdPZ2TB7G1UdEUtyO1V9KKK4mIjJfRDaLyCYReTyPdUr8mHkYV4kfMxEJFZHlIrLOFddzeaxT4r9HD+Mq8d+j276DRGSNiMzNY1nxHi9V9fsXEAQkABFACLAOaJNrnYeBd13v7wY+LiVxjQDeLOHj1QvoDGzMZ/lNwLeAAD2AZaUkrj7AXB/8/2oAdHa9rwpsz+PvWOLHzMO4SvyYuY5BFdf7YGAZ0CPXOr74PXoSV4n/Ht32/SQwM6+/V3Efr7JS4u8GxKvqDlU9C8wGBuZaZyDwgev9Z0B/EZFSEFeJU9WfgWMFrDIQmK6OpUANEfH6GJYexOUTqnpQVVe73p8EtgCNcq1W4sfMw7hKnOsYnHJNBrteuVuRlPjv0cO4fEJEGgM3A5PzWaVYj1dZSfyNgL1u0/u4+Adwbh1VzQRSgNqlIC6AO1zVA5+JSBMvx+QJT+P2hStdl+rfikjbkt656xK7E05p0Z1Pj1kBcYEPjpmr2mItkAj8oKr5Hq8S/D16Ehf45vf4OvA7IDuf5cV6vMpK4vdnXwHhqtoB+IHzZ3VzsdU4fY90BN4A5pTkzkWkCvA58ISqnijJfRekkLh8csxUNUtVo3HG1u4mIu1KYr+F8SCuEv89isgAIFFVV3l7XznKSuLfD7ifmRu75uW5joiUB6oDSb6OS1WTVDXdNTkZ6OLlmDzhyfEscap6IudSXVW/AYJFJKwk9i0iwTjJdYaqfpHHKj45ZoXF5ctj5tpnMjAfuCHXIl/8HguNy0e/x6uBX4szDvlsoJ+IfJRrnWI9XmUl8a8AokSkuYiE4Nz8+G+udf4LDHe9vxOYp647Jb6MK1c98K9x6ml97b/AMFdLlR5Aiqoe9HVQIlI/p15TRLrh/P/1erJw7XMKsEVV/53PaiV+zDyJyxfHTETqiEgN1/uKwHXA1lyrlfjv0ZO4fPF7VNU/qGpjdYajvRvnWNyba7ViPV5eG3O3JKlqpog8CnyH05JmqqpuEpHngZWq+l+cH8iHIhKPcwPx7lIS12Mi8msg0xXXCG/HJSKzcFp7hInIPuBZnBtdqOq7wDc4rVTigdPASG/H5GFcdwIPiUgmcAa4uwRO3uCUyO4DNrjqhwGeAZq6xeaLY+ZJXL44Zg2AD0QkCOdE84mqzvX179HDuEr895gfbx4v67LBGGMCTFmp6jHGGOMhS/zGGBNgLPEbY0yAscRvjDEBxhK/McYEGEv8xq+ISJar18SNIvJVTrvsYtjuCBF5szi2lWu75UXkHyIS59bj4x+LcfvTROTO4tqeCQyW+I2/OaOq0araDqc98yO+DqgQLwANgfaurgJ64no2wZ3rwS/7PZoSYf/RjD9bgqsjNBHpJiJLxOnP/BcRaeWaP0JEvhCR/7lK3S/nfFhERorIdhFZjvMwVM78cBGZ5+qoK1ZEmrrmTxORd0RkqYjsEKev+6kiskVEpuUOTkQqAWOAcaqaBk4vmqr6V7f9bBOR6cBGoIlr+yslV3/xIrJLRF4WkQ3i9Ckf6barXq7vvMNK/8YTlviNX3I9fdmf811gbAV6qmon4C/AP9xWjwYGA+2BweIMYNIAeA4n4V8DtHFb/w3gA1dHXTOACW7LagJXAv/n2vdrQFugvYhE5wozEtjj6jI5P1HA26raVlV3A39U1RigA9BbRDq4rZuiqu2BN3F6c8zRwPUdBgAvFbAvYwBL/Mb/VHR1T3AIqIfTgyI4nVZ9Ks7oXTnJOEesqqa4St2bgWZAd+AnVT3iGivhY7f1r8QZEAPgQ5ykmuMrV5cHG4DDqrpBVbOBTUB4QYG7rjDWisheOd/d725X//05BonIamCN6zu4n5Bmuf17pdv8OaqaraqbXcfEmAJZ4jf+5oyrrrwZzohKOXX8fwPmu+r+bwFC3T6T7vY+i8vroypnW9m5tpudx3bjgaYiUhVAVd93xZ6C03cTQGrOyiLSHHgK6O+62vg61/fQfN67x+HtwYVMGWCJ3/glVT0NPAb8Rs53U5vTDfIIDzaxDKcqpbY4XRvf5bbsF853gjUUWHgZMU4B3hSRUDhXRRWSz0eq4ZwIUkSkHnBjruWD3f5dUpSYjIEy0junCUyqukZE1gNDgJdxel78E05JubDPHhSRv+Ik0GRgrdviccD7IvJb4AiX19PmH3GuRjaKyEmcHjI/AA7gtPZxj2mdiKzBuV+xF1ica1s1Xd83Hec7G1Mk1junMX5AnEE6YlT1qK9jMf7PqnqMMSbAWInfGGMCjJX4jTEmwFjiN8aYAGOJ3xhjAowlfmOMCTCW+I0xJsD8P40PO4yv18VvAAAAAElFTkSuQmCC\n",
      "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.7.11"
  },
  "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
}