Mam takie zadanie:
Drzewo G jest jednoznacznie wyznaczone przez zbiór odległości między liśćmi.
Zastanawia mnie czy mój tok rozumowania jest poprawny.
Rozpatruje przypadek gdy w drzewie są trzy liście, oznaczmy je przez \(\displaystyle{ v_{1}, v_{2}, v_{3}}\). Mamy dane odległości między tymi liśćmi,
\(\displaystyle{ \begin{tabular}{ccc}
a=dist(v_{1},v_{2})\\
b=dist(v_{1},v_{3}) \\
c=dist(v_{2},v_{3})\\
\end{tabular}}\), gdzie \(\displaystyle{ a,b,c>2}\)
Droga \(\displaystyle{ v_{1}-v_{2}}\) oraz droga \(\displaystyle{ v_{2}-v_{3}}\) mają wspólny wierzchołek różny od \(\displaystyle{ v_{1},v_{2},v_{3}}\). Oznaczmy go \(\displaystyle{ v}\). Wprowadźmy oznaczenia: \(\displaystyle{ \begin{tabular}{ccc}
\alpha_{1}=dist(v_{1},v)\\
\alpha_{2}=dist(v_{2},v) \\
\alpha_{3}=dist(v_{3},v)\\
\end{tabular}}\)
Interesuje nasz teraz czy drzewo to jest jednoznacznie wyznaczone, czyli czy odległości \(\displaystyle{ \alpha_{1},\alpha_{2},\alpha_{3}}\) są jednoznacznie wyznaczone. Zauważmy, że
\(\displaystyle{ \begin{tabular}{ccc}
a=\alpha_{1}+\alpha_{2}\\
b=\alpha_{1}+\alpha_{3} \\
c=\alpha_{2}+\alpha_{3}\\
\end{tabular}}\)
Zastanówmy się nad ilością rozwiązań układu równań o macierzy układu:
\(\displaystyle{ \begin{bmatrix} 1&1&0&a\\1&0&1&b\\0&1&1&c\end{bmatrix}}\)
Układ ten ma zawsze dokładnie jedno rozwiązanie, które ma w naszym przypadku sens wtedy i tylko wtedy, gdy
\(\displaystyle{ \begin{array}{l}
a+b<c\\
a+c<b \\
b+c<a\\
(a+b+c)mod2=0
\end{array}}\)
Mamy więc udowodnione, że każde trzy wierzchołki z danymi odległościami są wyznaczone jednoznacznie.
Mając więc dane \(\displaystyle{ n}\) liści oraz wszystkie odległości między nimi wybierając dowolną trójkę liści
możemy wyznaczyć je jednoznacznie, następnie dobieramy jeden liść i rozpatrujemy jego położenie względem dwóch dowolnych liści już wybranych. W ten sposób utworzymy dokładnie jedno drzewio.
Proszę o wasze uwagi i o dokładne wytknięcie wszystkich błędów.
