Showing posts with label Graph theory. Show all posts
Showing posts with label Graph theory. Show all posts

Saturday, March 21, 2026

2026-329

A company is looking for people that have really close acquaintances with its three interviewers. Therefore, candidates whose average length to each interviewer are closer to 1 will have the most chances to get the job.

Given the network of acquaintances of each of the following three applicants, indicate which of the following statements are true (T) or False (F).

Robert:

John:

Casey:

  1. Casey has the most chances of getting the job.
  2. For Robert’s network of aquaintances: If the clustering coeficient of Taylor were higher while maintaining the same degree, then Robert would have more chances of being hired.
  3. The chances of Casey getting the job does not depends on knowing Micah, Mary or Harry.
  4. John has the least chances of getting the job.
  1. F F T T
  2. T T T F
  3. T F T F
  4. T F F F
  5. None of the above
Original idea by: Giuliano Macedo

 

Saturday, March 14, 2026

2026-323

Considering the following two undirected Graphs and three Degree Distributions:

Based on the previous figure, evaluate the following sentences as true (T) or false (F):

  • Graph (1) matches the Degree Distribution X.
  • Graph (2) matches the Degree Distribution Y.
  • The maximum degree of Graph (1) is greater than that of Graph (2).
  • The diameter of Graph (2) is greater than that of Graph (1).

Chose the correct alternative:

A) F, T, F, T

B) T, F, T, F

C) F, T, T, F

D) T, T, F, T

E) None of the above

 

Original idea by: Gabriela Caspa

Sunday, March 8, 2026

2026-322

Given a graph where each node represents a student and two students are connected by a link if they have ever studied at the same school (not necessarily in the same class or year), which of the following statements is true?  Assume that every school has at least 3 students.

a) A node with clustering coefficient equal to 1 implies that the student never changed schools.
b) A complete graph implies that there is just one school.
c) A student who never changed schools will have clustering coefficient equal to 1.
d) The number of connected components in the graph is necessarily equal to the number of schools.
e) None of the above.

Original idea by: Henrique Campos Padula

2026-321

Let \(G=(V,E)\) be a simple undirected graph, meaning that it has no self-loops (edges of the form \((v, v)\)) and no multiple edges between the same pair of vertices.

For such a graph we can define its degree sequence, as the sequence of its vertex degrees in nonincreasing order..

For example, the graph shown below has degree sequence

(3,1,1,1)

Example graph with degree sequence (3,1,1,1)

For each of the following statements, determine whether it is True (T) or False (F).

i) \( (2,2) \) is the degree sequence of several nonisomorphic graphs.
ii) \( (2,2,2) \) is the degree sequence of exactly one graph, up to isomorphism.
iii) \( (2,2,2,2,2,2) \) is the degree sequence of exactly one graph, up to isomorphism.

Alternatives

a) FTF
b) FTT
c) TFT
d) TTF
e) None of the above

Original idea by: Luis Alberto Vásquez Vargas

2026-320

Figure 1(a) below shows a drawing of a network \(N\). Figures 1(b), 1(c), and 1(d) show the matrices \(A\), \(D\), and \(S\), respectively, and Figure 1(e) shows the vector \(k\). 

Regarding the figures above, consider the following six propositions:

  1. For matrix \(A\), shown in Figure 1(b), entry \(a_{ij} = 1\) if and only if there is a link in network \(N\) connecting node \(i\) to node \(j\). Therefore, \(A\) is the adjacency matrix of network \(N\).
  2. Matrix \(D\), shown in Figure 1(c), can be regarded as a matrix indicating second neighbors (nodes at distance two) of network \(N\), since entry \(d_{ij} \not= \infty\) if and only if nodes \(i\) and \(j\) are second neighbors.
  3. Matrix \(D\), shown in Figure 1(c), can be regarded as a distance matrix of network \(N\), since if \(d_{ij} = \infty\) there is no path between nodes \(i\) and \(j\), and if \(d_{ij} \not= \infty\) then \(d_{ij}\) equals the length of a shortest path between nodes \(i\) and \(j\).
  4. Matrix \(S\), shown in Figure 1(d), can be regarded as a matrix of second neighbors of network \(N\), since \(s_{ij} = 1\) if, and only if, nodes \(i\) and \(j\) are second neighbors.    
  5. Vector \(k\) is the vector of the node degrees of network \(N\) and can be obtained multiplying matrix \(A\) by vector \( (1, 1, \ldots, 1) \)^T \) .  

