Graph theory problem that requires transitive reduction

Правка en3, от Lance_HAOH, 2017-12-13 16:32:15

Hi. I am trying to solve this problem.

For convenience, I have summarized the problem statement below (based on my understanding):

Given a directed graph with N vertices and E edges (with cycles and not necessarily connected), find the minimum number of edges that we need to retain such that connectivity between vertices is retained as given in the original graph.

For example, for the following graph:

graph

We should retain the edges:

0 -> 1
0 -> 3
1 -> 2
1 -> 3

So we must use a minimum of 4 edges.

Note that 0 -> 2 is redundant as

Теги #graph, #algorithms, #connectivity, #dunjudgeme, #teleportation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en11 Английский Lance_HAOH 2017-12-16 05:46:23 2672 Tiny change: 'ans);\n}\n</spoile' -> 'ans);\n}\n\n</spoile'
en10 Английский Lance_HAOH 2017-12-14 01:10:01 6 Tiny change: '\n0 -> 1\n0 -> 3\n1 -> 2\n~~~~~\n\' -> '\n0 -> 1\n1 -> 2\n1 -> 3\n~~~~~\n\'
en9 Английский Lance_HAOH 2017-12-14 01:08:24 16 Tiny change: ' (Thanks [filippos] ' -> ' (Thanks [user:filippos] '
en8 Английский Lance_HAOH 2017-12-14 01:07:37 160 Tiny change: '\n1 -> 2\n1 -> 3\n~~~~~\n\' -> '\n1 -> 2\n<strike>1 -> 3</strike>\n~~~~~\n\'
en7 Английский Lance_HAOH 2017-12-13 16:47:46 14 Tiny change: 'me limit. However, the list' -> 'me limit. Furthermore, the list'
en6 Английский Lance_HAOH 2017-12-13 16:45:44 0 Tiny change: 'olutions suggests that ther' -> 'olutions seems to suggest that ther' (published)
en5 Английский Lance_HAOH 2017-12-13 16:41:42 289 Tiny change: 'olutions seems to suggest that ther' -> 'olutions suggests that ther'
en4 Английский Lance_HAOH 2017-12-13 16:34:58 186
en3 Английский Lance_HAOH 2017-12-13 16:32:15 313
en2 Английский Lance_HAOH 2017-12-13 16:29:13 137
en1 Английский Lance_HAOH 2017-12-13 16:27:44 311 Initial revision (saved to drafts)