Combien d'arêtes un graphe unipathique peut-il avoir?

19

Un graphe unipathique est un graphe orienté tel qu'il existe au plus un chemin simple d'un sommet à un autre sommet.

Les graphiques unipathiques peuvent avoir des cycles. Par exemple, une liste doublement chaînée (pas circulaire!) Est un graphe unipathique; si la liste contient n éléments, le graphique a n1 cycles de longueur 2, pour un total de 2(n1) .

Quel est le nombre maximum d'arêtes dans un graphe unipathique à n sommets? Une borne asymptotique ferait l'affaire (par exemple O(n) ou Θ(n2) ).

Inspiré par Trouver les chemins les plus courts dans un graphique unipathique pesé ; dans ma preuve , j'ai d'abord voulu affirmer que le nombre d'arêtes était mais j'ai ensuite réalisé que limiter le nombre de cycles était suffisant.O(n)

Gilles 'SO- arrête d'être méchant'
la source
Bonne question. Nous devons essayer d'améliorer votre limite inférieure ou ma limite supérieure :).
RB

Réponses:

12

Un graphique unipathic peut avoir des bords. Il y a une sorte bien connu du graphique qui est unipathic et a n 2 / 4 arêtes.Θ(n2)n2/4

Considérons un graphe bipartite complet, avec des arêtes orientées . Ce graphe est unipathique et n'a pas de cycle: tous ses chemins ont une longueur 1 . Il a 2 m de sommets et m 2 d' arêtes.(i,j)[1,m]2,aibj12mm2

(Question de suivi: ce rapport est-il maximal? Probablement pas, mais je n'ai pas d'autre exemple. Cet exemple est maximal dans le sens où n'importe quelle arête que vous ajoutez entre des nœuds existants rompra la propriété unipathique.)

Gilles 'SO- arrête d'être méchant'
la source
"tout bord que vous ajoutez entre des nœuds existants rompra la propriété unipathique" Comment l'ajout du bord romprait-il la propriété? b1a1
mitchus
@mitchus a2b1a1b2
Gilles 'SO- arrête d'être méchant'
1
Je suppose que mon esprit était en quelque sorte unipathique ce jour-là :) En ce qui concerne la maximalité, le rapport peut aller à 1/4 pour les grands , mais pour n { 2 , 3 , 4 , 5 , 6 } la liste doublement liée a plus de bords que n 2 / quatre . nn{2,3,4,5,6}n2/4
mitchus
0

Je ne sais pas s'il y a un graphique unipathique sur plus de bords, mais voici un argument montrant que pas plus den2n24arêtes sont possibles:n22+3

Supposons par contradiction que est un graphe unipathique tel que | E | n 2G=(V,E).|E|n22+3

Par le principe du pigeonnier, il existe tel que d dans ( v ) nvV

din(v)n2+1

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

Notez que s'il y avait un sommet tel que u 1u 2U : ( x , u 1 ) , ( x , u 2 ) ExV{v}

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

Alors le graphe ne serait pas unipathique (car et ( x u 2v ) sont tous les deux des chemins valides).(xu1v)(xu2v)

{v}×U

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

U

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

R B
la source