Which alternative contains all the TRUE propositions?

(a) 1 and 3.

(b) 1, 2, and 3.

(c) 1, 2, and 5.

(d) 1, 3, 4, and 5.

(e) None of the above.


Original idea by: Joao Vianini

2026-319

Consider the four graphs below:

Which graph has the highest average clustering coefficient C, and what is its value?


A) Graph 1, with C = 0

B) Graph 4, with C = 0.47

C) Graph 2, with C = 0.50

D) Graph 3, with C = 0.10

E) None of the above


Original idea by: Gustavo P. C. P. da Luz

Saturday, March 7, 2026

2026-318

Suppose a graph \(G\) has the following second power of the adjacency matrix:

$$ A^2 = \left( \begin{array}{cccc}1 & 0 & 1 & 1\\0 & 3 & 1 & 1\\1 & 1 & 2 & 1\\1 & 1 & 1 & 2 \end{array}\right) $$

Which one could be \(G\)?

a)

b)



c) 


d) 

e) None of the above


Original idea by: Leticia Marques

2026-317

 In an undirected network, suppose there are exactly 4 triangles and exactly 12 additional connected triplets, not belonging to triangles.  According to the definition of the global clustering coefficient, what is the value of ?

  1. 1/2
  2. 2/3
  3. 3/4
  4. 6/7
  5. None of the above
Original idea by: Antonio De Cesare Del Nero

2026-316

Consider the following graph and the subsequent statements:


1. The graph is connected because the links (0, 1), (0, 2) and (0, 3) intersect with the links (4, 5), (4, 6) and (5, 6).

2. If we consider the components of this graph as projections of a bipartite graph, the parent bipartite graph could be:

3. The adjacency matrix of this graph can be rearranged and separated into two non-zero submatrices of size 4x4 and 3x3.

The correct statements are:

a) Just 3

b) 1 and 2

c) 1 and 3

d) 2 and 3

e) None of the above.


Original idea by: Rafael Brusiquesi Martins

2026-314

Let \(A\) be the \(N \times N\) adjacency matrix of an undirected, unweighted network without self-loops. Let \( \textbf{1}\) be a column vector of \(N\) elements, all equal to 1, i.e., \( \textbf{1} = (1, 1, \ldots, 1)^T \). Let \(t(A)\) denote the trace of matrix \(A\), i.e., the sum of the elements on its main diagonal.

Which of the following expressions gives the number of connected triplets in the network?

  1. \( ( \textbf{1}^T A^2 \textbf{1} ) / 2 \)
  2. \( ( \textbf{1}^T A^2 \textbf{1} - t(A^2) ) / 2 \)
  3. \( ( \textbf{1}^T A^2 \textbf{1} - t(A^2) - t(A^3) ) / 2 \)
  4. \( ( \textbf{1}^T A^2 \textbf{1} - t(A^2) ) / 2 - t(A^3)/6 \)
  5. None of the above

Original idea by: Pedro Ferreira

2026-313

 Consider the following networks:


Choose the correct answer:

A) Only networks A, B, and D are bipartite.
B) All networks are bipartite.
C) Only networks A, B, and C are bipartite.
D) Only networks A and D are bipartite.
E) None of the above.

Original idea by: Melissa Araújo

2026-312

Look at the figures below, analyze the statements, and choose the right answer:

I- The graph in figure A is a multigraph and in figure B is a simple graph.

II- In a complete graph, known as a clique, all nodes are connected to each other.
III- The diameter of the graph in figure B is dmax= 4.

IV- The adjacency matrix of graph in figure B is:










  1. I and II are correct
  2. II, III and IV are correct
  3. II and IV are correct
  4. I, III, IV are correct
  5. None of the above

Original idea by: Tássia Martins

2026-311

 Consider the following network.



Which of the following statements are true:

I. FECFAU and FEAGRI are the only nodes with the lowest degree.
II. The degree distribution shows that 60% of the nodes have degree 3.
III. The local clustering coefficient of IQ and IE is 1.
IV. The diameter of the graph is 4.
V. No links are bridges

a) I, II, and III.
b) III and V.
c) I, III, and IV.
d) II, IV, and V.
e) None of the above.

Original idea by: George Gigilas Junior

Wednesday, August 27, 2025

