I have an oriented graph. The orientation is not acyclic. Am I permitted to say that it is cyclic?

Advertisements

I have an oriented graph. The orientation is not acyclic. Am I permitted to say that it is cyclic?

Advertisements

Comments are closed.

%d bloggers like this:

I think you’re permitted to say it, but you have to define it first; I feel like it’s not standard terminology.

In particular, a “cyclic oriented graph”

couldrefer to an oriented graph which has cycles when regarded as a non-oriented graph. “Oriented cyclic graph” seems better for that meaning, though — the idea being that the unmodified word “graph” represents a nonoriented object, which we then declare to have cycles, and then finally put orientations on. A “cyclic oriented graph” seems like something where first you put an orientation and then you say “aha! it is cyclic!”, which is what you describe. But terminology which is this fragile with respect to word order seems dangerous.I vote no. “Cyclic graph” should be a graph which is a single cycle. I think “not acyclic” would be my choice, though “cycled” might work.

I’d go with non-acyclic, unless you want to say something more specific such as that it’s strongly connected.

Another no vote. Some graphs are acyclic, some cyclic (though I’m not totally sure which ones), some neither.

A similar issue: is the empty graph connected? No way. Every graph should be uniquely the disjoint union of connected graphs.

If the empty graph is not connected, then how do you represent it as the disjoint union of connected graphs?

It is the union of the empty set of connected graphs. (Just as 1 is the product of the empty set of primes.)

Allen, you’re nuts. If you’re willing to admit the existence of an empty graph, I don’t see how you can claim it isn’t connected. If you really want, you can make that a convention, but I don’t see how you can claim that is somehow morally correct.

What is more, I would claim that the empty graph is

notdisconnected, since a disconnected graph should be the disjoint union of two non-empty subgraphs.I also vote no. There’s no reason you couldn’t explain in your paper what you meant the first time you said this, but it is likely to confuse readers who haven’t been paying close attention to your definitions (so it would be an awkward expository choice).

Well, you all have convinced me. (I was torn between the arguments stated above, and the ugliness of “non-acyclic”, but ugliness wins over confusion.) Don’t let that cut off the discussion though.

I agree with Allen about connectedness, but for a slightly different reason. Maps between (path-)connected spaces should yield isomorphisms on Pi_0 (= homotopy classes of maps from a point). If the empty space is connected, the definition loses functoriality.

I also agree with Ben that the empty graph is not disconnected. Similarly, I agree with David that 1 is neither prime nor composite (not that he said as much).

A

connected componentof a graph is a maximal non-empty sub-graph such that there is a path between every pair of vertices in the sub-graph.A graph is called

connectedif it has exactly one connected component.This distinction was actually important in an enumeration course I took once, where we used exponential generating functions.

A quick definition is that a graph G is *connected* if the functor

hom(G, -): Graph –> Set

preserves coproducts. By this definition, the initial (i.e., empty) graph cannot be connected.

Namasté, Todd. I bow to your categorical Buddha-nature.

This distinction was actually important in an enumeration course I took once, where we used exponential generating functions.I assume you were dealing with the exponential formula, for example as follows?

If F(x) is the exponential generating functiont that counts connected graphs (with labeled vertices), and G(x) is the one that counts all graphs, then G(x) = exp F(x). This beautiful relationship would get messed up if the empty graph were connected. It amounts to Allen’s insistence that every graph should be uniquely the disjoint union of connected components. The great thing is that counting all graphs is easy (there are 2^(n choose 2) on n vertices), but connected graphs are more subtle, so we learn something about them from this relationship.

Henry: yes, exactly. In fact, looking over my notes, I see that we were given axioms for “natural classes of structures”, and that such a class was said to be

connectedif it had no structures on the empty set.I very much like Todd’s definition, though. I suspect it may even turn out to be quite closely related to the natural-classes-of-structures definition of connectedness, but I’m too tired to figure out how at the moment.

If one makes the most natural definition of connectedness in formal logic (for all vertices u,v there exists a path from u to v) the empty graph satisfies that definition vacuously. The alternative definition that, for every partition of the vertices into two nonempty sets, there is an edge crossing the partition, again is satisfied vacuously by the empty graph. This could be taken as implying that the empty graph is connected, but I’d rather take it as evidence that these aren’t quite the right definitions.

Those are pretty natural sounding definitions. I don’t know much about formal logic, but I guess it may be a domain where uniqueness of decomposition is not so important, perhaps because of some kind of quantifier burden.

It seems to me that the questions is about grammar. And at least for indoeuropean languages, “no X” and “aX” are different concepts. “Non theist” is a different thing than “atheist”. And different grammar constructs.

I suggest disruptive approach.

Let alone empty graph, is graph with single vertex should be considered connected or not?

Naturally, to be called “connected” graph should contain at least one “connection”, i.e. edge. So only graphs with no less than two vertices can be connected.

Seriously, I can see two distinct concepts in graph theory:

(1) graph with exactly one connected component

(2) graph with one or zero connected components

Either of them can be called “connected” for short. So we can have: (1) = “connected”, (2) = “connected or empty” or (1) = “connected non-empty”, (2) = “connected”.

Personally, I prefer latter approach. I also have a feeling that this definition of “connected” makes graph theory as whole a little bit simpler.

This could be taken as implying that the empty graph is connected, but I’d rather take it as evidence that these aren’t quite the right definitions.I agree that it is evidence that the definitions aren’t quite perfect. It’s much like defining “prime” in elementary number theory – many people’s first attempt at a definition implies that units are prime, and it’s easy to get high school students to debate this vociferously.

In fact, the analogy is a little more substantial (as David and Scott hinted at above). Connected graphs are the primes under the operation of taking disjoint unions, and the empty graph is a unit and not a prime. This is despite the fact that it has no nontrivial factorization.

Allen, you’re nuts.Ben, you’re a hoser!

Actually I had a much more polite and reasoned response, but Henry Cohn beat me to it just above.

Suffice it to say, I feel that definitions Should be chosen to simplify the statements and proofs of theorems, even if they are then confusing to high school students.

You know, Allen, I think this illustrates a couple of points from the (increasingly long) discussion at an even more popular post.

1. Mathematicians seem to be pretty bad at flame wars. “Hoser”? Really? (Not mention that I seem to be the one who got hosed up there).

2. On the other hand, it’s easy for things to look meaner on the internet than they really are. Someone who didn’t know that Allen and I know each other (in fact, he was on my qualifying exam committee in Berkeley, way back in the mists of time) and didn’t know that I have the utmost respect for his mathematical judgement, might think we were having an actual flame war. Stupid internet, thinks it’s so cool with its “lack of context.”

Funny, this came up in October on another mailing list. Certainly having fewer than two connected components is necessary. If the goal is merely to capture the intuition behind “connected” then it’s also sufficient. However in some applications it may be desirable or even necessary to define it as exactly one connected component. So if you always explicitly say whichever of “connected or empty” or “having exactly one connected component” you have in mind you’ll never go wrong. To justify using just “connected,” either it should be the case that it doesn’t matter which, or you should specify up front which. I probably left out a case or two.

Yes. The concepts “at most one” and “exactly one” are both very useful in mathematics. I propose we distill this argument down to its essence and argue about which of them is more important.