For example this digraph, start from s1, we can realize depth first traverse by different sequences such as { s1 t1 s2 t3 s3 t4 s1 t5 s3, s1 t2 s2} or {s1 t5 s3 t4 s1 t2 s2 t3 s3, s1 t1 s2}. I find that in each group the start nodes is realated with the nodes whose outdegree is larger than its indegree, the end nodes in each group is realated with the nodes whose indegree is larger than its outdegree.
my question is:Given a digraph and start from the same node for depth first traverse,considering the solutions of each group, can we conclude the following properties ?
Property i: The same number of sequences in each group.
Property ii: The same kind of start nodes and the same number of each kind of start nodes for sequences in each group.
Property iii: The same kind of end nodes and the same number of each kind of end nodes for sequences in each group.
The kind of start nodes is realated with the nodes whose outdegree is larger than its indegree and the number of each kind of start nodes is the number of the outdegree for the node after offset with the indegree. The end nodes in each group is realated with the nodes whose indegree is larger than its outdegree and the number of each kind of end nodes is the number of the indegree for the node after offset with the outdegree.
Can it be?
@Peter Breuer · Dear sir, thank you very much and I learn a lot from your answer. In fact, I want to find as few sequences as possible in a directed graph by which every edge of the graph is passed through only once. I use the following method :start from a node , go down along outgoing edges until we reach a node all of whose outgoing edges have been traversed such that we must stop and a sequence from the start node to the current node is obtained. Then we repeat this process in all the un-traversed edges to find other sequences until all the edges of the graph are passed through once.
Obviously,various solutions can be obtained because of different traversal order. I want to find whether the three properties hold between these solutions. If they hold then I can select one solution randomly for my follow-up work.
@Peter Breuer Dear sir, the "group" means a set of sequences, i.e., there is one or more sequences in the group by which every edge in the directed graph is passed through only once. I think carefully over the problem and give a more detailed description:
Given a strong-connected digraph which is not symmetric, considering the nodes with high out-degree and select the one with the most excess of out-degree. Start from this node , go down along outgoing edges until we reach a node all of whose outgoing edges have been passed such that we must stop and a sequence from the start node to the current node is obtained. Put the sequence to an empty set. Then delete the passed edges in the graph and repeat the above process in the courrent digraph to find other sequences until all the nodes of the graph are isolated. The final set is a solution.
In the above process, there may be various solutions because of different traversal order(for example the choice problem when there are more than one outgoing edge for a node). I think it should be but I am not sure that sequences in every solution have the following characteristics:
(1)Start nodes of sequences must be the nodes with high out-degree
(2)End nodes of sequences must be the nodes with high in -degree
(3)The number of sequences in each solution is eaqual to the sum total excess of out-degree over in-degree in those nodes that have an exctess of out-degree over in-degree. In fact, it is also equal to the sum total excess of in-degree over out-degree in those nodes that have an excess of in-degree over out degree.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering