{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\n# Maximum Independent Set\n\nAn independent set is a set of vertices in a graph where no two vertices in the\nset are adjacent. The maximum independent set is the independent set of largest\npossible size for a given graph.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import numpy as np\nimport matplotlib.pyplot as plt\nimport networkx as nx\nfrom networkx.algorithms import approximation as approx\n\nG = nx.Graph(\n    [\n        (1, 2),\n        (7, 2),\n        (3, 9),\n        (3, 2),\n        (7, 6),\n        (5, 2),\n        (1, 5),\n        (2, 8),\n        (10, 2),\n        (1, 7),\n        (6, 1),\n        (6, 9),\n        (8, 4),\n        (9, 4),\n    ]\n)\n\nI = approx.maximum_independent_set(G)\nprint(f\"Maximum independent set of G: {I}\")\n\npos = nx.spring_layout(G, seed=39299899)\nnx.draw(\n    G,\n    pos=pos,\n    with_labels=True,\n    node_color=[\"tab:red\" if n in I else \"tab:blue\" for n in G],\n)"
      ]
    }
  ],
  "metadata": {
    "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.12.7"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}