Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
1 beğenilme 0 beğenilmeme
534 kez görüntülendi
Ikili agactan (binary tree) kastim  yapraklar disinda  kosenin iki tane cocugu olmasi.

Mesafeden kastim iki tane yaprak arasindaki yolda kac kenar oldugu.

Bu mesafenin bir formulu var midir?

Yukaridaki mesafe agacin yapraklari kumesi ile birlikte metrik uzay aksiyomlarini saglar mi?

Soruyu ikili agaclar icin sordum ama genel $n$-agac yada genel agac cizgeler icin de genisletilebilir
Lisans Matematik kategorisinde (1.6k puan) tarafından  | 534 kez görüntülendi

Problemi belirginleştirmek için soruyorum: Wkipedia'da ifade edilen iki tanım var.

Bilgisayar biliminde, ikili ağaç (binary tree), her düğümün sol çocuk ve sağ çocuk olarak adlandırılan en fazla iki çocuğa sahip olduğu bir ağaç veri yapısıdır. Şöyle olabilir:

 

Matematikte ikili ağaç olarak adlandırılan şey yazardan yazara önemli ölçüde değişebilir. Bazıları bilgisayar bilimlerinde yaygın olarak kullanılan tanımı kullanır, ancak diğerleri bunu her yaprak olmayanın tam olarak iki çocuğa sahip olması olarak tanımlar ve çocukları da mutlaka (sol/sağ olarak) sıralamaz.

Biz, ikinci tanımı kullanacağız diye anlıyorum. Yani, yaprak olmayan köşenin tam olarak iki çocuğa sahip olması durumunu alacağız. Şunun gibi:

 

Ikinci tanimi kullanmak vardi benim kafamda. Soruyu bir derece daha kolay yapmak icin agacin son seviyesinin tam ($2^n$ tane yaprak var) oldugunu da varsayabiliriz.

1 cevap

1 beğenilme 0 beğenilmeme
En İyi Cevap

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.

 

 

(2.6k puan) tarafından 
tarafından seçilmiş
Koseler yerine kenarlara isim verdim ben, "LR" yerine "01" tercih ettim.

Bu gosterimle tam bir ikili agactaki mesafeleri iki bit zincirini $XOR$ layip sonucun $0$ dan farkli ilk basamagi

olarak ifade edebiliyoruz

ucgen esitsizligi icin sanirim sunu gostersek olur

$a$ kosesi, $x$ ve $y$ koselerinin ortak atasi, $k$ ise kok olsun.

O zaman

$d(x,y) = d(k,x) + d(k,y) - 2d(k,a)$

(sanirim bu ifade herhangi bir $k$ icin gecerli)
@lokman.gokce yaniliyorsam duzeltin ama sanirim ispatiniz butun agaclar icin dogru degil mi ? Hatta Sanirim yapraklarla sinirlamamiza gerek yok kendimizi genel olarak her agac icindeki her kose icin dogru ?
Merhaba @eloi Biraz daha zorlu görünen $M4.$'ün kanıtını sonlu ağaç için yaptım. Burada ağacın ikili ağaç olduğunu kullanmadım. $M1, M2, M3$ üzerinde çalışırken ikili ağaç bilgisini kullanarak bir koordinatlandırma yaptım. Tabii $M1, M2, M3$ özelliklerinin kanıtları genelde kolay olduğu için genel bir sonlu ağaç üzerinde de bunların sağlandığını söyleyebiliriz. Sonuç olarak, sonlu ağaçtaki iki nokta arası uzaklığı "bunları bağlayan yolun kenar sayısı" olarak tanımlarsak bu uzaklık fonksiyonu $4$ metrik aksiyomunu sağlar.

Sayilabilir sonsuz agaclar kanitinizin gecerli oldugunu dusunuyorum.  Su soru uzaktan alakali gibi

20,282 soru
21,820 cevap
73,505 yorum
2,542,101 kullanıcı