Il modo più compatto per rappresentare un grafico [chiuso]

Question

Il modo più compatto per rappresentare un grafico [chiuso]

#1 da (3 voti)

1

Dati questi nodi:

a
b
c
d
e
f
g
h

E dato alcuni bordi tra i nodi come questo:

a/b/c
b/c/d
c/e
c/d/e/f
c/g
f/g
e/f/g
a/c/h
h/a/b
c/a
d/b/c
f/g/c
d/a/f
g/f
g/a/b/c
f/a/b
e/a/c

(dove a / b / c significa un bordo da a a b, e un altro da b a c), quindi questo descrive un grafico diretto.

Ecco un'altra rappresentazione più compatta per lo stesso grafico:

a(b(c(d, e(f), g)))
f(g)
e(f(g), a(c))

...

utilizzando una rappresentazione ad albero. Ma ci sono ancora dei duplicati (ad esempio a e c sono mostrati due volte nell'ultimo snippet).

Un altro modo per rappresentarlo è come questo:

a:b
a:c
b:c
c:d
c:e

Ma questo usa ancora più lettere rispetto allo snippet originale (primo).

Ti stai chiedendo se c'è qualcosa di meglio di questi 3 approcci per rappresentare un grafico diretto.

Forse c'è un modo per assegnare numeri alle lettere e fare tutti e 3 gli approcci come uno. O forse qualcos'altro.

Quindi quale potrebbe essere una rappresentazione utilizzando la più piccola quantità di byte?

optimization graph

posta Lance Pollard 29.06.2018 - 18:21

fonte

1 risposta

Leggi altre domande sui tag optimization graph

L'JPA ha sostituito CMP? Brainstorming domande per suscitare caratteristiche nella nuova versione del software? [chiuso]

score 3 · Accepted Answer

Qualsiasi grafico diretto con i vertici V={v_1, ..., v_n} può essere identificato con un sottoinsieme di

 S = V x V \ {(a,a) | a in V}

dove V x V indica il prodotto cartesiano e ciascuno di questi sottoinsiemi rappresenta un grafico diverso. Quindi questo significa che ci sono 2 ^ (n * (n-1)) grafici diversi su V. Quindi, una rappresentazione uniforme dove ogni grafico prende la stessa dimensione di memoria richiede necessariamente n * (n-1) bit per grafico. Meno non è possibile a causa del principio del foro dei piccioni.

Naturalmente, si può trovare una rappresentazione in cui alcuni grafici su V hanno bisogno di molto meno di n * (n-1) bit, ma poi altri ne avranno bisogno di più. Ma senza alcuna conoscenza su quali grafici devono essere elaborati o memorizzati nel contesto di un caso d'uso specifico, o vincoli aggiuntivi (come un numero limitato di spigoli), non si può decidere quale di queste rappresentazioni avrà bisogno di meno o più byte di un altro. / p>

Ad esempio, si possono sviluppare rappresentazioni in cui i grafici con un numero minore di bordi occupano meno spazio rispetto ai grafici con un numero più alto. Per un'analisi più approfondita, puoi trovare questa tesi sulle rappresentazioni dei grafici utili ed efficienti.