Need help: Proving a solution for a Graph problem

Revision en1, by 3509, 2021-04-08 07:09:16

The problem

I have prepared a problem as follow: There is this secret sequence $$$S$$$ consists of $$$N$$$ distinct numbers. Given a matrix $$$G$$$ of size $$$N \times N$$$, where $$$G_{i,j}=$$$\t{Y}' if $$$S_i>S_j$$$. Otherwise, $$$G_{i,j}=$$$\t{?}', meaning we have no information about the relation of $$$S_i$$$ and $$$S_j$$$, whether they are larger or smaller. You need to output a sequence $$$P = {P_1, P_2, ..., P_n}$$$, such that $$$S_{P_1} > S_{P_2} > ... > S_{P_n}$$$, or report that it is impossible to determined exactly the order.

Example

\begin{array}{|c|c|c|} \hline a & b & c \cr \hline d & e & f \cr \hline g & h & i \cr \hline \end{array}

Tags help, algorithm proving, graph

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en16 English 3509 2022-03-26 05:17:03 73
en15 English 3509 2021-04-08 18:24:48 14
en14 English 3509 2021-04-08 10:55:28 183
en13 English 3509 2021-04-08 09:29:09 26 (published)
en12 English 3509 2021-04-08 09:21:53 85
en11 English 3509 2021-04-08 08:02:51 12
en10 English 3509 2021-04-08 08:02:18 38
en9 English 3509 2021-04-08 08:01:23 33
en8 English 3509 2021-04-08 07:58:53 15
en7 English 3509 2021-04-08 07:58:16 7
en6 English 3509 2021-04-08 07:56:44 66
en5 English 3509 2021-04-08 07:53:15 1867
en4 English 3509 2021-04-08 07:15:48 130
en3 English 3509 2021-04-08 07:15:37 132
en2 English 3509 2021-04-08 07:12:25 240
en1 English 3509 2021-04-08 07:09:16 711 Initial revision (saved to drafts)