Computational Thinking (CO2412) Tutorial 4.6: Week 23

4.6.1 Paths and cycles in graphs

Have a look at the object knowledge_graph from the knowledge-graph notebook. Draw the graph (on paper or on screen) and answer:

  1. Why is knowledge_graph not a tree? Give a concrete example of how the graph violates the definition of a tree.
  2. How many cycles are there in the graph?
  3. For each vertex, what is its indegree and what is its outdegree? (Number of incoming and outgoing edges.)
  4. How many paths of length two (i.e., two edges) are there starting from each of the vertices? How many paths of length five are there in the graph as a whole?
  5. Think of an algorithm that determines the number of paths with a given length (number of edges, i.e., assuming an unweighted graph) starting from a given node. Describe your algorithm (very roughly, at a high level). What would the time and space efficiency of that algorithm be, using an incidence-list data structure?

4.6.2 Spanning trees

  1. What vertices could potentially be used as the root node for a breadth-first tree (BFS spanning tree) that covers all the vertices from the graph? Draw such a breadth-first tree (on paper or on screen).
  2. What is the depth of each of the vertices in the breadth-first tree? Determine or validate this by calling the bfs_depth function developed in one of the previous labs.
  3. Draw a depth-first tree (DFS spanning tree) with the same root node.

4.6.3 Knowledge graphs and predicates

For our purposes, a predicate is a function with a boolean return value. We will discuss them more in depth in the upcoming lecture. A predicate can be used in a similar role as an atomic statement, but with the potential of adding meaning to logical statements in a more explicit and more powerful way.

In the previous lab, we were using atomic statements with the naming convention pxy to state whether there is an edge from vertex x to y. In the present notebook, there is a predicate edge(x, y) with exactly the same purpose.

As an introduction to these concepts, have a look at the predicates defined in the notebook. Assume below that x and y are variables that can refer to any of the nodes from the knowledge_graph object. The logical operators have the same meaning as usual:

  1. Are there any nodes x, y for which the logical expression   edge(x, y) ∧ label(y, "Larnaca")   becomes True?
  2. Are there any nodes x, y for which the logical expression   has_campus_in(x, y) → label(x, "UCLan")   becomes False?