{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 9-Solving Graph Coloring Problem with PyQUBO\n",
"この節では、[Ising formulations of many NP problems](https://arxiv.org/pdf/1302.5843v3.pdf) から6.1. Graph ColoringをPyQUBOを用いて解きます。"
]
},
{
"cell_type": "markdown",
"metadata": {
"colab_type": "text",
"id": "view-in-github"
},
"source": [
"[](https://colab.research.google.com/github/OpenJij/OpenJijTutorial/blob/master/source/ja/009-GraphColorPyqubo.ipynb)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### グラフ彩色問題\n",
"グラフ彩色問題は以下のような状況の最適解を求める問題であり、NP完全問題の一つです。まずは具体的な問から考えてみましょう。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 具体例\n",
"分かりやすくするために具体的に以下のような問を考えます。\n",
"> 10個のノードと20本の枝を持つ無効グラフが与えられたとします。枝で繋がれたノード同士は異なる色となるようにノードを色分けする時、3色で全てのノードを塗ることは可能であるか考えます。\n",
"> グラフは下のようになっているとします。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"
![](\"images/graph_color.png\")
\n",
"
\n",
"
![](\"images/graph_color_res.png\")
\n",
"