Perpustakaan Digital ITB

Misalkan D adalah digraf berorder n dengan himpunan terurut W = fw1;w2; :::;wkg V (D): Misalkan v adalah titik di D: Representasi v terhadap W adalah k-vektor r(vjW) = (d(v;w1); d(v;w2); :::; d(v;wk)), dimana d(x; y) menotasikan jarak (berarah) dari x ke y; yaitu panjang lintasan berarah terpendek dari x ke y di D: Jika setiap titik memiliki representasi dan setiap dua titik berbeda di D memiliki representasi yang berbeda maka himpunan W disebut himpunan pembeda di D: Kardinalitas minimum dari himpunan pembeda di D disebut dimensi metrik dari D; dinotasikan dengan dim(D): Dalam tesis ini dibahas mengenai syarat cukup bagi digraf berdimensi 2 dan dimensi metrik dari digraf bipartit lengkap.