What is topological sorting in the data structure

author
 
Babohabo111
Formerly active
With us since: 09/24/2018
Messages: 69
Topic start: 2018-10-04

Hey, I want to solve the following problem, but I can't get any further. What is the maximum number of edges in a directed graph that can be sorted topologically. The whole thing should be done with induction for all n positive numbers. The following is given as a hint: One should construct a graph with n nodes for n = 1, 2, 3, 4, which is topologically sortable with the maximum number of edges and can then formulate the assertion for induction from this. ____________________________________________________________________________ I have now drawn the graphs as indicated in the note, as follows: https://matheplanet.com/matheplanet/nuke/html/uploads/b/50515_a_d.png Now the number of edges is always the same as the number of nodes + Edges from the graph with one node less. My problem is, I don't know how to formulate this skillfully and then use it as a hypothesis for induction. I would appreciate help. Greeting


noteCtrlAltDel
Senior
With us since: January 19, 2013
Messages: 6882
Residence: Milky Way
Post No.1, registered 2018-10-04

Hello Babohabo111, I think the concept of topological sortability is not widely used. Can you please give the definition?


noteligning
Senior
With us since: December 7th, 2014
Messages: 3236
Place of residence: Berlin
Post No.2, registered 2018-10-04

I think you already have it. The maximum number of edges at n nodes is obviously the sum 1 + 2 + ... + (n-1), one can use the Gaussian sum formula to get a closed representation. Induction is also straight-forward: Remove the node without outgoing edges (which exists according to the assumption.)


noteBabohabo111
Formerly active
With us since: 09/24/2018
Messages: 69
Post No.3, from the topic starter, entered 2018-10-04

\ quoteon (2018-10-04 16:09 - StrgAltEntf in Post No. 1) Hello Babohabo111, I think the term topological sortability is not generally used. Can you please give the definition? \ quoteoff Definition: a sequence v1, ..., vn of vertices is a topological sorting of G = (V, E) if for every edge (vi, vj) € V it holds that i < j,="" und="" v="{v1,...,vn}" @ligning:="" also="" erhalte="" ich="" dann="" sowas="" oder="" sum(k,k="1,n-1)" =="" n(n-1)/2="" danke="" schonmal="" für="" eure="">


noteCtrlAltDel
Senior
With us since: 01/19/2013
Messages: 6882
Place of residence: Milky Way
Post No.4, registered 2018-10-04

Does that mean that exactly the subgraphs of G = ({1, ..., n}, {(i, j): i

noteBabohabo111
Formerly active
With us since: 09/24/2018
Messages: 69
Post No.5, from the topic starter, entered 2018-10-05

@StrAltEntf Can't answer your question, sorry :( Studies only started 2 weeks ago and the definition is simply the one that was on the slides.


noteScynja
active
With us since: 02/23/2011
Messages: 383
Place of residence: Germany
Post No.6, registered 2018-10-06

Isn't the result just sum (k-1, k = 1, n) So the first node can be connected to all of them and then one less at a time? Edit: Who can read has an advantage. I had somehow overlooked the = in the total. I hereby withdraw the comment.


noteligning
Senior
With us since: December 7th, 2014
Messages: 3236
Place of residence: Berlin
Post No.7, registered 2018-10-06

Yes, but that has already been said.


note