1 files changed, 117 insertions, 0 deletions
diff --git a/Elements_of_discrete_mathematics/Chapter4.ipynb b/Elements_of_discrete_mathematics/Chapter4.ipynb
new file mode 100755
index 00000000..2adb4c8f
--- /dev/null
+++ b/Elements_of_discrete_mathematics/Chapter4.ipynb
@@ -0,0 +1,117 @@
+{
+ "metadata": {
+  "name": "",
+  "signature": "sha256:a85fddad5ca1dfcfd83be3de3e24c0c6e6b3cfc061b0141fb4ecc95c31a3f057"
+ },
+ "nbformat": 3,
+ "nbformat_minor": 0,
+ "worksheets": [
+  {
+   "cells": [
+    {
+     "cell_type": "heading",
+     "level": 1,
+     "metadata": {},
+     "source": [
+      "4 Graphs and planar graphs"
+     ]
+    },
+    {
+     "cell_type": "heading",
+     "level": 2,
+     "metadata": {},
+     "source": [
+      "Example 03:Page 199 "
+     ]
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": [
+      "print \"GRAPH TRAVERSLS-DEPTH FIRST SEARCH\"\n",
+      "graph={'A': ['G','B'],\n",
+      "       'B': ['C'],\n",
+      "       'C': ['E','D'],\n",
+      "       'D': [],\n",
+      "       'E': ['D','F'],\n",
+      "       'F': ['A'],\n",
+      "       'G': ['F']}#Input the graph details using a sequence data structure \n",
+      "\n",
+      "def dfs(graph,start):\n",
+      "    path=[]#Initially the path is empty, as no nodes are visited\n",
+      "    stack=[start]#The starting node is pushed into the stack\n",
+      "    while stack!=[]:\n",
+      "        visited=stack.pop()#The node is marked as visited\n",
+      "        if visited not in path:\n",
+      "            path.append(visited)#The node is added to the path\n",
+      "        for w in reversed(graph[visited]):#The node is checked to see if it has any adjacent nodes. \n",
+      "            if w not in path:\n",
+      "                stack.append(w)#Adjacent nodes if any without being visited are added to the stack\n",
+      "    return path\n",
+      "print  \"path=\",dfs(graph,'A')#The sequence and the starting nodes are given as input \n"
+     ],
+     "language": "python",
+     "metadata": {},
+     "outputs": [
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": [
+        "GRAPH TRAVERSLS-DEPTH FIRST SEARCH\n",
+        "path= ['A', 'G', 'F', 'B', 'C', 'E', 'D']\n"
+       ]
+      }
+     ],
+     "prompt_number": 1
+    },
+    {
+     "cell_type": "heading",
+     "level": 2,
+     "metadata": {},
+     "source": [
+      "Example 04:Page 201"
+     ]
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": [
+      "print \"GRAPH TRAVERSALS-BREADTH FIRST SEARCH\"\n",
+      "graph={'A': set(['G','B']),\n",
+      "       'B': set(['C']),\n",
+      "       'C': set(['D','E']),\n",
+      "       'D': set([]),\n",
+      "       'E': set(['D','F']),\n",
+      "       'F': set(['A']),\n",
+      "       'G': set(['F'])}#Input the graph information\n",
+      "\n",
+      "def bfs(graph,start):\n",
+      "    path=[]#Initially path is empty as no nodes are visited\n",
+      "    queue=[start]#The start node is added to the queue\n",
+      "    while queue:\n",
+      "        v=queue.pop(0)#Always the first node is only popped\n",
+      "        if v not in path:\n",
+      "            path+=[v]#The popped node is added to the path\n",
+      "            queue+=graph[v]#The adjacent nodes of the visited nodes are inserted in the queue\n",
+      "    return path\n",
+      "print \"path=\",bfs(graph,'A')\n"
+     ],
+     "language": "python",
+     "metadata": {},
+     "outputs": [
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": [
+        "GRAPH TRAVERSALS-BREADTH FIRST SEARCH\n",
+        "path= ['A', 'B', 'G', 'C', 'F', 'E', 'D']\n"
+       ]
+      }
+     ],
+     "prompt_number": 2
+    }
+   ],
+   "metadata": {}
+  }
+ ]
+}
+\ No newline at end of file