Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » Math Topics » discretemath

Topic: Maximum number of iterations (set theory, graph theory)
Replies: 0  

Advanced Search

Back to Topic List Back to Topic List   Topics: [ Previous | Next ]
Dmitrey Yershov

Posts: 7
Registered: 11/14/12
Maximum number of iterations (set theory, graph theory)
Posted: Feb 19, 2013 5:26 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Hello! This problem seems rather simple, but I can't solve it. Help, please!

Tehere is a set S1={A1, A2, ..., An}, where A1, A2,..., An are some sets. We call some element which belongs to at least one of the sets from S1. After that all sets which contain this element are removed from S1, so we obtain a new set of sets S2. Than the process repeats: we call some element which belongs to at least one of the sets from S2. After that all sets which contain this element are removed from S2, so we obtain a new set of sets S3. And so on, untill Sm is empty set.

The question is: what element do we have to call at each step in order to number of iterations until Sm = "empty set" be maximal?

My hypothesis is: at the k-th iteration we have to call element belonging to the minimum number of sets from Sk.

But how can I prove it? What method of proof can I apply?

I found that the problem about finding maximum number of iterations is equivalent to the following problem on graph. Let's build a graph in the following way: if elements "a" and "b" belongs simultaneously to some set from S1 then vertexes "a" and "b" are linked to each other with the edge. Let all vertexes are filled with white color. We have a brush with red color. Then the problem is: what is the maximum number of "brush strokes" which we should make to fill all vertexes with red color?

When I say "brush stroke" I mean the following action: we touch some vertex with the brush, this vertex and all vertices which are adjacent to this vertex are filled with red color. Of course, we can't make idle "brush strokes".

Maybe this problem could be solved with some standart graph algorithm?



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.