0
$\begingroup$

Let's say we have a graph of size 10. So, we have nodes $\{0,1,2,3,4,5,6,7,8,9\}$.

For the sake of keeping this problem under a certain level of complexity, accept that we somehow know that edges going out of node $0$ are always heavier than node $1$, and edges going out of node $1$ are always heavier than node $2$, etc etc, in a way where we don't need to worry about what the actual weights are. So, we know that for any given node, it's edges are lighter than the edges of all nodes with a lower value.

So my question is, given this value "$n$" that determined the numbers of nodes in our cycle, for any cycle of size n made from these nodes, what is the worst subpath of size $(n/2)$ that we can have?

It clearly is not $$0 \to 1 \to 2 \to 3 \to \cdots \to (n/2),$$ because if we have this configuration in our cycle then we could just start at $(n/2) $ and choose the subpath: $$\tfrac{n}{2} \to (\tfrac{n}{2} +1) \to \cdots \to n$$

So, there must be some scheme by which it balances out such that if you take the best possible subpath in the cycle, it will contain certain nodes relative to our value $n$. But, I do not know how to figure it out.

Good luck and thank you!

quick edit of more info:

It is a directed graph. It is a fully connected graph. n is the amount of nodes in the graph. The weight of ANY edge coming from a specific node, is equal to (n-(that node's value)). So in my example, edges coming from 0, have a weight of 10. Edges coming from node 5 have a weight of 5. Edges coming from 9 have a weight of 1. Also, for any given edge a-->b, there IS NOT an edge b--->a.

$\endgroup$
  • $\begingroup$ This is very confusing. 1) Is this a directed graph? 2) Why should it have any cycles at all? 3) What is $n$? I don't think you're describing your problem completely. $\endgroup$ – saulspatz Feb 15 '18 at 17:52
  • $\begingroup$ Edited to add more information. If you are still confused please let me know. $\endgroup$ – Travis Black Feb 15 '18 at 18:03
  • $\begingroup$ By "fully connected graph" do you mean that there is an edge between every pair of nodes? If so, can there be an edge in each direction? That is, can we have an edge $ab$ and also an edge $ba$ or must it be one or the other? $\endgroup$ – saulspatz Feb 15 '18 at 18:16
  • $\begingroup$ Yes, there is an edge between every pair of nodes. No, it cannot go both a-->b AND b-->a - it can only go one direction. I will add that to my edit. $\endgroup$ – Travis Black Feb 15 '18 at 18:20
  • $\begingroup$ Just to aid you in research, a digraph of this sort (without the weights) is called a "tournament." $\endgroup$ – saulspatz Feb 15 '18 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.