锐客网

  1. 首页 > it技术 > >

CSC111 More with Graphs

后端

【CSC111 More with Graphs】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.... 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).
  3. To make sure you understand the definition of bipartite graphs, identity which of the following ar
    bipartite graphs.
  4. 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.... 3/5
  5. 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.
  6. 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/r...)
    pygame.draw.line (https://www.pygame.org/docs/r...)
    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.... 4/5
  7. 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.... 5/5
    Further exploration
    The networkx library provides several different graph layout algorithms, which you can see on its onlin
    documentation (https://networkx.org/document...).
    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...) as a starting point for further reading
    Additional exercises
  8. Prove that for every graph , if has a cycle of odd length, then is not bipartite.
  9. 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.?
  10. You’ll also be installing and using these libraries for Assignment 3!?
  11. nx is a common short form for the networkx library.?
  12. 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

    推荐阅读


    上一篇：李宏毅机器学习课程|李宏毅机器学习课程笔记4（CNN、Why Deep、Semi-supervised）

    下一篇：兑现 Service Mesh 的新价值（精确控制“爆炸半径”）