Talk:Pseudoforest

GA Review

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)

Anyway, just leave me a note on my talk page when you want me to have another look. Adam Cuerden ^talk 17:06, 14 October 2007 (UTC)

There was certainly an attempt to make this readable to a lay-person, but it's a fair criticism that those attempts were unsuccessful. Any specific parts you found even more difficult than the rest to understand? —David Eppstein 17:15, 14 October 2007 (UTC)

If we take the sentence A pseudoforest can be defined as a graph in which each connected component has at most one cycle. this is fine for someone who knows a bit about graph theory, but for the un-initiated, graph, connected component and cycle, could benefit from a little expansion, without having to visit links. --Salix alba (talk) 20:04, 15 October 2007 (UTC)

And we should follow the normal convention in graph theory: define what graph means in this article (probably in a footnote) before we use it. Septentrionalis PMAnderson 05:42, 22 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)

It's not easy finding appropriate references for such basic definitions, compared with the more specific facts that were better-cited in the later parts of the article, but I added a few. I hope you're not one of those people who believe in peppering every sentence with one or more footnotes (see Wikipedia:Scientific citation guidelines) but I agree that they were somewhat lacking in that section. —David Eppstein 06:40, 31 October 2007 (UTC)

Ew, no. What I like, personal preference, is that when I read something interesting that I want to know more about, there is a citation. And as brought up before, such basic facts aren't that basic to all of us, and I have no idea whether you're making up the assumption or not (I don't think that, and obviously you're not). Thanks for addressing it. ALTON .ıl 20:32, 31 October 2007 (UTC)

New GA review

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)

Thanks! —David Eppstein (talk) 16:24, 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)

Minors

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.

If one forbids only the diamond but not the butterfly, the resulting larger graph family consists of the cactus graphs and disjoint unions of multiple cactus graphs.

The butterfly graph (left) and diamond graph (right), forbidden minors for pseudoforests

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)

It is neither necessary nor standard to handle multigraphs in graph minor theory. The definition of minors that I'm familiar with condenses down multiple edges to single edges and removes loops. You may use some other definition; you may even use it in Wikipedia if you properly reference it, but you need to cite it well to convince me that it's the right definition. In the meantime I intend to revert any change of this nature that you make. —David Eppstein 08:19, 16 November 2007 (UTC)

The Robertson-Seymour theory and matroid theory both allow multigraphs and have no need whatever for simple graphs. In coloring theory one eliminates multiple edges but this is not appropriate in all graph theory, e.g., in treating the Tutte polynomial or its relatives. The part of this article of interest to me is that on the bicircular matroid. I suggest that should be a separate article in which multigraphs are allowed. Would that resolve your disagreement?

The article has significantly non-standard graph theory terminology. E.g., "bicycle matroid" (in the literature I know, "bicircular matroid"); "simple cycle" (in computer science this may be common; in graph theory it is rare to vanishing). I would appreciate having either standard graph theory terminology or an explanation of why non-graph theory terminology is preferred. Zaslav 08:38, 16 November 2007 (UTC)

Added new article on bicircular matroid. Perhaps it could be improved with some of the text from this article, but I leave that to others. Zaslav 09:10, 16 November 2007 (UTC)

There are times when multigraphs are appropriate and times when simple graphs are appropriate. For instance, the fact that graphs in minor-closed graph families have a number of edges that's linearly bounded in their numbers of vertices only makes sense for simple graphs. You have said elsewhere that this distinction comes from computer science vs mathematics, but I don't think so: certainly, when dealing with adjacency list representations of graphs in computer science, multigraphs are more appropriate, but I see many pure graph theory works in which graphs are defined to have edges that are sets of unordered pairs (therefore, by extensionality, simple graphs). If we can handle both undirected and directed graphs in a single article, I don't see why we can't handle both simple graphs and multigraphs. Anyway, thanks for paying some attention to this article, it's good to have multiple people actually working on it and not just suggesting vaguely from the sidelines that it's hard to read. —-- David Eppstein (talk) 17:05, 16 November 2007 (UTC)

I was hasty in the original revision and comments. I don't mean that simple graphs are c.s. and multigraphs are math. Also, "even I" find the simple-graph minors for pseudoforests interesting. In general the definition of a "graph" is rightly dependent on the needs of the moment. Still, there is some terminology here that seems to be specifically c.s. or optimization rather than math (though no terminology is universal in graph theory); e.g., "simple cycle" where most graph theorists (and basic Wikipedia articles on graphs) say "cycle"; and "pseudoforest" (from optimization, apparently, but there's no standard term in graph theory; the nearest might be "1-forest"; note that I'm not objecting to "pseudoforest").

I would be happy if the article can be revised to smoothly cover both simple graphs and nonsimple graphs. Would you (or someone else?) be willing to advise or lend a hand? For starters, do you object to replacing "simple cycle" by "cycle" as is (I thought) supposed to be standard in Wikipedia per graph – or, am I mistaken in that belief? Zaslav (talk) 05:20, 17 November 2007 (UTC)

