• Create Account

# zomg

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

74 replies to this topic

### #41Zefrieg  Members   -  Reputation: 316

Like
Likes
Like

Posted 12 November 2003 - 05:39 PM

NAUGHTY, an isomorphic algorithm, uses adjacency matrices to determine isomophism. It runs at exponential time. The fact is, comparing two adjacency matrices is quite expensive.

Think of it like this. You have a black and white photo, both are the same picture, but the horizontal lines are all mixed up. What is the minimum time complexity required to determine if both represent the same picture?

Yes, my algorithm works for loops, multi-graphs, and directed graphs. Basically a loop is a vertex connected with itself. In this case:

1-1-1

There is only one vertex, so there will be one graph key value. The value would be determined like this:

first vertex has two connections:
sum = 2
first vertex is connected to a vertex with two connections:
sum = 4
first vertex is connected to a vertex with two connections:
sum = 6

The graph key would be G = {6}

For a graph that is like this:

1=2-3

This is how the algorithm would find the graph key

first vertex has two connections
sum = 2
first vertex is connected to a vertex with three connections
sum = 5
first vertex is connected to a vertex with three connections
sum = 8
sum is 8.

second vertex has three connections
sum = 3
second vertex is connected to a vertex with two connections
sum = 5
second vertex is connected to a vertex with two connections
sum = 7
second vertex is connected to a vertex with one connection
sum = 8
sum is 8

third vertex has one connection
sum = 1
third vertex is connected to a vertex with three connections
sum = 4
sum is 4

The graph key for that graph is G = {4, 8, 8}

Only another graph that is an isomorphism of that graph would also have a graph key of G = {4, 8, 8}

In the case of directed graphs like this:

1->2

One would be connected to 2, but two would have no connections. You would get a graph key of G = {0, 1}

You see, the graph keys complement eachother. If you were to change the connections in a fashion that wasn''t isomorphic, the graph key would also change.

### #42Zefrieg  Members   -  Reputation: 316

Like
Likes
Like

Posted 12 November 2003 - 05:44 PM

The coolest thing about my method is that it works across all types too. You are not going to have a multigraph that has the same graph key as a simple graph, a directed graph, or a directed multigraph. Each graph has a universally unique graph key.

### #43sjelkjd  Members   -  Reputation: 168

Like
Likes
Like

Posted 12 November 2003 - 05:58 PM

How do you know that graph keys are unique(not counting isomorphisms)?
You haven''t shown that if two graphs have the same graph key, they are isomorphic.

This sounds quite cool, but you did claim you had a proof... =)

### #44Zefrieg  Members   -  Reputation: 316

Like
Likes
Like

Posted 12 November 2003 - 06:02 PM

I have several other papers that go with the algorithm. I have some papers on uses for graph keys, and I also have a proof for graph keys. I have about 50 or so pages on this stuff

### #45sjelkjd  Members   -  Reputation: 168

Like
Likes
Like

Posted 12 November 2003 - 06:06 PM

How long is the proof that if two graphs have the same key, they are isomorphic?

### #46sjelkjd  Members   -  Reputation: 168

Like
Likes
Like

Posted 12 November 2003 - 06:11 PM

Interesting sidenote...given a graph of size k, there are at most 2^(k^2) = (2^k)^k graphs. However, given this graph labeling scheme, there is an upper limit of (k^2)^k graph keys for a graph of size k(at most k keys, each can be from 0 to k^2).

Anyone know how many isomorphically-unique graphs there are of size k?

### #47Zefrieg  Members   -  Reputation: 316

Like
Likes
Like

Posted 12 November 2003 - 06:17 PM

There is no need for a proof in that aspect. One unique graph key represents one unique graph. If two graphs have the same graph key, then they are isomorphic.

Only a proof that shows that each graph has a unique graph key is needed. I used universal generalization and existential instantiation to prove this. Basically, you need to prove this for every graph to infinite complexity. It is basically an impossible task like finding all prime numbers.

I didn''t put much in my proof, but I have data on my computer for the first 2,000 graphs. Its'' unique all the way up to that. You can assume it is unique from there on.

Say for example you asked how many graph keys there are for a single vertex. There would be infinite since you can continually add and infinite number of loops to that one vertex.

You know, I find all this stuff out, and I still got shafted on a mathematics scholarship. Pfft. I''ve been working on this stuff for about a year.

### #48sjelkjd  Members   -  Reputation: 168

Like
Likes
Like

Posted 12 November 2003 - 06:21 PM

quote:
Original post by Zefrieg
There is no need for a proof in that aspect. One unique graph key represents one unique graph.

