Wie viele Kanten kann ein unipathischer Graph haben?

19

Ein unipathischer Graph ist ein gerichteter Graph, so dass es höchstens einen einfachen Pfad von einem Scheitelpunkt zu einem anderen Scheitelpunkt gibt.

Unipathische Graphen können Zyklen haben. Beispielsweise ist eine doppelt verknüpfte Liste (keine kreisförmige!) Ein unipathischer Graph. Wenn die Liste Elemente enthält, enthält der Graph Zyklen der Länge 2 für insgesamt .n - 1 2 ( n - 1 )nn12(n1)

Was ist die maximale Anzahl von Kanten in einem unipathischen Graphen mit Eckpunkten? Eine asymptotische Bindung würde ausreichen (zBnO(n) oderΘ(n2) ).

Inspiriert von Finden Sie kürzeste Wege in einem gewichteten unipathischen Diagramm . In meinem Beweis wollte ich zunächst behaupten, dass die Anzahl der Kanten , erkannte dann aber, dass die Begrenzung der Anzahl der Zyklen ausreichend war.O(n)

Gilles 'SO - hör auf böse zu sein'
quelle
Gute Frage. Wir sollten versuchen, entweder deine Untergrenze oder meine Obergrenze zu verbessern :).
RB

Antworten:

12

Ein unipathischer Graph kann Kanten haben. Es gibt eine bekannte Art von Graph, der unipathic ist und hat n 2 / 4 Kanten.Θ(n2)n2/4

Betrachten Sie einen vollständigen zweigliedrigen Graphen mit orientierten Kanten . Dieser Graph ist unipathisch und hat keinen Zyklus: Alle seine Pfade haben die Länge 1 . Es hat 2 m Eckpunkte und m 2 Kanten.(i,j)[1,m]2,aibj12mm2

(Folgefrage: Ist dieses Verhältnis maximal? Wahrscheinlich nicht, aber ich habe kein anderes Beispiel. Dieses Beispiel ist maximal in dem Sinne, dass jede Kante, die Sie zwischen vorhandenen Knoten hinzufügen, die unipathische Eigenschaft verletzt.)

Gilles 'SO - hör auf böse zu sein'
quelle
"Jede Kante, die Sie zwischen vorhandenen Knoten hinzufügen, wird die unipathische Eigenschaft brechen." Wie würde das Hinzufügen der Kante die Eigenschaft brechen? b1ein1
Mitchus
@mitchus a2b1a1b2
Gilles 'SO - hör auf, böse zu sein'
1
Ich denke, mein Verstand war an diesem Tag irgendwie unpathisch :) Was die Maximalität betrifft, kann das Verhältnis für großes auf 1/4 gehen , aber für n { 2 , 3 , 4 , 5 , 6 } hat die doppelt verknüpfte Liste mehr Kanten als n 2nn{2,3,4,5,6} . n2/4
Mitchus
0

Ich weiß nicht, ob es einen unipathischen Graphen für mehr als Kanten, aber hier ist ein Argument, das zeigt, dass nicht mehr alsn2n24Kanten sind möglich:n22+3

Nehmen wir im Widerspruch an, dass ein unipathischer Graph ist, so dass | E | n 2G=(V,E).|E|n22+3

Nach dem Pigeonhole-Prinzip gibt es so dass d in ( v ) n istvV

dim(v)n2+1

Bezeichne U={uV(u,v)E}

Beachten Sie, dass , wenn es ein Scheitelpunkt , so dass u 1u 2U : ( x , u 1 ) , ( xxV{v}

u1u2U:(x,u1),(x,u2)E

Dann wäre der Graph nicht unipathisch (als und ( x(xu1v) beide gültige Pfade sind).(xu2v)

Dies bedeutet (Hinzufügen der Kanten aus ): | E ( V × U ) |{v}×U

|E(V×U)|2|U|

U

|E|=|E(V×U)|+|E(V×(VU))|
2|U|+n|VU|2(n2+1)+n(n2-1)<n22+3

RB
quelle