My reading of the graph article is not that "simple cycle" should be avoided, but rather that "cycle" without qualification is usually understood to mean "simple cycle", but I don't object to taking out "simple" if you think that would help make the article easier to read for novices to graph theory (as I think that's the target we should be aiming for to the extent possible here). As for the "pseudoforest" name, I took it from a paper that mentioned the lack of a standard name and settled on that one for lack of anything better (the Gabow-Tarjan paper); it is a C.S. paper, but I don't see that as a reason to come to a different decision than its authors did. —David Eppstein (talk) 06:00, 17 November 2007 (UTC)

I accept both points. I don't at all disparage C.S., just note that some standards differ. If you think "simple cycle" would be better, I don't mind; I'm not enforcing my preference (which is against "cycle" anyhow). I will continue when time permits to think about possible improvements to this article and bicircular matroids. Zaslav (talk) 01:45, 19 November 2007 (UTC)

I'm less familiar with the literature, but I'm used to running into the term "graph" meaning "simple graph". I've added a footnote to the definition of graph to the effect that this sort of graph is a generalization, often called a multigraph or pseudograph. I hope this doesn't bog things down, or give a mistaken impression of what to expect from current literature, so I welcome correction from people who read more. –Dan Hoey^talk 12:41, 31 March 2008 (UTC)

A few suggestions (and a comment):

• I don't think the explanation is needed in the introduction. It's reasonable to save this for the technical definition.
• To be most useful it should be in the text (as a parenthetical remark), not a footnote.
• But in general, a pseudoforest is whatever kind of graph you're working with, so it may be simple or multi depending on the context. I think this is better than fixing it to be a multigraph, and the footnote should say the "graph" may be simple or not, as you choose.
• In the literature the definition of a graph as simple or multi depends on the needs of the work. (Many articles don't say what they mean; you have to figure it out.)

Do you agree with these suggestions? I await comment before editing. Zaslav (talk) 09:46, 1 April 2008 (UTC)

References

Enumeration

--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 n^n-1. OEIS sequence number OEIS: A000169.

-The number of maximal pseudoforests on [n] with cycles of length at most one, and k pseudotrees, is ${n-1 \choose k-1}{n^{n-k}}$ OEIS: A061356.

Illustration of the bijection.

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)

For enumeration of pseudoforests with no trees, see Nancy Ann Neudauer, Andrew M. Meyers, and Brett Stevens, Enumeration of the bases of the bicircular matroid on a complete graph. Proc. Thirty-second Southeastern Internat. Conf. Combinatorics, Graph Theory and Computing (Baton Rouge, La., 2001). Congr. Numer. 149 (2001), 109-127. Zaslav (talk) 00:19, 21 February 2008 (UTC)

I added some enumeration, but I need help with the "harvtxt" template. How do I get it to say the item is a dissertation, in a correct format? Zaslav (talk) 05:39, 21 February 2008 (UTC)

You mean {{citation}}? I changed it to use series=Dissertation. Is that what you wanted it to look like? —David Eppstein (talk) 05:42, 21 February 2008 (UTC)

Quite satisfactory. Thanks. I'm not comfortable with these templates (and I want first name first, as is usual in math and POV! is more readable) -- but it's not important. Zaslav (talk) 06:38, 21 February 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

${\binom {n-1}{2}}\sum _{1\leq r\leq n-2}{\frac {(n-3)!n^{n-2-r}}{(n-2-r)!}}$

(See sequence OEIS: A129137.)

2) You add the result

The number of labelled simple 1-forests with n vertices and m connected components is

$\sum _{partitions\ of\ n:\ 1K_{1}+2K_{2}+\cdots +nK_{n},\ with\ m\ parts\geq 3}{\frac {n!\prod _{1\leq i\leq n}A057500(i)^{K_{i}}}{\prod _{1\leq i\leq n}K_{i}!\ i!^{K_{i}}}}=$

$\sum _{partitions\ of\ n:\ 1K_{1}+2K_{2}+\cdots +nK_{n},\ with\ m\ parts\geq 3}{\frac {n!\prod _{1\leq i\leq n}({\binom {i-1}{2}}\sum _{1\leq r\leq i-2}{\frac {(i-3)!i^{i-2-r}}{(i-2-r)!}})^{K_{i}}}{\prod _{1\leq i\leq n}K_{i}!\ i!^{K_{i}}}}$.

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)

Pseudoarboricity

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)

Origin of the term "pseudoforest"

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)

Thanks for the correction. I think I've fixed it; please check the changes for accuracy. —David Eppstein (talk) 17:34, 28 April 2014 (UTC)

Graphs of functions

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)?

67.252.103.23 (talk) 02:23, 10 June 2014 (UTC)