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

Video ini membahas tentang pengurutan topologis dalam Matematika Diskrit, terutama pada bab Relasi. Konsep penyortiran topologis digunakan untuk mengurutkan total dari urutan parsial dengan memperhatikan hubungan setiap elemen. Proses ini berdasarkan pada lema yang menyatakan bahwa setiap poset berhingga dan tidak kosong akan memiliki setidaknya satu elemen minimal. Dengan mengikuti algoritma yang dijelaskan, kita dapat melakukan topological sorting untuk mendapatkan urutan total yang kompatibel dari himpunan elemen-elemen minimal.

Konsep berikutnya adalah, tadi kan diagramnya sudah dibuat,

sekarang kalau kita mau melakukan pengurutan total dari urutan parsial CR tadi,

itu kita sebut pengurutannya atau penyortirannya,

itu kita sebut sebagai penyortiran topologis atau bahasa Inggrisnya topological sorting.

Jadi bagaimana dapatnya, sebelumnya kita bahas dulu lemanya,

lemanya itu mengatakan bahwa setiap poset yang berhingga dan tidak kosong tentu,

jadi S lebih kecil sama dengan, itu mempunyai paling sedikit satu elemen minimal,

ingat ya elemen minimal itu kadang tidak tunggal,

jadi caranya melihat bagaimana kita ambil elemen A0 dari sehimpunan tersebut si S nya,

nanti kita akan mendapatkan elemen A1 di mana A1 nya lebih kecil dari A0,

kalau A0 nya itu elemen minimal berarti sudah berhenti buktinya,

tapi karena A0 nya bukan elemen minimal berarti ada yang lebih kecil lagi yaitu A1.

Kita lihat lagi kalau A1 juga bukan elemen minimal nanti ada A2,

ini prosesnya jalan terus sampai kita punya,

kalau A n nya bukan elemen minimal akan terdapat A n plus 1 di mana A n plus 1 nya itu lebih kecil dari A n.

Karena banyaknya elemen di dalam poset ini berhingga tadi,

jadi proses ini akan berhenti di satu saat,

jadi misalnya berhenti akan di A n di mana A n nya itu akan menjadi elemen minimal.

Ini untuk penyortiran topologis ini berlaku untuk sembarang poset berhingga yang tidak kosong dari lemanya.

Kalau misalnya kita bikin pengurutan total yang pertama dipilih elemen minimalnya A1,

ini pasti ada karena lema tadi menjamin bahwa akan ada elemen minimalnya.

Kemudian kita lihat apa namanya himpunan nya,

jadi kita punya A dikurang himpunan A1 relasinya sama lebih kecil sama dengan,

kita bisa mengulangi lagi tadi mengambil elemen minimal A2 nya,

Terus habis itu kita kurangi lagi si A1 A2 nya dari A,

Terus itu sampai kita mendapatkan AK plus 1 sebagai elemen minimal,

dari A dikurang himpunan A1 A2 sampai AK.

maka proses ini pasti akan berakhir di N tertentu atau K tertentu.

Sehingga nanti kita akan dapat barisan elemen-elemen minimal yang sudah kita peroleh tadi,

Jadi kita lihat di sini algoritmanya untuk melakukan topological sorting.