首页 >
> 详细

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

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Cs2461-10实验程序代做、代写java，C/C++，Python编程设 2021-03-02
- 代写program程序语言、代做python，C++课程程序、代写java编 2021-03-02
- Programming课程代做、代写c++程序语言、Algorithms编程 2021-03-02
- 代写csc1-Ua程序、代做java编程设计、Java实验编程代做 代做留学 2021-03-02
- 代做program编程语言、代写python程序、代做python设计编程 2021-03-02
- 代写data编程设计、代做python语言程序、Python课程编程代写 代 2021-03-02
- Cse 13S程序实验代做、代写c++编程、C/C++程序语言调试 代写留学 2021-03-02
- Mat136h5编程代做、C/C++程序调试、Python，Java编程设计 2021-03-01
- 代写ee425x实验编程、代做python，C++，Java程序设计 帮做c 2021-03-01
- Cscc11程序课程代做、代写python程序设计、Python编程调试 代 2021-03-01
- 代写program编程、Python语言程序调试、Python编程设计代写 2021-03-01
- 代做r语言编程|代做database|代做留学生p... 2021-03-01
- Data Structures代写、代做r编程课程、代做r程序实验 帮做ha 2021-03-01
- 代做data留学生编程、C++，Python语言代写、Java程序代做 代写 2021-03-01
- 代写aps 105编程实验、C/C++程序语言代做 代写r语言程序|代写py 2021-03-01
- Fre6831 Computational Finance 2021-02-28
- Sta141b Assignment 5 Interactive Visu... 2021-02-28
- Eecs2011a-F20 2021-02-28
- Comp-251 Final Asssessment 2021-02-28
- 代写cs1027课程程序、代做java编程语言、代写java留学生编程帮做h 2021-02-28