Schließsequenzlängen in Graphen

Question

Es gibt drei bekannte Operationen an Digraphen: symmetrischer Verschluss, transitiver Verschluss, reflexiver Verschluss. Wenn wir diese nennen$S, T, R$, dann können wir Sequenzen von ihnen nehmen und Dinge wie berechnen $TSTSR(G)$und der resultierende Graph kann sich von unterscheiden $G$.

Inspiriert von https://math.stackexchange.com/questions/3873941/what-is-the-smallest-digraph-whose-reflexive-symmetric-transitive-closures-in/3874003?noredirect=1#comment7990405_3874003Ich frage mich "Für eine feste Grafik von $n$ Knoten, wenn wir alle Sequenzen von betrachten $S,T,$ und $R$Operationen beliebiger endlicher Länge können viele unterschiedliche Graphen erhalten. Was ist die größte Anzahl unterschiedlicher Diagramme, die auftreten können? (möglicherweise als Funktion von$n$) "

Eine schwache Obergrenze, wie viele verschiedene Graphen aus einem Startgraphen entstehen können $G$ ist $2^{n^2}$, weil das die Anzahl der Digraphen ist $n$Knoten, aber sicherlich ist die Anzahl viel kleiner. Und$R$ ist hier wirklich nur ein roter Hering, in dem Sinne, dass, sobald Sie sich bewerben $R$ einmal hat es nie mehr eine weitere Wirkung, so dass Sie immer alle "versickern" können $R$s bis zum Ende (oder Anfang) der Sequenz, und wenn mehr als 1 vorhanden sind, können Sie diese durch eine einzelne ersetzen $R$.

Answer 1

Konzentrieren wir uns zunächst auf symmetrische und transitive Verschlüsse.

Wenn wir eine Folge von Operationen ausführen, die einen symmetrischen Abschluss gefolgt von einem transitiven Abschluss enthält, wird jede schwach verbundene Komponente (außer einem isolierten Scheitelpunkt) zu einem vollständig gerichteten Graphen mit eingeschlossenen Schleifen. Zu diesem Zeitpunkt kann dem Diagramm nichts mehr passieren, da verschiedene schwach verbundene Komponenten niemals interagieren. Die möglichen unterschiedlichen Graphen, die wir erhalten könnten, sind:

• $TS(G)$, was uns das obige Ergebnis gibt, und
• $G$, $S(G)$, $T(G)$, $ST(G)$Dies sind die einzigen Kombinationen, die nicht zweimal hintereinander dieselbe Operation enthalten und nicht enthalten $TS$.

Ebenfalls, $R$ pendelt mit beiden $S$ und $T$Also könnten wir es genauso gut am Anfang machen, wenn wir es überhaupt machen. Das gibt uns$10$ möglicherweise unterschiedliche Kombinationen: $$ G, S(G), T(G), ST(G), TS(G), R(G), SR(G), TR(G), STR(G), TSR(G). $$

Für eine Grafik, in der alle $10$ von diesen sind unterschiedlich, betrachten Sie die $5$-Vertex-Diagramm

$$a \gets b \to c \to d \phantom{{} \to {}} e$$

Um dies effizient zu überprüfen, überprüfen Sie zunächst, ob das Ausführen einer anderen Teilmenge von Vorgängen zu unterschiedlichen Ergebnissen führt, da:

• Nur die Grafiken mit einem $R$ Operation enthalten die Kante $e \to e$.
• Nur die Grafiken mit einem $S$ Operation enthalten die Kante $a \to b$.
• Nur die Grafiken mit a $T$ Operation enthalten die Kante $b \to d$.

Alles was übrig bleibt ist zu unterscheiden $ST(G)$ von $TS(G)$, und $STR(G)$ von $TSR(G)$, weil die Teilmenge der durchgeführten Operationen in diesen Fällen dieselbe ist. Wir haben$ST(G) \ne TS(G)$ und $STR(G) \ne TSR(G)$ da $ST(G)$ und $STR(G)$ Enthalten Sie nicht die Kanten $a \to d$ und $d \to a$während $TS(G)$ und $TSR(G)$ machen.