Contando el número de polígonos en una figura

Question

Me vienen a menudo a través de figuras como este en la red, o como concurso de problemas, haciendo para encontrar el número de un tipo específico de polígono en la figura (triángulos, en este caso). Pero yo nunca he encontrado un método para resolver, en lugar de a ciegas contar y esperando la respuesta correcta. Para completar los gráficos, el problema es trivial: - ${n \choose k} \times (n-k)$ donde $n$ es el número de vértices del grafo completo, y $(k+1)$ es el número de lados del polígono en cuestión. Pero me preguntaba si existe un algoritmo general para ir sobre estos problemas. Alguna idea?

DISCUSIÓN hasta el momento: Mi respuesta anterior, obtenidos para el grafo completo es incorrecta, ya que no había considerado la posibilidad de colineales vértices, y por lo tanto degenerado polígonos (Gracias a Carl brillante respuesta, para señalar esto!). Así que aquí está la discusión hasta el momento: se puede obtener el número de triángulos (incluyendo degenerado) en cualquier gráfico de la traza de su matriz de adyacencia $A$, por la fórmula $\text{Tr}(A^3)/3!$ (lectura de Carl post para la explicación). Por desgracia, este no puede ser utilizado para más polígonos, ya que los ciclos de longitudes de trayectoria $k$, $ k>3$ se que se puede lograr en menos de $k$ vértices. Por lo tanto, concentrarse por ahora en obtener el número de triángulos en un grafo, el algoritmo es calcular los $\text{Tr}(A^3)/3!$, y luego restar el número de los degenerados triángulos a partir de ella. Así que ahora, la pregunta esencial es: ¿existe un método para que de manera sistemática la enumeración de distintos conjuntos de colineales nodos en un grafo?

Answer 1

Este post se ilustra por qué los $\text{Tr}(A^k)$ da el número de ciclos de longitud $k$ en el grafo con matriz de adyacencia $A$. Debemos tener cuidado ya que un ciclo no es la misma cosa como un polígono. Por ejemplo, podemos hacer un 4-ciclo moviendo entre dos nodos: XYXY es un 4-ciclo, pero no un cuadrilátero.

Para los triángulos, resulta que esto no es un problema ya que no se puede formar un 3-ciclo, que no es también un triángulo. (Advertencia: puede formar un degenerado (plana) triángulo si tres nodos son colinear. No hay manera de detectar si los puntos son colinear usando un resumen gráfico, representada como una matriz de adyacencia.)

Incluso con triángulos, todavía tenemos que ser cuidadosos de doble conteo. $\text{Tr}(A^3)$ es el número de 3-ciclos en un grafo no dirigido, pero esto da 6 para el caso simple de un 3-gráfico de nodos que es en sí mismo triángulo. $$A=\left(\begin{array}{ccc}0&1&1\\1&0&1\\1&1&0\end{array}\right) \Rightarrow \text{Tr}(A^3)=6$$ Esto es porque todos los ciclos siguientes son triángulos, a pesar de que todos forman un mismo triángulo: XYZ, XYZ, YXZ, YZX, ZXY, ZYX.

Ya que cada triángulo son contados 6 veces, el número total de triángulos en un grafo con matriz de adyacencia $A$ $$\text{Tr}(A^3)/6 = \text{Tr}(A^3)/3!$$

En el ejemplo de la pregunta original va a tener unos cuantos degenerados triángulos, ya que hay muchas colinear vértices, haciendo de este método es menos que ideal. Sin embargo, puede calcular todos los triángulos utilizando la traza de la matriz de adyacencia y, a continuación, tratar de contar y restar el número de los degenerados triángulos.

Answer 2

Número de longitud de $k$ cerrado camina en una gráfica es $\operatorname{Tr}(A^k)$ donde $A$ es la matriz de adyacencia del grafo.

Ver, por ejemplo, el capítulo 1 de la R. Stanley Temas en la combinatoria algebraica para obtener más detalles.

Answer 3

Me estoy adaptando mi respuesta a una pregunta similar. En lugar de un general algebraica de enfoque, me voy a concentrar en un método adecuado para lápiz-y-papel de soluciones.

Ser sistemático. Etiqueta todos sus puntos. Elija una etiqueta única para cada triángulo, por ejemplo, mediante un listado de las etiquetas de los puntos en orden alfabético. Enumerar los triángulos en orden así que usted puede comprobar para ellos uno a la vez. Te sugiero que lexicográfica del orden.

Aprovechar la simetría. Para todos los triángulos existen otros triángulos que son los mismos excepto para la rotación y, posiblemente, de la reflexión. Debido a esto, habrá seis o doce copias de la mayoría de ellos. Así que usted puede guardar el trabajo si usted encuentra que sólo un representante de cada grupo, mientras que asegúrese de obtener los asociados conteo.

La combinación de estas ideas, me gustaría etiqueta de la figura como este:

A continuación, puede enumerar los triángulos como este:

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

Así que el total es

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

a menos que cometí un error.