If there is such a mapping, it seems as though it could turn the graph isomorphism problem from a purely combinatorial problem to a discrete geometric one.
4
-
$\begingroup$ There is bijection from finite graphs to natural numbers. $\endgroup$– joroCommented Jun 28, 2016 at 15:46
-
$\begingroup$ ...So if a point with natural coordinates is "discrete geometric object", the answer is positive. $\endgroup$– joroCommented Jun 28, 2016 at 15:56
-
$\begingroup$ I'm voting to close this question because it seems like a fishing-expedition that has not been thought through $\endgroup$– Yemon ChoiCommented Jun 29, 2016 at 3:38
-
$\begingroup$ Yes, I think that's fair. I was just starting to think about different approaches to the graph isomorphism problem, and was trying to consider a nice mapping that would reduce the complexity of an algorithm which would check for isomorphism. I've made a bit of progress on this since the question was posted, but I agree, I hadn't given it much thought at the time. $\endgroup$– adamcattoCommented Jul 25, 2016 at 17:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Map any $n$-vertex graph $G$ into a collection of $n$ points in $(n-1)$-dimensional space that are all at unit distance from each other, together with a line segment connecting two points whenever the corresponding two graph vertices are adjacent. Then two graphs are isomorphic if and only if the corresponding geometric objects are congruent.
answered Jun 28, 2016 at 19:54