Aşağıdaki gibi bir ikili ağacı göz önüne alalım. Bu örnek üzerinden giderek köşeleri koordinatlayacağız. Sonra da uzaklık fonksiyonunu tanımlayacağız.
Ağacın başlangıç noktası olan $A$ köşesini $0$ olarak koodinatlayalım. Diğer noktaları ise, $A$ ya göre ya sağ tarafta ya da sol tarafta kalacak biçimde $L$ (left), $R$ (right) harfleriyle kodlayacağız. Örneğin $H$ noktası için üç kez sola gidildiği için $H = \text{0LLL}$ dizesini kullanacağız. $E$ noktası için önce sola sonra sağa gidildiği için $E = \text{0LR}$ dizesini kullanacağız. İlk bileşen hep $0$ (sıfır) olacak. Benzer şekilde $J=\text{0RLL}$ ve $N = \text{0RRLL}$ olur.
Tüm koordinatlarının listesi verilmiş bir ikili ağaç belirlenmiş bir ağaçtır. Bu tür bir listenin bize sunulmuş olduğunu varsayalım, artık çizgenin resmine ihtiyacımız kalmayacaktır. (Eğer istersek, koordinatlar listesine bakarak çizgenin resmini de tekrar yapabiliriz.)
Küçük çizgelerde iki nokta arası mesafeyi, ayrıtları kullanarak sayabiliyoruz. Şekilde $H$ ile $E$ arasındaki mesafe $3$ tür. Eğer kooddinatlar listesi verilmişse, iki nokta arasındaki mesafeyi Python kodu kullanarak yazabiliriz:
def d(x,y):
n = min(len(x),len(y)) # x ve y dizelerinden uzunluğu min olanın uzunluğu.
noet = 0 # number of equal terms. Eşit olan ilk k terimin sayısıdır. k+1-inci terimler farklıdır.
for i in range(0,n):
if x[i]==y[i]:
noet = noet + 1
else:
break
return len(x) + len(y) - 2*noet
# Bu kodu H ve N noktaları arasındaki mesafeyi kullanmak için çalıştıralım.
H = "0LLR"
N = "0RRLL"
d(H,N)
# Çıktımız 7 olacaktır. Yani H ve N noktalarını birbirine bağlayan 7 kenar vardır.
Bu şekilde tanımladığımız $d(x,y)$ uzaklık fonksiyonunda; $\text{len}(x)$, $x$ noktasının $A$ başlangıcına uzaklığının $1$ fazlası veya eşdeğer olarak $x$ in dize uzunluğu, $m = \text{$x$ ve $y$ dizelerindeki eşit olan ilk $k$ terimin sayısı} $ olmak üzere
$\text{M1.}$ $ d(x,y) = \text{len}(x) + \text{len}(y) - 2\cdot m = (\text{len}(x) - m) + (\text{len}(y) - m) \geq 0 $.
$\text{M2.}$ $ d(x,y) =0 \iff \text{len}(x) - m = \text{len}(y) - m = 0$ olmalıdır. Bu ise $x$ ve $y$ dizelerinin aynı indisli tüm terimlerinin birbiriyle çakışması demektir. Yani $x=y$.
$\text{M3.}$ $d$ fonksiyonunun tanımından dolayı $x$ ile $y$ nin konumlarının değiştirilebilir olduğunu görüyoruz. Dolayısıyla simetri özelliği vardır ve $d(x,y) = d(y,x)$ tir.
$\text{M4.}$ $ d(x,y) = (\text{len}(x) - m_1) + (\text{len}(y) - m_1) $ dir. $x$ ve $y$ nin ilk $m_1$ terimi çakışıyor, $x$ ve $z$ nin ilk $m_2$ terimi çakışıyor, $z$ ve $y$ nin ilk $m_3$ terimi çakışıyor, olsun.
$ d(x,z) + d(x,z) = (\text{len}(x) - m_2) + (\text{len}(z) - m_2) + (\text{len}(z) - m_3) + (\text{len}(y) - m_3)$
olur.
$ d(x,z) + d(x,z) \geq d(x,y)$ olduğunu kanıtlamak gerekiyor. Örnekler bunu destekliyor ve eşitsizlik sanki açık gibi görünüyor ama bu kısmın cebirsel ispatını tamamlamadım.
$\text{M4.}$ de doğru ise, (doğru olmasını bekliyorum) $d(x,y)$ fonksiyonu bir metrik oluşturur. Son kısmı beraberce biraz daha kurcalayabiliriz...
$\text{Ek Çabalar:}$ Ağaç yapısını kullanırsak önceki paragrafta bahsettiğim "açık gibi" olan kısım "açık" hale dönüşüyor. $d(x,y)$ ile $x$ ile $y$ arasındaki yolun uzunluğunu (kenarların sayısını) buluyoruz. Ağaç çizge ile çalıştığımız için bu tür bir yol tek türlü belirlidir. Farklı bir yolla daha ulaşım mümkün olsaydı, döngü oluşurdu. Ağaç çizgede ise döngü yoktur. $x$ i $y$ ye bağlayan yol bir alt ağaçtır ve mümkün olan en kısa yoldur. $d(x,z) + d(z,y)$ ile önce $x$ ten $z$ ye gidiyoruz ve sonra da $z$ den $y$ ye geçiyoruz. Yine $x$ ten $y$ ye bir rota çizildiği için bu bir yürüyüş (walk) olur. Yürüyüş içinde tekrar geçilen noktalar olabilir. Böylece $d(x,y) \leq d(x,z) + d(z,y)$ üçgen eşitsizliği de sağlanır. $d(x,y)$, ikili ağaç üzerinde bir metriktir.
Muhtemelen ağaç özellikleri kullanılarak $\text{M1, M2, M3}$ şartları daha kolayca açıklanabilir. Çözümü uzatmış olabilirim.