From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/1867 Path: news.gmane.org!not-for-mail From: Eduardo Dubuc Newsgroups: gmane.science.mathematics.categories Subject: Re: Unlabeled graphs Date: Sun, 18 Feb 2001 18:38:52 -0500 (EST) Message-ID: <200102182338.SAA11720@cogito.math.uqam.ca> References: <4.1.20010215151228.009f0500@mail.oberlin.net> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1241018162 894 80.91.229.2 (29 Apr 2009 15:16:02 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:16:02 +0000 (UTC) To: categories@mta.ca Original-X-From: rrosebru@mta.ca Mon Feb 19 11:54:24 2001 -0400 Return-Path: Original-Received: (from Majordom@localhost) by mailserv.mta.ca (8.11.1/8.11.1) id f1JF2IP22661 for categories-list; Mon, 19 Feb 2001 11:02:18 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f In-Reply-To: <4.1.20010215151228.009f0500@mail.oberlin.net> from "Charles Wells" at Feb 15, 2001 03:31:44 PM X-Mailer: ELM [version 2.5 PL2] Original-Sender: cat-dist@mta.ca Precedence: bulk X-Keywords: X-UID: 49 Original-Lines: 56 Xref: news.gmane.org gmane.science.mathematics.categories:1867 Archived-At: this is in reply to Charles Wells, I quote in between ' " ' " Major point: Any way you store an unlabeled graph in a computer will involve a memory location for each node, and so introduces a labeling, indeed a total ordering, on the nodes. However, a high level language with pointers such as C can be used to describe the structure without any names being given explicitly. The structure head will point to a node, which will have a pointer to another node, etc, and the program text will not mention all the nodes directly. For the purpose of computing with the graph, you can have the program traverse the nodes without naming them. This is a commonly used technique. (There will have to be pointer structures for the edges with pointers to the two nodes each is incident on.) When the program is compiled, the nodes are made to correspond to memory locations but the locations are hidden from the user. It seems to me that this preserves the psychology of a drawing with no labels on the nodes. " quite wright, i agree that the technique you describe "preserves the psychology of a drawing with no labels on the nodes. ". i had no thought about the pointer technique !!! but then, try to put an unlabeled graph in a computer using assembler languge ! is what i should have said ! " You can respond that each node has an implicit label, essentially an integer, which is the number of pointers you have to dereference to get to the node. But that is just like saying that in the drawing of the graph on a piece of paper, each node has an implicit label, namely its location on the paper. If you allow implicit labels like this the drawing has them and so does the graph in the computer. If you don't allow them then neither has labels. Let me forestall someone bringing up a red herring: The coordinates of the node on the paper depend on an arbitrary choice of coordinate system, unlike the number of pointers you need to get to the stored node in the computer. This argument, if someone makes it, is based on a misreading of what I said. I said each node is labeled by its location on the paper. I didn't say the coordinates of the location. The location itself is the label. " the final conclusion of your arguing : " The location itself is the label" means that there is no such a thing as an unlabeled graph. interesting . . . but what about permutation of the labels ? en fin ! we should perhaps leave this problem to the philosophers, if they would be able to understand it e.d.