![]() | Pseudoforest has been listed as one of the Mathematics good articles under the good article criteria. If you can improve it further, please do so. If it no longer meets these criteria, you can reassess it. | |||||||||
| ||||||||||
![]() | A fact from this article appeared on Wikipedia's
Main Page in the "
Did you know?" column on
October 6, 2007. The text of the entry was: Did you know ...that in
graph theory, a
pseudoforest can contain
trees and pseudotrees, but cannot contain any butterflies, diamonds, handcuffs, or bicycles? |
![]() | This article is rated GA-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
In many ways, this is almost a good article. The illustrations are well-chosen, and the information is well-cited. The writing style is - except for the "but" that you no doubt no is coming - clear and well-written.
But there's no attempt to make this readable to a lay-person. If just a little bit more time was spent explaining terms, then this concept - which from what I gather is connection graphs that form rings, possibly with branches off them, but with not more than one ring in any connected parts of the graph - should be much easier to understand. You have good images. If you use them a bit better and highlight out the key parts, I think this article should make GA. Adam Cuerden talk 17:04, 14 October 2007 (UTC)
I've made another pass for readability and understandability, including the addition of another figure and a second restatement of the definition in the lede. I'd like to hear opinions on whether it's ready to show Cuerden again or, if not, which parts still need work. For what it's worth, my attitude on this sort of request is that articles on topics of mathematical research should be as readable as possible, but that readability should not come at the expense of mathematical content. That is, some mathematically-important parts of an article are likely to require too much background to be made readable to the uninitiated, but they should nevertheless remain in the article; on the other hand, everything that can reasonably be made readable to a layperson should be. I hope that attitude is not incompatible with the GA process. — David Eppstein 04:03, 18 October 2007 (UTC)
The first section has no inline citations, everything must be cited! ALTON .ıl 04:22, 31 October 2007 (UTC)
Although this article is rather technical, I don't think that this is a bad thing. A certain "layman's introduction" can be added to the article, but this is not a problem for any of the GA-criteria. In my estimation, this is a good article. I have passed it. ScienceApologist ( talk) 16:17, 26 November 2007 (UTC)
It is one of the best mathematics articles that I found in Wikipedia. —Preceding unsigned comment added by 163.1.148.94 ( talk) 15:44, 17 May 2008 (UTC)
I am correcting an error in the article. The forbidden minors for pseudoforests are just one graph: a vertex with two loops. This follows if one allows graphs with loops and multiple edges, as is necessary in both graph minors theory and matroid theory. I present here for future reference the interesting information about forbidding only one of the "butterfly" and "diamond", which seems not especially relevant to this article. If someone wants to put it in an article that treats the diamond, please do so. However, the statement is false unless the graphs are restricted to be simple; this should be made clear.
I also put here the no-longer-needed but nice illustration of the "butterfly" and "diamond". Perhaps someone can find a use for it. Zaslav 08:15, 16 November 2007 (UTC)
References
-- Webonfim ( talk) 00:23, 24 January 2008 (UTC)
The Tree (graph theory) article has a section on enumeration, so perhaps we can make a new section with results on the number of pseudoforests.
I show below simple results, (but new at the best of my concern), on the number of pseudoforests, so I think that them deserve to be in Wikipedia, and if so, perhaps in this article.
In the text below I include some OEIS sequence numbers, because with them people can easily have an idea of the magnitude of the numbers of distinct pseudoforests. It is obvious that everything in this text can be modified. After all this is the spirit of Wikipedia! I only wish that those results were linked to me.
[==Enumeration==]
Maximal pseudoforests when cycles of length at most one are allowed
-The number of unlabeled pseudotrees with n nodes, and cycles of length one is equal to the number of unlabeled rooted trees with n nodes. OEIS sequence number OEIS: A000081.
-The number of maximal pseudoforests with n nodes, k pseudotrees, and cycles of length at most one is equal to the number of forests of k rooted trees and n nodes. OEIS sequence number OEIS: A033185.
-The number of pseudotrees on [n] with cycles of length one is nn-1. OEIS sequence number OEIS: A000169.
-The number of maximal pseudoforests on [n] with cycles of length at most one, and k pseudotrees, is OEIS: A061356.
The results above follow from the bijection between rooted forests and maximal pseudoforests with cycles of length at most one, where each root corresponds to an endpoint of a loop and conversely each endpoint of a loop corresponds to a root. -- Webonfim ( talk) 00:25, 24 January 2008 (UTC)
I suggest that:
1) You edit the formula of the number of simple 1-trees with n labeled vertices changing it to the simple formula
2) You add the result
The number of labelled simple 1-forests with n vertices and m connected components is
The values for n up to 11 can be found in Sequence
OEIS:
A106239.
OBS. Fell free to edit 2).
What do you think? -- Webonfim ( talk) 18:16, 22 February 2008 (UTC)
The compution the pseudoarboricity is easily derived from the one of the maximum average degree, which is known to be computable in polynomial time by (Gallo, Grigoriadis & Tarjan; 1989) without help of matroid theory. — Preceding unsigned comment added by Taxipom ( talk • contribs) 20:46, 6 October 2011 (UTC)
Gabow and Tarjan do not attribute the term "pseudoforest" to Dantzig, but to "J.-C. Picard and M. Queyranne. A network flow solution to some nonlinear 0-l programming problems, with applications to graph theory, Networks 12 (1982) 141-159." Indeed, the term pseudoforest or pseudotree does not appear at all in Dantzig book (he uses a notion of sl-tree).
pom ( talk) 10:44, 28 April 2014 (UTC)
I made some changes to the beginning of the "Graphs of functions" section to point out that only endofunctions can be interpreted as directed pseudoforests. Are further changes needed? (ex. §Graphs of functions → §Graphs of endofunctions)?
![]() | Pseudoforest has been listed as one of the Mathematics good articles under the good article criteria. If you can improve it further, please do so. If it no longer meets these criteria, you can reassess it. | |||||||||
| ||||||||||
![]() | A fact from this article appeared on Wikipedia's
Main Page in the "
Did you know?" column on
October 6, 2007. The text of the entry was: Did you know ...that in
graph theory, a
pseudoforest can contain
trees and pseudotrees, but cannot contain any butterflies, diamonds, handcuffs, or bicycles? |
![]() | This article is rated GA-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
In many ways, this is almost a good article. The illustrations are well-chosen, and the information is well-cited. The writing style is - except for the "but" that you no doubt no is coming - clear and well-written.
But there's no attempt to make this readable to a lay-person. If just a little bit more time was spent explaining terms, then this concept - which from what I gather is connection graphs that form rings, possibly with branches off them, but with not more than one ring in any connected parts of the graph - should be much easier to understand. You have good images. If you use them a bit better and highlight out the key parts, I think this article should make GA. Adam Cuerden talk 17:04, 14 October 2007 (UTC)
I've made another pass for readability and understandability, including the addition of another figure and a second restatement of the definition in the lede. I'd like to hear opinions on whether it's ready to show Cuerden again or, if not, which parts still need work. For what it's worth, my attitude on this sort of request is that articles on topics of mathematical research should be as readable as possible, but that readability should not come at the expense of mathematical content. That is, some mathematically-important parts of an article are likely to require too much background to be made readable to the uninitiated, but they should nevertheless remain in the article; on the other hand, everything that can reasonably be made readable to a layperson should be. I hope that attitude is not incompatible with the GA process. — David Eppstein 04:03, 18 October 2007 (UTC)
The first section has no inline citations, everything must be cited! ALTON .ıl 04:22, 31 October 2007 (UTC)
Although this article is rather technical, I don't think that this is a bad thing. A certain "layman's introduction" can be added to the article, but this is not a problem for any of the GA-criteria. In my estimation, this is a good article. I have passed it. ScienceApologist ( talk) 16:17, 26 November 2007 (UTC)
It is one of the best mathematics articles that I found in Wikipedia. —Preceding unsigned comment added by 163.1.148.94 ( talk) 15:44, 17 May 2008 (UTC)
I am correcting an error in the article. The forbidden minors for pseudoforests are just one graph: a vertex with two loops. This follows if one allows graphs with loops and multiple edges, as is necessary in both graph minors theory and matroid theory. I present here for future reference the interesting information about forbidding only one of the "butterfly" and "diamond", which seems not especially relevant to this article. If someone wants to put it in an article that treats the diamond, please do so. However, the statement is false unless the graphs are restricted to be simple; this should be made clear.
I also put here the no-longer-needed but nice illustration of the "butterfly" and "diamond". Perhaps someone can find a use for it. Zaslav 08:15, 16 November 2007 (UTC)
References
-- Webonfim ( talk) 00:23, 24 January 2008 (UTC)
The Tree (graph theory) article has a section on enumeration, so perhaps we can make a new section with results on the number of pseudoforests.
I show below simple results, (but new at the best of my concern), on the number of pseudoforests, so I think that them deserve to be in Wikipedia, and if so, perhaps in this article.
In the text below I include some OEIS sequence numbers, because with them people can easily have an idea of the magnitude of the numbers of distinct pseudoforests. It is obvious that everything in this text can be modified. After all this is the spirit of Wikipedia! I only wish that those results were linked to me.
[==Enumeration==]
Maximal pseudoforests when cycles of length at most one are allowed
-The number of unlabeled pseudotrees with n nodes, and cycles of length one is equal to the number of unlabeled rooted trees with n nodes. OEIS sequence number OEIS: A000081.
-The number of maximal pseudoforests with n nodes, k pseudotrees, and cycles of length at most one is equal to the number of forests of k rooted trees and n nodes. OEIS sequence number OEIS: A033185.
-The number of pseudotrees on [n] with cycles of length one is nn-1. OEIS sequence number OEIS: A000169.
-The number of maximal pseudoforests on [n] with cycles of length at most one, and k pseudotrees, is OEIS: A061356.
The results above follow from the bijection between rooted forests and maximal pseudoforests with cycles of length at most one, where each root corresponds to an endpoint of a loop and conversely each endpoint of a loop corresponds to a root. -- Webonfim ( talk) 00:25, 24 January 2008 (UTC)
I suggest that:
1) You edit the formula of the number of simple 1-trees with n labeled vertices changing it to the simple formula
2) You add the result
The number of labelled simple 1-forests with n vertices and m connected components is
The values for n up to 11 can be found in Sequence
OEIS:
A106239.
OBS. Fell free to edit 2).
What do you think? -- Webonfim ( talk) 18:16, 22 February 2008 (UTC)
The compution the pseudoarboricity is easily derived from the one of the maximum average degree, which is known to be computable in polynomial time by (Gallo, Grigoriadis & Tarjan; 1989) without help of matroid theory. — Preceding unsigned comment added by Taxipom ( talk • contribs) 20:46, 6 October 2011 (UTC)
Gabow and Tarjan do not attribute the term "pseudoforest" to Dantzig, but to "J.-C. Picard and M. Queyranne. A network flow solution to some nonlinear 0-l programming problems, with applications to graph theory, Networks 12 (1982) 141-159." Indeed, the term pseudoforest or pseudotree does not appear at all in Dantzig book (he uses a notion of sl-tree).
pom ( talk) 10:44, 28 April 2014 (UTC)
I made some changes to the beginning of the "Graphs of functions" section to point out that only endofunctions can be interpreted as directed pseudoforests. Are further changes needed? (ex. §Graphs of functions → §Graphs of endofunctions)?