{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\n",
"\\def\\CC{\\bf C}\n",
"\\def\\QQ{\\bf Q}\n",
"\\def\\RR{\\bf R}\n",
"\\def\\ZZ{\\bf Z}\n",
"\\def\\NN{\\bf N}\n",
"$$\n",
"# Dictionaries and Graph Theory\n",
"\n",
"Authors \n",
"-Franco Saliola\n",
"\n",
"## Dictionaries\n",
"\n",
"A *dictionary* is another builtin datatype. Unlike lists or tuples,\n",
"which are indexed by a range of numbers, dictionaries are indexed by\n",
"*keys* , which can be any immutable type. Strings and numbers can always\n",
"be keys. Dictionaries are sometimes called \"associative arrays\" in other\n",
"programming languages.\n",
"\n",
"There are several ways to define dictionaries. Below are equivalent ways\n",
"to define a dictionary that pairs 'key1' with 'value1' and 'key2' with\n",
"'value2'."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'key2': 'value2', 'key1': 'value1'}"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"d = {'key1':'value1', 'key2':'value2'}\n",
"d"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'key2': 'value2', 'key1': 'value1'}"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"d = dict(key1='value1', key2='value2')\n",
"d"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'key2': 'value2', 'key1': 'value1'}"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"d = dict([('key1','value1'), ('key2','value2')])\n",
"d"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'a': (6, 5), 1: [2, 2], 0: {1: 2}}"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"d = {1:[2,2], 'a':(6,5), 0:{1:2}}\n",
"d"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Dictionaries behave as lists, tuples, and strings for several important\n",
"operations.\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"**Operation** | **Syntax for lists** | **Syntax for dictionaries** |

Accessing elements | `L[3]` | `D[3]` |

Length | `len(L)` | `len(D)` |

Modifying | `L[3] = 17` | `D[3] = 17` |

Deleting items | `del L[3]` | `del D[3]` |

