dtldarek
Reputation
24,639
Top tag
Next privilege 25,000 Rep.
 3h awarded Good Answer Apr 28 comment Is there an efficient algorithm to find all the maximum matching in any tree? @DanielAlejandroJaume If you want all the edges that belong to some maximum matching, that should be much easier. Apr 27 comment Is there an efficient algorithm to find all the maximum matching in any tree? @DanielAlejandroJaume Simplex works well in most cases for different reasons, it's exponential only for very special cases. On the other hand, in this problem I would guess that then number of matchings of a random tree on $n$ vertices is exponential in the number of leaves it has. Apr 26 comment Is there an efficient algorithm to find all the maximum matching in any tree? @DanielAlejandroJaume But if there are too many, then no efficient algorithm could list them all (normally you measure complexity with regard to input, not output). Apr 26 answered Is there an efficient algorithm to find all the maximum matching in any tree? Apr 26 revised How to calculate $\langle v,w\rangle$ based only on $\langle v,x_i\rangle$ and $\langle w,x_i\rangle$? added 68 characters in body Apr 26 revised How to calculate $\langle v,w\rangle$ based only on $\langle v,x_i\rangle$ and $\langle w,x_i\rangle$? added 68 characters in body Apr 26 revised How to calculate $\langle v,w\rangle$ based only on $\langle v,x_i\rangle$ and $\langle w,x_i\rangle$? added 518 characters in body Apr 26 answered How to calculate $\langle v,w\rangle$ based only on $\langle v,x_i\rangle$ and $\langle w,x_i\rangle$? Apr 15 answered Is it possible to find Hamilton path in this graph? Apr 13 comment Show that $f(n) \in \Theta(n^k)$ Welcome to math.SE! Could you provide any context for this problem (e.g., what topics did you cover, where the question comes from, what course you are attending, etc.)? Also, what have you tried? Apr 13 comment Why polynomial functions f(x)+g(x) = (f+g)(x)? If you have trouble understanding this, consider $(f+g)$ as a name, e.g. you could define $h(x) = f(x) + g(x)$, only that you use symbol $(f+g)$ instead of $h$. The upside of this is that you need a new definition for any new name like $h$, but it is obvious what $(f+f)$ means or $(g+h)$ or even $(f + (f + g))$. Apr 13 awarded Populist Apr 8 comment Infinite graph theory: What's a tree? @user21820 I think we disagree on something else entirely, and if that is true then I misunderstood your comment. Frequently we impose some additional structure on an object to make it easier to handle (like a root in a tree). However, unless that structure was there in the first place (i.e. it was intrinsic to that object), I would not say that this object has/had this structure. For example, if I direct edges of a graph, I say I create a new graph. Assuming that the imposed structure becomes the property of an object, I clearly agree with you. Apr 7 revised A bipartite graph with a perfect matching has a vertex with each edge contained in a perfect matching added 762 characters in body Apr 7 comment A bipartite graph with a perfect matching has a vertex with each edge contained in a perfect matching @ArmanMalekzade I could not know that, because you provided no context to the question. I would advise you to add it, otherwise the people that could answer your question have very limited knowledge of what would actually help you. Context is very important, consider this when asking your future questions! Apr 7 comment Infinite graph theory: What's a tree? @user21820 I disagree with the sentiment that in computer science trees are (almost) always directed. That is true if the tree in question is rooted (which indeed is often the case). However, trees described by the OP are unrooted, and these also happen frequently in computer science and they do not come with any default way of directing the edges (unless, of course, the underlying graph was directed in the first place). Apr 7 answered A bipartite graph with a perfect matching has a vertex with each edge contained in a perfect matching Apr 5 answered Show that if G is a connected simple k-regular graph with k ≥ 2 and χ'(G) = k, then G is Hamiltonian Apr 5 comment Show that if G is a connected simple k-regular graph with k ≥ 2 and χ'(G) = k, then G is Hamiltonian @Math1000 That's not true, just consider a cube with each direction X,Y,Z colored different way. You have to use all the three colors to get the Hamilton cycle.