SM286D · Introduction to Applied Mathematics with Python · Spring 2020 · Uhan
\n",
"\n",
"
Lesson 12.
\n",
"\n",
"
Graph theory with Python
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## This lesson..."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Introduction to graph theory\n",
"\n",
"- Using NetworkX to compute measures of centrality/influence\n",
" - Degree centrality\n",
" - Closeness centrality\n",
" - Betweenness centrality"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Introduction to graph theory"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- __Graphs__ model how various entities are connected.\n",
"\n",
"- Graphs have numerous and diverse applications throughout operations research, including in utility planning, job scheduling, task assignment, and modeling networks. \n",
"\n",
"- Graphs are a central focus of SM342, our class in discrete mathematics (a math or breadth elective in the Operations Research major). "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- A __graph__ $G = (V,E)$ consists of \n",
" - a set of __vertices__ $V$ (also called __nodes__), and \n",
" - a set $E$ of pairs of vertices. \n",
" \n",
"- In an __undirected__ graph, each pair $(v_1, v_2) \\in E$ is an __edge__ with endpoints $v_1$ and $v_2$.\n",
" - For edges, direction doesn't matter: the edges $(v_1,v_2)$ and $(v_2,v_1)$ are the same.\n",
" - We use line segments to draw edges.\n",
" \n",
"- In a __directed__ graph, each pair $(v_1, v_2) \\in E$ is an __arc__ that starts at $v_1$ and ends at $v_2$.\n",
" - For arcs, direction matters: the arcs $(v_1, v_2)$ and $(v_2, v_1)$ are NOT the same.\n",
" - We use arrows to draw arcs.\n",
"\n",
"- Figure 1 shows an example of an undirected graph $G$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"
Figure 1. The graph of $G$.
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Example.__ Is $(0, 1)$ an edge of $G$? Is $(0, 2)$ an edge of $G$?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"_Write your notes here. Double-click to edit._"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- For this lesson, we will focus on undirected graphs — we will simply call them graphs."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- We often describe a graph by its __adjacency matrix__ $A$: a square matrix with one row and one column for each node, where\n",
"\n",
"\\begin{equation*}\n",
"A_{ij} = \\begin{cases}\n",
"1 & \\text{if } (i, j) \\text{ is an edge of } G\\\\\n",
"0 & \\text{otherwise}\n",
"\\end{cases}\n",
"\\end{equation*}\n",
"\n",
"- The adjacency matrix for $G$ in Figure 1 is \n",
"\\begin{equation*}\n",
"A = \\begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\\\\n",
"1 & 0 & 1 & 1 & 0 \\\\\n",
"0 & 1 & 0 & 1 & 0 \\\\\n",
"0 & 1 & 1 & 0 & 1 \\\\\n",
"0 & 0 & 0 & 1 & 0 \\end{bmatrix}.\n",
"\\end{equation*}\n",
"\n",
"\n",
"- The __degree__ of a node $v$ is the number of edges that contain $v$.\n",
" - In Figure 1, you can see the degree of a node by seeing how many edges come out of it."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Example.__ What is the degree of node 3 in graph $G$ in Figure 1?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"_Write your notes here. Double-click to edit._"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- A __path__ is a sequence of nodes $(v_1,v_2,v_3,\\ldots,v_n)$ such that subsequent nodes $(v_i,v_{i+1})$ form an edge in $G$. \n",
"\n",
"- The __length of a path__ is the number of edges it contains. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Example.__ Consider the graph $G$ in Figure 1. Give an example of a path from node 0 to node 4. What is its length? What is the shortest path from node 0 to node 4?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"_Write your notes here. Double-click to edit._"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Using NetworkX to compute measures of centrality/influence"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- In today's lesson and Project 5, we will be using Python to compute measures of centrality/influence in social networks. \n",
"\n",
"- Consider the following example."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Example.__ Suppose Ann, Dan, Dave, Eve, Jay, Jen, Joe, and Sara are all on Facebook. Ann is friends with Eve and Jay; Dan is friends with Dave, Jen, Joe, and Sara; Dave is friends with Jay, Joe, and Dan; Eve is friends with Ann and Jay; Jay is friends with Ann, Eve, Dave, and Sara; Jen is friends with Dan, Dave, and Sara; Joe is friends with Dan and Dave; and Sara is friends with Dan, Jay, and Jen. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- This is a lot of words to explain the connections between these individuals. \n",
"\n",
"- It might be better to illustrate their relationships with a graph. See Figure 2 below."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"
Figure 2. Social network example.
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- __[NetworkX](https://networkx.github.io)__ is a Python package that lets us work with graphs.\n",
" - [Here is the NetworkX documentation.](https://networkx.github.io/documentation/stable/index.html)\n",
"\n",
"- Let's start with importing `networkx`:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"import networkx as nx"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Next we define an empty graph `G`, followed by the list of nodes and edges:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"# Define an empty graph\n",
"G = nx.Graph()\n",
"\n",
"# Define the list of nodes\n",
"nodes = ['Ann', 'Dan', 'Dave', 'Eve', 'Jay', 'Jen', 'Joe', 'Sara']\n",
"\n",
"# Define the list of edges\n",
"# Note that each edge is a list\n",
"edges = [['Jay', 'Dave'], ['Sara', 'Dan'], ['Dan', 'Jen'], ['Eve', 'Ann'],\n",
" ['Sara', 'Jen'], ['Jay', 'Ann'], ['Joe', 'Dave'], ['Jay', 'Eve'],\n",
" ['Jen', 'Dave'], ['Jay', 'Sara'], ['Joe', 'Dan'], ['Dan', 'Dave']]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- We can add `nodes` and `edges` to the graph `G` like this:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"# Add nodes to G\n",
"G.add_nodes_from(nodes)\n",
"\n",
"# Add edges to G\n",
"G.add_edges_from(edges)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Now that we've defined the network, a natural question to ask is: \n",
"\n",
"
Which individual is the most central/influential of the group?
\n",
"\n",
"- There are many ways to measure this. We will discuss three of them here."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Degree centrality"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Recall that the degree of a node is the number of edges containing that node.\n",
"\n",
"- Figure 3 below shows our social network example with the degree of each node listed next to it."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"
Figure 3. Social network example with node degrees.
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- The __degree centrality__ of a node is defined as the node's degree divided by the maximum possible degree. \n",
"\n",
"- The maximum possible degree is given by $N-1$, where $N$ is the total number of nodes in the graph.\n",
" - For our example, the maximum possible degree is 7. \n",
"\n",
"- Figure 4 below shows our social network with the degree centrality of each node listed next to it."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"
Figure 4. Social network example with node degree centrality values.
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- To compute the degree centrality of each node in a graph using NetworkX, we can do this:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{'Ann': 0.2857142857142857, 'Dan': 0.5714285714285714, 'Dave': 0.5714285714285714, 'Eve': 0.2857142857142857, 'Jay': 0.5714285714285714, 'Jen': 0.42857142857142855, 'Joe': 0.2857142857142857, 'Sara': 0.42857142857142855}\n"
]
}
],
"source": [
"# Compute degree centrality for each node\n",
"degree_centrality = nx.degree_centrality(G)\n",
"\n",
"# Check our work\n",
"print(degree_centrality)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- We see that `nx.degree_centrality()` returns a dictionary.\n",
"\n",
"- Let's print this information nicely:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Ann has degree centrality 0.286.\n",
"Dan has degree centrality 0.571.\n",
"Dave has degree centrality 0.571.\n",
"Eve has degree centrality 0.286.\n",
"Jay has degree centrality 0.571.\n",
"Jen has degree centrality 0.429.\n",
"Joe has degree centrality 0.286.\n",
"Sara has degree centrality 0.429.\n"
]
}
],
"source": [
"# Print degree centrality for each node\n",
"for key, value in degree_centrality.items():\n",
" print(f'{key} has degree centrality {value:.3f}.')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Closeness centrality"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Another way to measure the centrality/influence of a member of the network is _closeness centrality_.\n",
"\n",
"- In order to define closeness centrality, we begin by looking at the _shortest path distance_ between two nodes. \n",
"\n",
"- The __shortest path distance__ between two nodes is simply the length of a shortest path between the two nodes.\n",
"\n",
"- Let's use Jay as the starting node, and find the shortest path from Jay to all the other nodes in the graph. \n",
" - This process is illustrated in Figure 5 below."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"
Figure 5. Finding shortest paths between nodes in our social network example.
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Next we find the sum of the shortest path distances from Jay to all the other nodes:\n",
"\n",
" \\begin{equation*}\n",
" 1 + 1 + 1 + 2 + 2 + 2 + 1 = 10\n",
" \\end{equation*}\n",
"\n",
"- The __closeness__ $c$ of a node measures how close it is to every other node.\n",
"\n",
"- The closeness of the node Jay is given by\n",
"\n",
" \\begin{equation*}\n",
" c(\\text{Jay}) = \\frac{1}{\\sum_{i} d(i,\\text{Jay})} = \\frac{1}{10}\n",
" \\end{equation*}\n",
"\n",
" where $d(i,\\rm{Jay})$ is the shortest path distance from node $i$ to node $\\rm{Jay}$.\n",
"\n",
"- The __closeness centrality__ of the node Jay is \n",
"\n",
" \\begin{equation*}\n",
" C(\\text{Jay}) = (N-1)c(\\text{Jay})\n",
" \\end{equation*}\n",
" \n",
" where $N$ is the total number of nodes in the graph. \n",
"\n",
"- For our example, the closeness centrality of node Jay is\n",
"\n",
" \\begin{equation*}\n",
" C(\\text{Jay}) = (N - 1) c(\\text{Jay}) = (8-1) \\frac{1}{10} = \\frac{7}{10}\n",
" \\end{equation*}\n",
"\n",
"- Figure 6 below shows our social network example with the closeness centrality of each node listed next to it."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"
Figure 6. Closeness centrality values for our social network example.
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- To compute the closeness centrality of each node in a graph using NetworkX, we can do this:"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{'Ann': 0.4666666666666667, 'Dan': 0.5833333333333334, 'Dave': 0.7, 'Eve': 0.4666666666666667, 'Jay': 0.7, 'Jen': 0.5384615384615384, 'Joe': 0.5, 'Sara': 0.6363636363636364}\n"
]
}
],
"source": [
"# Compute closeness centrality for each node\n",
"closeness_centrality = nx.closeness_centrality(G)\n",
"\n",
"# Check our work\n",
"print(closeness_centrality)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Like `nx.degree_centrality()`, `nx.closeness_centrality()` also returns a dictionary.\n",
"\n",
"- Let's print this information nicely:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Ann has closeness centrality 0.467.\n",
"Dan has closeness centrality 0.583.\n",
"Dave has closeness centrality 0.700.\n",
"Eve has closeness centrality 0.467.\n",
"Jay has closeness centrality 0.700.\n",
"Jen has closeness centrality 0.538.\n",
"Joe has closeness centrality 0.500.\n",
"Sara has closeness centrality 0.636.\n"
]
}
],
"source": [
"# Print closeness centrality for each node\n",
"for key, value in closeness_centrality.items():\n",
" print(f'{key} has closeness centrality {value:.3f}.')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Betweenness centrality"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Yet another way to measure the centrality/influence of a member of the network is _betweenness centrality_. \n",
"\n",
"- The __betweenness centrality__ of a node measures how often it is on the shortest path between two other nodes. \n",
"\n",
"- This is illustrated in Figure 7 below where we are looking at shortest paths from Dave to other nodes. \n",
" - We see that Jay is on the shortest path from Dave to Eve and Dave to Sara, but Jay is not on the shortest path from Dave to Dan."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"
Figure 7. Betweenness illustration for our social network example.
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- To compute the betweenness centrality of each node in a graph using NetworkX, we can do this:"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{'Ann': 0.0, 'Dan': 0.08730158730158728, 'Dave': 0.30952380952380953, 'Eve': 0.0, 'Jay': 0.492063492063492, 'Jen': 0.015873015873015872, 'Joe': 0.0, 'Sara': 0.14285714285714285}\n"
]
}
],
"source": [
"# Compute betweenness centrality for each node\n",
"betweenness_centrality = nx.betweenness_centrality(G)\n",
"\n",
"# Check our work\n",
"print(betweenness_centrality)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Yup, `nx.betweenness_centrality()` also returns a dictionary.\n",
"\n",
"- Let's print this information nicely:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Ann has betweenness centrality 0.000.\n",
"Dan has betweenness centrality 0.087.\n",
"Dave has betweenness centrality 0.310.\n",
"Eve has betweenness centrality 0.000.\n",
"Jay has betweenness centrality 0.492.\n",
"Jen has betweenness centrality 0.016.\n",
"Joe has betweenness centrality 0.000.\n",
"Sara has betweenness centrality 0.143.\n"
]
}
],
"source": [
"# Print betweenness centrality for each node\n",
"for key, value in betweenness_centrality.items():\n",
" print(f'{key} has betweenness centrality {value:.3f}.')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Figure 8 below shows our social network example with the betweenness centrality of each node listed next to it."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"
Figure 8. Betweenness centrality values for our social network example.
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### So... who is the most central/influential of the group?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- As usual, the answer is, \"it depends\". \n",
"\n",
"- In particular, it depends on which measure you want to use.\n",
"\n",
"- The table below summarizes the results from the three measures we explored above.\n",
"\n",
"| Degree Centrality | Closeness Centrality | Betweenness Centrality |\n",
"|:--- |:--- |:--- |\n",
"| 1. Dan - 0.571 | 1. Dave - 0.700 | 1. Jay - 0.492 |\n",
"| 2. Dave - 0.571 | 2. Jay - 0.700 | 2. Dave - 0.310 |\n",
"| 3. Jay - 0.571 | 3. Sara - 0.636 | 3. Sara - 0.143 |"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Classwork"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Problem 1.__ In the code below, we first define the adjacency matrix of a graph with NumPy. Note the way that we filled in a different row of $A$ on each of lines 6 through 10. For example, on line 7 we filled row 1 by setting $A_{10} = A_{12} = A_{13} = 1$.\n",
"\n",
"On line 13, we use the adjacency matrix $A$ to define the graph $G$. Note that this is different from how we defined a graph in the lesson above. We get a list of the nodes of $G$ on line 14 and a list of the edges of $G$ on line 15."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"import networkx as nx\n",
"\n",
"# Define adjacency matrix\n",
"A = np.zeros([5,5])\n",
"A[0, [1]] = 1\n",
"A[1, [0, 2, 3]] = 1\n",
"A[2, [1, 3]] = 1\n",
"A[3, [1, 2, 4]] = 1\n",
"A[4, [3]] = 1\n",
"\n",
"# Define graph using NetworkX\n",
"G = nx.Graph(A)\n",
"nodes_list = list(G.nodes)\n",
"edges_list = list(G.edges)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Print the lists of nodes and edges to the screen. Make sure you understand why they look the way they do."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Nodes: [0, 1, 2, 3, 4]\n",
"Edges: [(0, 1), (1, 2), (1, 3), (2, 3), (3, 4)]\n"
]
}
],
"source": [
"print(f'Nodes: {nodes_list}')\n",
"print(f'Edges: {edges_list}')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Problem 2.__ You can draw a graph `G` with `nx.draw_networkx(G)`. Use this to draw the graph `G` defined in Problem 1. Do you see what you expected?\n",
"\n",
"You may need to import the `matplotlib.pyplot` package as `plt` to get the drawing to work. \n",
"Take a look at the [documentation](https://networkx.github.io/documentation/stable/index.html) if you need to. Try calling `nx.draw_networkx()` with the keyword arguments `with_labels=True` and `font_color='w'`. "
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt\n",
"nx.draw_networkx(G, with_labels=True, font_color='w')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Problem 3.__ The graph `G` you defined in Problem 1 has a variety of methods and attributes. For example, the attribute `G.nodes` is a list-like object that contains all the nodes of `G`. As another example, the method `G.degree()` returns a data structure that contains the degree for each vertex: in particular, you can access the degree of vertex $j$ with `G.degree()[j]`. Use a `for` loop to print a sentence like \n",
"\n",
"```\n",
"The degree of vertex 0 is 1.\n",
"``` \n",
"\n",
"for each vertex in `G`. "
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The degree of vertex 0 is 1.\n",
"The degree of vertex 1 is 3.\n",
"The degree of vertex 2 is 2.\n",
"The degree of vertex 3 is 3.\n",
"The degree of vertex 4 is 1.\n"
]
}
],
"source": [
"for n in G.nodes: \n",
" print(f'The degree of vertex {n} is {G.degree()[n]}.')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Problem 4.__\n",
"You can find the vertices connected to vertex `v` in graph `G` with `G.neighbors(v)`. However, it returns a strange (`dict_keyiterator`) object. You can call `list()` on the result of `G.neighbors(v)` to turn it into something readable. \n",
"\n",
"Print the list of neighbors of vertex 2."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The neighbors of node 2 are the elements of the list [1, 3].\n"
]
}
],
"source": [
"two_neighbors = list(G.neighbors(2))\n",
"print(f'The neighbors of node 2 are the elements of the list {two_neighbors}.')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Problem 5.__\n",
"You can find the length of a shortest path from node 0 to node 4 with \n",
"\n",
"```python\n",
"nx.shortest_path_length(G, source=0, target=4)\n",
"```\n",
"\n",
"In today's lesson, we called this the __shortest path distance__ between node 0 and node 4. The method `nx.shortest_path()` produces the path itself. \n",
"\n",
"Modify the code in Problem 1 to construct the adjacency matrix `B` for a new graph with edges (0, 1), (0, 3), (1, 2), (2, 3), and (3, 4). Let `H` be the graph with adjacency matrix `B`. Find the shortest path length between 1 and 4. Use the `nx.all_shortest_paths()` method to find all the shortest paths from node 1 to node 4 in `H`. Read the NetworkX documentation if you're not sure how to use `nx.all_shortest_paths()`."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The shortest path distance from node 1 to node 4 is 3\n",
"The shortest paths from node 1 to node 4 are: \n",
"[1, 0, 3, 4]\n",
"[1, 2, 3, 4]\n"
]
}
],
"source": [
"# Define adjacency matrix\n",
"B = np.zeros([5,5])\n",
"B[0, [1, 3]] = 1\n",
"B[1, [0, 2]] = 1\n",
"B[2, [1, 3]] = 1\n",
"B[3, [0, 2, 4]] = 1\n",
"B[4, [3]] = 1\n",
"\n",
"# Define graph using adjacency matrix\n",
"H = nx.Graph(B)\n",
"\n",
"# Compute shortest path information\n",
"print(f'The shortest path distance from node 1 to node 4 is {nx.shortest_path_length(H, source=1, target=4)}')\n",
"print(f'The shortest paths from node 1 to node 4 are: ')\n",
"for i in nx.all_shortest_paths(H, source=1, target=4):\n",
" print(i)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Problem 6.__\n",
"The graph `H` from the last problem is really a graph of friendships among five people. Create a `names` dictionary that maps node numbers as keys to names as values as follows: Suzie (node 0), Tom (node 1), Jamal (node 2), Heather (node 3), and Nitish (node 4).\n",
"\n",
"In `H`, we see that Suzie is friends (separately) with Tom and Heather. Print the two shortest paths from Tom to Nitish, using names rather than node numbers. Do this without hard coding your answer (i.e. refer to the `names` dictionary rather than writing names directly in your code). One of your paths should be: \n",
"\n",
"```\n",
"Tom - Jamal - Heather - Nitish\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The shorest paths are: \n",
"Tom - Suzie - Heather - Nitish\n",
"Tom - Jamal - Heather - Nitish\n"
]
}
],
"source": [
"# Define dictionary that maps node numbers to names\n",
"names = {0: 'Suzie', 1: 'Tom', 2: 'Jamal', 3: 'Heather', 4: 'Nitish'}\n",
"\n",
"# Print all shortest paths from Tom to Nitish,\n",
"# using names rather than node numbers\n",
"print('The shorest paths are: ')\n",
"for path in nx.all_shortest_paths(H, source=1, target=4):\n",
" \n",
" # Create list of names corresponding to path\n",
" # I'm using a list comprehension here, but \n",
" # you can also use a for loop with .append()\n",
" path_names = [names[n] for n in path]\n",
"\n",
" # Print the list of names, using .join() to format them nicely\n",
" # See Problem 1 from Lesson 10 for more information about .join()\n",
" print(' - '.join(path_names))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Bonus classwork\n",
"\n",
"The following problems are included as bonus material. Work on them only after completing the problems above."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Problem 7 (Directed graphs).__\n",
"Directed graphs are used to model many different situations in operations research. There is a popular OR textbook, _Network Flows_ (by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin), devoted to the topic and USNA often offers an elective course in this area. \n",
"\n",
"Network flow problems are defined on _directed_ graphs $(V, E)$: the set $E$ consists of arcs $(v_1, v_2)$ that allow flow from vertex $v_1$ to vertex $v_2$. Each vertex has an associated supply or demand, and each edge has an associated capacity and cost.\n",
"\n",
"One type of network flow problem is the _maximum flow of minimum cost problem_. In this problem, we want to move as much flow along edges from a source vertex to a destination vertex, leaving nothing behind at any other vertex, while respecting the capacity constraints on the edges, and at minimum cost. The decision variables in this problem determine how much to flow along each edge of the network.\n",
"\n",
"The code below solves a maximum flow of minimum cost problem using NetworkX on a directed graph (note the use of `DiGraph()`) where vertex 1 is the source and vertex 7 is the destination. On paper, draw a picture of the network, and label each edge with capacity/cost/flow, where flow comes from the solution to the problem. "
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{1: {2: 12, 3: 16}, 2: {3: 0, 6: 14}, 3: {4: 6, 5: 10}, 6: {5: 11, 7: 3}, 4: {2: 2, 5: 4}, 5: {7: 25}, 7: {4: 0}}\n",
"373\n"
]
}
],
"source": [
"# Define empty directed graph\n",
"G = nx.DiGraph()\n",
"\n",
"# Add edges to directed graph\n",
"# Note that NetworkX will add the corresponding nodes automatically\n",
"# Also note that some edges do not have 'capacity' defined: \n",
"# read the documentation to understand what this means.\n",
"G.add_edges_from([(1, 2, {'capacity': 12, 'weight': 4}),\n",
" (1, 3, {'capacity': 20, 'weight': 6}),\n",
" (2, 3, {'capacity': 6, 'weight': -3}),\n",
" (2, 6, {'capacity': 14, 'weight': 1}),\n",
" (3, 4, {'weight': 9}),\n",
" (3, 5, {'capacity': 10, 'weight': 5}),\n",
" (4, 2, {'capacity': 19, 'weight': 13}),\n",
" (4, 5, {'capacity': 4, 'weight': 0}),\n",
" (5, 7, {'capacity': 28, 'weight': 2}),\n",
" (6, 5, {'capacity': 11, 'weight': 1}),\n",
" (6, 7, {'weight': 8}),\n",
" (7, 4, {'capacity': 6, 'weight': 6})])\n",
"\n",
"# Find the max flow of min cost from vertex 1 to vertex 7\n",
"# Read the documentation to understand the structure of the \n",
"# dictionary that nx.max_flow_min_cost returns.\n",
"min_cost_flow = nx.max_flow_min_cost(G, s=1, t=7)\n",
"print(min_cost_flow)\n",
"\n",
"# Compute the cost of the max flow of min cost\n",
"min_cost = nx.cost_of_flow(G, min_cost_flow)\n",
"print(min_cost)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Problem 8 (Eulerian graphs)__. A path in an undirected graph $G$ is called _Eulerian_ if it uses all of the edges of $G$ precisely once. A path where the initial vertex and the last vertex are the same is called a _cycle_ or a _circuit_. A graph $G$ that has an Eulerian cycle (an Eulerian path that is also a cycle) is called an *Eulerian graph*, named after Leonhard Euler (look up the Königsberg Bridge Problem if you are curious about how such graphs first appeared). \n",
"\n",
"Define a graph $P$ with six vertices 0, 1, 2, 3, 4 and 5 and edges (0, 1), (0, 3), (1, 2), (2, 3), (3, 4), (3, 5), (4, 5). Draw $P$ using NetworkX. Then convince yourself that $P$ is Eulerian. \n",
"\n",
"The code \n",
"\n",
"```\n",
"list(nx.eulerian_circuit(G))\n",
"```\n",
"\n",
"produces an Eulerian cycle for a graph `G` if one exists. Use this code to check your work. Find the degree of each vertex in $P$. The degrees all share a common property; can you guess what it is? Make your guess and then check out the cell below for a fun fact about Eulerian graphs."
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Eulerian circuit: [(0, 3), (3, 5), (5, 4), (4, 3), (3, 2), (2, 1), (1, 0)]\n",
"Degree of vertex 0: 2\n",
"Degree of vertex 1: 2\n",
"Degree of vertex 2: 2\n",
"Degree of vertex 3: 4\n",
"Degree of vertex 4: 2\n",
"Degree of vertex 5: 2\n",
"All the degrees are even!\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3dd1gU99YH8O8sS1NYiYoBSyQRARsqEMUYWgRRmoKKiliCEa4aRWNeG3bFkmvsEgNG7IoSRSCI9KKGGEAxURC4iQWvKBoFVJayzPuHF6Kh6+7OlvN5Hp8n2Zmd/RLCcfjNmTMMy7IghBAiHTyuAxBCiDKhoksIIVJERZcQQqSIii4hhEgRFV1CCJEifnMbO3fuzBoYGEgpCiGEKIasrKzHLMvqNrat2aJrYGCAzMxMyaQihBAFxTDMnaa20fICIYRIERVdQgiRIiq6hBAiRVR0CSFEiqjoEkKIFFHRJYQQKaKiSwghUkRFlxBCpIiKLiGESFGzd6QRQmTb4+eVCM8qQl5xGcqENRBo8GGiJ8AE8+7opKXOdTzSCCq6hMihnHvPsDelEKn5JQCAypra+m0a/GJsT8iHrbEu5tgYYmAPHa5ikkZQ0SVEzhzNuI3AmDwIa0Ro7Glbwv8V4LibD5GW/xgBTibwtjSQbkjSJCq6hMiRVwU3FxXVtS3uy7JARbUIgTG5AECFV0bQhTRC5ETOvWcIjMlrVcF9XUV1LQJj8nC96JmEkpG2oDNdQuTE3pRCCGtEb7ympsLD+jH9MdywE3TaqeHukxf45sItpPxvrbeOsEaEoJRC7PO2kGZk0ggquoTIgcfPK5GaX9JgDVeFx+BBaQUmBWfgfmkF7Iy7YI+XGUbtSEPRs4r6/VgWSL5VgifPK6mrgWO0vECIHAjPKmr09YpqEXYkFqDoWQVYFkjKe4R7f71E/24dGuzLAAjPbvw4RHqo6BIiB/KKy95oC2tKZy01fNS5PQoelTfYJqypRd6Dhq8T6ZLq8gI1chPydsqENS3uw+cx2DFxMH7MLsJ/Sl40cZxqcUcjbSSVokuN3IS8G4FG8z+qDANs9xyEalEtVkXeaOY4quKORtpI4kWXGrkJeXcmegKo84ubXGL4xsMUnbXUMePgFdTUNvKDBkCDz4OJvrYkY5JWkOia7t+N3I0X3Ne93sh9NOO2JGMRInfGm3dvclvg2P4w7KKFmYd/bXbdlwUw3qzp4xDpkFjRbamR26BTO9xaNwrbPQe98To1chPSUGctdZjpawC1b/48ddPRxJShPdFXX4Bfl9vjxhpH3FjjiDGDur6xH8MAdsa6dO1EBkhseaGxRu7XrRvTHzlFpY1uo0ZuQv7GsixCQkKQtHs/BO6rUP3ab433n1XAYNlPLR5Dg6+CObaGEkxJWksiRbepRu46rqb6KKuoRvajp+jZqX2D7dTITcgrT58+ha+vLwoKCpB69iQyn2m0evZCHU1VHgKcTGDanS5SywKJLC801cgNAFrqfCx0MMKGn3KbPQY1chNld+nSJQwePBjdunVDRkYGTExeXWQOcOoDTVUVMEzz72cAsNWVmG4qoIvTMkQiRbe5Ru5FDkY49es9FJcJmz0GNXITZSUSibB+/XqMGzcOe/bswY4dO6ChoVG/3dvSAGG+lnDs+z7U+Txo8N/8Mdbg86DO58Gx3/uY30+E7xZ5obi4WNpfBmmCRJYXmmrk7qsvwHDDznDend7K41AjN1EuRUVF8Pb2Bo/HQ3Z2Nrp27drofqbddbDP2wJPnlciPLsIeQ/KUSashkBDFSb62hhvVnfDkQXK79zA2LFjkZycDE1NTel+QaQBiRTdphq5LT/qiO7vaeLyks8AAO3U+FDhMejd5VO47LnYyHGokZsoj3PnzsHPzw/+/v5YvHgxVFRUWnxPJy11+Fn3anaf1atXIy8vDzNnzsSxY8fAtLQuQSRKIkW3qUbu41fuIirnQf2/z7L6CN3f08SKc783OAY1chNlUVFRgf/7v/9DTEwMIiIiYGlpKdbjMwyD0NBQ2NraYsOGDVi5cqVYj0/aRiJruk01cgura1HyvLL+z8uqGlTW1OKvF1UN9qVGbqIMbt68iaFDh6KkpATZ2dliL7h1NDU1ERERgf379+PUqVMS+QzSOhIpup211GFjpNvi1dUdiQVYeOpaww21tRj8vhq1ixGFxbIsgoODYWNjA39/f5w8eRI6OpJt6dLX18e5c+cwd+5c/PrrrxL9LNI0id2RNtfWEBr8ltekGqOqwiB571Js2bIFIlHTN1gQIo+ePn0KT09PBAUFIS0tDTNnzpTaOuugQYMQEhICd3d3FBVRSyYXJFZ0B/bQQYCTCTRV2/YRmqo8rHbrj1/On0ZMTAxsbW3x559/SiglIdJV13vbtWtXZGRkoE+fPlLPMHbsWMybNw9ubm548aLxEZBEciQ68KZNjdwMoKmqggCnPvC2NICBgQGSkpIwZswYDBkyBKGhoWBbmppDiIx6vfd29+7d2Llz5xu9t9K2ePFimJqaYurUqaitbduDLsm7YZorZBYWFmxmZuY7f8j1omcISilE8q0SMPh7nCPwqkuBxathHHNsDRu9VfH69euYOnUqPvroIwQHB0NXV/edMxEiLa/33h45cgTdunXjOhIAoLKyEg4ODvj000+xceNGruMoFIZhsliWbXR4jFQe11PXyH15yWdY6GAE1ftXYaGvDvdB3bDQwQiXl3yGfd4WTd4bbmpqiitXrsDIyAgDBw5EdHS0NGIT8s7OnTsHc3NzjBw5EvHx8TJTcAFAXV0dZ86cQVhYGA4fPsx1HOXBsmyTf8zNzVlJMDY2Zm/cuPFW701NTWV79uzJzpo1iy0vLxdzMkLE4+XLl+zcuXNZAwMD9vLly1zHadaNGzdYXV1dNj09nesoCgNAJttEXeXkwZSVlZVQV3+7djBra2tcv34d1dXVGDRoEH7++WcxpyPk3bzee3v16lUMGzaM60jN6tu3Lw4fPowJEybQRWspkLuiCwACgQChoaH45ptv4O7ujhUrVqCqquENFoRIE8tB7624jBo1CsuWLYOrqyvKysq4jqPQOCu64rhy6+HhgWvXrtWfTeTmNj8ukhBJ4bL3VlzmzZsHKysrTJ48mfrjJUguz3Rfp6enh+joaPj6+sLKygq7du2iFhgiVbLQeysODMNg165dqKysxNdff811HIUl90UXePU/i5+fH37++WccP34cjo6OdLcNkThZ670VB1VVVZw+/erGpODgYK7jKCSpF93a2lqIRCKoqop/bGPv3r1x8eJFWFtbw8zMDCdPnhT7ZxACvOq9HTFiBJKTk5GVlQVXV1euI4nNe++9h+joaKxcuRJJSUlcx1E4Ui+6lZWVUFNTk9h6F5/Px8qVKxETE4M1a9Zg8uTJePr0qUQ+iygnWe69FZfevXvj5MmTmDx5MvLz87mOo1A4KbriXFpoioWFBbKzs6GrqwtTU1MkJCRI/DOJYquoqMCXX36JBQsWICIiAsuXL2/VoHF5ZWdnhw0bNsDFxYVOXMRIYYsuALRr1w67du3CDz/8gBkzZsDf3x8VFRVS+WyiWOSt91ZcZs2aBRcXF4wfPx7V1fT4LHFQ6KJbZ+TIkbh+/TqKi4thZmaGrKwsqX4+kV/y3HsrLv/+97+hqamJefPm0dApMVCKogsAHTt2xMmTJ7Fy5UqMHj0agYGBqKlp/AGahACK0XsrDioqKjh+/DguXbqEXbt2cR1H7ilN0QVetZZ5eXkhKysLSUlJsLa2RmFhISdZiGxTlN5bcREIBIiKisLmzZtx/vx5ruPINaUqunV69OiB+Ph4TJw4EZaWlggJCaFfmwgAxey9FRcDAwOEh4dj+vTp+P33hg+TJa2jlEUXAHg8Hvz9/ZGWlobvvvsObm5uKC4u5joW4ZAi996Ky/Dhw7Ft2za4ubmhpKSE6zhySWmLbp2+ffsiIyMDpqamGDRoECIiIriORDigDL234uLt7Y3JkyfD3d0dlZWVXMeRO0pfdAFATU0NgYGB+PHHH7Fo0SL4+PjQpCUloWy9t+Kyfv166OnpwdfXl5bm2oiK7muGDx+Oa9euQUVFBYMGDUJ6ejrXkYgEKWvvrTjweDwcOnQIv//+O7Zs2cJ1HLki9aIrFApltugCgLa2NkJCQrBjxw54enpi6dKl9CuUgqHeW/Fo3749IiMjsWfPHpw9e5brOHKDznSb4ObmhpycHOTm5mLo0KF0tVZB1PXe7t27V6l7b8WlW7duiIiIgK+vL65evcp1HLlARbcZXbp0QUREBObPnw87Ozt8++23NKtXjl2+fBmDBw+Gvr4+fvnlF6XvvRUXCwsLfPfddxgzZgwePHjAdRyZx0nRlae+R4Zh4OPjg19++QVnz57FiBEjcPfuXa5jkTYQiUTYsGEDPDw8sHv3buzatUuu/h+UB+PHj4evry/GjBlD801aQGe6rfTRRx8hNTUVjo6OMDc3x5EjR+iqrRyo671NTEyk3lsJCwgIQO/evTFjxgz6jbAZVHTbQEVFBUuXLkVcXBw2b94MT09PPHnyhOtYpAl1vbcODg5ISEig3lsJYxgGP/zwA+7evYu1a9dyHUdmUdF9C4MHD0ZWVhY++OADmJqaIjY2lutI5DVCoRDz5s3DggULcPbsWQQEBFDvrZRoaGggIiIChw4dwokTJ7iOI5Oo6L4lDQ0NfPvttzhy5Aj8/Pwwd+5cvHjxgutYSu/mzZsYMmQIHj58iKtXr+KTTz7hOpLSef/99xEZGYn58+fjl19+4TqOzKGi+44+++wz5OTkoKysDGZmZrhy5QrXkZQSy7IICQmp770NCwuj3lsOmZqa4sCBA/Dw8KALz//Al/YHKlrRBQAdHR0cOXIEp06dgqurK2bPno2AgACJPHyTNPT06VP4+voiPz8faWlp1AomI1xdXZGfnw83NzdcvHgRWlpaXEeSCXSmK0aenp7Izs7Gzz//jOHDh+PWrVtcR1J41Hsr27766itYWFhgypQpEIlEXMeRCVR0xaxbt26IjY3F9OnTMXz4cAQFBVFrmQRQ7618YBgGQUFBKC0txbJly7iOIxOo6EoAwzCYO3cuLl26hIMHD2L06NH473//y3UshUG9t/JFTU0NP/74I86cOYPQ0FCu43COiq4EGRsb49KlS7C0tMTgwYMRHh7OdSS5R7238qlTp06Ijo7GkiVLkJaWxnUcTlHRlTBVVVWsWbMGkZGRWL58OaZNm4bS0lKuY8kd6r2VfyYmJjh27Bg8PT3xn//8h+s4nKGiKyVDhw7F1atXoaWlBVNTU6SkpHAdSW5Q763icHBwwKpVq+Dq6qq0Jx9UdKWoffv2CAoKwr59+zBlyhQsWrQIQqGQ61gyi3pvFdOcOXMwYsQIeHp6oqamhus4UkdFlwOjR49GTk4O7ty5AwsLC1y7do3rSDKnbu7tnj17aO6tAtq+fTsAYOHChRwnkT56cgRHOnfujNOnT2PJkiVwcHDAli1bqI/xf6j3VvHx+XyEhYUhISEBQUFBXMeRKjrT5RDDMJg6dSoyMzMRExMDW1tb/Pnnn1zH4gz13ioXHR0dREdHY926dYiPj+c6jtRQ0ZUBPXv2RFJSEsaMGYMhQ4YgNDRU6W6ooN5b5dSrVy+cOnUK3t7eyMvL4zqOVNCTI2SEiooKvv76ayQlJWHHjh1wd3fHo0ePuI4lFdR7q9ysra2xadMmuLq6KsV8ajrTlTEDBgzAlStXYGxsjIEDByIqKorrSBJT13vr7+9PvbdKzsfHB2PHjsW4ceNQVVXFdRyJoqIrg9TV1bFlyxaEhYVh/vz58PX1xfPnz7mOJVav995eu3aNem8JNm/ejA4dOmDOnDkKvbwm1aLLsiyqqqqgpqYmzY+VW9bW1sjJyUF1dTUGDRqEy5cvcx3pndX13lpbW2P+/PnUe0vqqaio4NixY/j111/rW8oUkVTn6VZVVUFVVRU8ntRPsOWWQCBAaGgozp49Cw8PD3zxxRdYtWqVXP7F9frc2/T0dGoFIw1oaWkhKioKw4YNg5GREVxcXLiOJHZSrX60tPD23N3dce3aNVy7dg3Dhg3DzZs3uY7UJnW9t3p6etR7S5r1wQcf4Mcff4SPjw+uX7/OdRyxo6IrR/T09BAVFQU/Pz9YW1tj165dMv+o67reW3d3d+zatQu7d++m7hXSIktLS+zcuRNubm54+PAh13HEioqunGEYBr6+vsjIyMCJEyfg6OiIoqIirmM16vXe2+zsbLi5uXEdiciRyZMnY9q0aXB3d1eoGSVUdOWUoaEh0tPTYWNjAzMzM5l73DX13hJxWLNmDbp3746ZM2cqTEcDFV05xufzsWLFCsTExGDdunWYPHkynj59ymkm6r0l4sTj8XDw4EHk5+dj48aNXMcRCyq6CsDCwgJZWVnQ1dWFqakpZ/exU+8tkYR27dohMjIS33//vUI8fYWKroJo164ddu3ahQMHDsDHxwf+/v6oqKiQymdT7y2RNH19fZw7dw6zZ89GZmYm13HeCRVdBePg4ICcnBw8fPgQZmZmyMrKkujnvT73Nj09HV988QXNvSUSMXjwYAQHB2Ps2LG4f/8+13HemlRvjqCiKx0dO3bEyZMnceLECYwePRr+/v5YsmQJ+Pymv92Pn1ciPKsIecVlKBPWQKDBh4meABPMu6OTVuPfs8uXL8PLywuurq44cuQItYIRiXN3d0deXh7c3NyQlpaG9u3bcx2pzZjmrghaWFiw4jyVj4qKwvfff4/o6GixHZM07969e/j888/x8uVLHD58GIaGhm9sz7n3DHtTCpGaXwIAqKz5u+9Xg88DC8DWWBdzbAwxsMerJQORSITNmzdj9+7dCA4OplYwIlUsy2LGjBl48eIFTp06JZN3uDIMk8WyrEVj26Salp4aIX09evRAXFwcJk6cCEtLSwQHB9e33hzNuI1JIRmIz32IypraNwouAAj/91rczYeYFJKBoxm3cf/+fdjb2yMhIQFZWVlUcInUMQyD4OBgFBcXY9WqVVzHaTNa01UCPB4P/v7+SEtLw759++Dq6oq9cb8hMCYXFdUitNT+yLJARbUIa6N+xxCvr+qLLvXeEq6oq6vj7NmzOH78OI4ePcp1nDahNV0l0rdvX2RkZGD+2m/xTXwBGP6b34vtnoMwvFcnaKqpoOR5Jb5P/QNhmffqt1fXMmhvNQ2u04dT7y3hnK6uLiIjI/HZZ5/ho48+kpsWRamf6dLFFm6pqamh1sQBPH7Dv/yCUgrx6TfJGLA2DrMOZ+LrkUbo31Xwxj7Vta/2I0QW9O/fHwcPHsS4ceNw+/ZtruO0Ci0vKJnHzyuRml+CxlYUCh49R5Xo1bouy77607PTm1eHWRZIvlWCJ88rpZCWkJY5OTlhyZIlcHV1RVlZGddxWkRFV8mEZzU/HGf9mP7IXTsKSYts8ai8Esm3Gj6njQEQni2bQ3aIcvL398cnn3wCLy8viEQiruM0i4qukskrLmvQpfC6led+R781sRi/7zJibxSjqpF9hTW1yHtQLsmYhLQJwzDYs2cPKioqsHjxYq7jNIuKrpIpE9a0uE8tC2TeeQr9DhrwtuzZxHGqxR2NkHeiqqqK06dPIyoqCvv37+c6TpOk3r3QsWNHaX4k+QeBRuu/5So8Bj07tmviOKriikSI2HTs2BHR0dGwsrJCr169YGdnx3WkBuhMV8mY6Amgzm/4be/UXg2upvpop6YCHgNY9+4Mt4Fdcek/jxvsq8HnwURfWxpxCWkzIyMjHD9+HJMmTUJBQQHXcRqgPl0lM0DrBaqqqgDem996FoD30J4IHDsADAPcf1aBddE3kZDb8EIaC2C8WXfpBCbkLYwYMQLr1q2Di4sLMjIy8N5773EdqR4VXSVx69YtrF27FomJiejrtwO3qwVvtI399aIKE0MyWjwOwwB2xrpNDsEhRFb4+fkhNzcXEyZMwPnz56GqKhtLYrS8oOD++OMPzJgxA59++in69euHwsJC7Jg1Ghqqb3dHmQZfBXNsDVvekRAZ8O2330JNTQ3+/v4y87gfKroK6u7du/D19cXHH3+Mnj17oqCgAAEBAdDW1sbAHjoIcDKBpmobv/01VTAVFWBAtw6SCU2ImKmoqODkyZNIS0vDnj17uI4DgJYXFM79+/exceNGnDx5En5+figoKGi0Y8Tb0gAAEBiTB2FN80NvGObVGe68z3ojZPE6LHheiO3bt8vkSD1C/kkgECAqKgqffPIJevfujVGjRtVve5s50u+Kiq6CePjwITZv3oxDhw7Bx8cHubm56NKlS7Pv8bY0gGl3HQSlFCL5VgkYvLrxoU7dPF07Y13MsTWEaXcdeCUnw9nZGTNnzkRISEizg9EJkRUffvghTp8+DQ8PD6SkpKBau2szc6SLsT0hv8EcaXGhoivnHj9+jH//+98ICQmBt7c3bty4AX19/Va/37S7DvZ5W+DJ80qEZxch70E5yoTVEGiowkRfG+PN3vwbX0dHB3FxcXB3d8ekSZNw7Ngx+p4SufDpp59i69atcPbfDHXLyagU1Tb6G17diUfczYdIy3+MACeT+t8MxYGKrpx6+vQptm3bhqCgIEyYMAE5OTno0aPHWx+vk5Y6/Kx7tWrf9u3bIyoqCpMnT4abmxvOnDkjl49NIcqHZ2QNnoXOG7/RNaVujnRgTC4AiK3w0pMj5ExZWRnWr1+P3r174/79+8jMzMS+ffveqeC+DXV1dZw6dQp6enpwdHREaWmpVD+fkLbKufcMgTF5EOHvzp1pw3oicu5w3Fo/ClvHmzb6vorqWgTG5OF60TOx5KDuBTnx4sULbNmyBYaGhsjPz8fPP/+MAwcO4MMPP+QsE5/PR2hoKMzMzGBnZ4eSkhLOshDSkr0phRDWvDmB7GFZJfYkF+J0ZvNT84Q1IrHNkaaiK+MqKiqwbds29OrVC9nZ2UhNTcWRI0fQu3dvrqMBePUooJ07d8LZ2RnW1tYoKqKRj0T21M+R/sca7oUbxYi7+RBPX1Y1+35xzpGmJ0fIqMrKSuzZsweGhoZIT09HXFwcwsLC0KdPH66jNcAwDNavX4+ZM2fCysoKhYX0ZAkiW1qaI90a4pojTRfSZEx1dTVCQ0OxYcMGDBgwAJGRkTA3N+c6Vqt8/fXXEAgEsLGxQWxsLAYMGMB1JEIAtDxHujXENUeaiq6MqKmpwdGjR7Fu3ToYGhoiLCwMw4YN4zpWm/n6+kIgEMDBwQGRkZEYMmQI15EIadUc6dYd593nSEut6LIsS0W3ESKRCGFhYVi7di309PRw8OBBWFtbcx3rnUyaNAna2tpwcXFBWFiYTM40JcqlLXOkmz/Ouw/Nkdqabk1NDXg8Hj26+39qa2tx+vRpmJqaYs+ePQgKCkJKSorcF9w6zs7OOHXqFCZOnIioqCiu4xAl19QcaRUeA3U+Dyo8BrzX/rkx4pojLbUzXTrLfYVlWURGRmL16tXg8/nYunUrRo0aBYZp/Bstz2xtbREdHQ03Nzds27YNXl5eXEciSmq8eXdsT8hv8Po8O0MssDeq/3ePwd2xIyEfOxIbDj8X1xxpKrpSwrIsYmNjsWrVKlRVVWHdunVwc3NTyGL7uiFDhiAhIQGjRo1CeXk5/Pz8uI5ElFBnLXXYGOki/ubDN+ZI70gsaLTA/pM450hT0ZUwlmWRlJSElStX4tmzZ1i7di3GjRunVBO6+vfvj9TUVDg4OKC0tFTmn9ZKFNM08y6I++0eoKLW5veKc4601H7ylbHopqenw87ODrNnz8bcuXPx22+/YcKECUpVcOv06tUL6enpOHjwIJYvXy4zA6WJcigpKcG8KWNgKvpPm+dIa6ryEOBkAtPu4pk2RkVXAjIyMjBy5EhMnz4dM2bMwM2bNzFlyhSlv4jYrVs3pKam4sKFC5g3bx5qa9+tb5KQ1rh//z6sra3h4uKCc1sXIcCpDzRVVdDSyh7DAJqqKghw6iPWKWNUdMUoKysLzs7O8PT0xPjx45GXl4cZM2bQzNnX6OrqIikpCdevX8eMGTNQUyOe/klCGnP79m1YW1tjxowZWL9+PRiGgbelAcJ8LeHY932o83nQ+EdXgwafB3U+D45930eYr6VYCy5Aa7picf36daxevRpXrlzBsmXLcObMGYX9WsWhQ4cOiI2Nxbhx4zBhwgScOHGCbg8nYnfr1i04ODhg8eLF+PLLL9/Y1tY50uJERfcd5ObmYs2aNUhNTcXixYtx/PhxaGpqch1LLrRr1w7nzp2Dt7c3XFxcEBERAS0tLa5jEQVx/fp1jBo1CoGBgfj888+b3K8tc6TFhZYX3kJBQQGmTp0KGxsbmJmZobCwEF999RUV3DZSU1PDiRMn0LNnT4wcORJPnz7lOhJRAFeuXMHIkSOxY8eOZgsuV6jotsHt27fh4+ODYcOGwcjICIWFhViyZAmdob0DFRUVhISEYOjQobC1tcXDhw+5jkTkWFpaGlxcXLB//354enpyHadRUiu68vzUiHv37uFf//oXzM3N0a1bNxQUFGDlypUQCARcR1MIPB4P27Ztg4eHB6ysrHD37l2uIxE5dOHCBYwbNw4nTpyAi4sL13GaRGu6zXjw4AE2bdqEo0ePYtasWbh16xY6d+7MdSyFxDAMVq9ejQ4dOsDKygrx8fEwMjJq+Y2EAIiIiICvry8iIiIwfPhwruM0i4puI0pKSrBlyxYcOHAA06dPR25uLt5//32uYymFBQsWQCAQwNbWFufPn8fAgQO5jkRk3LFjx7Bo0SLExsbCzMyM6zgtkuqarqy3Bf31119Yvnw5TExMUFFRgd9++w3bt2+ngitlPj4+2LlzJ0aOHInLly9zHYfIsODgYCxevBiJiYlyUXABupAGACgtLcWaNWtgZGSEx48f4+rVq9i7dy+6devGdTSlNWHCBBw6dAhjxoxBQkIC13GIDNq+fTs2btyI1NRU9OvXj+s4rabURbe8vByBgYEwNDTE7du3ceXKFQQHB+ODDz7gOhoBMGrUKJw5cwZeXl6IiIjgOg6RESzLYsOGDfjuu++QlpYGQ0PxDKKRFqVc03358iX27t2LrVu3YsSIEbh48SKMjY25jkUaYWVlhfPnz8PZ2SlahlIAABC2SURBVBnl5eWYOnUq15EIh1iWxdKlSxETE4O0tDTo6elxHanNlKroCoVCfP/999i8eTOGDx+OxMRE9O/fn9NMpGXm5uZISkqCo6MjysrKMHfuXK4jEQ7U1tZi/vz5yMjIQEpKCjp16sR1pLci1aLLVV9rVVUVfvjhB2zcuBGDBw9GTEwMBg8ezEkW8nb69u2LtLQ02Nvbo7S0FMuWLVP4AfDkbzU1NZg1axYKCwuRmJiIDh06cB3prSn0mW51dTUOHTqEDRs2oE+fPvjxxx/p6bRy7MMPP0R6ejpGjhyJ0tJSbN68mQqvEqiqqoK3tzeePXuG2NhYtG/fnutI70QhL6SJRCIcPnwYffr0wYkTJ3Ds2DGcP3+eCq4C6Nq1K1JTU5GUlITZs2dDJBJxHYlIkFAohIeHByorKxEZGSn3BRdQsKJbW1uLkydPol+/fggJCcH+/fuRmJgo83eokLbp1KkTEhMTkZeXh2nTpqG6uprrSEQCnj9/DmdnZ2hrayM8PFzm+/xbSyGKLsuyOHPmDAYOHIjt27dj165dSEtLg62trUQ+j3BPIBDg/PnzKC0thYeHByoqKriORMTo2bNnGDlyJD788EMcPXoUqqqqXEcSG7kuuizLIjo6Gubm5tiwYQM2bdpU/6gcWutTfJqamjh79iy0tLTqW8qI/CspKcFnn32Gjz/+GMHBwQr3mCu5LLosyyIuLg7Dhg3DsmXLsGLFCmRlZcHFxYWKrZJRVVXF0aNHYWhoCHt7e/z1119cRyLv4L///S9sbW0xevRo7NixQyEf4ip3RTc5ORnW1tbw9/fHwoULkZOTAw8PDyq2SkxFRQXff/89rK2tYWNjgwcPHnAdibyFO3fuwNraGt7e3ggMDFTYn2m5aRm7dOkSVq5cibt372L16tXw8vJSuF87yNtjGAbffPMNdHR0YGVlhYSEBBgYGHAdi7RSfn4+HBwcsGjRIsyfP5/rOBIl0aL7+HklwrOKkFdchofG7gj+rQo32f9ggnnrH/p25coVrFq1Cnl5eVi5ciWmTZumUIvqRHwYhkFAQAAEAgGsra0RFxcHExMTrmORFvz2229wdHTEhg0b4OPjw3UciZNI0c259wx7UwqRml8CAKisqQV0jXGxqBKZxfnYnpAPW2NdzLExxMAeOo0e49q1a1i1ahWys7MREBCAyMhIqKmpSSIuUTDz5s1Dhw4dYGdnh59++kluRv4po8zMTLi4uGDHjh2YNGkS13GkQuxF92jGbQTG5EFYIwLLNtwurKkFAMTdfIi0/McIcDJ547nyN27cwOrVq3Hp0iUsXboUp06dUpj+PCI906ZNg7a2dv2ksk8//ZTrSOQf0tPTMW7cOOzfvx9ubm5cx5EasRbdVwU3FxXVtS3uy7JARbUIgTG5AICP36vE2rVrkZiYiP/7v//D4cOH0a5dO3HGI0rG3d0dWlpacHd3x9GjR+Ho6Mh1JPI/8fHx8PLywokTJ2Bvb891HKli2MZOR//HwsKCzczMbNWBcu49w6SQDFRUN7wt8+QsSwzuoYOa2lefVVwmxIhtqfXbebU1eBG5Af5T3TFv3jxoa2u38csgpGmXLl2Cu7s7vvvuO4wbN47rOErv3LlzmDVrlkL/BsIwTBbLshaNbRPbme7elEIIa5q+D35V5A2EZd5rdFstTwUui3dj+eeW4opDSL3hw4cjLi4OTk5OKC8vx4wZM7iOpLROnDiBhQsX4vz58zA3N+c6DifEUnQfP69Ean5Jo2u4rcPg4h9P8eR5Zau7Gghpi0GDBiE5Obl+Qpm/vz/XkZTO/v37sXr1aiQkJCj1HGux3BwRnlXU4j6LHY2RvcIB4X7DYPlhxwbbGQDh2S0fh5C3ZWxsjLS0NOzZswfr1q1Dc0trRLx27tyJ9evXIyUlRakLLiCmM9284rJXbWFN2Bybh4KH5agWsXAdqI/90z+G06503P3rZf0+wppa5D2ge+eJZPXs2fONmbxbt25V2DufZMXGjRsRGhqKtLQ09OzZk+s4nBPLmW6ZsKbZ7dfuPcOLKhGqRLX4Mfs+su78BTvjLo0ch0b0EcnT09NDSkoKLl++DF9fX5rJKyEsy2LZsmU4duwYFdzXiKXoCjTadsLMskBjJxcCDbrTjEhHx44dER8fjz/++ANeXl6oqqriOpJCqa2thb+/P+Li4pCamgp9fX2uI8kMsRRdEz0B1PmNH0qgwYd1785Q5/OgwmMwZlBXDPmwY/3danU0+DyY6FOrGJEeLS0t/PTTTxAKhRg7dixevnzZ8ptIi0QiEb744gtkZWUhKSkJnTt35jqSTBFL0R1v3r3JbXwVHhaNNEbWCgdcXeGAGcMM4HskC38+fvHGfiyA8WZNH4cQSdDQ0EB4eDg6duyI0aNHo6ysjOtIcq26uhpTpkzB3bt3ERcXJ9cPkJQUsVxI66ylDhsjXcTnPmzQNvbXiyqM2Xup2fczDGBnrEvtYoQTqqqqOHz4ML788kuMGDEC58+fp7OztyAUCuHp6Vn/cAG6fb9xYpunO9fWEBr8txu1qMFXwRxbQ3FFIaTNeDwe9u7dC3t7e9jY2OD+/ftcR5IrL168gIuLCzQ1NXHmzBkquM0QW9Ed2EMHAU4m0FRt2yE1VXkIcDKBaffGp40RIi0Mw2DTpk2YOnUqrKys8Mcff3AdSS6UlpbC0dERH3zwAY4fP06jV1sg1oE3ddPCmpsyVodhXp3h/nPKGCFcW7p0KTp06ABra2tcuHAB/fr14zqSzHr8+DEcHR3xySefYOfOnQr5eB1xE/toR29LA5h210FQSiGSb5WAwd/jHIFXXQosXq3hzrE1pDNcIpNmz54NbW1tjBgxAtHR0bCwaHR2iVJ78OABHBwc4Orqio0bN9JNJq0kkSHmpt11sM/bAk+eVyI8uwh5D8pRJqyGQEMVJvraGG/W+idHEMIVb29vCAQCODk54fTp07CxseE6ksy4c+cO7O3t8fnnn2P58uVcx5ErYhvtSIiiSkxMxKRJk3Do0CE4OTlxHYdzBQUFsLe3x8KFC7FgwQKu48ik5kY70gIMIS0YMWIEoqKi8PnnnyMsLIzrOJz6/fffYWtri5UrV1LBfUtSexowIfLM0tIS8fHxGD16NMrLy/HFF19wHUnqsrKy4OzsjO3bt2Py5Mlcx5FbVHQJaSVTU1OkpKTAwcEBpaWlWLRoEdeRpObixYvw8PBASEgIxowZw3UcuUZFl5A26N27N9LT02Fvb4/S0lKsXbtW4a/aJyQkYPLkyTh27BhGjhzJdRy5R2u6hLRRjx49kJ6ejqioKCxYsAC1tS0/iFVeRUVFwcvLC2fOnKGCKyZUdAl5C126dEFycjIyMzMxc+ZM1NQ0P1NaHoWFhWHWrFn46aefYGVlxXUchUFFl5C3pKOjg7i4ONy/fx+TJk1CZWUl15HE5sCBA1i4cCHi4+Px8ccfcx1HoVDRJeQdtG/fHlFRUaitrYWbmxtevHjR8ptk3O7du7FmzRqkpKRgwIABXMdROFR0CXlH6urqOHXqFPT09ODo6IjS0lKuI721TZs2YefOnUhLS4ORkRHXcRQSFV1CxIDP5yM0NBRmZmaws7PDo0ePuI7UJizLIiAgAEeOHEFaWhoMDAy4jqSwqOgSIiY8Hg87d+6Es7MzrK2tUVRUxHWkVmFZFgsWLMD58+eRmpqKrl27ch1JoVGfLiFixDAM1q9fjw4dOsDKygrx8fEwNJTdAf0ikQh+fn64efMmkpKSoKNDU/8kjYouIRLw9ddfQyAQwMbGBrGxsTJ5Qaq6uhrTpk3Do0ePEBcXBy0tLa4jKQUquoRIiK+vLwQCAezt7REZGYmhQ4dyHameUCjExIkTIRKJEB0dDU1NTa4jKQ1a0yVEgiZNmoQDBw7AxcUFycnJXMcB8Op5Zm5ublBXV8eZM2eo4EoZFV1CJMzZ2RmnT5/GxIkTERUVxWmW0tJSjBo1Cl27dsXx48ehpqbGaR5lREWXECmwtbVFdHQ0Zs2ahePHj3OS4cmTJxgxYgRMTU1x4MAB8Pm0usgF+q9OiJQMGTIECQkJGDVqFMrKyvCvf/1Lap9dXFwMBwcHODk5YfPmzQo/GU2WUdElRIr69++P1NTU+pm8S5Yskfhn3r17F/b29pg2bRoCAgKo4HKMii4hUtarVy+kp6fXF97AwECJFcLCwkLY29vD398fCxculMhnkLahNV1CONCtWzekpqbiwoULmDdvnkRm8t64cQO2trZYvnw5FVwZQkWXEI7o6uoiKSkJ169fx/Tp08U6kzc7Oxv29vbYsmULfH19xXZc8u6o6BLCoQ4dOiA2NhaPHz/G+PHjIRQK3/mYly9fxujRoxEUFIQpU6aIISURJ1rTJYRj7dq1w7lz5+Dt7Q0XFxdEREQ0uCX38fNKhGcVIa+4DGXCGgg0+DDRE2CCeXd00lKv3y8xMRGTJk3C0aNH4ejoKO0vhbQCw7JskxstLCzYzMxMKcYhRHmJRCL4+voiNzcXP/30E9577z3k3HuGvSmFSM0vAQBU1vy99qvB54EFYGusizk2hriXcxE+Pj44ffo0bGxsOPoqCAAwDJPFsqxFo9uo6BIiO1iWxaJFi5CYmAi/rUexO/0+hDUiNPNjCoYB+GDx4uIRRGxdhCFDhkgvMGlUc0WX1nQJkSEMw+Dbb79FXzdffBNXiIrq5gsuALAsUM0y0LaejvzaLtIJSt4arekSImOuF5XiGtML4IveeL2Dpiq+GWcKq96d8deLKnxz4RYic/5bv71SxCIwJg+m3XVg2p3m4soqOtMlRMbsTSmEsEbU4PX1Y/qhWlQLi8AELAi7hg1j+6N3lzcvuAlrRAhKKZRWVPIWqOgSIkMeP69Ean5JgyUFTVUVjOqnj2/j8/GySoTMO0+RkPsQHoO7vbEfywLJt0rw5LniPA5e0VDRJUSGhGc1/ly1jzq3h6iWxZ+P/37Ee+6DcvR+X7vBvgyA8Gz5eD6bMqKiS4gMySsue6MtrE47dRU8r6x+47VyYTW01BtelhHW1CLvQbnEMpJ3Q0WXEBlSJmz8VuCXlSJoqau+8ZqWOh/PKxvfv0xY3ejrhHtUdAmRIQKNxhuK/nj8Aio8Bgad2tW/1kdfgIKHjZ/RCjRUG32dcI+KLiEyxERPAHV+wx/LimoRLtwoxlcORtBUVYF5z/fg0Pd9nLl6v8G+GnweTPQbrvUS2UBFlxAZMt68e5PbVpz7HRp8FWStsMeuSYOxIuJ3FDx63mA/FsB4s6aPQ7hFN0cQIkM6a6nDxkgX8bkPG7SNlVZUw/doVrPvZxjAzlj3jSE4RLbQmS4hMmaurSE0+Cpv9V4Nvgrm2BqKORERJyq6hMiYgT10EOBkAk3Vtv14aqryEOBkQrcAyzhaXiBEBnlbGgAAAmPyWjVlTIOvggAnk/r3EdlFRZcQGeVtaQDT7joISilE8q0SMHh140Odunm6dsa6mGNrSGe4coKKLiEyzLS7DvZ5W+DJ80qEZxch70E5yoTVEGiowkRfG+PNutNFMzlDRZcQOdBJSx1+1r24jkHEgC6kEUKIFFHRJYQQKaKiSwghUkRFlxBCpIiKLiGESBEVXUIIkSIquoQQIkVUdAkhRIqo6BJCiBQxbDOTNBiGKQFwR3pxCCFEIfRkWVa3sQ3NFl1CCCHiRcsLhBAiRVR0CSFEiqjoEkKIFFHRJYQQKaKiSwghUvT/xrkz8CLlddkAAAAASUVORK5CYII=\n",
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# Define adjacency matrix of P\n",
"C = np.zeros([6,6])\n",
"C[0, [1, 3]] = 1\n",
"C[1, [0, 2]] = 1\n",
"C[2, [1, 3]] = 1\n",
"C[3, [0, 2, 4, 5]] = 1\n",
"C[4, [3, 5]] = 1\n",
"C[5, [3, 4]] = 1\n",
"\n",
"# Define graph P based on adjacency matrix\n",
"P = nx.Graph(C)\n",
"\n",
"# Draw the graph\n",
"nx.draw_networkx(P, with_labels=True, font_color='w')\n",
"\n",
"# Find an Eulerian circuit and print the output\n",
"print(f'Eulerian circuit: {list(nx.eulerian_circuit(P))}')\n",
"\n",
"# Print the degree of every vertex\n",
"for i in P.nodes:\n",
" print(f'Degree of vertex {i}: {P.degree()[i]}')\n",
"\n",
"print('All the degrees are even!')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It turns out that every vertex in an Eulerian graph has even degree. In fact, if the graph is connected (any two vertices can be connected by a path) and every vertex has even degree, then the graph is also Eulerian!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Problem 9 (Planarity).__\n",
"A (undirected) graph is called planar if it can be drawn in the plane without edges crossing (you are allowed to draw the graph edges as curved lines if you like). All the graphs we've seen so far have been planar graphs. \n",
"\n",
"Two non-planar graphs are $K_{5}$ and $K_{3,3}$. The graph $K_{5}$ is called the complete graph on 5 vertices. It has ... wait for it ... five vertices. And it is complete in the sense that every possible edge is in the graph: every pair of vertices is connected by an edge. \n",
"\n",
"The graph $K_{3,3}$ is an example of a complete bipartite graph. Such graphs have two kinds of vertices (call them blue and gold) and all possible edges between blue and gold vertices are present while no edges between vertices of the same color are present. The graph $K_{3,3}$ has 3 vertices of each color. \n",
"\n",
"In fact, in a precise sense, these are the only examples of non-planar graphs. It turns out that every other non-planar graph can be obtained from $K_5$ or $K_{3,3}$ by a combination of actions: adding edges between existing vertices, subdividing an existing edge by inserting a vertex on the edge, or adding new vertices. The Petersen graph is the graph pictured in Figure 9."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"
Figure 9. The Petersen graph.
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It is a counterexample to many natural conjectures in graph theory. In the code below, we define the Petersen graph in NetworkX using `nx.petersen_graph()`, and draw the graph."
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nOzdeVxN+RsH8M9tUyhEiAhFC5W2ITszg6mEFBn7ln2smTEY2xhLjN0gM5YYomwtY6xZy7iVLJWKUCjti9bbPb8/zO3XmaLt3nvu7T7v1+u+XuN27jlPnfn2dL7L8+UxDMOAEEIIURBKXAdACCGESBMlPkIIIQqFEh8hhBCFQomPEEKIQqHERwghRKFQ4iOEEKJQKPERQghRKJT4CCGEKBRKfIQQQhQKJT5CCCEKhRIfIYQQhUKJjxBCiEKhxEcIIUShUOIjhBCiUFS4DoAQIvvS8orgG5aEmOQc5BQKoKWuAuPWWnC11kPzxg24Do+QGuHRfnyEkE+JTMzC3uB43IxNBQAUCYRlX1NXUQIDYICRDub0N4RFu6YcRUlIzVDiI4RU6njoS2wIikGhoBSf+y3B4wHqKspYYW+M8T07SC0+QmqLujoJIRV8THrRKCgRVnkswwAFJaXYEBQNAJT8iMyjJz5CCEtkYhbcvEJRUFJa9t7U3h3gat0OXVppQlmJhx1XY7HjWlyFz2qoKsPHvSfM9ajbk8gumtVJCGHZGxyPQkEp671ubZsgu6AE77ILPvvZQkEp9gXHSzI8QuqMEh8hpExaXhFuxqZWGNNbfDoSbl6hiHqb89nPMwxw41kq0vOKJBglIXVDiY8QUsY3LKnO5+AB8A2v+3kIkRRKfISQMjHJOawlC7VRKBAi5l2umCIiRPwo8RFCymQXlIjlPDmF4jkPIZJAyxkIUVBCoRDx8fF48OAB+Hw++Hw+4nR6Q92ob53PraWuKoYICZEMSnyEKACGYfDy5Uvw+fyyRBcWFgZtbW3Y2NjAxsYGa9aswaOSVth/N7FCd+cYm3aw7dAMXds2AQAMNm0FvWYauByVgstRKaxj1VWUYKyrKbXvjZCaosRHSD3DMAzevHlT9hQnSnTq6uqwtbWFjY0Nli1bBmtra+jo6LA+a5FXhP13Eyuc07ZDM7hYtyv7t2mbJjBt0wRJmQUVEh8DwMVKTyLfGyHiQAvYCZFzKSkpZUlO9CotLYWNjU1ZorO2tkabNm2qdT53bz6uRKd8tkzZp/B4wBDTVtg/3qbmHyZESijxESJHMjIyKiS53Nzcsu5KUaJr164deDxera5RWeWW6lJXUcLpmXZUuYXINEp8hMionJwchIeHsyafpKamwsrKipXoOnXqVOsk9yk1qdUposyUQvnxBVzZ9xP09fXFGg8h4kSJjxAZ8OHDBzx8+JA1JpeUlAQLC4uyJGdjYwMjIyMoKUlnFdLvt2Kxzv8JlFQa4HO/JES7M/z4jTHS75+Hp6cnLly4ABsb6u4ksokmtxAiZUVFRYiMjGR1V8bHx6Nr166wtbXFoEGDsGzZMpiamkJFhbsmmhZyDl3fJaD90Om48SwVPHxcnC4i2o9voJEO5gww/Ni9abcQ+vr6+Oabb/D777/DycmJs/gJ+RR64iNEgkpKSvD06VNWd2V0dDS6dOnC6q7s1q0bGjSQnZ3Ms7Oz0blzZ9y8eRMmJiZIzyuCb3gSYt7lIqewBFrqqjDW1YSLVeU7sP/zzz8YMWIEfvjhB3z33XccfAeEfBolPkLEpLS0FDExMazuysePH6NDhw6s7sru3btDQ0OD63A/a+3atXj+/DmOHTtW63MkJCTAwcEBgwcPxrZt26CsrCzGCAmpPUp8hNSCqOpJ+bVyDx8+hK6uLivJWVpaQlNTvhZzp6enw8jICPfv34eBgUGdzpWZmYlRo0ZBS0sLJ06cQKNGjcQUJSG1R4mPkCqUr3oieoWFhaFp06asJQRWVlZo1qwZ1+HW2Q8//IDMzEwcOHBALOcrLi7GjBkzEBUVBX9/f7Ru3Vos5yWktijxEVIOwzB4+/Yta0yOz+ejQYMGrDG5yqqe1AfJyckwNTVFZGQk2rVrV/UHqolhGKxfvx5//PEHAgMD0bVrV7Gdm5CaosRHFNr79+9ZY3J8Ph8CgaDsKU70qm7VE3m3YMEC8Hg87NixQyLn9/b2xpIlS3Dy5El8+eWXErkGIVWhxEcURkZGBsLCwliJrnzVE9Grffv2Yl8QLg8SExNhYWGBqKgoiXZHBgcHY8yYMdi8eTMmT54ssesQ8imU+Ei9JKp6Un7yyfv372FlZcV6mjMwMFDIJFcZd3d3aGtrY9OmTRK/VnR0NBwcHDBu3DisW7eO7gGRKkp8RO7l5+cjIiKCNSb3+vXrsqonokTXpUsXmlL/CfHx8ejRowfi4uKgra0tlWu+f/8eTk5OMDAwwB9//CFT6xhJ/UaJj8iVoqIiPHr0iDUmJ6p6Un7yCddVT+TNhAkTYGhoiNWrV0v1uvn5+ZgwYQJSU1Nx7tw5NG/eXKrXJ4qJEh+RWaKqJ+XH5P5b9cTGxgZmZmb0tFAHUVFRGDBgAOLj46GlpSX16wuFQnz//fe4ePEigoKC6rx2kJCqUOIjMqF81RPR69GjR9DX12d1V1pYWKBhw4Zch1uvuLq6wtbWFsuWLeM0jt9++w3r1q3D2bNnYWdnx2kspH6jxEek7r9VT/h8PiIiItC6dWtWd6U8Vj2RNxEREXBwcEBcXJxMVFUJCgrCpEmTsG/fPri6unIdDqmnKPERiWIYBq9evWKNyZWveiJ6WVtb14uqJ/LG0dERQ4YMwfz587kOpUxERAScnJwwf/58eHh40IxPInaU+IjYiKqelF9CwOfzoaamVmFBeH2seiJvQkJCMGbMGMTFxcncGGlSUhIcHBxgZ2eHPXv20EQlIlaU+EitiaqelE90AoGANSanSFVP5M2XX36JsWPHYvr06VyHUqmcnByMHj0aPB4Pp0+fpm5vIjaU+Ei1ZGZmspIcn89HdnY2a0xOkaueyJvr16/D3d0d0dHRUFVV5TqcTyopKcG8efNw//59BAQEQE9Pj+uQSD1AiY9UkJubi/DwcNa4XEpKCqysrFiJrlOnTlBSUuI6XFJDDMOgd+/emDNnDsaPH891OFViGAaenp7YvXs3/P390b17d65DInKOEp+Cy8/Px8OHD1ljcuWrnoheRkZGVPWknggKCoKHhwcePXokV/f09OnTmDt3Lo4dO4ZvvvmG63CIHKPEp0BEVU/Kj8nFx8fD1NSUNSZnamoq091fpPaEQiFsbGywYsUKjBo1iutwauzevXtwdnbGmjVrMGvWLK7DIXKKpkrVU+WrnoheUVFR6Ny5c1lX5ezZs6nqiYI5d+4cAMDZ2ZnjSGqnV69euHPnDuzt7fHixQts2rSJuttJjdETXz1QWlqKZ8+escbkylc9ESU6qnqi2EpLS2FmZoatW7fC3t6e63DqJD09HSNGjEDr1q1x7NgxaGhocB0SkSOU+OSMUCjE8+fPWd2V/616YmNjAysrK5r+TViOHz+Offv24e7du/Vi5m1hYSGmTp2KhIQEXLx4kdaGkmqjxCfDRFVPyndXhoWFQUtLi7WEgKqekKqUlJTAxMQEXl5eGDhwINfhiI1QKMRPP/2EkydPIigoCEZGRlyHROQAjfHJkDdv3lRYK6eiolKW4JYsWQJra2u0bNmS61CJnDly5Aj09fXrVdIDACUlJfz888/o1KkT+vXrhzNnzqBfv35ch0VkHD3xceS/VU/4fD6Ki4tZsyttbW2p6gmps8LCQnTp0gU+Pj71eteDq1ev4ttvv8X27dsxbtw4rsMhMowSnxRkZmYiLCyMtVaufNUTUZKjqidEEnbt2oXLly8jICCA61Ak7smTJ3B0dMS0adOwcuVKak+kUpT4xExU9aT85JOUlBRYWlqynuYMDAxoGjaRuA8fPsDQ0BBBQUGwtLTkOhypePfuHYYNGwYzMzMcOHAAampqXIdEZAwlvjooX/VE9Hr16hXMzc1Zk0+o6gnhypYtW/DgwQOcOXOG61Ck6sOHDxg7diw+fPgAPz8/NG3alOuQiAyhxFdNRUVFePz4MWutXFxcHExNTVndlVT1hMiK7OxsdO7cGcHBwTA1NeU6HKkrLS3F4sWLcfXqVQQGBqJDhw5ch0RkhNQTX1peEXzDkhCTnIOcQgG01FVg3FoLrtZ6aN5YNiqIlJSUICoqijUmV77qiehlbm5OVU+IzFq7di2eP3+OY8eOcR0Kp3bu3InNmzfjwoULsLW15TocIgOklvgiE7OwNzgeN2NTAQBFAmHZ19RVlMAAGGCkgzn9DWHRTnrdEqKqJ+XH5B49eoT27duzxuS6d+9OVU+I3EhPT4eRkRHu378PAwMDrsPh3IULFzB9+nQcOnQIw4cP5zocwjGpJL7joS+xISgGhYJSfO5qPB6grqKMFfbGGN+zg9jjYBgG8fHxrDG5iIgItGzZkjUmZ2lpCS0tLbFfnxBp+eGHH5CZmYkDBw5wHYrMePDgAUaMGIFly5ZhwYIFXIdDOCTxxPcx6UWjoERY9cH/0lBVwgp7kzolP4Zh8Pr1a9aYXPmqJ6JEZ2VlBW1t7VpfhxBZk5ycDFNTU0RGRqJdu3ZchyNTXr58CQcHB3z55ZfYvn07TTpTUBJNfJGJWXDzCkVBSWnZe5uczWCjrw3dJuooLhXiYWIWNv4VjdiUPNZnNVSV4ePeE+Z61ev2fPv2LWtM7r9VT0QvqnpC6jvR08zOnTs5jkQ2ZWVlYdSoUWjUqBFOnjyJRo0acR0SkTKJJj53bz6uRKewujdfbnRA+OtMPEvORR/DFmin3RDvsgswYGswa9yPxwOGmLbC/vE2Fc6bmprKGpMTVT0p311pY2ODNm3a0AJWolASExNhYWGBqKgotG7dmutwZFZxcTFmzpyJx48fw9/fH7q6ulyHRKRIYokvLa8IvTdfZyUzAOjWRgtP3uYAAPSaauDO94MAAA67b+Ppv++LNFBRQtAsayREszdPzc7OhrW1NSvR6evrU5IjCs/d3R3a2trYtGkT16HIPIZhsGHDBhw6dAgBAQHo1q0b1yERKZFYkWrfsKRK339SLrmpqnysXCIoFeJ9blGFY4sKC9Fz7AKY4A1sbGzg7OyMjRs3UtUTQioRHx8PPz8/xMXFcR2KXODxeFi5ciU6duyIQYMG4c8//8RXX33FdVhECiSW+GKScyo87ZXXUE0ZnqPMAQCH7iQgtZLEBxU1jJu7DDvGKEapJULqYt26dfjuu+9oslYNjRs3Dnp6ehg9ejQ2btyIqVOnch0SkTCJJb6cQsEnv6bdSA2HJ9vCQq8p/vznNTZdivnksbmfOQ8h5KOoqChcunQJ8fHxXIcil/r3749bt27B3t4eL168wPr162nopB6TWH+hlnrlObVtUw2cmWkHC72m2HsjHj+ee1zFeaj8FyFVWb16NZYuXUrrT+vAyMgIoaGhuHbtGsaNG4eiokp6oUi9ILHEZ9xaCw1UKp7eb1YvGOg0RlJmPjTUlPGToyl+cjSFhV6TCseqqyjBWFdTUiESUi9ERETg7t27mDt3LtehyD0dHR1cv34dxcXF+Prrr5Gens51SEQCJJb4XKz1Kn2/dRN1AIBes4aY2rtj2atzy4oJTlBaihEWNM2YkM9ZtWoVli9fTuvRxERDQwOnT59Gz5490atXL+o+roekvo6vunhgoJ4Wi8Kru7Fo0SJMnToVjRs3Fn+QhMixkJAQjBkzBnFxcVQwXQIOHDiANWvWwM/PD7169eI6HCImEl0TMHeAIdRValcSSF1VBT6rp+LkyZO4desWOnbsiJUrVyI5OVnMURIiv1auXIlVq1ZR0pOQmTNn4o8//sDw4cNx+vRprsMhYiI3tTrj4+Px66+/4uTJk3BxccGSJUtgbGwsgYgJkS2f2sqrdcFLLJ03E9HR0bQHpIRFRkbC0dER8+bNw7Jly2jGp5yTu90ZUlNTsXfvXuzbtw92dnbw8PBA79696X9EUu9UtZVXYVExTJoKsWnCQKlu5aWokpKS4OjoiC+++AJ79+6lPzbkmNT243uUlIV9wfG48SwVPACFlezHN9BIB3MGGFarMHV+fj6OHj2Kbdu2QUdHBx4eHhg+fDhVWyf1gqxs5UXYcnNzMXr0aDAMg9OnT9PyETkl9R3Y0/OK4BuehJh3uThx5izGuTrDWFcTLla124G9tLQU58+fh6enJ9LT07FkyRJMmjQJGhoaEoieEMnjaisvUj0CgQDz58/H3bt3ERgYSFs/ySGpJz7WxXk8iOvyDMPgzp078PT0xP379zFnzhzMnTsXLVq0EMv5CZGGyrbyAj7uVDJnoCGMWmmiuFSIZ8m5mHb0AatCUk238iK1xzAMtm7dip07d8Lf3x+WllRWUZ7Um0rPPB4Pffv2xcWLFxEcHIzExER07twZc+fOxfPnz7kOj5Bq2Rscj0IBO+k5WbTBgQk2MG6liStRKQh6/A6NG6hAQ43drV8oKMW+YFpzJg08Hg8eHh7YsWMHBg8ejKCgIK5DIjVQb574KpOcnIzdu3fjwIEDGDBgADw8PNCjRw+JXY+QuvjUVl53vx+Etk014HYwBKEJGZ89RwMVJdz7flCthg1I7YSEhMDZ2RmrVq3CnDlzuA6HVEO9eeKrTOvWrbFhwwa8fPkSffv2xZgxY9CvXz/4+/tDKKz++Akh0lDZVl4dWzRC26YaKCguxcz+Bni6ZgiClw7AhJ76lZ6DB8A3vPItwYhk2NnZ4c6dO9i5cyeWLl1Kv1vkQL1OfCKNGzfGggULEB8fjzlz5mDNmjXo2rUrfv/9dypES2RGZVt5NWuoBgDQUFNG+2YNEfj4HVprqWP98G4YbNqqwjkKBULEvMuVSrzk/wwMDBASEoJ//vkHrq6uyM/P5zok8hkKkfhEVFRU4ObmBj6fj71798LX1xcdO3bExo0bkZmZyXV4RMFVtpVXxof//2G26MxDLPN7hNP8RADAVyYVE9/H85RIJkDyWdra2rhy5QrU1dUxaNAgvH//nuuQyCcoVOIT4fF4GDRoEP766y/8/fffiImJgYGBARYuXIhXr15xHR5RUJVt5fUmq+CTiexDceV7VdJWXtxp0KABjh8/jsGDB6Nnz56Iifn0XqOEOwqZ+MozMzPD0aNH8ejRI6ipqcHKygrffvstIiIiuA6NKJjKtvIqKWVw+G4CAOBX1+7YMsoco23aQVAqxIWHbyucg7by4h6Px8O6deuwatUq9O/fHzdv3uQ6JPIfCp/4RPT09LBlyxa8ePECVlZWGDZsGL766itcunRJojNPCRH51FZeu67HY19wPLTUVeBorotnKbmY7s3Hw8SsCscyAFysKj8Pka4pU6bgzz//hKurK44fP851OKScer2coS6Ki4tx6tQpbN26FQCwdOlSuLm5QU1NjePISH3m7s3HlagU1KZV8HgfF7rvH28j9rhI7T19+hQODg6YOnUqVq1aRXWFZQA98X2CmpoaJk6ciMjISGzZsgXHjh2DgYEBtm7diuzsbK7DI/WUk2EDMILiWn1WXUUZcwYYijkiUlddu3ZFaGgo/P39MWXKFBQX1+7+EvGhxFcFHo+HoUOH4urVq7hw4QLCw8PRqVMneHh4ICmJ1ksR8bl37x6mj/waQ1p+gIZqzZrmx1qdxlSuTEa1bt0awcHByMrKwtChQ5GVVbGbmkgPJb4asLKywp9//omwsDCUlJTA3NwckyZNwuPHj7kOjci506dPY/jw4Th8+DAOeIzHCnsTaKgqo6peMR7vY41OKlAt+xo1agQ/Pz9YWFigV69eSEhI4DokhUVjfHWQmZmJ/fv3Y/fu3bCwsICHhwcGDhxIffik2hiGwZYtW7Bnzx4EBATAwsKi7Gvi3sqLyI7du3dj48aNOH/+PL744guuw1E4lPjEoKioCMePH8fWrVvRsGFDLF26FK6urlBRqbguixCRkpISzJ07F//88w8CAgKgp1f5bExxb+VFZMPFixcxbdo0HDx4ECNHjuQ6HIVCiU+MhEIhAgMD4enpidevX2PRokWYNm0aGjduzHVoRMbk5ORg9OjR4PF4OH36NDQ1q7f2rr61GUUXFhYGJycnLF26FAsXLqTeIimhMT4xUlJSwrBhw3Dr1i34+Pjgzp076NixI1asWIHk5GSuwyMyIjExEX369EHHjh3h7+9f7aRH6h9ra2vcu3cPv//+O+bPnw+BoPJqPES8KPFJSI8ePXDmzBmEhoYiKysLJiYmmD59OpUwUnARERGws7PDhAkTsG/fPuoOJ9DX18fdu3fx7NkzjBw5Enl5eVyHVO9R4pMwAwMD7N27F3FxcWjXrh369+8PJycn3L59m7qsFExQUBAGDx6MHTt2wMPDg7q1SJkmTZogKCgILVu2RL9+/fD2bcVydER8KPFJSYsWLbB69WokJCTA3t4eU6dOhZ2dHfz8/FBaWlr1CYhc27dvH6ZNm4aLFy/CxcWF63CIDFJVVcWhQ4cwatQo2NnZ0TIpCaLJLRwpLS3FhQsX4OnpibS0NCxevBiTJk1Cw4YNuQ6NiJFQKMSyZcvg7++PoKAgGBgY1Ol8itxmFMnJkyexYMGCsp0eiHhR4uMYwzC4e/cuPD09ERoaitmzZ2Pu3LnQ0dGp0XnS8orgG5aEmOQc5BQKoKWuAuPWWnC1pinvXMnPz8eECROQmpqK8+fPQ1tbu87npDajOG7fvg0XFxds2LAB06dP5zqceoUSnwyJiYnBtm3b4Ovri7Fjx2Lx4sUwNPx87cXIxCzsDY7HzdhUAGDt4C1a5DzASAdz+hvCoh0tcpaWlJQUDB8+HIaGhvj999/RoIF4/vigNqNYYmNjYW9vj9GjR+Pnn3+GkhKNTokD/RRliLGxMby8vBAdHQ1tbW3Y2dnBxcUFoaGhlR5/PPQl3LxCcSU6BUUCISvpAR8rfRQJhLgclQI3r1AcD30phe+CREdHw87ODoMHD4a3t7fYkh5RPF26dEFISAiCg4Px7bfforCwkOuQ6gV64pNheXl5+OOPP7B9+3bo6enBw8MDjo6OUFJSwvHQl9gQFI2Cko/JrmdHbZxyt6v0PEvPRMI3POnfQsZU01GSgoODMWbMGGzevBmTJ08W+/mpzSimgoICTJo0CW/fvsX58+fRokULrkOSa5T45IBAIICvry88PT2Rn5+PsXN/wJ/vW6Kw5P9PePrNG2KSXYeyfzdUU4abbXsAgMv+e+C/ygTwsaCxj3tPqu0oAd7e3liyZAlOnjyJL7/8UiLXoDajuIRCIX788UecPXsWgYGB6Ny5M9chyS1KfHKEYRgEBwfju9OPkaPVEbzP9PdPsuuAtU5d8fhNNobtuVP2Pm1WKn4Mw2DdunU4cuQIAgMDYWpqKrFrUZshXl5eWLVqFfz8/NC7d2+uw5FLNMYnR3g8Hsxse6G4RefPJj0AmNyrAwDgj7vsrU8YBrjxLBXpeUWSClOhFBcXY/LkyQgICEBISIhEkx4hADBjxgwcPXoUI0eOhI+PD9fhyCVKfHLGN6zqzW+/NG6Jji0aISWnEAGPKlaA4AHwDadNdOsqMzMTQ4cORXZ2NoKDg9G6dWuuQyIKYsiQIbh69So8PDywadMm6gWoIUp8ciYmOafC7M3/mtq7IwDg+P1XKCmt2CAKBULEvMuVSHyKIiEhAb169YKFhQX8/PzQqFEjrkMiCsbc3BwhISHw8fGBu7s7SkpKuA5JblDikzM5hZ+v3m7UShO9DVugsKQUJ+6//uRxWfnF4g5NYfzzzz/o3bs35syZg+3bt0NZWZnrkIiCatu2LW7duoW3b9/C0dER2dnZXIckFyjxyRkt9c9X8xc97Z1/+AYZHz6d3IIu+KJnz56YN28ejhw5gidPnlDN0Go4d+4cHBwcsH//fsyfP5/rcAiBpqYmLly4AAMDA/Tp0wevX3/6D17yESU+OWPcWgsNVCq/bc0aqmJ49zYAKk5qKU9dRQkr5k6Bp6cnOnXqhMuXL8PZ2RlNmzZF3759sWjRIpw4cQKxsbEQCj/fraooGIbB9u3bMW/ePFy6dAlOTk5ch0RIGRUVFezduxeTJ09Gr169EB4eznVIMo2WM8iZtLwi9N58vcpxvs9poKKEe98PqlDDMysrC2FhYeDz+WWvjIwMWFtbw8bGBra2trCxsUGHDh0UaksdgUCAhQsXIjg4GIGBgdDX1+csFmozpCp+fn6YNWsWDh8+DEdHR67DkUmU+OSQuzcfV6JTUJsfXU3X8aWmplZIhgUFBaxEaGNjg7Zt29bLZJiXl4exY8eisLAQvr6+aNKkCafxUJsh1REaGoqRI0di5cqVmDt3LtfhyBxKfHIoMjELbl6hKCip+ZicEiOA3+w+sNRvXuvrv337tiwZPnjwAHw+H8rKymVJUPRq1apVra8hC0QTBiwtLbF//36oqqpyHRK1GVJtL168gL29Pezt7eHp6UmTsMqhxCen/lurszrUVZTQNOEamqY9wenTp6GlpSWWWBiGQWJiIisR8vl8aGpqVkiG4tiaRxoeP34MR0dHzJw5E8uXL5eZp1lqM6QmMjIy4OzsDG1tbRw/fpz2+/wXJT459jH5xaBQUPrZbk8eD1BXUcYKe2O42ehh3rx5CAkJQWBgIPT09CQSG8MwePHiBSsRhoeHQ0dHpywJ2trawsrKSmwJWFwuX76M8ePHY+fOnRg7dizX4bBQmyE1VVRUhOnTpyM2NhYXL16U+54YcaDEJ+ceJWVhX3A8bjxLBQ8fF6eLiPbjG2ikgzkDDMsKUzMMg61bt2LXrl3w9/dH9+7dpRKrUCjEs2fPWOOFkZGR0NPTY40Zdu/enbMF4YcOHcLKlStx5swZ9O3bl5MYPofaDKkNhmGwZs0aHDt2DEFBQTAxMeE6JE5R4qsn0vOK4BuehJh3ucgpLIGWuiqMdTXhYvXpHdjPnDmDuXPn4siRI7C3t5dyxB8JBAJERUWVJcIHDx7g6dOnMDQ0ZHWRWlhYSHRfO6FQWJbwAgMD0aVLF4ldqy6ozZC6OHr0KJYtW4ZTp05h4MCBXIfDGUp8Ci4kJATOzs746aefMHv2bK7DAfCxa+bJk+Wi7/QAACAASURBVCesMcPY2FiYmJiwkmG3bt3EMuGksLAQkydPRmJiIs6fPw8dHR0xfBeSQW2G1NX169cxduxYeHp6YuLEiVyHwwlKfATPnz+Hvb09nJycsHnzZihVsfMDFwoKChAZGckaM3z58iXMzMxYY4bGxsY1mr2WlpaGESNGoG3btjh69CjU1dUl+F3UHbUZIg7R0dFwcHDAxIkTsXr1apmZvCUtlPgIgI+zv0aMGIGWLVvC29sbGhoaXIdUpdzcXERERLDGDN+9e4fu3buzxgwNDQ0rTeZxcXGwt7fHqFGj8Msvv8hkwv8vajNEXFJSUjBs2DAYGxvj0KFDUFNT4zokqaHER8oUFRVh6tSpePHiBS5cuICWLVtyHVKNZWZmIjw8nDVmmJWVVVZ9RvRKSkqCq6sr1q9fjxkzZnAddrVRmyHilJ+fj/HjxyMzMxNnz55Fs2bNuA5JKijxERaGYbB69WqcOHECgYGBMDY25jqkOitffebBgwe4ffs2srKyYGVlhaFDh5Y9HbZp00bmu3yozRBxKy0thYeHB/766y8EBQWhY8eOXIckcZT4SKUOHz6MH374AadPn0b//v25DkcsGIbBpk2b8Ntvv+GPP/5AQUFB2ZjhgwcPoKKiwhovtLGxkbmnXmozRFL27t2LDRs24Ny5c+jRowfX4UgUJT7ySdeuXcPYsWPx66+/Yvz48VyHUyclJSWYPXs2wsLCEBAQgLZt27K+Lqo+U37yTPnqM6JEaG1tzWn1GWozRJICAgIwZcoUHDhwAM7OzlyHIzGU+MhnPX36FA4ODpg2bRpWrlwp812BlcnOzoarqytUVVVx6tQpaGpqVutzDMPg+fPnrPHC8PBwtGzZklWgW5rVZ6jNEEkLDw+Hk5MTFi9ejEWLFsllm68KJT5SpeTkZAwbNgzdunXDgQMH5Gr21+vXr+Hg4IC+ffti165dUFH5/Ea+VSktLUVsbCwrGUZGRqJ9+/asyTOWlpYSqYtIbYZIg6jd9OvXDzt37qxzu5E1lPhItXz48AHffvst8vLy4Ofnh6ZNm3IdUpWk9Zdr+eozoq7S/1afsbW1hbm5eZ2rz1CbIdJSvqfEx8cHjRs35joksaHER6qttLQUS5YsweXLlxEUFIQOHTpwHdIncT1WIao+U37MsHz1GVFXadeuXWtUfYbaDJGmkpISzJkzB3w+v9KxcXlFiY/U2K5du7Bp0yacP38eX3zxBdfhVCCrs9Py8/MRGRnJ6iZ99eoVzMzMWGOGn6s+Q22GSFv52dABAQEwNzfnOqQ6o8RHauXixYuYNm0avLy8MGLECK7DAcBejxQYGIhOnTpxHVKVylefET0dJicnw9LSkjVmKKo+Q22GcOXUqVP47rvv4O3tjSFDhnAdTp1Q4iO1xufzMXz4cHh4eGDBggWczv6qTxUoRNVnyneTiqrPXL9+HadPn4atrS309fXr5Yw7Irvu3LkDFxcXrFu3Du7u7lyHU2uU+EidvHr1Cg4ODhg4cCB27NhRowLR4pKSkgInJycYGRnV25qDqamp4PP5ZcXE+Xw+ioqKKiy4l4fqM0S+yWON2/+ixEfqLDs7Gy4uLlBXV8fJkyelOvtL0arMl28zb9++ZS22L199pvyYoaxVnyHyLy0tDcOHD4eenp5c7GryX5T4iFiUlJRg1qxZePjwIQICAqCrqyvxa964cQNubm7YsmULJk2aJPHryYLPtRmGYfD69WtWIgwLC4OmpiYrEXJdfYbUD+X3sbxw4QJatGjBdUjVRomPiA3DMPjll19w8OBBBAQEwMzMTGLXOnbsGDw8PBRuJ+matpny1WdEY4bh4eFo1aoVa/KMNKvPkPpDKBRi5cqVOHPmDIKCgtC5c2euQ6oWSnxE7E6ePIkFCxbgxIkT+Prrr8V6boZhsHbtWhw7dgyBgYEwMTER6/llnTjajKj6TPnJM/+tPmNra4vu3btLpPoMqX8OHTqElStXwtfXF3369OE6nCpR4iMScfv2bbi6umLDhg2YNm2aWM5ZVFSEGTNmICYmBv7+/mjVqpVYzitPJNVmBAIBnj59yhozLF99RtRVKo7qM6R+unz5MsaPH4+dO3di7NixXIfzWZT4iMTExsbC3t4eY8aMwfr16+s0+yszMxMjR46EtrY2jh8/rrBPItJsM0VFRXj8+DFrzDAuLg4mJiasMcOaVp+RhLS8IviGJSEmOQc5hQJoqavAuLUWXK310LwxJWppefz4MRwdHTFz5kwsX768wmQzWblPlPiIRKWmpmL48OHQ19fH4cOHazX768WLF7C3t4e9vT08PT05WTIhK7huM+Wrz4i6Sl+9egVzc3NWN6mRkZFU7lNkYhb2BsfjZmwqAKBIICz7mrqKEhgAA4x0MKe/ISzayX592frg7du3cHR0hJWVFX777TeoqqrK3H2ixEckrqCgAJMmTcK7d+9w/vx5NG/evNqfvX//PkaOHIkVK1Zg7ty5EoxSPshimxFVnyk/Zli++ozo6dDAwECsa76Oh77EhqAYFApK8bkfCY8HqKsoY4W9Mcb37CC265NPy8vLg5ubG4qLi+G6fBd+vfFSpu4TJT4iFUKhED/++CPOnj2LoKAgGBoaVvkZPz8/zJo1C4cPH4ajo6MUopR98tJmMjMzERYWxhozFFWfKd9NWtvqMx+TXjQKSoRVH/wvDVUlrLA3oeQnJQKBACM8tuGJShdApfpFJaRxnyjxEak6ePAgVq9eDT8/P/Tq1avSYxiGwa+//ort27fj4sWLsLKyknKUskue28z79+9ZyfDBgwcoLi6usOC+qh0AIhOz4OYVioKSUtb7p2b0RM9O7N6EZ8m5GLLzVtm/NVSV4ePeE+Z61O0paZGJWRjjFYLC//xx0kBFCcu/MYGjuS4aN1DBkzfZ+DkoGg8Ts8qOkfR9osRHpO7SpUuYOHEidu/ejTFjxrC+JhAI8N133+HOnTsIDAxEu3btOIpSNtW3NlO++oyoq1RVVZW1xvC/1Wfcvfm4Ep1SodtMlPj+uJtQ9t77nELsv/Wi7N88HjDEtBX2j7eR+Pem6D51nzaM6IZxPfQRk5yD2JRcOJq1wYdiAfp53kBmfgkAyd+n+rWtLpELQ4cOxZUrVzBs2DAkJCTg+++/B4/HQ15eHsaMGQOBQIA7d+7QgmoF0KZNGzg5OcHJyQkAu/rMgwcP8Ouvv4LP56NJkyYfZ5Ba9cD1/K6fHStaFxD1ya8xDHDjWSrS84potqcEpeUV4WZsaoX71LyRGlyt26FUyGDcoftI/1AMgZCBs6UeJtl1wI5rcQAkf5/kr7ooqRcsLCwQEhICHx8fuLu74+XLl+jbty/atGmDgIAASnoKisfjQV9fH6NGjcKmTZtw9epVZGRk4Nq1a3BxcUF4lhoEJSWfPUfkT4Px6KfBODGtB8z1mlS8BgDf8CQJfQcEAHzDKv/5dmmlCTUVJbzNKkD6h2IAwOOkbACAqS67zUvyPlHiI5xp27Ytbt26hZiYGJiYmGD48OE4ePAg52vCiGxRUlKCoaEhxo4dC0Ob/oBy5f9/5BUJcDU6BQGP3uJNVgF6G7bAsSlfQOc/TwyFAiFi3uVKI3SFFZOcw1qyINKi8cdJLh+KBWXv5Rd/HKvV0ZTefaKuTsKpe/fuISYmBn369MHZs2cxbdo0Gtcjn5Rd8OmnvenH+GX/rarMw40lA6DXrCHsDJrjYuRb1rEnzpzFDjdLicWp6HRGrULDzj0qvJ+W9/Epr5Ha/1NPowYf13um5hZVOD6n8PNP97VFT3yEMwcPHsSkSZNw/vx5XL58GZMmTYKdnR3Cw8O5Do3IAIZhEB8fj1OnTmHp0qXo378/Ll08W+mx6qpKaKlZ+ViQUFhxQHCcqzMYhqGXhF7fuo6s9F7Evc9FsUCINk01yp7+RDM3o5NzKhyvpS6Z3h964iNSJ1rT5+fnh9u3b5dVdF+yZAk6dOiAIUOG4MiRI3BwcOA4UiIt5Se1lH9pamqWLXdYuXIlHgta48C9pArdaC0aNcC1Jf0R8jwdb7IKYNW+GfSaNURqbiHuPk9jHauuogRjXU1pfnsKx7i1FhqoJFe4T2l5xfANT8K3X7THiWk9EZuSCwczXeQVCXA05BXrWEneJ1rOQKSqsLAQkyZNwps3b3D+/PlK9/AKDQ3FyJEjsWrVKsyZM4eDKGVXfWkz7969Y1V64fP5UFJSKlvPZ2trC2tr6wqFyNPyitB78/UKv1AbqSljpYMpehk0RystdeQWliD8dRa2Xn6GuPd5rGMbqCjh3veDaFanBH3qPgEff/4r7E3gYPbvOr63OdgQFIXw11kVjpPUfaLER6RGtGtz+/btq6zbKarP6eDgAE9PT7GWupJn8thmUlNTERYWxkp0hYWFrEXrtra2aNOmTbWquHxqfVh10Do+6XH35uNKVApq83+rpO8TJT4iFXFxcbC3t4erqyt+/vnnaiWyjIwMODs7o3nz5vD29lbYHRnKk/U2k5WVVVadRZToRKXKyi9I79ChQ61KlQGfrtxSHVS5RXr8gvlYHPgaPJWaP7FR5RYi9+7cuQMXFxf8/PPPmD59eo0+W1RUhOnTpyM2NhYXL15UyD34ypOlNpOXl4fw8HBWd+W7d+/QvXt31tOcoaGh2J/YqVanbLty5QrGjRuHsT/tw+X3jWTuPlHiIxIljt3YGYbBmjVr4O3trZC7rpfHVZspKChAZGQkq7vy5cuXMDMzY9XaNDY2ltq2UbQ7g2z6/fffsWLFCpw5cwZ9+/aVyftEiY9IBMMw2LhxIw4cOICAgACYmZnV+ZxHjx7FsmXL4OPjgwEDBtQ9SDkkjTZTXFxctgGtKNHFxsbCxMSENSYnCxvQPkrKwr7geNx4lgoePi56FhHt8zbQSAdzBhhS96aECYVCrFq1Cj4+PggKCkKXLl3KviZr94kSHxG7kpISzJ49GxEREfD390ebNm3Edu7r169j7Nix2Lp1KyZMmCC288oLcbcZgUCAqKgoVqHop0+fwsDAgNVdaW5uXqtNhKUlPa8IvuFJiHmXi5zCEmipq8JYVxMuVrQDuzQUFhZiypQpePXqFS5cuAAdHZ1Kj5OV+0SJj4hVdnY2XFxcoK6ujpMnT6Jx48Ziv0ZUVBQcHBwwefJk/PTTT7WeJCGP6tJmhEIhnj17xhqTi4yMhJ6eHqu7snv37mjUqJGYIyf1VXp6OkaMGAFdXV0cPXoUGhoaXIdUJUp8RGxevXoFBwcHDBw4EDt27JDoWE9ycjKcnJxgYmICLy8vqKlVf6NLeVbdNsMwDF68eMEakwsPD4eOjg6ru9LS0hJNmlQs5ExIdcTHx8Pe3h7Ozs745Zdf5GbZESU+IhZhYWFwcnKCh4cHFixYIJWnsPz8fIwbNw5ZWVk4e/YsmjVrJvFrcq2yNsMwDBITE1ljcmFhYWjcuDFrCYG1tTWaN2/+iTMTUjP37t3DqFGjsHbtWri7u3MdTo1Q4iN15u/vj6lTp+LgwYMYObLyGn2SUlpaiqVLl+LSpUsICgpCx44dpXp9aePxeJVu3lq+6okoybVu3ZrrcEk95ePjg/nz5+PYsWMYOnQo1+HUGCU+Uie7d+/Gxo0bcf78eXzxxRecxbFnzx788ssvOHfuHHr0qFgVXl6lpaWxxuQuXLgAbW1tVneljY0N2rZtq1BjnYQbDMNg8+bN2LdvH/z9/WFhYcF1SLVCiY/UiuhJ6++//0ZgYKBMPGmJnjwPHDgAZ2dnrsOpsaysLISHh7PG5TIyMlhVT8aMGQOhUEhJjkhdSUkJ5syZAz6fj4CAALRt25brkGqNEh+psQ8fPmDcuHHIycmBn5+fTI2thYWFYfjw4Vi8eDEWLVokswkiLy8PERERrO7Kt2/fwtLSkjUu17lzZ9aEAWozhAs5OTlwdXWFsrIyfHx8oKkp37tbUOIjNZKcnIxhw4bB1NRUZmdTvn79Gg4ODujXrx927twJFRVud98SVT0pPy6XkJAAMzMz1riciYlJlTNhqc0QaUtMTISDgwN69+6N3bt3c96exIESH6k20fq5KVOmYNWqVTL7NAV8XE/o6uoKNTU1nDp1SiLrCStTXFyMJ0+esLornz17BmNjY9aYXNeuXWv1RwO1GSJN4eHhcHJywqJFi7B48WKZbvM1QYmPVMv169fh5uaGbdu2yU3FFNGYRFhYGAICAsRaQQb4WPUkOjqa1V355MkTGBgYsCafiLPqCbUZIi2BgYGYPHky9u/fj1GjRnEdjlhR4iNVkucamQzDYNOmTdi/f3+daoYKhULExsayuivLVz0RvSwtLSVa9YTaDJGGffv2Yf369Th37hx69uzJdThiR4mPfBLDMFi9ejVOnDiBwMBAGBsbcx1SrZ06dQrfffcdjh8/jsGDB3/2WFHVk/JJLjw8HC1atGCNyVlZWUm96gm1GSJJQqEQHh4eCAwMRFBQEDp16sR1SBJBiY9USrQPXlxcHC5evIiWLVtyHVKdifYFXL9+PWbMmAHgY5JLSkpijcnx+Xw0atSI1V0pK1VPqM0QScnPz8eECROQnp6Os2fPQltbm+uQJIYSH6kgIyMDI0eOhI6ODry9veWi6Gx13bt3Dy4uLujUqRO0tLQQFhYGAKwnORsbG5mtekJthkhCSkoKnJyc0KVLFxw6dAgNGtTvHS3kf14qEasXL17A3t4ew4YNw+bNm+Wm6Gxl0tLSEBYWxpp8UlBQAHNzc8THx0NfXx937tyBoaFhvZmtRkhNRUdHw8HBARMmTMCaNWsUoi3QEx8pExoaCmdnZ6xatQqzZ8/mOpwayc7OLktyokSXkZEBKysr1tNcx44dwePxUFhYiMmTJyMpKQnnz59HixYtuP4WqoXaDBGn4OBgjBkzBlu2bMGkSZO4DkdqKPERAICfnx9mz56NI0eOwN7enutwPuvDhw+IiIhgjcu9efMG3bt3Z62V+2/Vk/8SCoVYsWIFfH19ERQUhM6dO0vxu6gdajNEXLy9vbF06VKcPHkSgwYN4jocqaLEp+AYhsG2bduwc+dOXLx4EZaWllyHxFJYWFhW9USU6BISEtCtWzfW5BNjY+NaV5Tw8vLCqlWr4Ovriz59+oj5OxAvajOkrhiGwbp163DkyBEEBgbC1NSU65CkjhKfAhMIBJg/fz7u3buHwMBA6OnpcRqPqOpJ+e7K8lVPRK9u3bqJvVTa33//jQkTJmDXrl1wc3MT67nFidoMqYvi4mLMmDED0dHRuHjxosxO4pI0SnwKKjc3t6zS/+nTp6GlpSXV65eveiJ6PXnyBB07dmSNyZmbm0ttVumjR4/g6OiIWbNmYfny5TI5yE9thtRWZmYmnJ2d0bRpU5w4cQINGzbkOiTOUOKrJ9LyiuAbloSY5BzkFAqgpa4C49ZacLXWQ/PG7KnJb968gYODA3r06IE9e/ZAVVVVorEJhULExcWxuisfPnyItm3bsroru3fvLrWamp/y9u1bODo6wsrKCr/99pvEfzY1RW2G1EZCQgLs7e0xdOhQbN26tcpi6PUdJT45F5mYhb3B8bgZmwoAKBIIy76mrqIEBsAAIx3M6W8Ii3ZNERkZiWHDhmHevHnw8PAQ+1MNwzBISEhgJbnw8HA0b96c1V1pbW0t9aon1ZWXlwc3NzcUFxfjzJkzMhUntRlSU/fv38fIkSPx448/Yt68eVyHIxMo8cmx46EvsSEoBoWCUnzux8jjAeoqyhiuX4o/lk/Bnj17MHr06DpfX1T1pPyYHJ/PR8OGDVndldbW1nKzXEBEIBBg4cKFuHnzJgIDA9G+fXuuQwJAbYbUzNmzZzFz5kz88ccfGDZsGNfhyAxKfHLqY9KLRkGJsOqD/8WUFGGqVVOs/rZ2U5dTUlIqlPYSCoWwtbUtS3TW1tbQ1dWt1fllDcMw2LFjB7Zt24YLFy7A2tqa65CozZBqYRgG27dvx6+//ioz/+/KEkp8cigyMQtuXqEoKCllvW+qq4UfhhrDTK8J1FWUkZSZj6Ohr3A89FXZMRqqyvBx7wlzvaafvUZ6ejrCwsJYie7Dhw+sMTkbGxvo6enJ5CQQcTp37hzc3d1l4q9majOkKgKBAAsWLMCtW7dkqrdCllDik0Pu3nxciU6p0L15Z9lA6DVriIeJWXiRlocRFm2hpMTDWK9QhLxIB/Cx23OIaSvsH29T9rns7GyEh4ezuivT0tJgbW3NGpfr1KlTvU9yn/LPP/9gxIgRnI+TUJshnyPL49OyhGp1ypm0vCLcjE2tkPRUlHjQbfJx2v8yv0jEpuTBUKcxzPWaQq/Z/5cDMAxwLToFv/y6G1Hh9/HgwQO8efMGFhYWsLW1hZOTE9atW4cuXbrIdZ1Ocfviiy9w9+5d2Nvb4/nz5zQzjsgc0Yxka2tr7Nu3T+ZmJMsSeuKTM/tvPsf2q7Gs2ZsiKx1MML1PJ9YTX0xyDty8QpFTKPj/gaUlMC6OwxiLFrCxsYGJiUmtq54oGq7XQlGbIZV5/Phx2RrUH374QWF7ZqqL/qSXMzHJOZUmPQC4/DQFiRn56N6uKZwt9SAQMrgclYK8IgH7QGVVmNh9jSlTpsDMzIySXg00a9YMf//9NzQ1NTFgwACkpKRwHRJRcJcvX8aXX36JzZs3y2zhBVlDiU/OsJ7cymnaUBVHptiinXZDuOy/B/O1fyPqXQ4WftUF3/bQr+Q8JZIOtd5SU1PD0aNH4eDggJ49eyIqKorrkIiC8vLywsSJE3H27FmZLrUna+hPfTmjpV75LWvXrCEaqqmgWCDEo6RsFJcK8Tw1D93bNYWhTsVqKFrq1P9fFzweD6tXr0bHjh0xcOBAhaxwT7hTfmeR27dvy8XOIrKEEp+cMW6tBTXldyguZY/zxL/PQ2Z+MZo1VMOJ6T3wOiMfw8zbAAD4LzNYx6qrKMFYV1NqMddnEydORPv27RVyTzPCDdFekomJiQgJCZG74hCygLo65Qifz8eVA+tRVFRU4WsFJaWYcuQBbselwrBlY9h308Wr9A9Y6/8UAY/fsY5lALhYcbsTQ30yYMAABAcHY+3atVi9ejVNPiESk5aWhq+++goAcO3aNUp6tUSzOmUcwzD466+/4OnpiefPn2PhwoV40qwXbsSlf7ZM2adUto6PiEdKSgqcnJxgZGQELy8vNGjQoOoP1RC1GcUVFxcHe3t7uLi4YMOGDbTcqA7oJyejiouLceTIEZiZmeHHH3/EtGnT8Pz5cyxevBgLvjKGukrt1pCpqyhjzgBDMUdLAKBVq1a4ceMG8vLyMGTIEGRkZFT9IUKq4c6dO+jbty+WLVuGjRs3UtKrI/rpyZjs7Gxs2bIFnTp1wp9//ont27cjIiIC48ePL1uQatGuKVbYG0NDtWa3T0NVCSvsjassV0Zqr2HDhjhz5gysra3Rq1cvvHjxguuQiJw7efIknJ2dcfToUcyYMYPrcOoFmtwiIxITE7Fjxw4cOXIE33zzDQICAtC9e/dPHj++ZwcAqNHuDCvsjcs+RyRHWVkZ27ZtQ6dOndC7d2+cO3cOPXv25DosImcYhsHGjRuxf/9+XL16Febm5lyHVG/QGB/HIiMjsXXrVgQFBWHy5MlYsGBBjYrKPkrKwr7geNx4lgoegMJK9uMbaKSDOQMM6UmPAwEBAZgyZQr279+PUaNG1fl81GYUQ0lJCWbPno3w8HAEBASgTZs2XIdUr1Di4wDDMLh27Ro8PT3x5MkTfPfdd5g5cyaaNq19YkrPK4JveBJi3uUip7AEWuqqMNbVhItVxR3YiXSFh4fDyckJCxcuxJIlS+pUWUNR24wiyc7OhqurK9TU1HDq1Ck0blxxHS6pG0p8UlRSUoLTp09j69atKC4uxtKlS/Htt99KZPYfkS2JiYlwcHBAnz59sGvXrlqXiVO0NqNoXr9+DQcHB/Tv3x87duygcoISQolPCnJzc3Ho0CHs2LEDnTp1goeHB4YOHUozsxRMTk4ORo8eDWVlZZw6dQqamjUvIqAobUYRhYWFYfjw4ViyZAkWLlxINTcliH7zStC7d++wfPlydOzYEaGhofDz88ONGzdgb29PSU8BaWlpwd/fH23btkW/fv3w5s0brkMiMsLf3x9Dhw7F7t27sWjRIkp6Eka/fSUgKioK06ZNQ9euXZGXl4d//vkHPj4+sLGhReOKTlVVFQcOHICbmxvs7OwQGRnJdUiEY3v27MHMmTMRGBiIkSNHch2OQqAOZDFhGAa3bt2Cp6cn+Hw+5s2bh7i4ODRv3pzr0IiM4fF4+P7779GhQwd8/fXXOHbsGIYOHcp1WETKSktLsXTpUly6dAl3795Fx44duQ5JYdAYXx0JBAKcO3cOnp6eyM7OxpIlSzBhwgRoaGhU/WGi8O7evQsXFxesXbsW7u7ulR6TllcE37AkxCTn4M8z5/Ct60gYt9aCqzXN2JVX+fn5GDduHLKysnD27Fk0a9aM65AUCiW+Wvrw4QMOHz6MX3/9Fbq6uvDw8ICTkxON3ZEai4+Ph729PUaOHMkqRxWZmIW9wfG4GZsKAKwNiEVrNAcY6WBOf0NYtKM1mvIiJSUFw4YNg7GxMQ4dOgQ1NTWuQ1I4lPhq6P3799izZw/279+PPn36YOnSpejVqxfXYRE5l56ejhEjRkBXVxdHjx6FX2QKVeWph6KiouDg4IDJkyfjp59+okksHKHEV01xcXHYtm0bTp8+jdGjR2Px4sXo0qUL12GReqSwsBBTpkxBVLE2ikwdWVV4qvKxDqsJJT8Zdv36dYwdOxaenp6YOHEi1+EoNEp8VQgJCYGnpyfu3LmDWbNmYd68eWjZsiXXYZF6KuJ1Blx+u4NS/H/3DcOWjfHDUGNYtW8GNRUl3ItPw9qAKLzJKmB9VkNVGT7uPak0nQw6evQoli1bBh8fHwwYMIDrcBQezeqshFAoxMWLF+Hp6Ynk5GQsXrwY3t7eaNSoEdehkXrut5svIOQpigtIigAAFWRJREFUf9wtGICWugqOT+2B1k3UcTU6BSWlQnzTTRf6zRth6K5brG7QQkEp9gXH016LMoRhGKxZswbe3t4IDg6GiYkJ1yERUOJjKSwsxLFjx7Bt2zY0adIEHh4ecHZ2hrJy7fa+I6Qm0vKKcDM2lZXMrPW10bqJOhIz8jH9GB8AEDS/D0zbNMEQ09a49DS57FiGAW48S0V6XhHN9pQBRUVFmD59OmJjYxESEoJWrVpxHRL5F01BxMeJBevXr0eHDh3g7+8PLy8v3L9/H66urpT0iNT4hiVVeK9IUAoAaNpQFe2aaaC1ljpaaqkDAEx0tSoczwPgG17xPES6MjIyMHjwYHz48AE3btygpCdjFDrxJSQkYP78+ejcuTNevnyJ69evw9/fH/369aPZVkTqYpJzWEsWAOB+QgYevMyAproqbi8bhNDlX6LFv09zOpoVn+oKBULEvMuVSrykci9evECvXr1gY2ODM2fOoGHDhlyHRP5DIbs6+Xw+PD09ce3aNcyYMQNPnz6Frq4u12ERBZdTKKjwXqmQwVivUDiY66JzS028zSrAFx21MaJ7W2R8KP7EeUokHSr5hNDQUIwcORIrV67E3LlzuQ6HfILCJD6hUIi//voLnp6eSEhIwMKFC3Ho0KFaVcgnRBK01CtvjjwecOHhWwCAdiM1LPn64zKau/FpnziPqmQCJJ/l5+eHWbNm4ciRI3BwcOA6HPIZ9T7xFRUV4c8//8TWrVuhpqYGDw8PuLq6QlWVfjkQ2WLcWgsNVJIrdHd6T+2BzPxi5BQIMMBIB80bN8C1mBSEvEivcA51FSUY69Ifc9LEMAy2bduGHTt24PLly7C0tOQ6JFKFepv4srKycODAAezatQvdunXDzp078eWXX9LYHZFZLtZ62H41tsL70ck5cDRrg6YNVfE+twi/Bcdjx7W4Ss/BAHCx0pNwpEREIBDgu+++w507dxASEoJ27dpxHRKphnqX+F6/fo2dO3eWdTcEBQXBwsKC67AIqVKLxg3Qv4sOrkSnsJY0rPWPwlr/qCo/z+MBA/99IiSSl5ubCzc3N5SWluLOnTvQ0qo4y5bIpnozqzMyMhLjx4+HpaUleDweHj58iGPHjlHSI3Jl7gBDqKvUbgmNuooy5gwwFHNEpDJv3rxBv3790LZtW/j7+1PSkzNST3xpeUXYf/M5FvpEQGfUKiz0icD+m8+RnldU43MxDIMrV65g8ODBsLe3h7m5OV68eIGtW7dSlwORSxbtmmKFvTE0VGvWND/W6jSmcmVSEBkZCTs7O7i5ueHAgQM0X0AOSa1Wpzi3WCkpKYGPjw+2bt1atpnj2LFjaXsPUm8cD31Zvd0ZAKir0u4M0nLp0iVMnDgRu3fvxpgxY7gOh9SSVBJftRtxFVus5ObmwsvLCzt27IChoSE8PDwwdOhQmrBC6qVHSVnYFxyPG89SwQNYuzWoqyihuKQErUrTcGCBMz3pScHBgwexevVq+Pr6onfv3lyHQ+pA4onvY9KLRkFJ7bdYefv2LXbt2oVDhw7h66+/xtKlS2FtbS2hiAmRLel5RfANT0LMu1zkFJZAS10Vxrqa6Kenht42FoiMjKSufQkSCoVYvnw5zp07h6CgIBga0jiqvJNo4otMzIKbVygKSkpZ729ztUBvgxZo1kgVH4pK8fhNFrZceoan73LKjtFQVcbGr1ri4pE9OH/+PCZMmIBFixahQ4cOkgqXELnzww8/IDMzEwcOHOA6lHqpoKAAkyZNwrt373D+/Hk0b96c65CIGEg08bl78ytMzQaAUzN6IiWnELmFAtgZNIeBTmMkZeajz5Yb/z+IEaL0VQRmdVPG7Nmzoa2tLakwCZFbGRkZ6NKlC+7fvw8DAwOuw6lXUlNTMXz4cOjr6+Pw4cNQV1fnOiQiJhJLfGl5Rei9+XqFKhT/1bWNFgLn90WpkIHRqr8gEP4/HDUVJYR8P4jWJRHyGWvXrsXz589x7NgxrkOpN2JjY2Fvb48xY8Zg/fr1UFKqNyu/CCS4gL2yLVbKm2inj84tNdHL4GPXgdftF6ykB3xca+EbnoSZ/egvWUI+ZdGiRTA0NERUVBRMTU25Dkfu3b59G66urtiwYQOmTZvGdThEAiT2Z0xlW6yUZ99NFxN66sNApzHeZhUg7FVmhWNoixVCqqalpYWlS5di9erVXIci9/7880+MGjUK3t7elPTqMYklvsq2WCnPzSsURqv+woxjfLTSUse+cVZo21SjkvPQFiuEVGXu3Lm4e/cuIiIiuA5FLjEMg59//hnLly/HtWvX8PXXX3MdEpEgiSW+T22x0kBFCUr/LrsrEghxMzYVH4oFUFVWQnvtihs2pr1LRHR0NEpLSyt8jRDyUaNGjbB8+XKsWrWK61DkTklJCaZNm4Zz584hJCQEZmZmXIdEJExiY3yf2mLFsl1T7HSzxD8JGcguKIFtB21oqasiLa8IT95ks45VhhCZL55g2LBleP/+PSwtLWFrawsbGxvY2NjAwMCAFq8T8i93d3d4enoiJCQEdnZ2XIcjF7KysuDi4oKGDRvi5s2baNy4MdchESmQ+qzOji0aYeNIMxi11kQjNRVkfCgG/1UGdl2PQ2xKHuvYBipKuPfvrM6MjAz8r717D4qyXuMA/l0uR0gjvIthoQgsl7jt7tGyKbUaJxAyrxGOzWjkpKWni5dJx0Ynx5JTWpaZWNOFaEiZBhUaK7NmPFHz7sIG4mKC4oiJGSY3uSy77/mDs3v4BajIsu8u+/3M+Idc3vdxRvm6z7O/5y0uLoYkSdDr9dDr9WhsbIRGo7EHoU6nw4QJExiG5LH27duHL774AkePHlW6FJd37tw5JCcnY+bMmdixYwe8vW9tOTi5H0XO8d0MlQqYFTUWexZre/2aP/74wx6Cer0ekiTBYrHYg9AWhkFBQf34UxC5D7PZjMjISOzduxczZ85UuhyXpdfr8dhjj2Ht2rVYvXq10uWQkymyueVm+Pt6I/eZqX3aQSjLMn7//fduYThkyBAhCDUaDUaPHt3nmojcweeff47du3fj+PHj7H704ODBg1i2bBmysrIwZ84cpcshBbjFrs7+kGUZ586dE4LQYDAgMDDQHoRarRYajQaBgVz0S+7PYrEgNjYWmZmZSEpKUrocl/LOO+/g9ddfR35+PnQ6ndLlkELc6ukMjmK1WlFVVWUPQr1ej5KSEgQFBQlt0sTERA67yS3l5eVh69atMBgMfNWHzv8MvPTSS/jmm29QWFjInb8ezmnP47vRI1ZkADMiRmPF9MmKPGLFYrGgoqJCaJOWlpYiJCREaJPGxcXB37/7eUMiVyLLMjQaDTZs2IB58+YpXY6impubkZ6ejsbGRuTl5bGzQ84LPpveHrEyPzHY5XZyms1mlJeXC21Sk8mE8PBwoU16zz338CG45HIKCwuxZs0alJaWeuw7Fmtra5GSkoLo6Gjs3buX/04JgALB5+5aW1tRVlYmtEkrKysRHR0tnDGMioqCj8+AHZMkuiFZlnH//fdjxYoVSE9PV7ocpysvL0dycjKWLVuGjRs3suVLdgw+B7h27RqMRqNwxvD8+fOIi4sTZoYRERHc8k5OdezYMWRkZMBkMsHX11fpcpzm6NGjSEtLw1tvvYXFixcrXQ65GAbfAGloaEBxcbHQJr18+TISExOFmeGkSZP4P1EaUA899BDS0tLw9NNPK12KU3z88cdYt24dvvzySzz44INKl0MuiMHnRFeuXIHBYBDapE1NTfbtM7ZWKbfPkCMVFRVh0aJFOH36NIYMca05uiPJsoxNmzYhJycHBQUFUKvVSpdELorBp7BLly7BYDDYg1CSJFitViEItVott89Qv8yePRuzZs3C888/r3QpA6KtrQ1Lly5FVVUVDh48iDFjxihdErkwBp+LsW2f6TovlCQJ/v7+wrxQq9Vi1KhRSpdLbqKkpATJycmorKzEbbd1fwqKO6urq8Pjjz+OMWPG4LPPPuNxI7ohBp8bkGUZ1dXVwhlDg8GA4cOHC/PCxMREnlGiXi1YsAA6nQ5r165VuhSHqaqqQlJSElJTU/HGG2/wzWN0Uxh8bspqtaKyslJ4VWg0GoXtMzqdDgkJCdw+QwCAkydPYvr06aisrERAQIDS5fRbUVER5s6di02bNuHZZ59VuhxyIwy+QaTr9hlbq7SsrAwhISHCvJDbZzzXkiVLEBoaildffVXpUvpl//79WLlyJT755BM8+uijSpdDbobBN8jZts90nRmaTCZEREQI80Jun/EMVVVVmDJlCk6dOoWRI0cqXU6fybKMzMxM7Nq1C4cOHUJ8fLzSJZEbYvB5oNbWVpSWlgpt0jNnziA6Olpok0ZGRnL7zCC0fPlyjBgxAtu2bVO6lD7p6OjAc889h6KiIhQUFCA4OFjpkshNMfgIQOciX6PRKLRJa2pq7NtnbK3S8PBwvoHAzZ0/fx7x8fEoLy/HuHHjlC7npjQ2NmLhwoUAgNzc3EExoyTlMPioV/X19SgpKRHapLbtM11nhtw+435Wr14NlUqFnTt3Kl3KDdXU1GD27NmYOnUq3n33XXYhqN8YfNQndXV19u0ztl9NTU3dzhhy+4xrq62tRVRUFH799VdMmDBB6XJ6ZTQakZKSglWrVuHll1/m3ylyCAYf9Vttba0QhpIkQZZlIQh1Op3btNU8xfr16/HXX3/hgw8+ULqUHn399dd46qmn8N5772HBggVKl0ODCIOPHE6WZVy4cEGYF+r1emH7jE6ng0aj4fYZBV25cgXh4eH45ZdfEBoaqnQ5gj179mDz5s3Iy8vDfffdp3Q5NMgw+MgpbNtnugahwWDAiBEjhHmhRqPBHXfcoXS5HmPz5s2oqqrCp59+qnQpADoXM6xfvx75+fkoLCx0uUCmwYHBR4qxWq04ffq0MC80Go0YP3680Cbl9pmB09DQgMmTJ+OHH35AVFSUorW0tLRgyZIluHTpEr766iu3PGdI7oHBRy7FYrHAZDIJ88ITJ05g4sSJQps0Li4Ofn5+Spc7KGzfvh2SJGH//v2K1XD58mWkpqZi0qRJ+Oijjwb145NIeQw+cnnt7e0oLy8XZoYVFRX27TO2VmlMTAy3z9yC5uZmhIWFoaCgAAkJCU6/f0VFBZKTk/Hkk09iy5YtfOcmDTgGH7kl2/aZrjND2/aZrjNDbp+5Obt27cKRI0dw+PBhp973xx9/xMKFC7Ft2zYsXbrUqfcmz8Xgo0GjubkZJSUlwsywpqYG8fHxwsyQ22e6a2trQ1hYGHJzc3Hvvfc65Z7Z2dl48cUXkZOTg4cfftgp9yQCGHw0yNXX16O4uFiYGdbV1SExMVGYGU6cONHjW2xZWVnIzc3Fd999N6D3kWUZr732Gj788EMcPnwYMTExA3o/or9j8JHHsW2f6dombW5uFoJQq9UiODjYo8LQbDYjMjISWVlZmDFjxoDco729HcuXL0dZWRkOHTqEoKCgAbkP0fUw+IjQuX2ma4tUkiQAEIJQq9UO+u0z2dnZeP/993H8+HGHh/7Vq1cxb948DBs2DDk5ORg6dKhDr090sxh8RD2QZRk1NTVCGNq2z3QNQq1WO6jOm1ksFsTGxiIzMxNJSUkOu251dTWSk5PxyCOP4M0334S3t7fDrk3UVww+opskyzLOnj0rvCosLi7GyJEjhSB09+0zeXl52Lp1KwwGg0Ne9UmShDlz5mDdunVYtWqVAyok6h8GH1E/dN0+Y5sZGo1G3HnnncLMMCEhwW1ae1arFVqtFhs3bsTcuXP7da38/HxkZGRg3759SE1NdVCFRP3D4CNysI6ODmH7jF6vt2+f6domdeXtM4WFhVizZg1KS0tvuS359ttvY/v27cjPz4dWq3VwhUS3jsFH5ATt7e04ceKEEIYVFRVQq9VCm9RVts/Isoxp06Zh5cqVSE9P79P3WiwWvPDCC/j+++9RUFCAu+++e4CqJLo1DD4ihbS0tKC0tFSYGZ49exYxMTFCm1StViuyfebYsWPIyMiAyWRCfZsVBww1qKhtQENrBwL8fKAeF4AFmmCMHPb/vZrNzc1IS0vDtWvXcODAAQQGBjq9bqIbYfARuZCmpiYYjUbhjOGFCxfs22dsrdKwsDCnbJ+Zlvokhv1zLqrbOueTbR1W++f8fLwgA5geMRorHpyMMT4tSElJQWxsLPbs2eMSr1yJesLgI3Jx9fX1whPu9Xq9fftM15mho7fPZP9cjS2Hy9FmtkJ1nZBVqYB/eKnQ9nMOMmZE4pVXXvGog//kfhh8RG7ozz//FMJQkiS0tLQI88L+bJ/J/rkaWwtNaDFbb/zF/+OrkvFqagwWTw3p8/2InInBRzRIXLx40R6GkiRBkiR4eXkJQajT6TB27NjrXufX81fxRNbPaDFbun0uNW483nmi89FFH/3nLLYcPil83t/XG7nPTEVsMGd75LoYfESDVNftM11nhkOHDhWCUKPRCNtnnvlMj29Nl/D3nwzjAvxw5F8P4LZ/eMPX26vH4FOpgFlRY7FnMY8vkOti8BF5EFmWcebMGWFeaDAYMGrUKGi1WkRrpiK7IQI9dTg/XzYFo28fglO1jUiJG99j8AHAEB8v/LRupvBuTyJXwid0EnkQlUqF0NBQhIaGYtGiRQA6N7X89ttv0Ov1+MJ4GWYvM+DtK3zfsmkToQ0Zjsd3/4Sl00Kufw8AB4prsPyB0AH6UxD1D4OPyMN5eXlBrVZDrVZD71uCcuPvwufDxw7D2lkR2PHtbzh5seGG12vtsKLiYuNAlUvUbww+IrJraO3o9rFHY4Lg6+2FKZNGQjdxBCLHBQAAHo4ci1azBduPnOrhOuYBr5XoVjH4iMguwK/7jwQVAC8vFWZEjBE+fteI25B41/BeruPb48eJXAGDj4js1OMCMMSnVtjQsvPoaew8etr++3/Pj8V8zYRe39zi5+MFddDtTqmX6FYM/M4jInIb8zXB/b6GDGB+Yv+vQzRQeJyBiAS9neO7GTzHR+6Ar/iISLBy+mT4+dzaM/j8fLyxYvpkB1dE5FgMPiISxE0IxIYkNfx9+/bjwd/XCxuS1FxXRi6Pb24hom5si6a3FlagtcNy3banStX5Sm9DkpoLqsktcMZHRL0qrbmK3T9U4tipy1Ch83C6je15fDMiRmPF9Ml8pUdug8FHRDdU19SGA8U1qLjYiIZWMwL8fKEOuh3zE4O5k5PcDoOPiIg8Ct/cQkREHoXBR0REHoXBR0REHoXBR0REHoXBR0REHoXBR0REHoXBR0REHoXBR0REHoXBR0REHoXBR0REHoXBR0REHoXBR0REHoXBR0REHuW/Wf7d4x4SecIAAAAASUVORK5CYII=\n",
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# Define Petersen graph in NetworkX\n",
"G = nx.petersen_graph()\n",
"\n",
"# Draw the Petersen graph\n",
"nx.draw_shell(G, nlist=[range(5, 10), range(5)], with_labels=True, font_weight='bold', font_color='w')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Use the code below to learn whether the Petersen graph is planar or not. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> *Note.* You may need to update to the latest version of NetworkX to use `nx.check_planarity()`. To do that, go to the Anaconda Prompt (search in the Windows Start Menu) and then type \n",
">\n",
"> ```\n",
"> pip install networkx --upgrade\n",
"> ```\n",
">\n",
"> You'll need to restart the kernel in Jupyter in order to access the new version of the package once it is installed."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(False, None)"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Check for planarity\n",
"nx.check_planarity(G)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On paper, can you build the Petersen graph from $K_{3,3}$ using the actions described above? "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
}
],
"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.7.6"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
![\"Drawing\"](\"img/graph.png\")
\n",
"![\"Drawing\"](\"img/social_network_leg.png\")
\n",
"\n",
"![\"Drawing\"](\"img/social_network_deg.png\")
\n",
"\n",
"![\"Drawing\"](\"img/social_network_deg_centrality.png\")
\n",
"![\"Drawing\"](\"img/closeness.gif\")
\n",
"\n",
"![\"Drawing\"](\"img/closeness_centrality.png\")
\n",
"\n",
"![\"Drawing\"](\"img/betweenness.png\")
\n",
"\n",
"![\"Drawing\"](\"img/betweenness_centrality.png\")
\n",
"\n",
"![\"Drawing\"](\"img/Question_7_solutiona.jpg\")
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Problem 8 (Eulerian graphs)__. A path in an undirected graph $G$ is called _Eulerian_ if it uses all of the edges of $G$ precisely once. A path where the initial vertex and the last vertex are the same is called a _cycle_ or a _circuit_. A graph $G$ that has an Eulerian cycle (an Eulerian path that is also a cycle) is called an *Eulerian graph*, named after Leonhard Euler (look up the Königsberg Bridge Problem if you are curious about how such graphs first appeared). \n",
"\n",
"Define a graph $P$ with six vertices 0, 1, 2, 3, 4 and 5 and edges (0, 1), (0, 3), (1, 2), (2, 3), (3, 4), (3, 5), (4, 5). Draw $P$ using NetworkX. Then convince yourself that $P$ is Eulerian. \n",
"\n",
"The code \n",
"\n",
"```\n",
"list(nx.eulerian_circuit(G))\n",
"```\n",
"\n",
"produces an Eulerian cycle for a graph `G` if one exists. Use this code to check your work. Find the degree of each vertex in $P$. The degrees all share a common property; can you guess what it is? Make your guess and then check out the cell below for a fun fact about Eulerian graphs."
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Eulerian circuit: [(0, 3), (3, 5), (5, 4), (4, 3), (3, 2), (2, 1), (1, 0)]\n",
"Degree of vertex 0: 2\n",
"Degree of vertex 1: 2\n",
"Degree of vertex 2: 2\n",
"Degree of vertex 3: 4\n",
"Degree of vertex 4: 2\n",
"Degree of vertex 5: 2\n",
"All the degrees are even!\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3dd1gU99YH8O8sS1NYiYoBSyQRARsqEMUYWgRRmoKKiliCEa4aRWNeG3bFkmvsEgNG7IoSRSCI9KKGGEAxURC4iQWvKBoFVJayzPuHF6Kh6+7OlvN5Hp8n2Zmd/RLCcfjNmTMMy7IghBAiHTyuAxBCiDKhoksIIVJERZcQQqSIii4hhEgRFV1CCJEifnMbO3fuzBoYGEgpCiGEKIasrKzHLMvqNrat2aJrYGCAzMxMyaQihBAFxTDMnaa20fICIYRIERVdQgiRIiq6hBAiRVR0CSFEiqjoEkKIFFHRJYQQKaKiSwghUkRFlxBCpIiKLiGESFGzd6QRQmTb4+eVCM8qQl5xGcqENRBo8GGiJ8AE8+7opKXOdTzSCCq6hMihnHvPsDelEKn5JQCAypra+m0a/GJsT8iHrbEu5tgYYmAPHa5ikkZQ0SVEzhzNuI3AmDwIa0Ro7Glbwv8V4LibD5GW/xgBTibwtjSQbkjSJCq6hMiRVwU3FxXVtS3uy7JARbUIgTG5AECFV0bQhTRC5ETOvWcIjMlrVcF9XUV1LQJj8nC96JmEkpG2oDNdQuTE3pRCCGtEb7ympsLD+jH9MdywE3TaqeHukxf45sItpPxvrbeOsEaEoJRC7PO2kGZk0ggquoTIgcfPK5GaX9JgDVeFx+BBaQUmBWfgfmkF7Iy7YI+XGUbtSEPRs4r6/VgWSL5VgifPK6mrgWO0vECIHAjPKmr09YpqEXYkFqDoWQVYFkjKe4R7f71E/24dGuzLAAjPbvw4RHqo6BIiB/KKy95oC2tKZy01fNS5PQoelTfYJqypRd6Dhq8T6ZLq8gI1chPydsqENS3uw+cx2DFxMH7MLsJ/Sl40cZxqcUcjbSSVokuN3IS8G4FG8z+qDANs9xyEalEtVkXeaOY4quKORtpI4kWXGrkJeXcmegKo84ubXGL4xsMUnbXUMePgFdTUNvKDBkCDz4OJvrYkY5JWkOia7t+N3I0X3Ne93sh9NOO2JGMRInfGm3dvclvg2P4w7KKFmYd/bXbdlwUw3qzp4xDpkFjRbamR26BTO9xaNwrbPQe98To1chPSUGctdZjpawC1b/48ddPRxJShPdFXX4Bfl9vjxhpH3FjjiDGDur6xH8MAdsa6dO1EBkhseaGxRu7XrRvTHzlFpY1uo0ZuQv7GsixCQkKQtHs/BO6rUP3ab433n1XAYNlPLR5Dg6+CObaGEkxJWksiRbepRu46rqb6KKuoRvajp+jZqX2D7dTITcgrT58+ha+vLwoKCpB69iQyn2m0evZCHU1VHgKcTGDanS5SywKJLC801cgNAFrqfCx0MMKGn3KbPQY1chNld+nSJQwePBjdunVDRkYGTExeXWQOcOoDTVUVMEzz72cAsNWVmG4qoIvTMkQiRbe5Ru5FDkY49es9FJcJmz0GNXITZSUSibB+/XqMGzcOe/bswY4dO6ChoVG/3dvSAGG+lnDs+z7U+Txo8N/8Mdbg86DO58Gx3/uY30+E7xZ5obi4WNpfBmmCRJYXmmrk7qsvwHDDznDend7K41AjN1EuRUVF8Pb2Bo/HQ3Z2Nrp27drofqbddbDP2wJPnlciPLsIeQ/KUSashkBDFSb62hhvVnfDkQXK79zA2LFjkZycDE1NTel+QaQBiRTdphq5LT/qiO7vaeLyks8AAO3U+FDhMejd5VO47LnYyHGokZsoj3PnzsHPzw/+/v5YvHgxVFRUWnxPJy11+Fn3anaf1atXIy8vDzNnzsSxY8fAtLQuQSRKIkW3qUbu41fuIirnQf2/z7L6CN3f08SKc783OAY1chNlUVFRgf/7v/9DTEwMIiIiYGlpKdbjMwyD0NBQ2NraYsOGDVi5cqVYj0/aRiJruk01cgura1HyvLL+z8uqGlTW1OKvF1UN9qVGbqIMbt68iaFDh6KkpATZ2dliL7h1NDU1ERERgf379+PUqVMS+QzSOhIpup211GFjpNvi1dUdiQVYeOpaww21tRj8vhq1ixGFxbIsgoODYWNjA39/f5w8eRI6OpJt6dLX18e5c+cwd+5c/PrrrxL9LNI0id2RNtfWEBr8ltekGqOqwiB571Js2bIFIlHTN1gQIo+ePn0KT09PBAUFIS0tDTNnzpTaOuugQYMQEhICd3d3FBVRSyYXJFZ0B/bQQYCTCTRV2/YRmqo8rHbrj1/On0ZMTAxsbW3x559/SiglIdJV13vbtWtXZGRkoE+fPlLPMHbsWMybNw9ubm548aLxEZBEciQ68KZNjdwMoKmqggCnPvC2NICBgQGSkpIwZswYDBkyBKGhoWBbmppDiIx6vfd29+7d2Llz5xu9t9K2ePFimJqaYurUqaitbduDLsm7YZorZBYWFmxmZuY7f8j1omcISilE8q0SMPh7nCPwqkuBxathHHNsDRu9VfH69euYOnUqPvroIwQHB0NXV/edMxEiLa/33h45cgTdunXjOhIAoLKyEg4ODvj000+xceNGruMoFIZhsliWbXR4jFQe11PXyH15yWdY6GAE1ftXYaGvDvdB3bDQwQiXl3yGfd4WTd4bbmpqiitXrsDIyAgDBw5EdHS0NGIT8s7OnTsHc3NzjBw5EvHx8TJTcAFAXV0dZ86cQVhYGA4fPsx1HOXBsmyTf8zNzVlJMDY2Zm/cuPFW701NTWV79uzJzpo1iy0vLxdzMkLE4+XLl+zcuXNZAwMD9vLly1zHadaNGzdYXV1dNj09nesoCgNAJttEXeXkwZSVlZVQV3+7djBra2tcv34d1dXVGDRoEH7++WcxpyPk3bzee3v16lUMGzaM60jN6tu3Lw4fPowJEybQRWspkLuiCwACgQChoaH45ptv4O7ujhUrVqCqquENFoRIE8tB7624jBo1CsuWLYOrqyvKysq4jqPQOCu64rhy6+HhgWvXrtWfTeTmNj8ukhBJ4bL3VlzmzZsHKysrTJ48mfrjJUguz3Rfp6enh+joaPj6+sLKygq7du2iFhgiVbLQeysODMNg165dqKysxNdff811HIUl90UXePU/i5+fH37++WccP34cjo6OdLcNkThZ670VB1VVVZw+/erGpODgYK7jKCSpF93a2lqIRCKoqop/bGPv3r1x8eJFWFtbw8zMDCdPnhT7ZxACvOq9HTFiBJKTk5GVlQVXV1euI4nNe++9h+joaKxcuRJJSUlcx1E4Ui+6lZWVUFNTk9h6F5/Px8qVKxETE4M1a9Zg8uTJePr0qUQ+iygnWe69FZfevXvj5MmTmDx5MvLz87mOo1A4KbriXFpoioWFBbKzs6GrqwtTU1MkJCRI/DOJYquoqMCXX36JBQsWICIiAsuXL2/VoHF5ZWdnhw0bNsDFxYVOXMRIYYsuALRr1w67du3CDz/8gBkzZsDf3x8VFRVS+WyiWOSt91ZcZs2aBRcXF4wfPx7V1fT4LHFQ6KJbZ+TIkbh+/TqKi4thZmaGrKwsqX4+kV/y3HsrLv/+97+hqamJefPm0dApMVCKogsAHTt2xMmTJ7Fy5UqMHj0agYGBqKlp/AGahACK0XsrDioqKjh+/DguXbqEXbt2cR1H7ilN0QVetZZ5eXkhKysLSUlJsLa2RmFhISdZiGxTlN5bcREIBIiKisLmzZtx/vx5ruPINaUqunV69OiB+Ph4TJw4EZaWlggJCaFfmwgAxey9FRcDAwOEh4dj+vTp+P33hg+TJa2jlEUXAHg8Hvz9/ZGWlobvvvsObm5uKC4u5joW4ZAi996Ky/Dhw7Ft2za4ubmhpKSE6zhySWmLbp2+ffsiIyMDpqamGDRoECIiIriORDigDL234uLt7Y3JkyfD3d0dlZWVXMeRO0pfdAFATU0NgYGB+PHHH7Fo0SL4+PjQpCUloWy9t+Kyfv166OnpwdfXl5bm2oiK7muGDx+Oa9euQUVFBYMGDUJ6ejrXkYgEKWvvrTjweDwcOnQIv//+O7Zs2cJ1HLki9aIrFApltugCgLa2NkJCQrBjxw54enpi6dKl9CuUgqHeW/Fo3749IiMjsWfPHpw9e5brOHKDznSb4ObmhpycHOTm5mLo0KF0tVZB1PXe7t27V6l7b8WlW7duiIiIgK+vL65evcp1HLlARbcZXbp0QUREBObPnw87Ozt8++23NKtXjl2+fBmDBw+Gvr4+fvnlF6XvvRUXCwsLfPfddxgzZgwePHjAdRyZx0nRlae+R4Zh4OPjg19++QVnz57FiBEjcPfuXa5jkTYQiUTYsGEDPDw8sHv3buzatUuu/h+UB+PHj4evry/GjBlD801aQGe6rfTRRx8hNTUVjo6OMDc3x5EjR+iqrRyo671NTEyk3lsJCwgIQO/evTFjxgz6jbAZVHTbQEVFBUuXLkVcXBw2b94MT09PPHnyhOtYpAl1vbcODg5ISEig3lsJYxgGP/zwA+7evYu1a9dyHUdmUdF9C4MHD0ZWVhY++OADmJqaIjY2lutI5DVCoRDz5s3DggULcPbsWQQEBFDvrZRoaGggIiIChw4dwokTJ7iOI5Oo6L4lDQ0NfPvttzhy5Aj8/Pwwd+5cvHjxgutYSu/mzZsYMmQIHj58iKtXr+KTTz7hOpLSef/99xEZGYn58+fjl19+4TqOzKGi+44+++wz5OTkoKysDGZmZrhy5QrXkZQSy7IICQmp770NCwuj3lsOmZqa4sCBA/Dw8KALz//Al/YHKlrRBQAdHR0cOXIEp06dgqurK2bPno2AgACJPHyTNPT06VP4+voiPz8faWlp1AomI1xdXZGfnw83NzdcvHgRWlpaXEeSCXSmK0aenp7Izs7Gzz//jOHDh+PWrVtcR1J41Hsr27766itYWFhgypQpEIlEXMeRCVR0xaxbt26IjY3F9OnTMXz4cAQFBVFrmQRQ7618YBgGQUFBKC0txbJly7iOIxOo6EoAwzCYO3cuLl26hIMHD2L06NH473//y3UshUG9t/JFTU0NP/74I86cOYPQ0FCu43COiq4EGRsb49KlS7C0tMTgwYMRHh7OdSS5R7238qlTp06Ijo7GkiVLkJaWxnUcTlHRlTBVVVWsWbMGkZGRWL58OaZNm4bS0lKuY8kd6r2VfyYmJjh27Bg8PT3xn//8h+s4nKGiKyVDhw7F1atXoaWlBVNTU6SkpHAdSW5Q763icHBwwKpVq+Dq6qq0Jx9UdKWoffv2CAoKwr59+zBlyhQsWrQIQqGQ61gyi3pvFdOcOXMwYsQIeHp6oqamhus4UkdFlwOjR49GTk4O7ty5AwsLC1y7do3rSDKnbu7tnj17aO6tAtq+fTsAYOHChRwnkT56cgRHOnfujNOnT2PJkiVwcHDAli1bqI/xf6j3VvHx+XyEhYUhISEBQUFBXMeRKjrT5RDDMJg6dSoyMzMRExMDW1tb/Pnnn1zH4gz13ioXHR0dREdHY926dYiPj+c6jtRQ0ZUBPXv2RFJSEsaMGYMhQ4YgNDRU6W6ooN5b5dSrVy+cOnUK3t7eyMvL4zqOVNCTI2SEiooKvv76ayQlJWHHjh1wd3fHo0ePuI4lFdR7q9ysra2xadMmuLq6KsV8ajrTlTEDBgzAlStXYGxsjIEDByIqKorrSBJT13vr7+9PvbdKzsfHB2PHjsW4ceNQVVXFdRyJoqIrg9TV1bFlyxaEhYVh/vz58PX1xfPnz7mOJVav995eu3aNem8JNm/ejA4dOmDOnDkKvbwm1aLLsiyqqqqgpqYmzY+VW9bW1sjJyUF1dTUGDRqEy5cvcx3pndX13lpbW2P+/PnUe0vqqaio4NixY/j111/rW8oUkVTn6VZVVUFVVRU8ntRPsOWWQCBAaGgozp49Cw8PD3zxxRdYtWqVXP7F9frc2/T0dGoFIw1oaWkhKioKw4YNg5GREVxcXLiOJHZSrX60tPD23N3dce3aNVy7dg3Dhg3DzZs3uY7UJnW9t3p6etR7S5r1wQcf4Mcff4SPjw+uX7/OdRyxo6IrR/T09BAVFQU/Pz9YW1tj165dMv+o67reW3d3d+zatQu7d++m7hXSIktLS+zcuRNubm54+PAh13HEioqunGEYBr6+vsjIyMCJEyfg6OiIoqIirmM16vXe2+zsbLi5uXEdiciRyZMnY9q0aXB3d1eoGSVUdOWUoaEh0tPTYWNjAzMzM5l73DX13hJxWLNmDbp3746ZM2cqTEcDFV05xufzsWLFCsTExGDdunWYPHkynj59ymkm6r0l4sTj8XDw4EHk5+dj48aNXMcRCyq6CsDCwgJZWVnQ1dWFqakpZ/exU+8tkYR27dohMjIS33//vUI8fYWKroJo164ddu3ahQMHDsDHxwf+/v6oqKiQymdT7y2RNH19fZw7dw6zZ89GZmYm13HeCRVdBePg4ICcnBw8fPgQZmZmyMrKkujnvT73Nj09HV988QXNvSUSMXjwYAQHB2Ps2LG4f/8+13HemlRvjqCiKx0dO3bEyZMnceLECYwePRr+/v5YsmQJ+Pymv92Pn1ciPKsIecVlKBPWQKDBh4meABPMu6OTVuPfs8uXL8PLywuurq44cuQItYIRiXN3d0deXh7c3NyQlpaG9u3bcx2pzZjmrghaWFiw4jyVj4qKwvfff4/o6GixHZM07969e/j888/x8uVLHD58GIaGhm9sz7n3DHtTCpGaXwIAqKz5u+9Xg88DC8DWWBdzbAwxsMerJQORSITNmzdj9+7dCA4OplYwIlUsy2LGjBl48eIFTp06JZN3uDIMk8WyrEVj26Salp4aIX09evRAXFwcJk6cCEtLSwQHB9e33hzNuI1JIRmIz32IypraNwouAAj/91rczYeYFJKBoxm3cf/+fdjb2yMhIQFZWVlUcInUMQyD4OBgFBcXY9WqVVzHaTNa01UCPB4P/v7+SEtLw759++Dq6oq9cb8hMCYXFdUitNT+yLJARbUIa6N+xxCvr+qLLvXeEq6oq6vj7NmzOH78OI4ePcp1nDahNV0l0rdvX2RkZGD+2m/xTXwBGP6b34vtnoMwvFcnaKqpoOR5Jb5P/QNhmffqt1fXMmhvNQ2u04dT7y3hnK6uLiIjI/HZZ5/ho48+kpsWRamf6dLFFm6pqamh1sQBPH7Dv/yCUgrx6TfJGLA2DrMOZ+LrkUbo31Xwxj7Vta/2I0QW9O/fHwcPHsS4ceNw+/ZtruO0Ci0vKJnHzyuRml+CxlYUCh49R5Xo1bouy77607PTm1eHWRZIvlWCJ88rpZCWkJY5OTlhyZIlcHV1RVlZGddxWkRFV8mEZzU/HGf9mP7IXTsKSYts8ai8Esm3Gj6njQEQni2bQ3aIcvL398cnn3wCLy8viEQiruM0i4qukskrLmvQpfC6led+R781sRi/7zJibxSjqpF9hTW1yHtQLsmYhLQJwzDYs2cPKioqsHjxYq7jNIuKrpIpE9a0uE8tC2TeeQr9DhrwtuzZxHGqxR2NkHeiqqqK06dPIyoqCvv37+c6TpOk3r3QsWNHaX4k+QeBRuu/5So8Bj07tmviOKriikSI2HTs2BHR0dGwsrJCr169YGdnx3WkBuhMV8mY6Amgzm/4be/UXg2upvpop6YCHgNY9+4Mt4Fdcek/jxvsq8HnwURfWxpxCWkzIyMjHD9+HJMmTUJBQQHXcRqgPl0lM0DrBaqqqgDem996FoD30J4IHDsADAPcf1aBddE3kZDb8EIaC2C8WXfpBCbkLYwYMQLr1q2Di4sLMjIy8N5773EdqR4VXSVx69YtrF27FomJiejrtwO3qwVvtI399aIKE0MyWjwOwwB2xrpNDsEhRFb4+fkhNzcXEyZMwPnz56GqKhtLYrS8oOD++OMPzJgxA59++in69euHwsJC7Jg1Ghqqb3dHmQZfBXNsDVvekRAZ8O2330JNTQ3+/v4y87gfKroK6u7du/D19cXHH3+Mnj17oqCgAAEBAdDW1sbAHjoIcDKBpmobv/01VTAVFWBAtw6SCU2ImKmoqODkyZNIS0vDnj17uI4DgJYXFM79+/exceNGnDx5En5+figoKGi0Y8Tb0gAAEBiTB2FN80NvGObVGe68z3ojZPE6LHheiO3bt8vkSD1C/kkgECAqKgqffPIJevfujVGjRtVve5s50u+Kiq6CePjwITZv3oxDhw7Bx8cHubm56NKlS7Pv8bY0gGl3HQSlFCL5VgkYvLrxoU7dPF07Y13MsTWEaXcdeCUnw9nZGTNnzkRISEizg9EJkRUffvghTp8+DQ8PD6SkpKBau2szc6SLsT0hv8EcaXGhoivnHj9+jH//+98ICQmBt7c3bty4AX19/Va/37S7DvZ5W+DJ80qEZxch70E5yoTVEGiowkRfG+PN3vwbX0dHB3FxcXB3d8ekSZNw7Ngx+p4SufDpp59i69atcPbfDHXLyagU1Tb6G17diUfczYdIy3+MACeT+t8MxYGKrpx6+vQptm3bhqCgIEyYMAE5OTno0aPHWx+vk5Y6/Kx7tWrf9u3bIyoqCpMnT4abmxvOnDkjl49NIcqHZ2QNnoXOG7/RNaVujnRgTC4AiK3w0pMj5ExZWRnWr1+P3r174/79+8jMzMS+ffveqeC+DXV1dZw6dQp6enpwdHREaWmpVD+fkLbKufcMgTF5EOHvzp1pw3oicu5w3Fo/ClvHmzb6vorqWgTG5OF60TOx5KDuBTnx4sULbNmyBYaGhsjPz8fPP/+MAwcO4MMPP+QsE5/PR2hoKMzMzGBnZ4eSkhLOshDSkr0phRDWvDmB7GFZJfYkF+J0ZvNT84Q1IrHNkaaiK+MqKiqwbds29OrVC9nZ2UhNTcWRI0fQu3dvrqMBePUooJ07d8LZ2RnW1tYoKqKRj0T21M+R/sca7oUbxYi7+RBPX1Y1+35xzpGmJ0fIqMrKSuzZsweGhoZIT09HXFwcwsLC0KdPH66jNcAwDNavX4+ZM2fCysoKhYX0ZAkiW1qaI90a4pojTRfSZEx1dTVCQ0OxYcMGDBgwAJGRkTA3N+c6Vqt8/fXXEAgEsLGxQWxsLAYMGMB1JEIAtDxHujXENUeaiq6MqKmpwdGjR7Fu3ToYGhoiLCwMw4YN4zpWm/n6+kIgEMDBwQGRkZEYMmQI15EIadUc6dYd593nSEut6LIsS0W3ESKRCGFhYVi7di309PRw8OBBWFtbcx3rnUyaNAna2tpwcXFBWFiYTM40JcqlLXOkmz/Ouw/Nkdqabk1NDXg8Hj26+39qa2tx+vRpmJqaYs+ePQgKCkJKSorcF9w6zs7OOHXqFCZOnIioqCiu4xAl19QcaRUeA3U+Dyo8BrzX/rkx4pojLbUzXTrLfYVlWURGRmL16tXg8/nYunUrRo0aBYZp/Bstz2xtbREdHQ03Nzds27YNXl5eXEciSmq8eXdsT8hv8Po8O0MssDeq/3ePwd2xIyEfOxIbDj8X1xxpKrpSwrIsYmNjsWrVKlRVVWHdunVwc3NTyGL7uiFDhiAhIQGjRo1CeXk5/Pz8uI5ElFBnLXXYGOki/ubDN+ZI70gsaLTA/pM450hT0ZUwlmWRlJSElStX4tmzZ1i7di3GjRunVBO6+vfvj9TUVDg4OKC0tFTmn9ZKFNM08y6I++0eoKLW5veKc4601H7ylbHopqenw87ODrNnz8bcuXPx22+/YcKECUpVcOv06tUL6enpOHjwIJYvXy4zA6WJcigpKcG8KWNgKvpPm+dIa6ryEOBkAtPu4pk2RkVXAjIyMjBy5EhMnz4dM2bMwM2bNzFlyhSlv4jYrVs3pKam4sKFC5g3bx5qa9+tb5KQ1rh//z6sra3h4uKCc1sXIcCpDzRVVdDSyh7DAJqqKghw6iPWKWNUdMUoKysLzs7O8PT0xPjx45GXl4cZM2bQzNnX6OrqIikpCdevX8eMGTNQUyOe/klCGnP79m1YW1tjxowZWL9+PRiGgbelAcJ8LeHY932o83nQ+EdXgwafB3U+D45930eYr6VYCy5Aa7picf36daxevRpXrlzBsmXLcObMGYX9WsWhQ4cOiI2Nxbhx4zBhwgScOHGCbg8nYnfr1i04ODhg8eLF+PLLL9/Y1tY50uJERfcd5ObmYs2aNUhNTcXixYtx/PhxaGpqch1LLrRr1w7nzp2Dt7c3XFxcEBERAS0tLa5jEQVx/fp1jBo1CoGBgfj888+b3K8tc6TFhZYX3kJBQQGmTp0KGxsbmJmZobCwEF999RUV3DZSU1PDiRMn0LNnT4wcORJPnz7lOhJRAFeuXMHIkSOxY8eOZgsuV6jotsHt27fh4+ODYcOGwcjICIWFhViyZAmdob0DFRUVhISEYOjQobC1tcXDhw+5jkTkWFpaGlxcXLB//354enpyHadRUiu68vzUiHv37uFf//oXzM3N0a1bNxQUFGDlypUQCARcR1MIPB4P27Ztg4eHB6ysrHD37l2uIxE5dOHCBYwbNw4nTpyAi4sL13GaRGu6zXjw4AE2bdqEo0ePYtasWbh16xY6d+7MdSyFxDAMVq9ejQ4dOsDKygrx8fEwMjJq+Y2EAIiIiICvry8iIiIwfPhwruM0i4puI0pKSrBlyxYcOHAA06dPR25uLt5//32uYymFBQsWQCAQwNbWFufPn8fAgQO5jkRk3LFjx7Bo0SLExsbCzMyM6zgtkuqarqy3Bf31119Yvnw5TExMUFFRgd9++w3bt2+ngitlPj4+2LlzJ0aOHInLly9zHYfIsODgYCxevBiJiYlyUXABupAGACgtLcWaNWtgZGSEx48f4+rVq9i7dy+6devGdTSlNWHCBBw6dAhjxoxBQkIC13GIDNq+fTs2btyI1NRU9OvXj+s4rabURbe8vByBgYEwNDTE7du3ceXKFQQHB+ODDz7gOhoBMGrUKJw5cwZeXl6IiIjgOg6RESzLYsOGDfjuu++QlpYGQ0PxDKKRFqVc03358iX27t2LrVu3YsSIEbh48SKMjY25jkUaYWVlhfPnz8PZ2SlahlIAABC2SURBVBnl5eWYOnUq15EIh1iWxdKlSxETE4O0tDTo6elxHanNlKroCoVCfP/999i8eTOGDx+OxMRE9O/fn9NMpGXm5uZISkqCo6MjysrKMHfuXK4jEQ7U1tZi/vz5yMjIQEpKCjp16sR1pLci1aLLVV9rVVUVfvjhB2zcuBGDBw9GTEwMBg8ezEkW8nb69u2LtLQ02Nvbo7S0FMuWLVP4AfDkbzU1NZg1axYKCwuRmJiIDh06cB3prSn0mW51dTUOHTqEDRs2oE+fPvjxxx/p6bRy7MMPP0R6ejpGjhyJ0tJSbN68mQqvEqiqqoK3tzeePXuG2NhYtG/fnutI70QhL6SJRCIcPnwYffr0wYkTJ3Ds2DGcP3+eCq4C6Nq1K1JTU5GUlITZs2dDJBJxHYlIkFAohIeHByorKxEZGSn3BRdQsKJbW1uLkydPol+/fggJCcH+/fuRmJgo83eokLbp1KkTEhMTkZeXh2nTpqG6uprrSEQCnj9/DmdnZ2hrayM8PFzm+/xbSyGKLsuyOHPmDAYOHIjt27dj165dSEtLg62trUQ+j3BPIBDg/PnzKC0thYeHByoqKriORMTo2bNnGDlyJD788EMcPXoUqqqqXEcSG7kuuizLIjo6Gubm5tiwYQM2bdpU/6gcWutTfJqamjh79iy0tLTqW8qI/CspKcFnn32Gjz/+GMHBwQr3mCu5LLosyyIuLg7Dhg3DsmXLsGLFCmRlZcHFxYWKrZJRVVXF0aNHYWhoCHt7e/z1119cRyLv4L///S9sbW0xevRo7NixQyEf4ip3RTc5ORnW1tbw9/fHwoULkZOTAw8PDyq2SkxFRQXff/89rK2tYWNjgwcPHnAdibyFO3fuwNraGt7e3ggMDFTYn2m5aRm7dOkSVq5cibt372L16tXw8vJSuF87yNtjGAbffPMNdHR0YGVlhYSEBBgYGHAdi7RSfn4+HBwcsGjRIsyfP5/rOBIl0aL7+HklwrOKkFdchofG7gj+rQo32f9ggnnrH/p25coVrFq1Cnl5eVi5ciWmTZumUIvqRHwYhkFAQAAEAgGsra0RFxcHExMTrmORFvz2229wdHTEhg0b4OPjw3UciZNI0c259wx7UwqRml8CAKisqQV0jXGxqBKZxfnYnpAPW2NdzLExxMAeOo0e49q1a1i1ahWys7MREBCAyMhIqKmpSSIuUTDz5s1Dhw4dYGdnh59++kluRv4po8zMTLi4uGDHjh2YNGkS13GkQuxF92jGbQTG5EFYIwLLNtwurKkFAMTdfIi0/McIcDJ547nyN27cwOrVq3Hp0iUsXboUp06dUpj+PCI906ZNg7a2dv2ksk8//ZTrSOQf0tPTMW7cOOzfvx9ubm5cx5EasRbdVwU3FxXVtS3uy7JARbUIgTG5AICP36vE2rVrkZiYiP/7v//D4cOH0a5dO3HGI0rG3d0dWlpacHd3x9GjR+Ho6Mh1JPI/8fHx8PLywokTJ2Bvb891HKli2MZOR//HwsKCzczMbNWBcu49w6SQDFRUN7wt8+QsSwzuoYOa2lefVVwmxIhtqfXbebU1eBG5Af5T3TFv3jxoa2u38csgpGmXLl2Cu7s7vvvuO4wbN47rOErv3LlzmDVrlkL/BsIwTBbLshaNbRPbme7elEIIa5q+D35V5A2EZd5rdFstTwUui3dj+eeW4opDSL3hw4cjLi4OTk5OKC8vx4wZM7iOpLROnDiBhQsX4vz58zA3N+c6DifEUnQfP69Ean5Jo2u4rcPg4h9P8eR5Zau7Gghpi0GDBiE5Obl+Qpm/vz/XkZTO/v37sXr1aiQkJCj1HGux3BwRnlXU4j6LHY2RvcIB4X7DYPlhxwbbGQDh2S0fh5C3ZWxsjLS0NOzZswfr1q1Dc0trRLx27tyJ9evXIyUlRakLLiCmM9284rJXbWFN2Bybh4KH5agWsXAdqI/90z+G06503P3rZf0+wppa5D2ge+eJZPXs2fONmbxbt25V2DufZMXGjRsRGhqKtLQ09OzZk+s4nBPLmW6ZsKbZ7dfuPcOLKhGqRLX4Mfs+su78BTvjLo0ch0b0EcnT09NDSkoKLl++DF9fX5rJKyEsy2LZsmU4duwYFdzXiKXoCjTadsLMskBjJxcCDbrTjEhHx44dER8fjz/++ANeXl6oqqriOpJCqa2thb+/P+Li4pCamgp9fX2uI8kMsRRdEz0B1PmNH0qgwYd1785Q5/OgwmMwZlBXDPmwY/3danU0+DyY6FOrGJEeLS0t/PTTTxAKhRg7dixevnzZ8ptIi0QiEb744gtkZWUhKSkJnTt35jqSTBFL0R1v3r3JbXwVHhaNNEbWCgdcXeGAGcMM4HskC38+fvHGfiyA8WZNH4cQSdDQ0EB4eDg6duyI0aNHo6ysjOtIcq26uhpTpkzB3bt3ERcXJ9cPkJQUsVxI66ylDhsjXcTnPmzQNvbXiyqM2Xup2fczDGBnrEvtYoQTqqqqOHz4ML788kuMGDEC58+fp7OztyAUCuHp6Vn/cAG6fb9xYpunO9fWEBr8txu1qMFXwRxbQ3FFIaTNeDwe9u7dC3t7e9jY2OD+/ftcR5IrL168gIuLCzQ1NXHmzBkquM0QW9Ed2EMHAU4m0FRt2yE1VXkIcDKBaffGp40RIi0Mw2DTpk2YOnUqrKys8Mcff3AdSS6UlpbC0dERH3zwAY4fP06jV1sg1oE3ddPCmpsyVodhXp3h/nPKGCFcW7p0KTp06ABra2tcuHAB/fr14zqSzHr8+DEcHR3xySefYOfOnQr5eB1xE/toR29LA5h210FQSiGSb5WAwd/jHIFXXQosXq3hzrE1pDNcIpNmz54NbW1tjBgxAtHR0bCwaHR2iVJ78OABHBwc4Orqio0bN9JNJq0kkSHmpt11sM/bAk+eVyI8uwh5D8pRJqyGQEMVJvraGG/W+idHEMIVb29vCAQCODk54fTp07CxseE6ksy4c+cO7O3t8fnnn2P58uVcx5ErYhvtSIiiSkxMxKRJk3Do0CE4OTlxHYdzBQUFsLe3x8KFC7FgwQKu48ik5kY70gIMIS0YMWIEoqKi8PnnnyMsLIzrOJz6/fffYWtri5UrV1LBfUtSexowIfLM0tIS8fHxGD16NMrLy/HFF19wHUnqsrKy4OzsjO3bt2Py5Mlcx5FbVHQJaSVTU1OkpKTAwcEBpaWlWLRoEdeRpObixYvw8PBASEgIxowZw3UcuUZFl5A26N27N9LT02Fvb4/S0lKsXbtW4a/aJyQkYPLkyTh27BhGjhzJdRy5R2u6hLRRjx49kJ6ejqioKCxYsAC1tS0/iFVeRUVFwcvLC2fOnKGCKyZUdAl5C126dEFycjIyMzMxc+ZM1NQ0P1NaHoWFhWHWrFn46aefYGVlxXUchUFFl5C3pKOjg7i4ONy/fx+TJk1CZWUl15HE5sCBA1i4cCHi4+Px8ccfcx1HoVDRJeQdtG/fHlFRUaitrYWbmxtevHjR8ptk3O7du7FmzRqkpKRgwIABXMdROFR0CXlH6urqOHXqFPT09ODo6IjS0lKuI721TZs2YefOnUhLS4ORkRHXcRQSFV1CxIDP5yM0NBRmZmaws7PDo0ePuI7UJizLIiAgAEeOHEFaWhoMDAy4jqSwqOgSIiY8Hg87d+6Es7MzrK2tUVRUxHWkVmFZFgsWLMD58+eRmpqKrl27ch1JoVGfLiFixDAM1q9fjw4dOsDKygrx8fEwNJTdAf0ikQh+fn64efMmkpKSoKNDU/8kjYouIRLw9ddfQyAQwMbGBrGxsTJ5Qaq6uhrTpk3Do0ePEBcXBy0tLa4jKQUquoRIiK+vLwQCAezt7REZGYmhQ4dyHameUCjExIkTIRKJEB0dDU1NTa4jKQ1a0yVEgiZNmoQDBw7AxcUFycnJXMcB8Op5Zm5ublBXV8eZM2eo4EoZFV1CJMzZ2RmnT5/GxIkTERUVxWmW0tJSjBo1Cl27dsXx48ehpqbGaR5lREWXECmwtbVFdHQ0Zs2ahePHj3OS4cmTJxgxYgRMTU1x4MAB8Pm0usgF+q9OiJQMGTIECQkJGDVqFMrKyvCvf/1Lap9dXFwMBwcHODk5YfPmzQo/GU2WUdElRIr69++P1NTU+pm8S5Yskfhn3r17F/b29pg2bRoCAgKo4HKMii4hUtarVy+kp6fXF97AwECJFcLCwkLY29vD398fCxculMhnkLahNV1CONCtWzekpqbiwoULmDdvnkRm8t64cQO2trZYvnw5FVwZQkWXEI7o6uoiKSkJ169fx/Tp08U6kzc7Oxv29vbYsmULfH19xXZc8u6o6BLCoQ4dOiA2NhaPHz/G+PHjIRQK3/mYly9fxujRoxEUFIQpU6aIISURJ1rTJYRj7dq1w7lz5+Dt7Q0XFxdEREQ0uCX38fNKhGcVIa+4DGXCGgg0+DDRE2CCeXd00lKv3y8xMRGTJk3C0aNH4ejoKO0vhbQCw7JskxstLCzYzMxMKcYhRHmJRCL4+voiNzcXP/30E9577z3k3HuGvSmFSM0vAQBU1vy99qvB54EFYGusizk2hriXcxE+Pj44ffo0bGxsOPoqCAAwDJPFsqxFo9uo6BIiO1iWxaJFi5CYmAi/rUexO/0+hDUiNPNjCoYB+GDx4uIRRGxdhCFDhkgvMGlUc0WX1nQJkSEMw+Dbb79FXzdffBNXiIrq5gsuALAsUM0y0LaejvzaLtIJSt4arekSImOuF5XiGtML4IveeL2Dpiq+GWcKq96d8deLKnxz4RYic/5bv71SxCIwJg+m3XVg2p3m4soqOtMlRMbsTSmEsEbU4PX1Y/qhWlQLi8AELAi7hg1j+6N3lzcvuAlrRAhKKZRWVPIWqOgSIkMeP69Ean5JgyUFTVUVjOqnj2/j8/GySoTMO0+RkPsQHoO7vbEfywLJt0rw5LniPA5e0VDRJUSGhGc1/ly1jzq3h6iWxZ+P/37Ee+6DcvR+X7vBvgyA8Gz5eD6bMqKiS4gMySsue6MtrE47dRU8r6x+47VyYTW01BtelhHW1CLvQbnEMpJ3Q0WXEBlSJmz8VuCXlSJoqau+8ZqWOh/PKxvfv0xY3ejrhHtUdAmRIQKNxhuK/nj8Aio8Bgad2tW/1kdfgIKHjZ/RCjRUG32dcI+KLiEyxERPAHV+wx/LimoRLtwoxlcORtBUVYF5z/fg0Pd9nLl6v8G+GnweTPQbrvUS2UBFlxAZMt68e5PbVpz7HRp8FWStsMeuSYOxIuJ3FDx63mA/FsB4s6aPQ7hFN0cQIkM6a6nDxkgX8bkPG7SNlVZUw/doVrPvZxjAzlj3jSE4RLbQmS4hMmaurSE0+Cpv9V4Nvgrm2BqKORERJyq6hMiYgT10EOBkAk3Vtv14aqryEOBkQrcAyzhaXiBEBnlbGgAAAmPyWjVlTIOvggAnk/r3EdlFRZcQGeVtaQDT7joISilE8q0SMHh140Odunm6dsa6mGNrSGe4coKKLiEyzLS7DvZ5W+DJ80qEZxch70E5yoTVEGiowkRfG+PNutNFMzlDRZcQOdBJSx1+1r24jkHEgC6kEUKIFFHRJYQQKaKiSwghUkRFlxBCpIiKLiGESBEVXUIIkSIquoQQIkVUdAkhRIqo6BJCiBQxbDOTNBiGKQFwR3pxCCFEIfRkWVa3sQ3NFl1CCCHiRcsLhBAiRVR0CSFEiqjoEkKIFFHRJYQQKaKiSwghUvT/xrkz8CLlddkAAAAASUVORK5CYII=\n",
"text/plain": [
"![\"Drawing\"](\"img/petersen.png\")
\n",
"\n",
"![\"Drawing\"](\"img/Question_8_solution.jpg\")
"
]
}
],
"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.7.6"
}
},
"nbformat": 4,
"nbformat_minor": 2
}