17
$\begingroup$

enter image description here

I often come across figures like this on the net, or as contest problems, asking to find the number of a specific type of polygon in the figure (triangles, in this case). But I've never really found a method for solving it, rather than blindly counting and hoping it's the right answer. For complete graphs, the problem is trivial:- ${n \choose k} \times (n-k)$, where $n$ is the number of vertices of the complete graph, and $(k+1)$ is the number of sides of the polygon in question. But I was wondering if there was a general algorithm for going about these problems. Any ideas?

DISCUSSION SO FAR: My above answer obtained for the complete graph is incorrect, as I hadn't considered the possibility of collinear vertices, and hence degenerate polygons (Thanks to Carl's brilliant answer, for pointing this out!). So here's the discussion so far: One can obtain the number of triangles (including degenerate) in any graph from the trace of its adjacency matrix $A$, by the formula $\text{Tr}(A^3)/3!$ (read Carl's post for the explanation). Unfortunately, this cannot be used for higher polygons, since cycles of path lengths $k$, $ k>3$ are attainable in less than $k$ vertices. So, focusing for now on obtaining the number of triangles in a graph, the algorithm is to compute $\text{Tr}(A^3)/3!$, and then to subtract the number of degenerate triangles from it. So now, the essential question is: Is there is a method for systematically enumerating distinct sets of collinear nodes in a graph?

$\endgroup$
  • $\begingroup$ Are you looking for automated (pattern) recognition of the triangles enclosed in the figure? That would require quite another answer than the graph-theoretical approaches below. $\endgroup$ – Han de Bruijn Dec 5 '13 at 20:42
  • $\begingroup$ Complete the graph, then count the number of extra lines and extra polygons obtained, and subtract them from the total. $\endgroup$ – Lucian Dec 8 '13 at 22:46
  • $\begingroup$ Do you care if your polygons self-intersect? Or if they are not convex? $\endgroup$ – cactus314 Dec 9 '13 at 15:17
  • $\begingroup$ @HandeBruijn: No, I'm not looking for automated pattern recognition. I'm rather looking for a "implementable-by-hand" algorithm that would give the right solution, in the least amount of time. But I'm curious though: What algorithm would such an automated recognition system implement? $\endgroup$ – Train Heartnet Dec 11 '13 at 12:50
  • 1
    $\begingroup$ @JobinIdiculla: Automatic recognition of (in this case) white areas within a figure can be done by a contouring algorithm. This is far from easy, though it pays off once you've developed the software. Tricky parts are that one must filter out the noise, for example by discarding contours that have too small an area. Furthermore, clockwise and counter-clockwise contours must be distinguished and the irrelevant ones discarded. There also will appear contours that surround the picture or the figure as a whole and these must been taken care of as well. $\endgroup$ – Han de Bruijn Dec 11 '13 at 14:25
5
+50
$\begingroup$

This post illustrates why $\text{Tr}(A^k)$ gives the number of cycles of length $k$ in the graph with adjacency matrix $A$. We have to be careful since a cycle is not the same thing as a polygon. For example, we can make a 4-cycle by moving between two nodes only: XYXY is a 4-cycle, but not a quadrilateral.

For triangles it turns out that this is not a problem since you can't form a 3-cycle that isn't also a triangle. (Caveat: you might form a degenerate (flat) triangle if three nodes are colinear. There is no way of detecting whether points are colinear using an abstract graph, represented as an adjacency matrix.)

Even with triangles, we still have to be careful of double counting. $\text{Tr}(A^3)$ is the number of 3-cycles in an undirected graph, but this gives 6 for the simple case of a 3-node graph that is itself triangle. $$A=\left(\begin{array}{ccc}0&1&1\\1&0&1\\1&1&0\end{array}\right) \Rightarrow \text{Tr}(A^3)=6$$ This is because all of the following cycles are triangles, even though they all form the same triangle: XYZ, XZY, YXZ, YZX, ZXY, ZYX.

Since each triangle gets counted 6 times, the total number of triangles in a graph with adjacency matrix $A$ is $$\text{Tr}(A^3)/6 = \text{Tr}(A^3)/3!$$

