26
Setiap DAG berhubungan dengan order parsial pada verteknya, dimana u <= v
dalam order parsial tepat pada saat dimana ada directed path dari
u
ke
v
pada graph.
Tapi,
banyak
DAG
yang
berbeda
merepresentasikan order
parsial
yang
sama.
Pada
graph-graph
tersebut, graph
yang
jumlah
edgenya paling
sedikit
adalah
pengurangan transitif dan
graph
yang jumlah edgenya paling banyak adalah closure
transitif.
DAG
yang
isinya
berupa
huruf
dapat
kita
sebut
Directed
Acyclic
Word
Graph (DAWG).
R
Words:
A
CAR
C
T
CARS
S
CAT
CATS
E
DO
DOG
G
DOGS
DONE
D
EAR
EARS
EAT
EATS
O
N
Gambar 2.4 DAWG
2.7
Algoritma Sorting
Dalam
dunia
Teknolgi
Informatika
dan
Matematika, dikenal
suatu
metode
pengurutan yang
disebut
sorting.
Sorting
adalah
suatu
metode
mengurutkan
sederetan
bilangan
atau
karakter
secara
teratur.
Ada
2
jenis
urutan
dalam
sorting
yaitu
diurutkan
secara
ascending
atau
descending. Secara
Ascending
berarti
sederetan bilangan
atau
karakter
tersebut
diurutkan
dari
yang
kecil
terlebih
dahulu
hingga
yang paling besar. Sedangkan secara descending berarti diurutkan dari
yang
paling besar hingga yang paling kecil.
 |