Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas contoh pengurutan total yang kompatibel dalam topological sorting menggunakan relasi. Dengan contoh poset dan proyek pekerjaan, penjelasan diberikan mengenai pemilihan elemen minimal untuk mencapai pengurutan yang tepat. Melalui proses eliminasi dan pemilihan urutan yang bijak, tercipta pengurutan total yang sesuai dengan aturan relasi yang ada. Konsep topological sorting dapat diterapkan dalam berbagai situasi, seperti penjadwalan proyek berjenjang untuk memastikan kelancaran dan keteraturan pelaksanaan tugas.

Sekarang kita lihat contohnya, kita punya poset seperti di gambar yang pertama ini,

kemudian kita diminta untuk mencari pengurutan total yang sesuai atau kompatibel dari poset yang ini,

1, 2, 4, 5, 12, 20 dengan relasi pembagian.

Sekarang kita lihat untuk mencari elemen minimalnya,

elemen minimal yang pertama dari semuanya ini kan adalah 1,

jadi kita masukkan 1 di sini, terus 1 ini kita buang,

jadi ini hilangkan, kita akan dapat diagram yang kedua.

Diagram yang kedua, di sini kita lihat elemen minimalnya itu siapa,

di sini kita ambil yang 5, ambil 2 boleh tidak? Boleh,

jadi kita lihat bahwa di sini tidak tunggal, tapi ini misalkan kita ambil 5,

habis itu kita lihat lagi kalau si 1 sama 5 ini kita keluarkan,

terus kita lihat di sini mana yang minimal, yaitu 2 kita taruh di tempat yang elemen minimal,

kemudian kita buang, dapat diagram yang berikutnya,

kita dapat elemen minimalnya 4, kita dapat diagram berikutnya,

jadi ini kamu boleh pilih mau 12 atau 20,

kalau dipilih 20 nanti yang 12 yang terakhir,

sehingga nanti kita punya pengurutan total 1 itu lebih kecil dari 5,

lebih kecil 2, lebih kecil 4, lebih kecil 20, lebih kecil 12.

Kalau pada saat pemilihannya tadi, tadi kan ada pilihan antara 2 sama 5,

maka nanti urutannya akan jadi 1 lebih kecil 2, lebih kecil 5,

lebih kecil 4, lebih kecil 20, lebih kecil 12.

Jadi ini ada beberapa cara pengurutan dari sorting ini,

di mana suatu pekerjaan itu harus bisa diselesaikan dulu

sebelum pekerjaan yang berikutnya bisa dilakukan.

Misalnya si proyek-proyek itu diberi nama A, B, C, D, E, F, G,

kemudian di sini sudah dibuat diagramnya,

kalau pekerjaan A harus selesai sebelum pekerjaan B mulai.

terus kita bisa membuat urutan tugas yang bisa kita laksanakan.

A-nya dibuang, kita dapat diagram yang kedua,

Enggak boleh, karena C harus dikerjakan dulu, baru B.

kamu boleh pilih A, boleh pilih C, boleh pilih E.

B-nya dikeluarkan, keluar diagram berikutnya,

sebetulnya kita boleh memilih antara D atau E.

F-nya nanti enggak bisa jalan yang berikutnya,

karena F itu kan tadi dikerjakan setelah B selesai sama E selesai.