Mindestgrad des „Baumgraphen“

8

Definieren Sie bei einem gegebenen Diagramm den Baumgraphen T ( G ) als einen Graphen, dessen Eckpunkte die Spannbäume von G sind , 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 ( T 1 , T 2 ), wenn zwei Kanten x , y G existieren, so dass T 1 - x = T 2 - y .GT(G)G(T1,T2)x,yGT1x=T2y

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.

Corwin
quelle
Ihre Definition einer Kante macht keinen Sinn. Meinen Sie "es gibt eine Kante zwischen und T 2, wenn zwei Kanten x , y G existieren, so dass T 1 - x + y = T 2 "? T1T2x,yGT1x+y=T2
Tyson Williams
Ja, tut mir leid, ich meinte Kanten.
Corwin
3
Wenn ein Baum ist, ist sein Baumgraph T ( G ) ein einzelner Scheitelpunkt mit Grad 0. Wenn G andererseits ein vollständiger Graph ist, hat jeder Scheitelpunkt in T ( G ) den Grad Θ ( n 2 ) . Was genau meinst du mit "nicht trivial"? GT(G)GT(G)Θ(n2)
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
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 S und T getrennt . Jetzt gibt es | S | | T | 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 Θ ( n 3 ) Bäume gibt. Θ(n2)ST|S||T|Θ(n3)
Corwin

Antworten:

12

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

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

Auf der anderen Seite , wenn hat Umfang (kürzeste Zykluslänge) g , dann den Weg in jedem Baum T zwischen den Endpunkten jeder Nichtbaumkante zusammen mit diesem Rand, einen Zyklus bildet , die Länge zumindest müssen g , so dass die Der Mindestgrad im Baumgraphen muss mindestens ( g - 1 ) ( m - n + 1 ) betragen . 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.GgTg(g1)(mn+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 m Kanten? nm
Corwin