2025-252

The Health Department of the imaginary region Scarlet is preparing contingency plans for a potential pandemic. To ensure efficient allocation of resources, they want to determine:

  1. Which city would serve as the most effective distribution center for medication, minimizing the expected distance and variance to the other cities, thus guaranteeing accessibility to the largest number of other cities in the shortest time.

  2. Which city would serve as the most strategic location for establishing a blockade, in order to minimize the potential spread of infection to other cities within the network?

Considering the graph below, where each node represents a city and the only means of connection between them is via roads represented by the edges, which cities represent the best candidates for these roles?








A) City 3 as the distribution center and City 3 as the blockade
B) City 3 as the distribution center and City 4 as the blockade
C) City 5 as the distribution center and City 3 as the blockade
D) City 5 as the distribution center and City 4 as the blockade
E) None of the above 

Original idea by: Carolina Albuquerque

Sunday, August 24, 2025

2025-251

Consider the adjacency matrices A and B below, where A represents an undirected network and B represents a directed network. 

Choose the alternative whose networks generate matrices A and B, respectively.


A.    


B. 


C. 


D. 
 

E. None of the above


Original idea by: Jhessica Silva

2025-250

Eight dogs are happily playing at Praça da Paz, Barão Geraldo. Each dog is a node, and each friendship (two dogs playing together) is an edge.

 


Considering the above undirected network of dog friendships, which of the following statements is correct?

A) The clustering coefficient of node Violeta is 0

B) Ginger is very social and her clustering coefficient is 0.5, participating in more than one triangle

C) The shortest path from Mindú to Violeta has length 4

D) The average degree of the nodes ⟨k⟩ is 2.375, and the degree distribution shows that three nodes have degree 1

E) None of the above

 

Original idea by: Aline Azevedo

2025-249

In a bomb defusing training, were each explosive is wired to another in different ways, the instructions given by the trainers include using Breadth-First-Search to defuse each bomb and leaving the main explosive to be defused last. Facing the following wired structure, which node should be the starting one in order to follow the instructions faithfully?



A) Node 5
B) Node 3
C) Node 2
D) Node 0
E) None of the above.

Original idea by: João Medrado Gondim

Tuesday, August 27, 2024

2024-234

 

 
The graph above represents the social network of a group of people in a research lab, illustrating co-authorship among the researchers. Based on this information, which of the following options is the average clustering coefficient rounded to the nearest tenth:
 
A) ⟨C⟩ = 0.2

B) ⟨C⟩ = 0.4

C) ⟨C⟩ = 0.6

D) ⟨C⟩ = 0.8

E) None of the above 
 
Original idea by: Matheus Lindino

2024-233

 

Which of the adjacency matrices below represents the graph above?

A) 0 0 1 1 1

    0 0 1 0 1

    1 1 0 1 1

    1 0 1 0 1

    1 1 1 1 0

 

B) 0 0 1 1 1

    0 0 1 0 1

    1 1 0 0 1

    1 0 0 0 1

    1 1 1 1 0


C) 0 1 1 0 0

    0 0 0 1 1

    1 1 0 1 1

    1 1 1 0 1

    0 1 0 0 1

 

D) 0 0 1 1 0

    0 0 1 0 1

    1 1 0 0 1

    1 0 0 0 1

    0 1 1 1 0

 

E) None of the above 

 

Original idea by: Gustavo Henrique Sencio de Souza 

Saturday, March 18, 2023

2023-201

The figure below is a dependency graph representing the course prerequisites in a school. The courses are the nodes, and the requirement relationships are defined by direct links from a course to its prerequisites to be enrolled.

For example, in the figure below:

  • Course D has course A as a prerequisite; and
  • Course E has courses A and B as prerequisites.

Considering the figure above, mark the following sentences as true (T) or false (F):

  • The only node with the highest degree is node M;
  • Nodes A, B, and C do not have prerequisites;
  • Course G is a prerequisite for course H;
  • The incoming degree for course O is 2;
  • The outgoing degree for course H is 2;
The correct option matching the sentences is:

a) T-T-F-F-T
b) F-T-F-F-T
c) F-F-T-T-T
d) T-T-F-T-F
e) None of above

Original idea by: Leonardo H. de Braz

2026-368

Consider the following partitions over the same graph: Which alternative lists the partitions in ascending order of modularity ? A) PA, PB...