Dimostrazione di un'emimetrica
Salve ragazzi, chiedo il vostro aiuto, non riesco a dimostrare la proprietà di triangolarità di una funzione da me definita, che mi farebbe dire che essa è un'emimetrica. Di seguito la sua definizione:
Dato un albero, dati $a$, $b$ due nodi dell'albero, dato $c$ il nodo genitore comune ai due nodi $a$ e $b$, definisco la funzione $e$ applicata ai nodi $a$ e $b$ come la distanza (il numero di spigoli) tra il nodo $a$ e il nodo $c$.
$ e(a,b) = d(a,c) $
Per essere più chiaro di seguito un'immagine che mostra la funzione $e$ applicata tra il nodo $G$ e tutti gli altri.
Grazie anticipatamente!
Dato un albero, dati $a$, $b$ due nodi dell'albero, dato $c$ il nodo genitore comune ai due nodi $a$ e $b$, definisco la funzione $e$ applicata ai nodi $a$ e $b$ come la distanza (il numero di spigoli) tra il nodo $a$ e il nodo $c$.
$ e(a,b) = d(a,c) $
Per essere più chiaro di seguito un'immagine che mostra la funzione $e$ applicata tra il nodo $G$ e tutti gli altri.
Grazie anticipatamente!
Risposte
La triangolarità è la verifica della disuguaglianza triangolare su \(d\)?
si, ma su $e$
Vi propongo la seguente dimostrazione (ma non mi fiderei troppo...)
Per ogni nodo \(x\) indico con \(\lambda_x\) la distanza di \(x\) dal nodo terminale, i.e. \(\lambda_x\) è la lunghezza del cammino \(\Gamma(x)\) che collega \(x\) con "root". Inoltre, per ogni coppia di nodi \(x\) e \(y\) indico con \(\lambda_{xy}\) la lunghezza del cammino \(\Gamma(x) \cap \Gamma(y)\): in altre parole, se \(z\) è il "nodo genitore" di \(x\) e \(y\), allora \(\lambda_{xy}\) è la lunghezza del cammino \(\Gamma(z)\) che collega \(z\) con "root".
Adesso, comunque scelti tre nodi \(a\), \(b\) e \(c\), dovrebbe essere vero che
\[
\lambda_{ab} + \lambda_{bc} \leq \lambda_b + \lambda_{ac} \qquad \qquad (\ast)
\]
da cui si ricava
\[
\lambda_a - \lambda_{ac} \leq \lambda_a - \lambda_{ab} + \lambda_b - \lambda_{bc}
\]
La disuguaglianza triangolare di \(\,\varepsilon\) segue osservando che \(\,\varepsilon(x,y) = \lambda_x - \lambda_{xy}\).
Dimostrazione di \((\ast)\). Sia \(z\) il nodo genitore di \(a\) e \(b\) e sia \(w\) il nodo genitore di \(b\) e \(c\). Se \(z \leq w\), allora \(w\) è anche il nodo genitore di \(a\) e \(c\), quindi \(\lambda_{ac} = \lambda_{bc}\). Se invece \(w \leq z\), allora \(\lambda_{ac} = \lambda_{ab}\). Segue la \((\ast)\) poiché, per definizione, abbiamo \(\lambda_{ab} \leq \lambda_b\) e \(\lambda_{bc} \leq \lambda_b\).
Per ogni nodo \(x\) indico con \(\lambda_x\) la distanza di \(x\) dal nodo terminale, i.e. \(\lambda_x\) è la lunghezza del cammino \(\Gamma(x)\) che collega \(x\) con "root". Inoltre, per ogni coppia di nodi \(x\) e \(y\) indico con \(\lambda_{xy}\) la lunghezza del cammino \(\Gamma(x) \cap \Gamma(y)\): in altre parole, se \(z\) è il "nodo genitore" di \(x\) e \(y\), allora \(\lambda_{xy}\) è la lunghezza del cammino \(\Gamma(z)\) che collega \(z\) con "root".
Adesso, comunque scelti tre nodi \(a\), \(b\) e \(c\), dovrebbe essere vero che
\[
\lambda_{ab} + \lambda_{bc} \leq \lambda_b + \lambda_{ac} \qquad \qquad (\ast)
\]
da cui si ricava
\[
\lambda_a - \lambda_{ac} \leq \lambda_a - \lambda_{ab} + \lambda_b - \lambda_{bc}
\]
La disuguaglianza triangolare di \(\,\varepsilon\) segue osservando che \(\,\varepsilon(x,y) = \lambda_x - \lambda_{xy}\).
Dimostrazione di \((\ast)\). Sia \(z\) il nodo genitore di \(a\) e \(b\) e sia \(w\) il nodo genitore di \(b\) e \(c\). Se \(z \leq w\), allora \(w\) è anche il nodo genitore di \(a\) e \(c\), quindi \(\lambda_{ac} = \lambda_{bc}\). Se invece \(w \leq z\), allora \(\lambda_{ac} = \lambda_{ab}\). Segue la \((\ast)\) poiché, per definizione, abbiamo \(\lambda_{ab} \leq \lambda_b\) e \(\lambda_{bc} \leq \lambda_b\).
In questo caso la dimostrazione fallisce, anche se la disuguaglianza (∗) continua a valere.
Ok. Direi allora che la dimostrazione (per come l'ho scritta) funziona solo se \(w\) e \(z\) sono distinti, poiché, in tal caso, segue almeno una tra la due uguaglianze \(\lambda_{ac} = \lambda_{bc}\) e \(\lambda_{ac} = \lambda_{ab}\).
Se \(w = z\), dovrebbero essere valide addirittura entrambe le disuguaglianze \(\lambda_{bc} \leq \lambda_{ac}\) e \(\lambda_{ab} \leq \lambda_{ac}\), e quindi abbiamo la disuguaglianza più forte
\[
\lambda_{ab} + \lambda_{bc} \leq \frac{1}{2} (\lambda_b + \lambda_{ac})
\]
Se \(w = z\), dovrebbero essere valide addirittura entrambe le disuguaglianze \(\lambda_{bc} \leq \lambda_{ac}\) e \(\lambda_{ab} \leq \lambda_{ac}\), e quindi abbiamo la disuguaglianza più forte
\[
\lambda_{ab} + \lambda_{bc} \leq \frac{1}{2} (\lambda_b + \lambda_{ac})
\]
Come hai trovato quest'ultima disuguaglianza?
L' 1/2 non c'è, semplicemente continua a valere la \((\ast)\). Scusa, oggi ho scritto un po' di fretta.
Sembra avere senso. Grazie! 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo