
Re: An Argument for the Subroot Node
Posted:
Mar 14, 2008 12:21 AM


briggs@encompasserve.org wrote: > In article <r0bdt314kmk4gc4pkjbau9j6vf4n99r48q@4ax.com>, G. Frege <nomail@invalid> writes: >> On Tue, 11 Mar 2008 16:51:03 +0100, G. Frege <nomail@invalid> wrote: >> >> Oopos... typo/thinko... >> >>>> According to it, the perimeter of a triangle is a tree... >>>> which, of course, it is not. >>>> >>> Wait a second. If the nodes of your triangle were, say a, b, c then >>> (say) a, b would be connected by more than one path: >>> >>> p_1 = ((a,b)) >>> >>> p_2 = ((a,b), (b,c), (c,a), (a,b)) >>> >> No? > Why not: > > p_3 = ((a,c),(c,b)) > > Now the example doesn't imply that cycles are the only way to get multiple > paths. > > You'd better lay out your definition of "path". > > It appears that your current working definition of path is along > the lines of: > > An "edge" is an ordered pair of vertexes that are directly connected. > > A "path" is a sequence of edges such that the terminal vertex of > each edge in the sequence is the initial vertex of the next edge > (if any) in the sequence. In addition, the initial vertex > of an edge in the sequence may not appear as the terminal vertex > of the next edge in the sequence. (No direct backtracking). > > It seems fairly easy to prove that: > > 1. If a graph has a cycle, it will have two distinct nodes with > more than one path between them. > > 2. If a graph has two distinct nodes with more than one path between > them, it will contain a cycle. > > 3. If a graph is connected, there will be at least one path between > any pair of distinct nodes. > > 4. If a graph has at least one path between any pair of distinct nodes, > it is connected.
Does this say anything about a node with a single edge between it and itself? It seems that doesn't quite qualify as a cycle, eh?
:) Tony

