Simple graph theory terminology question

For the discussion of math. Duh.

Moderators: gmalivuk, Prelates, Moderators General

Simple graph theory terminology question

Postby Bomaz » Fri Mar 16, 2012 1:31 pm UTC

What is a directed graph called if it has the property that all simple paths from some node n1 to a node n2 have the same length? (in this case length is defined as weights given to each edge in the usual manner of the shortest path problem)

Edit: added the requirement of the graph being simple
Last edited by Bomaz on Fri Mar 16, 2012 5:50 pm UTC, edited 3 times in total.
Bomaz
 
Posts: 22
Joined: Wed Dec 26, 2007 7:06 pm UTC

Re: Simple graph theory terminology question

Postby gorcee » Fri Mar 16, 2012 4:48 pm UTC

I'm a little uncertain what you mean by length. Do you mean length in terms of graph distance, which is a measure of the number of "steps" it takes to get from one point to another? (ie, from A to B to D would be distance 2). In such a case, the properties you're talking about would require the graph to be totally connected (every node is 1 step away from every other node).

Typically, we don't really care about the location of the nodes in some externally-fixed coordinate system, so, for instance, a Euclidean metric doesn't really mean much. We can get around that by assigning a weight to each connection, and link that weight to the physical separation between nodes w/r.t. some external metric. If this is what you're doing, you could just call the graph uniformly weighted.

These aren't really terms, per se, but rather a combination of phrases that have more or less universal meaning.
gorcee
 
Posts: 1501
Joined: Sun Jul 13, 2008 3:14 am UTC
Location: Charlottesville, VA

Re: Simple graph theory terminology question

Postby Bomaz » Fri Mar 16, 2012 4:55 pm UTC

With length I mean that with each edge having a given distance. the length of a path is the sum of the edges contained in the path. As per the normal definition of the shortest path problem
Last edited by Bomaz on Fri Mar 16, 2012 5:16 pm UTC, edited 1 time in total.
Bomaz
 
Posts: 22
Joined: Wed Dec 26, 2007 7:06 pm UTC

Re: Simple graph theory terminology question

Postby Talith » Fri Mar 16, 2012 4:56 pm UTC

Surely if p is a path from n1 to n2, then q=p(-p)p is a path from n1 to n2 also, but this path is 3 times as long as p, so no such graph exists.
User avatar
Talith
Proved the Goldbach Conjecture
 
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Simple graph theory terminology question

Postby Bomaz » Fri Mar 16, 2012 5:47 pm UTC

Ah, I am sorry I should have stated it as a simple path. I will now edit my original post to reflect this.
Bomaz
 
Posts: 22
Joined: Wed Dec 26, 2007 7:06 pm UTC

Re: Simple graph theory terminology question

Postby jaap » Fri Mar 16, 2012 6:15 pm UTC

Talith wrote:Surely if p is a path from n1 to n2, then q=p(-p)p is a path from n1 to n2 also, but this path is 3 times as long as p, so no such graph exists.

But this is a directed graph, so unless all those edges that form p are bidirectional, your construction does not work.
You don't want the graph to have any loops (of length k!=0) in it though, because if there is a loop going through the node n, then the distance from n to n is 0 or k.

I don't know if this property has a name.
User avatar
jaap
 
Posts: 1829
Joined: Fri Jul 06, 2007 7:06 am UTC

Re: Simple graph theory terminology question

Postby Tirian » Fri Mar 16, 2012 6:29 pm UTC

jaap wrote:I don't know if this property has a name.


Agreed. Graph theory is notorious for esoteric vocabulary, but you'd be on safe ground just clearly defining this as (n1-n2)-isopathitude or Property P or whatever in your introduction if you want to refer to it several times.
Tirian
 
Posts: 1626
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Simple graph theory terminology question

Postby Proginoskes » Sat Mar 17, 2012 7:52 am UTC

The closest term to what the OP wants, that I have heard of, is a geodesic; his directed graph has the property that every simple (u,v)-path is a geodesic.
User avatar
Proginoskes
 
Posts: 309
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

Re: Simple graph theory terminology question

Postby Bomaz » Sat Mar 17, 2012 11:44 am UTC

Ok, thanks for the help people
Bomaz
 
Posts: 22
Joined: Wed Dec 26, 2007 7:06 pm UTC


Return to Mathematics

Who is online

Users browsing this forum: 9pk7242q and 4 guests