CSC111设计编程代写、Python程序调试、Python语言编程代做

日期：2021-03-28 06:45

CSC111 Tutorial 8: More with Graphs

In lecture this week, we continued our study of graphs by looking at cycles and trees. In this tutorial,

you’ll get some more practice working with graphs, both by doing some more proofs on graphs and

writing some code.

Part 1: Proofs on graphs

1. In lecture, we proved that every non-empty tree satisfies . Our proof relied on the

fact that if we remove a degree-one vertex from the tree, the remaining vertices are still connected

Your first task is to prove this statement.

a. Let , and let be an arbitrary path in , with .

Prove that for all , .

b. Let be a tree, and let be a vertex with . Prove that the graph

obtained by removing from is connected.

2. Prove that any connected graph with at least three vertices has a vertex with degree .

Hint: you can prove this by contradiction.

Part 2: Bipartite graphs

Now, let’s introduce one new definition that is central to many applications of graphs.

Definition. Let be a graph. We say that is bipartite when it satisfies the following

properties:

There exist subsets such that , , and and form a partition of . Th

is, and .

|E| = |V | ? 1

G = (V , E) v0, v1, v2,…, vk G k ≥ 2

i ∈ {1, 2,…, k ? 1} d(vi) ≥ 2

G = (V , E) v ∈ V d(v) = 1

v G

≥ 2

1

G = (V , E) G

V1, V2 ? V V1 ≠ ? V2 ≠ ? V1 V2 V

V1 ∪ V2 = V V1 ∩ V2 = ?

3/25/2021 CSC111 Tutorial 8: More with Graphs

https://www.teach.cs.toronto.edu/~csc111h/winter/tutorials/08-graphs-more/ 2/5

Every edge in has exactly one endpoint in and one in (Equivalently, no two vertices in

are adjacent, and no two vertices in are adjacent).

When is bipartite, we call the partitions and a bipartition of .

Tip: bipartite graphs are typically drawn such that and are clearly separated (e.g., with all the

vertices of on the left, and all the vertices of on the right).

1. To make sure you understand the definition of bipartite graphs, identity which of the following ar

bipartite graphs.

2. Show that the following graph is bipartite by finding a bipartition of .

E V1 V2 V1

V2

G V1 V2 G

V1 V2

V1 V2

G = (V , E) G

V = {1, 2, 3, 4, 5, 6} and E = {{1, 2}, {1, 6}, {2, 3}, {3, 4}, {4, 5}, {5, 6}}

3/25/2021 CSC111 Tutorial 8: More with Graphs

https://www.teach.cs.toronto.edu/~csc111h/winter/tutorials/08-graphs-more/ 3/5

3. Finally, let’s develop an algorithm for computing a bipartition of a graph. Not surprisingly, we can

use the same recursive traversal approach as _Vertex.check_connected, but need to be a bit

clever in how we keep track of which vertices are in which of the partitioned sets.

Download tutorial8_part2.py (starter-files/tutorial8_part2.py) and implement the method

_Vertex.compute_bipartition according to its specification. We’ve provided a few hints in that

file, but this is a fairly complex function to implement, so we strongly encourage you to speak with

your classmates and TAs to share ideas!

After you’re done, complete the method Graph.bipartition to compute a bipartition of a graph.

(As usual, this method will be fairly short, as it should mainly just call the corresponding _Vertex

method.)

Part 3: Visualizing graphs

As our send-off to graphs, we’ll end by exploring how to visualize graphs using a few different

approaches.

1. First, download tutorial8_part3.py (starter-files/tutorial8_part3.py) and open it. Inside, we’ve

provided a fresh copy of the _Vertex and Graph class, and some pygame-related helper functions

that take care of the Pygame window setup for you.

Your task is to complete the method Graph.draw. To do so, you’ll need to review the pygame

functions:

pygame.draw.circle (https://www.pygame.org/docs/ref/draw.html#pygame.draw.circle)

pygame.draw.line (https://www.pygame.org/docs/ref/draw.html#pygame.draw.line)

After you’ve completed this method, test it by running the provided visualize_graph function o

some graphs of your choice. You can use the small ones from lecture or tutorial, or randomly

generate your own graphs! Here are two examples we created, both with 100 vertices and 150

randomly-chosen edges.

3/25/2021 CSC111 Tutorial 8: More with Graphs

https://www.teach.cs.toronto.edu/~csc111h/winter/tutorials/08-graphs-more/ 4/5

2. As you might have realized in completing the previous task, deciding how to positions vertices in

graph isn’t a straightforward task. While we can certainly choose vertex locations in a variety of

ways, it becomes much harder to do so if we want to keep neighbours closer to each other. So in

this final exercise of this tutorial, you’ll explore using a Python library to run a graph layout

algorithm that chooses vertex positions based on the structure of the graph.

a. First, install the new Python libraries networkx, numpy, and scipy. (In PyCharm, open the

Settings/Preferences window and go to “Project: csc111 -> Project Interpreter” and click on

the “+” icon.)

b. After everything has been installed, uncomment the import networkx line at the top of the

Python file and implement the method Graph.draw_nx, following our instructions.

c. Test your work with the visualize_graph_nx function. Try creating a graph with two

separate components (we did this by randomly generating edges between the first 50 vertice

then the last 50 vertices). The graph layout algorithm from networkx produces a graph that

separates these components:

2

3

3/25/2021 CSC111 Tutorial 8: More with Graphs

https://www.teach.cs.toronto.edu/~csc111h/winter/tutorials/08-graphs-more/ 5/5

Further exploration

The networkx library provides several different graph layout algorithms, which you can see on its onlin

documentation (https://networkx.org/documentation/stable/reference/drawing.html#modulenetworkx.drawing.layout).

Try playing around with these!

If you’re interested in graph visualization more generally, you can check out the Graph drawing

Wikipedia page (https://en.wikipedia.org/wiki/Graph_drawing) as a starting point for further reading

Additional exercises

1. Prove that for every graph , if has a cycle of odd length, then is not bipartite.

1. For example, the book review graphs you’re using on Assignment 3 are bipartite, with the two

partitions being the set of “user” vertices and “book” vertices.?

2. You’ll also be installing and using these libraries for Assignment 3!?

3. nx is a common short form for the networkx library.?

4. In fact, the converse of this statement is also true (so it’s an if and only if), but the converse is

harder to prove.?

G = (V , E) G G 4