Cómo encontrar todos los triángulos de un gráfico

Question

Estoy buscando un método computacionalmente eficiente para generar una lista completa de los triángulos de un gráfico dado. A efectos de esta pregunta, damos a cada vértice un nombre de letra, y un triángulo se registra escribiendo las tres letras. Aunque el orden de las letras no importa, sólo se debe registrar uno de los posibles órdenes (es decir, se puede registrar "EFA", "FEA", "AFE", "FAE", "EAF" o "AEF", pero sólo uno de ellos).

Cada vértice tiene una referencia a todos los demás vértices. El algoritmo comienza con un solo vértice, que se supone que está conectado de alguna manera con todos los demás puntos del gráfico. Por ejemplo, si empezamos con E en la imagen de ejemplo, podríamos pasar a F, A o B y continuar hasta registrar todos los triángulos del gráfico.

Un triángulo se define como un grupo de tres vértices que están conectados entre sí, pero que no contienen ningún punto en su interior. En el gráfico del ejemplo, mientras que ABD, ACD y BDC son triángulos, ABC no lo es. (En este caso, el conjunto completo de triángulos es EAB, EAF, AFG, AGC, ADB, ADC, BDC).

Para mis propósitos particulares, el gráfico resulta tener la suposición de que cada La forma encerrada en el gráfico es un triángulo. Por ejemplo, en este ejemplo, la eliminación de la arista AB haría que el gráfico no fuera válido, ya que EBDA sería un cuadrilátero. Además, no hay aristas "colgantes": cada arista bordea al menos un triángulo. Un gráfico que no cumpla estas condiciones no necesita ser considerado.

Answer 1

Enumere las aristas y asegúrese de que los puntos finales de cada arista están listados en orden alfabético. El siguiente programa simplemente recorrerá la lista de aristas, comprobará si tienen un punto común y, si lo tienen, comprobará si los dos puntos restantes también constituyen una arista en el conjunto de entrada.

edges = [
    ('A', 'B'),
    ('A', 'C'),
    ('A', 'D'),
    ('A', 'E'),
    ('A', 'F'),
    ('A', 'G'),
    ('B', 'C'),
    ('B', 'D'),
    ('B', 'E'),
    ('C', 'D'),
    ('C', 'G'),
    ('E', 'F'),
    ('F', 'G')
]

for i in range(0, len(edges) - 1):
    for j in range(i + 1, len(edges)):
        e1 = edges[i]
        e2 = edges[j]
        if e1[0] == e2[0]:
            if (e1[1], e2[1]) in edges:
                print(e1[0] + e1[1] + e2[1])
        else:
            break

El programa imprime:

ABC
ABD
ABE
ACD
ACG
AEF
AFG
BCD

Answer 2

Muchos sistemas de software permiten este tipo de búsqueda. En Mathematica :

g = Graph[{"E" <-> "A", "E" <-> "B", "E" <-> "F", "A" <-> "F", 
   "F" <-> "G", "G" <-> "C", "A" <-> "C", "A" <-> "D", "D" <-> "C", 
   "B" <-> "D", "A" <-> "B", "B" <-> "C"}, VertexLabels -> Automatic]

Encuentra todos los ciclos de longitud exacta $3$ :

FindCycle[g, {3}, All]

{{"A" <-> "C", "C" <-> "D", "D" <-> "A"}, 
 {"B" <-> "D", "D" <-> "C", "C" <-> "B"}, 
 {"A" <-> "C", "C" <-> "B", "B" <-> "A"}, 
 {"A" <-> "D", "D" <-> "B", "B" <-> "A"}, 
 {"E" <-> "B", "B" <-> "A", "A" <-> "E"}, 
 {"E" <-> "A", "A" <-> "F", "F" <-> "E"}}

Length[%]

(* 6 *)

Son seis.

GraphicsGrid[
 Partition[(HighlightGraph[g, #] & /@ FindCycle[g, {3}, All]), 3]]

Lo anterior es la solución para un gráfico verdadero, donde el diseño ("incrustación") no es esencial.