The example in the original question will have quite a few degenerate triangles since there are so many colinear vertices, making this method less than ideal. You can however compute all the triangles using the trace of the adjacency matrix and then try to count and subtract the number of degenerate triangles.

$\endgroup$
  • $\begingroup$ Thank you for this great answer! I wasn't aware of such a property of the adjacency matrix at all! I'm not sure I understand one thing though: Didn't you mean XYXYX as the 4-cycle instead of XYXY? Because the latter starts at X and ends at Y, unless I'm missing something. Okay, then I further understand why the method can't be applied to higher polygons. And thank you for pointing out the degenerate triangles in the case of collinear points (This makes my original answer for the complete graph incorrect, as I didn't consider the possibility of collinear points there). $\endgroup$ – Train Heartnet Dec 11 '13 at 12:53
  • $\begingroup$ Here are my final thoughts: Though the method is clever, and would have given a slick answer had there been no collinear points in the graph, it ultimately involves counting the number of degenerate triangles, which I believe is just as complex as counting the number of triangles in the original figure (perhaps even more complex!). So now my question turns to whether there is a method for systematically enumerating sets of collinear nodes in a graph? I know you mentioned there isn't a way of detecting them from the graph's adjacency matrix, but could there possibly be another way? $\endgroup$ – Train Heartnet Dec 11 '13 at 12:53
  • $\begingroup$ @JobinIdiculla Just to respond to your question about XYXY vs XYXYX, you're right that I left out the last X. This was on purpose, to make things read a little more easily. Basically, the last X is implicit. Sorry about the confusion. $\endgroup$ – Carl Dec 11 '13 at 14:31
  • $\begingroup$ Thank you for clarifying that. $\endgroup$ – Train Heartnet Dec 11 '13 at 22:08
1
$\begingroup$

Number of length $k$ closed walks in a graph is $\operatorname{Tr}(A^k)$, where $A$ is the adjacency matrix of the graph.

See e.g. chapter 1 of R. Stanley's Topics in algebraic combinatorics for details.

$\endgroup$
0
$\begingroup$

I'm adapting my answer to a similar question. Instead of a general algebraic approach, I'll concentrate on a method suitable for pen-and-paper solutions.

Be systematic. Label all your points. Choose a unique label for each triangle, e.g. by listing point labels in alphabetic order. Enumerate triangles in some order so you can check for them one at a time. I'd suggest lexicographic order.

Exploit symmetry. For all triangles there exist other triangles which are the same except for rotation and possibly reflection. Due to this, there will be six or even twelve copies of most of them. So you can keep the work down if you find only one representative of each such group, as long as you make sure to get the associated count right.

Combining these ideas, I'd label the figure like this:

Figure

Then you can enumerate triangles like this:

  • Axy: $6ABB, 12ABC, 24ABD$ ($12$ like $AB_1D_1$ and $12$ like $AB_1D_2$), $0ACC, 12ACD, 6ADD$
  • Bxy: $2BBB, 12BBC, 6BBD, 0BCC, 12BCD, 12BDD$ ($6$ like $B_1D_1D_6$ and $6$ like $B_1D_2D_5$)
  • Cxy: $0CCC,0CCD,0CDD$
  • Dxy: $0DDD$

So the grand total is

$$(6+12+24+12+6)+(2+12+6+12+12)=104$$

unless I made a mistake.

$\endgroup$
  • $\begingroup$ Ah, I see you found the $BBD$ triangles. Now your answer agrees with my program (posted in the other thread). :) $\endgroup$ – Steve Kass Nov 10 '14 at 0:47
  • $\begingroup$ @Steve: Yes, once I had my version of it ready, using it for this case here seemed the obvious thing to do. And it was a bit frustrating to realize that – once again – I had missed some triangles. I guess that's the downside of exploiting symmetry like this: it's easy to look at the wrong combinations of representatives only and thus miss possible triangles. $\endgroup$ – MvG Nov 10 '14 at 6:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.