Is there a way to encode a unique arrangement of vertices of a graph with a unique short word?
I call graphs $G_1$ and $G_2$ distinct iff (i) $G_1$ has a different arrangement1 of vertices than $G_2$ and (ii) $G_1$ and $G_2$ have the same number of vertices. All other properties of $G_1$ and $G_2$ have no effect on distinguishing them. For example, $G_1$ and $G_2$ may be the same even if the number of edges of the two graphs is different.
Example:
| $G_1$ | $G_2$ | $G_3$ |
|---|---|---|
 |
 |
 |
Here, $G_1 = G_2$ but $G_1 \neq G_3 \iff G_2 \neq G_3$.
I'm wondering if there is a way to create a unique correspondence between a graph and a single word (any string of letters, possibly gibberish) of the English alphabet. That is to say, distinct graphs $G_1$ and $G_2$ must necessarily map to a different word. It is preferable that the word has 4-7 characters. Additionally, the word may contain a single integer from 1-9 at the end of it. Hence, for example, $G_1$ could map to the word GLBXR7 and $G_2$ could map to the word MMTR.
I'm looking for an algorithm to map every distinct graph with a unique word. You may assume that every graph has the same number of vertices.
A very crude attempt is to label each vertex of a graph with letters from left to right, top to bottom and concatenate them in that order. However, I don’t think this is sufficient for uniqueness.
Clarifications
I attempt to clarify some of the potentially ambiguous elements of my post.
-
I agree that the notion of a "graph" is not entirely relevant here. I actually chose it because I am working with this sort of information in another project where connectivity matters. Nonetheless, viewing this as a point cloud is perfectly fine; you may edit the tag(s) if you'd like.
-
There doesn’t need to be a bijection between words and graphs. Every unique graph should map to a unique word, but every word need not map to a graph.
-
Since I placed a finite restriction on the length of a word (4 - 7 characters), I attempt to set an upper bound on the number of vertices of a graph.
$$\text{Number of words} = \sum_{k = 4}^7 \left(26^{k-1}\cdot (26 + 9)\right) = 11244509640$$ $$\text{Number of graphs with} \le n \; \text{vertices} = \sum_{k = 1}^n \sum_{i = 1}^k {{k - 1} \choose {i - 1}} = 2^n - 1$$ $$11244509640 = 2^n - 1 \implies \lfloor n\rfloor = 33$$
- I apologise for not making this point before, but the algorithm should be human computable, that is, possibly something a human can do in their head in about 15 seconds.
1I'm not sure how to perfectly formalise the notion of an arrangement, but a possible necessary and sufficient condition is to consider the number of vertices to the left, right and along the same vertical axis as each vertex of graphs $G_1$ and $G_2$—if any of the values are different, the graphs are distinct.
2 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
The following users marked this post as Works for me:
| User | Comment | Date |
|---|---|---|
| Carefree Explorer | (no comment) | Aug 21, 2022 at 08:53 |
I'm going to assume your points are lying on an integer grid. I'm also assuming you always have a finite number of points.
Then one way to make words for your point clouds is to enumerate the grid points, for example by starting at the origin and going in a spiral. Then you can assign an unique finite bit-string to each configuration by starting at the origin, following the spiral and note a $0$ for any unoccupied grid point, and a $1$ for any occupied grid point, terminating as soon as you've covered all points (that is, all occupied grid points). Note that the last obtained digit that way is always a $1$.
Now reverse that bit string. This ensures the first it is always $1$ (except for the empty cloud, which gets a single $0$), and therefore you can interpret the bit string as binary representation of a natural number, thus getting a bijection between point configurations and natural numbers.
Now all that remains is to map natural numbers to words. That's a pretty standard problem, and the best way to do so depends on the typical properties of your point arrangements. For example, if your points are generally always close to the origin, then you may just convert the number to base 26, and write it down using the 26 letters of the alphabet as digits. OTOH that may be a bad strategy if your points are frequently far from the origin.
Let's look at an example:
Here we see a graph with four points at the coordinates $(0,\pm 1)$, and $(\pm 1, 0)$. Starting at the origin (beginning of the spiral), we get the bit string $01010101$. Note that after the fourth $1$, we've covered all the dots, therefore we stop.
Reversing the bit string then gives $10101010$, which corresponds to the number $90$. Using the base-26 strategy with a=0, b=1, …, z=25, the resulting word is dm.
As mentioned in a comment, you seem to wish to classify sets of points, not graphs as such.
If you wish to classify them bijectively with word, you need the cardinalities of the sets to match; that is, there must be the same amount of possible word and the same about of possible sets of points.
The cardinality of the set of words is countably infinite, or if you set a bound on their length, some finite number.
If you wish to make the cardinality of sets of points countable, then you certainly need to discretize the plane (for example, only use coordinates with integer values).
If you wish to make the cardinality of sets of points finite, then you need to have an upper bound for how many points to place and you need a finite set of coordinates they can be placed into. Then, if you really need a bijection, you need to have an equal number of possible words as of possible sets of points. But maybe it does not damage if there are more words, so that not every word corresponds to a set of points?
In any case, once your two sets have the same cardinality, there exists a bijection, and likely quite a lot of bijections, between them.
The words have a natural order in terms of length and alphabet, so if you can create a natural order for the point sets, too, then you are done. Maybe order them by the number of points first, and then for example left to right, down to up (in case of a bounded part of the plane) or starting from closes to the origin and then in a clockwise fashion. Really, any ordering for the individual points, plus the idea of alphabetic ordering, does the trick here.
0 comment threads
1 comment thread