Mindestgrad des „Baumgraphen“

Definieren Sie bei einem gegebenen Diagramm den Baumgraphen als einen Graphen, dessen Eckpunkte die Spannbäume von , und es gibt eine Kante zwischen zwei Bäumen, wenn einer durch Ersetzen einer einzelnen Kante vom anderen erhalten werden kann. Das heißt, es gibt eine Kante wenn zwei Kanten so dass . $G$ $T(G)$ $G$ $(T_1, T_2)$ $x, y \in G$ $T_1 - x = T_2 - y$

Meine Frage lautet: Gibt es einige nicht triviale Unter- oder Obergrenzen für den Grad des Scheitelpunkts mit einem Mindestgrad in ? $T(G)$

Hinweis: Ich habe die Frage (letzte Zeile) etwas bearbeitet, um sie weniger mehrdeutig zu machen.

graph-theory tree Corwin
quelle

Ihre Definition einer Kante macht keinen Sinn. Meinen Sie "es gibt eine Kante zwischen

und

wenn zwei Kanten

so dass

T_{1}

$T_1$

T_{2}

$T_2$

x, y \in G

$x, y \in G$

T_{1} - x + y = T_{2}

$T_1 - x + y = T_2$

Tyson Williams

Ja, tut mir leid, ich meinte Kanten.

Corwin

Wenn

ein Baum ist, ist sein Baumgraph

ein einzelner Scheitelpunkt mit Grad 0. Wenn

andererseits ein vollständiger Graph ist, hat jeder Scheitelpunkt in

den Grad

. Was genau meinst du mit "nicht trivial"?

G

$G$

T (G)

$T(G)$

G

$G$

T (G)

$T(G)$

Θ (n^{2})

$\Theta(n^2)$

Jeffs

es ist auch deutlich größer als die Konnektivität von

minus 1. Ist das trivial? Sie sollten Ihre Frage mit dem erweitern, was Sie bereits über das Problem wissen, damit wir beurteilen können, was Sie für trivial halten und was nicht.

G

$G$

Artem Kaznatcheev

@ Jeffe Ich denke nicht, dass

für ein vollständiges Diagramm korrekt ist. Nehmen Sie zum Beispiel einen Baum, der eine Linie ist. Durch Entfernen einer Kante aus dem Baum wird der Baum in zwei Gruppen

und

. Jetzt gibt es

Kanten, die hinzugefügt werden können, um daraus wieder einen Baum zu machen. Wenn wir alle Kanten dieses Baumes übernehmen, sehen wir, dass es in der Nähe

Bäume gibt.

Θ (n^{2})

$\Theta(n^2)$

S

$S$

T

$T$

| S | \cdot | T |

$|S|\cdot|T|$

Θ (n^{3})

$\Theta(n^3)$

Corwin

Antworten:

Wenn hat Knoten und Kanten, dann für jeden Spannbaum von , wobei jedes der Kanten , die nicht in sind kann mit jedem der Kanten auf dem Pfad in wechselbar zwischen den Endpunkten der Nicht-Baumkante. Angenommen, ist kein Multigraph, ergibt dies mindestens verschiedene Swaps; das heißt, jedes hat einen Grad von mindestens $G$ $n$ $m$ $T$ $G$ $m-n+1$ $T$ $T$ $G$ $2(m-n+1)$ $T$ . $2(m-n+1)$

Diese Grenze ist eng: Wenn einen Scheitelpunkt neben allen anderen hat und der Spannbaum ist, der aus allen auf einfallenden Kanten besteht , hat der Pfad in zwischen den Endpunkten jeder Nichtbaumkante genau die Länge zwei , also nimmt jede Nichtbaumkante an genau zwei Swaps teil und hat den Grad genau . $G$ $v$ $T$ $v$ $T$ $T$ $T$ $2(m-n+1)$

Auf der anderen Seite , wenn hat Umfang (kürzeste Zykluslänge) , dann den Weg in jedem Baum zwischen den Endpunkten jeder Nichtbaumkante zusammen mit diesem Rand, einen Zyklus bildet , die Länge zumindest müssen , so dass die Der Mindestgrad im Baumgraphen muss mindestens . Diese Grenze ist für einige Diagramme wie die Zyklusdiagramme und vollständige zweigeteilte Diagramme und Moore-Diagramme eng, da diese Diagramme Spannbäume enthalten, für die alle Nichtbaumkanten Zyklen mit einer Länge induzieren, die dem Umfang entspricht. $G$ $g$ $T$ $g$ $(g-1)(m-n+1)$

Das Finden des Mindestgrads des Baumgraphen für einen beliebigen gegebenen Graphen (äquivalent das Finden eines Spannbaums, der die Summe der Längen der Zyklen minimiert, die durch Nichtbaumkanten induziert werden) ist NP-vollständig: siehe Deo, Prabhu und Krishnamoorthy, "Algorithmen zur Erzeugung grundlegender Zyklen in einem Graphen", ACM TOMS 1982 . Es erscheint daher unwahrscheinlich, solche Grenzen zu finden, die für alle Diagramme eng sind.

David Eppstein
quelle

Danke für die hervorragende Antwort. Können wir eine enge Obergrenze finden, die für alle Diagramme korrekt ist?

Corwin

Gibt es auch eine bekannte Obergrenze für den Umfang eines verbundenen Graphen mit

Eckpunkten und

Kanten?

n

$n$

m

$m$

Corwin