Quiz question 01

Consider the following network:


Which statements are TRUE or FALSE?

1. The degree distribution of this network would generate a graph with equal values of pk for k values. 

2. If link (4-5) were to be removed, then the network would have 2 components. This makes the connection between nodes 4 and 5 to be called a bridge.

3. Considering node 4 as the zero node, the diameter of this network is dmax = 4.

4. The degrees of the two mostl connected nodes are equivalent to 2/3 and 1. 

a.) T F F T

b.) F F T T

c.) T T F T 

d.) F T T F 

e) None of the above

Original idea by: Julia de Pietro Bigi

Comentários

  1. Joao Meidanis7 de março de 2026 às 04:17

    Dear Julia: good question. However, a few things make it hard to grasp. For instance, using the word "graph" in the phrase "the degree distribution would generate a graph" is confusing. One tends to associate the word "graph" with "network" in this course, and not to a pictorial rendering of values. Also, it is not clear what you mean by "equal values of pk for k values". In the network, we see nodes with degree 2 and 3, and that's it. No other degrees. They are not all the same, so it seems that "equal values" is false, but what is the purpose of the part "for k values"? The variable k does not even have a value. Perhaps you meant to say, "for k = 2 and 3"? We don't know. The other thing is that we don't need a zero node to find the diameter. We just try all zero nodes and take the overall maximum. So, Statement 3 sounds weird. Then, in Statement 4, you mention 2/3 as a possible degree. That's funny, since degrees are always nonnegative integers. The value 2/3 = 0.666... is not an integer. For all these reasons, I decided not to include your question in the official blog.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Quiz question 02

What do BFS and DFS have in common? What about their differences?  a.) Common: They both use an adjacency list as input. Both of them can be used to calculate distances and classify edges. Differences: BFS doesn't restart the search when it reaches a target node or when a tree is finished like DFS does. BFS visits all nodes reachable from a given node, so not necessarily the entire tree will be visited. b.) Common: they both use an adjancency list and starting + ending times of node's visits as input.  Differences: BFS can be used to calculate distances and finding connected components. While DFS can be used to detect cycles and classify edges.  c.) Common: they both use an adjancency list as input.  Differences: BFS doesn't restart the search when it reaches a target node or when a tree is finished like DFS does. BFS visits all nodes reachable from a giving node, so not necessarily the entire tree will be visited.  d.) Common: they both need an adjancency list ...
Leia mais

Quiz question 03

How does the Kosaraju–Sharir algorithm identify Strongly Connected Components (SCC)? a.) Performs a DFS on a graph G . Then, it orders the nodes by decreasing finishing times. The branches found by the DFS are considered strongly connected components. b.) Applies only to cyclic graphs. If a cycle has more than three nodes, then it is considered a strongly connected component. c.) Performs a DFS on a graph G . Then, it orders the nodes by decreasing finishing times. This order is used to perform a second DFS on the transposed graph G′ (where all edges are reversed). The trees formed during this DFS are considered strongly connected components. d.) Identifies cycles in a graph G , where for any pair of nodes u and v , there is a path from u to v and from v to u . e.) None of the above Original idea by: Julia de Pietro Bigi
Leia mais