{ "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": [ "[![Open in Colab](https://colab.research.google.com/assets/colab-badge.svg)](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": [ "