Quiz question 05

According to Kuratowski’s Theorem, for connected and planar networks, the number of vertices minus the number of edges plus the number of faces equals 2. This is Euler’s Formula, where: 

V - E + F = 2. 

Considering that faces are the regions bounded by links and that there will always be an outer face, given the following situations, how would Euler’s Formula behave?


Scenario 01: a single node A. 



Scenario 02: addition of a node B with a link to this existing node A.



Scenario 03: addition of another node C with a link to the existing node A. 



Scenario 04: addition of a link between nodes B and C. 



a.) Euler’s formula remains constant (equal to 2) in scenarios 01 and 02. 

b.) Euler’s formula remains constant (equal to 2) in all scenarios.

c.) Euler’s formula depends on the number of nodes; therefore, it takes on a different value for each scenario: Scenario 01 = 2; Scenario 02 = 2; Scenario 03 = 3; and Scenario 04 = 3

d.) Euler’s formula depends on the number of links, so it takes on a value for each scenario: 

Scenario 01 = 0; Scenario 02 = 1; Scenario 03 = 2; and Scenario 04 = 3

 e) None of the above

Original idea by: Julia de Pietro Bigi

Comentários

  1. Joao Meidanis27 de abril de 2026 às 01:48

    Good question, but it can be confusing. I uses the term "Euler's Formula" where perhaps "Euler's number" would be more appropriate. The difference between these two concepts is as follows: Euler's number is the value of the expression V - E + F. Euler's formula is the statement that Euler's number is always equal to 2.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Quiz question 01

Imagem
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
Leia mais

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