• Erhalten Sie die Formeldarstellung des Diagramms, erweitern Sie die Formeldarstellung und führen Sie sie auf. ――Zum Beispiel: Wenn jede Seite in einem Dreiecksdiagramm a, b, c ist, wird der Ausdrucksausdruck ** gesetzt ** (abc), und wenn dieser erweitert wird, wird er ab / ac / bc sein.
• Die Formeldarstellung des Diagramms wird wie folgt berechnet.
• Haben Sie als ersten Ausdruck der Seite einen Buchstaben des Alphabets. --Graphen können Seiten oder Seiten und Punkte entfernen, während die Ausdrucksdarstellung erhalten bleibt.
• Der Formelausdruck ist erforderlich, wenn der Graph einen Punkt erreicht.
• Die Ausdrucksdarstellung von Graph G (Ausdruck (G)) kann wie folgt transformiert werden, indem eine beliebige Seite E ausgewählt wird. (Standardregel)
• Ausdruck (G) = ** Summe ** (** Produkt ** (** Satz ** (Ausdruck (E)), Ausdruck (E aus G entfernen)), ** Produkt ** (Ausdruck (E)) , Ausdruck (reduziert von G auf E [^ 1]))

[^ 1]: Das Verkleinern einer Seite ist eine Operation, bei der die Seite 0 lang wird und die Punkte an beiden Enden in eins geändert werden.

Es gibt die folgenden Arten von Ausdrucksausdrücken.

• ** Summe ** (A, B): Die Summe der Elemente A und B.
• ** Produkt ** (A, B): Ein Produktsatz der Elemente A und B (kombinierte und angeordnete Zeichen).
• ** Paar ** (A): Löscht und erweitert ein Zeichen für jedes Element von A. Zum Beispiel werden ** Paare ** (abc) in drei, ab, ac und bc erweitert.

Sie können dies nur mit den oben genannten Standardregeln tun. Um jedoch den Rechenaufwand zu verringern, fügen Sie Regeln für bestimmte Fälle hinzu. (Abgeleitet von Standardregeln)

• Wenn Seite E sich selbst durchläuft: Ausdruck (G) = ** Produkt ** (** Paare ** (Ausdruck (E)), Ausdruck (E aus G entfernen))
• Wenn die Reihenfolge eines Endes der Seite E (Anzahl der verbundenen Seiten) = 1 ist: Ausdruck (G) = ** Produkt ** (Ausdruck (E), Ausdruck (Reduzieren von E von G))
• Wenn Seite E und Seite F durch Punkt V und die Reihenfolge von Punkt V = 2 verbunden sind: Ausdruck (E) = ** Produkt ** (Ausdruck (E), Ausdruck (F)) Finden Sie das Diagramm nach der Kontraktion.

Definieren Sie die Klasse.

python3

from itertools import combinations, product
from collections import namedtuple
Union = namedtuple('Union', 'l r') #Summe
Produ = namedtuple('Produ', 'l r') #Produkt
Combi = namedtuple('Combi', 'e') #einstellen
class Edge:
    def __init__(self, u, v, e):
        self.u = u
        self.v = v
        self.e = e
    def __repr__(self):
        return '<%s %s %s>'%(self.u, self.v, self.e)
class Graph:
    def __init__(self, num_nodes, edges):
        self.nodes = [[] for _ in range(num_nodes)]
        self.edges = []
        for i, (u, v) in enumerate(edges):
            self.edges.append(Edge(u, v, chr(97 + i)))
            self.nodes[u].append(i)
            self.nodes[v].append(i)
    def __repr__(self):
        return str(self.edges)
    def spanning_tree(self):
        res = Graph._reduct(self.nodes.copy(), self.edges.copy())
        return sorted(Graph._expand(res))
    @staticmethod
    def _reduct(nodes, edges):
        if not edges:
            return '' if len(nodes) == 1 else None
        for i, e in enumerate(edges): #Selbstschleife
            if e.u == e.v:
                Graph._erase(nodes, edges, i)
                return Produ(l=Combi(e=e.e), r=Graph._reduct(nodes, edges))
        for con in nodes: #Auftrag=1
            if len(con) == 1:
                e = edges[con[0]]
                Graph._erase(nodes, edges, con[0])
                return Produ(l=e.e, r=Graph._reduct(nodes, edges))
        for con in nodes: #Auftrag=2
            if len(con) == 2:
                e = edges[con[0]]
                edges[con[0]] = Edge(e.u, e.v, Produ(l=edges[con[0]].e,
                                                     r=edges[con[1]].e))
                Graph._shrink(nodes, edges, con[1])
                return Graph._reduct(nodes, edges)
        e = edges[0]
        nodes2, edges2 = nodes.copy(), edges.copy()
        Graph._erase(nodes, edges, 0)
        Graph._shrink(nodes2, edges2, 0)
        return Union(l=Produ(l=Combi(e=e.e), r=Graph._reduct(nodes, edges)),
                     r=Produ(l=e.e, r=Graph._reduct(nodes2, edges2)))
    @staticmethod
    def _erase(nodes, edges, k):
        for a, con in enumerate(nodes):
            nodes[a] = [b if b < k else b-1 for b in con if b != k]
        del edges[k]
    @staticmethod
    def _shrink(nodes, edges, k):
        e = edges[k]
        dn = max(e.u, e.v)
        sn = e.u+e.v-dn
        nodes[sn] = nodes[sn] + nodes[dn]
        for a, con in enumerate(nodes):
            nodes[a] = [b if b < k else b-1 for b in con if b != k]
        for a, ed in enumerate(edges):
            u = sn if ed.u == dn else ed.u if ed.u < dn else ed.u-1
            v = sn if ed.v == dn else ed.v if ed.v < dn else ed.v-1
            edges[a] = Edge(u, v, ed.e)
        del edges[k]
        del nodes[dn]
    @staticmethod
    def _expand(ex):
        if ex is None:
            return set()
        elif isinstance(ex, str):
            return set(ex) if ex else {''}
        elif isinstance(ex, Combi):
            exe = Graph._expand(ex.e)
            return set.union(*(set(''.join(s) for s in
                combinations(e, len(e)-1)) for e in exe))
        exl = Graph._expand(ex.l)
        exr = Graph._expand(ex.r)
        if isinstance(ex, Union):
            return exl.union(exr)
        return {''.join(sorted((i+j))) for i, j in product(exl, exr)}

Versuchen Sie es mit einem Dreiecksdiagramm.

python3

g = Graph(3, [(0,1), (1,2), (2,0)])
print(g.spanning_tree())
>>>
['ab', 'ac', 'bc']

Ich werde es mit einem vollständigen Diagramm von 4 Punkten versuchen.

python3

g = Graph(4, [(0,1), (1,2), (2,3), (3,0), (0,2), (1,3)])
print(g.spanning_tree())
>>>
['abc', 'abd', 'abf', 'acd', 'ace', 'acf', 'ade', 'aef',
 'bcd', 'bce', 'bde', 'bdf', 'bef', 'cdf', 'cef', 'def']

Übrigens hat dieser Python 85 Zeilen, aber es waren 500 Zeilen, wenn er in C geschrieben wurde, und ungefähr 330 Zeilen, wenn er in C # geschrieben wurde.

das ist alles