Блог пользователя taserghar

Dilworth Theorem
Автор taserghar, 13 лет назад, По-английски
Please someone give me the clear idea about dilworth theorem for graph or DAG. I read about it in multiple places but more I am reading getting more confusing. So please someone help me to understand it properly.
Thanks in advance.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
http://en.wikipedia.org/wiki/Dilworth%27s_theorem
Applicated to a DAG, it says that we can find divide the set of vertices into subsets V1, ..., Vk, so that any two vertices in any subset are reachable one from another (in one direction, of course), and then choose , so that none of vi are reachable from any other.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    actually I read it but since I am a beginner I am bit confused about that. But I got that "for any partial order set, minimum number of chain need to cover the set is SIZE of the biggest anti-chain". Is that correct... ?
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
someone please explain how dilworth related to bipertite matching for graph problem...

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    There is one-to-one correspondence between chain covers and bipartite matchings. If in a bipartite matching a vertex is not matched to any other then this vertex is a start of some chain, because there is no edge that comes to that vertex. Hence power of cover set equals to number of unmatched vertices. The more bipartite matching size is the less is the number of unmatched vertices and |Chain Cover Set| = |V| - |Max Bipartite Matching|.
    → Ответить