{
 "metadata": {
  "name": "",
  "signature": "sha256:02fe4bba17cba439f8d233db5bb8441508eb34f6f66a6e2f9bcff8cf8ec85b6f"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Instructions\n",
      "\n",
      "1. Implement functions that generate (undirected) [complete graphs](http://en.wikipedia.org/wiki/Complete_graph) and [path graphs](http://en.wikipedia.org/wiki/Path_graph) with an arbitrary number of vertices. Vertices are labeled by number, starting from zero. Graphs are represented by dictionaries, whose keys are individual vertices and values are lists of adjacent vertices. Eg., a complete graph of 3 vertices: `{0: [1, 2], 1: [0, 2], 2: [0, 1]}`, a path of 4 vertices: {0: [1], 1: [0, 2], 2: [1, 3], 3: [2]}.\n",
      "\n",
      "2. Implement a graph renumbering function, which can use an abritrary integer renumbering function as its argument. For example:\n",
      "```\n",
      "renumber({0: [1], 1: [0]}, lambda x: x + 1)\n",
      "```\n",
      "returns\n",
      "```\n",
      "{1: [2], 2: [1]}\n",
      "```\n",
      "\n",
      "3. Using these functions, implement a [lollipop graph](http://mathworld.wolfram.com/LollipopGraph.html) generator, i.e. a function `lollipop(m, n)`.\n",
      "\n",
      "4. Implement a function that from an arbitrary graph, represented as described above, creates the [adjacency matrix](http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29) as a numpy array. This m x m matrix (m is the graph order) contains only 0 or 1. 1 at (i,j) position represents an edge `(i -> j)`. For a complete graph of order 4, the adjacency matrix is\n",
      "```\n",
      "[[0 1 1 1]\n",
      "[1 0 1 1]\n",
      "[1 1 0 1]\n",
      "[1 1 1 0]]\n",
      "```\n",
      "and for a path of order 4:\n",
      "```\n",
      "[[0 1 0 0]\n",
      "[1 0 1 0]\n",
      "[0 1 0 1]\n",
      "[0 0 1 0]]\n",
      "```\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}