Chapter_34_NP-Completeness/exercises_34.2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 34.2 Polynomial-time verification"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.2-1\n",
    "\n",
    "> Consider the language GRAPH-ISOMORPHISM $ = \\{ \\langle G_1, G_2 \\rangle : G_1$ and $G_2$ are isomorphic graphs$\\}$. Prove that GRAPH-ISOMORPHISM $\\in$ NP by describing a polynomial-time algorithm to verfify the language."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The certificate should be a mapping $f$ that maps $u_1 \\in G_1$ to $u_2 \\in G_2$, which could be an array and the mapping takes $O(1)$ time in a random-access machine.\n",
    "\n",
    "For any $u_1, v_1 \\in G_1$ if there exists an edge in $G_1$ between $u_1$ and $v_1$, then there must exist an edge in $G_2$ that connects $u_2 = f(u_1) \\in G_2$ and $v_2 = f(v_1) \\in G_2$, and vice versa."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.2-2\n",
    "\n",
    "> Prove that if $G$ is an undirected bipartite graph with an odd number of vertices, then $G$ is nonhamiltonian."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* starts in even partition: leaves vertices in odd partition unvisited\n",
    "* starts in odd partition: no edge connects two vertices in the same partition"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}