\n",
"\n",
"**Exercise:** In the directed graph below, the vertex 1 points to the\n",
"vertices in the list \\[2, 3\\].\n",
"\n",
"\n",
"\n",
"Create a dictionary with keys the vertices of the above directed graph,\n",
"and with values the lists of vertices pointed to by the vertex."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** Use the `DiGraph` command to contruct the above directed\n",
"graph, and plot the directed graph"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(*hint*: in the documentation for `DiGraph`, take a look at the\n",
"'*dictionary of lists*' example.)\n",
"\n",
"**Exercise:** Find the *adjacency matrix* of the graph you constructed\n",
"above."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** Compute the square of the adjacency matrix. Give a\n",
"graph-theoretic intepretation of the numbers in this matrix. Does your\n",
"intepretation hold for the cube of the adjacency matrix?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The Seven Bridges of K\u00f6nigsberg\n",
"\n",
"**Exercise:** The *Seven Bridges of K\u00f6nigsberg* is the following famous\n",
"historical problem solved by Leonhard Euler in 1735. This is the problem\n",
"that started graph theory.\n",
"\n",
"> The city of K\u00f6nigsberg in Prussia (now Kaliningrad, Russia) was set on\n",
"> both sides of the Pregel River, and included two large islands which\n",
"> were connected to each other and the mainland by seven bridges. The\n",
"> problem was to find a walk through the city that would cross each\n",
"> bridge once and only once. The islands could not be reached by any\n",
"> route other than the bridges, and every bridge must have been crossed\n",
"> completely every time (one could not walk halfway onto the bridge and\n",
"> then turn around to come at it from another side).\n",
">\n",
"> \n",
"\n",
"1. Enter the graph on the right into Sage (use the `Graph` command, not\n",
" the `DiGraph` command)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"1. Solve the problem; that is, does such a walk exist?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(*hint:* Take a look at the documentation for the `eulerian_circuit`\n",
"method; look up *Eulerian circuit* in Wikipedia if you don't know its\n",
"definition.)\n",
"\n",
"*(The quotation and the image are from the Wikipedia page \\`Seven\n",
"Bridges of K\u00f6nigsberg\n",
"\\\\`\\_\n",
"; the problem is from* *\\`William Stein's\n",
"\\\\`\\_* *Graph Theory Worksheet for\n",
"\\`Math 480b \\[2009 \\\\`\\_ \\])*\n",
"\n",
"## The Coxeter Graph\n",
"\n",
"The *Coxeter graph* is the graph with 28 vertices $v_{i,j}$, for\n",
"$0 \\leq i\n",
"\\leq 3$ and $0 \\leq j \\leq 6$, and with edges described by the rules:\n",
"\n",
"1. $v_{0,i}$ is connected to $v_{1,i}$, $v_{2,i}$, $v_{3,i}$ for all\n",
" $0\\leq i \\leq 6$;\n",
"2. $v_{1,j}$ is connected to $v_{1, j+1 (mod\\, 7)}$ for all\n",
" $0\\leq j \\leq 6$;\n",
"3. $v_{2,j}$ is connected to $v_{2, j+2 (mod\\, 7)}$ for all\n",
" $0\\leq j \\leq 6$;\n",
"4. $v_{3,j}$ is connected to $v_{3, j+3 (mod\\, 7)}$ for all\n",
" $0\\leq j \\leq 6$.\n",
"\n",
"**Exercise:** Construct a dictionary `V` such that `V[(i,j)]` is the\n",
"list of vertices `(r,s)` that are connected to `(i,j)`. Use this\n",
"dictionary to construct and plot the *Coxeter graph* ."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(*hints:* note that writing `V[i,j]` is shorthand for writing\n",
"`V[(i,j)]`. You should be able to generate the lists of vertices by\n",
"using loops and list comprehensions.)\n",
"\n",
"## Spectrum of a graph\n",
"\n",
"The *spectrum* of a graph is the set of eigenvalues of the adjacency\n",
"matrix of the graph. The *spectrum* of the Coxeter graph is\n",
"\n",
"- $-1-\\sqrt{6}$ with multiplicity 6,\n",
"- $-1$ with multiplicity 7,\n",
"- $\\sqrt{2}-1$ with multiplicity 6,\n",
"- $2$ with multiplicity 8,\n",
"- $3$ with multiplicity 1.\n",
"\n",
"It turns out that no other graph has this same spectrum (in this case,\n",
"we say that the graph *is determined by its spectrum* ).\n",
"\n",
"**Exercise:** Test to see that you correctly constructed the Coxeter\n",
"graph in the previous exercise. That is, compute the `adjacency matrix`\n",
"of the Coxeter graph, find the `eigenvalues` of the adjacency matrix,\n",
"and then compare them with the above."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** The command `graphs(n)` generates all the graphs on $n$\n",
"vertices (up to isomorphism). Use this command to test whether there are\n",
"two graphs with less than 7 vertices that have the same spectrum."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Birthday Paradox\n",
"\n",
"In the following exercises, we will use Sage to estimate the probability\n",
"that in a group of $n$ people, two of them will have the same birthday.\n",
"\n",
"`Exercise:` Using the command `graphs.RandomGNP`, create a function that\n",
"returns a graph with $n$ vertices and where the probability that any two\n",
"of the vertices is connected is 1/365."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** Plot a graph `g` created by your function above using the\n",
"`g.plot(layout='circular')`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** Create 100 random graphs (using your above function) with\n",
"$n=23$ vertices. What ratio of them contains an edge?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(*hint:* for a graph `g`, the command `g.num_edges()` returns the number\n",
"of edges in `g`.)\n",
"\n",
"**Exercise:** Repeat the above exercise with $n=57$ vertices."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** Repeat the above exercises for all the values\n",
"$1, 2, ..., 120$. Plot the results using a line graph."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "sagemath",
"name": "sagemath"
}
},
"nbformat": 4,
"nbformat_minor": 2
}