There is a need for a proof. We don''t know that your algorithm works without one.

quote:

If two graphs have the same graph key, then they are isomorphic.

That''s what you have to prove =)

### #49Zefrieg  Members   -  Reputation: 316

Like
Likes
Like

Posted 12 November 2003 - 06:35 PM

Yeah, but proving that all non-isomorphic graphs have a unique graph key would also prove that if two graphs have the same graph key they are isomorphic to eachother. One would indirectly prove the other.

### #50sjelkjd  Members   -  Reputation: 168

Like
Likes
Like

Posted 12 November 2003 - 06:37 PM

ok. you still haven''t shown either proof... =)

### #51Zefrieg  Members   -  Reputation: 316

Like
Likes
Like

Posted 12 November 2003 - 06:40 PM

I''m not sure if there is a way to prove this beyond universal generalization.

### #52sjelkjd  Members   -  Reputation: 168

Like
Likes
Like

Posted 12 November 2003 - 06:42 PM

when you say the first 2000 graphs...do you mean graph sizes? So you have data on all 2000-vertex isomorphic graphs? Or just the first 2000 graphs?

### #53Zefrieg  Members   -  Reputation: 316

Like
Likes
Like

Posted 12 November 2003 - 06:44 PM

Yeah, but I''m not going to throw all my work on here to do that. People just wanted to see the algorithm. It is there and they can test it out if they like.

### #54Zefrieg  Members   -  Reputation: 316

Like
Likes
Like

Posted 12 November 2003 - 06:50 PM

All non-isomorphic graphs up to 2000 vertices? That would take years upon years. The number of graphs rise exponentially. No, I have around the first 2000.

[edited by - Zefrieg on November 13, 2003 1:52:44 AM]

### #55 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 12 November 2003 - 06:56 PM

For those whom don''t know what is talked about here:

http://mathworld.wolfram.com/IsomorphicGraphs.html

### #56sjelkjd  Members   -  Reputation: 168

Like
Likes
Like

Posted 12 November 2003 - 06:57 PM

but the question is, do they rise like (k^2)^k, or like (2^k)^k?

### #57Zefrieg  Members   -  Reputation: 316

Like
Likes
Like

Posted 12 November 2003 - 07:02 PM

This is how many graphs there are with n nodes starting at zero.

1,
1,
2,
4,
11,
34,
156,
1044,
12346,
274668,
12005168,
1018997864,
165091172592,
50502031367952,
29054155657235488,
31426485969804308768,
64001015704527557894928,
245935864153532932683719776,
1787577725145611700547878190848,
24637809253125004524383007491432768

[edited by - Zefrieg on November 13, 2003 2:03:20 AM]

### #58Zefrieg  Members   -  Reputation: 316

Like
Likes
Like

Posted 12 November 2003 - 07:05 PM

Like I said on an earlier post. Email me at Ultamos@msn.com to get the program I made that incorperates the algorithm.

### #59Punty50  Members   -  Reputation: 122

Like
Likes
Like

Posted 12 November 2003 - 07:45 PM

"I didn''t put much in my proof, but I have data on my computer for the first 2,000 graphs. Its'' unique all the way up to that. You can assume it is unique from there on."

No, you can''t. Figure out a sufficiently large N for which this always holds thereafter and prove up to N. How big of a number do you need? Just consider the prime number conjecture. People always thought that li(x) > pi(x). Is it, even though it holds for a lot of numbers? Nope. How large is X? Look up Skewes number. I am interested in the algorithm though, but I''m not willing to buy completely into it without formal proof, and neither will most mathematicians before they clain graph isomorphism isn''t "hard" computationally.

Brendan

### #60Wildfire  Members   -  Reputation: 154

Like
Likes
Like

Posted 12 November 2003 - 08:05 PM

If you can proof that each graph has a unique key, it is obvious that two graphs sharing the same key must be the same graph, but

quote:

I didn''t put much in my proof, but I have data on my computer for the first 2,000 graphs. Its'' unique all the way up to that. You can assume it is unique from there on.

You should not make such assumptions. Just because something is true for a limited number of entities (no matter how much there are), does not automatically imply it must be valid for every possible entity.

The only correct way (to my understanding) to proof something like this is to use ''complete induction''. You proof that something is valid for an entity n, and that if it is valid for n, that it is also valid for n+1.
I don''t know if there''s a practical way to do this for said isomorphic graphs, but that''s up to you to find out

[Haven''t been able to find a good link about ''principle of complete induction (pci)'' on google, if someone knows, please post it ]

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS