4. digraphelearning.amikompurwokerto.ac.id/index.php/download/... · isomorfisma sesuai dengan...
TRANSCRIPT
1
4. Digraph Oleh : Ade Nurhopipah
Pokok Bahasan :
1. Digraph dan Subdigraph
2. Derajat Titik Pada Digraph
3. Path dan Cycle Pada Digraph
4. Digraph Euler dan Digraph Hamilton
Sumber :
Aldous, Joan M. ,Wilson, Robin J. 2004. Graph and Applications. Springer: UK.
Digraph dan Subdigraph
Definisi 4.1 Sebuah digraph terdiri dari dari sebuah himpunan elemen yang disebut vertex, dan sebuah himpunan elemen yang disebut arc. Setiap arc menghubungkan dua vertex.
Sebagai contoh digraph yang ditunjukan pada Gambar 4.1 memiliki empat vertex {u,v,w,x}
dan enam arc {1,2,3,4,5,6} . Arc 1 menghubungkan vertex x ke vertex u, arc 2 menghubungkan vertex
u ke vertex w, arc 3 dan 4 menghubungkan vertex w ke vertex v, arc 5 menghubungkan vertex x ke
vertex w, sedangkan arc 6 menghubungkan vertex x dengan dirinya sendiri.
Gambar 4.1 Contoh sebuah digraph
Kita sering menunjukan suatu arc dengan dua vertex yang ia hubungkan dengan ururan
sesuai arahnya. Misalnya arc 1 dinotasikan sebagai xu, dan arc 2 dinotasikan sebagai uw.
Definisi 4.2 Pada sebuah digraph, dua atau lebih arc yang menghubungkan pasangan vertex yang sama disebut multiple arc. Sebuah arc yang menghubungkan suatu vertex dengan dirinya sendiri disebut loop. Suatu digraph yang tidak memiliki multiple arc atau loop disebut digraph sederhana (simple digraph)
2
Digraph yang ditunjukan oleh Gambar 4.1, memiliki multiple arc yang menghubungkan v
dan w, juga terdapat loop pada titik x, sehingga digraph tersebut bukanlah digraph yang sederhana.
Latihan 4.1 1. Tuliskan vertex dan arc pada digraph berikut. Apakah digraph tersebut termasuk digraph
sederhana?
2. Gambar digraph yang memiliki vertex dan arc berikut. Apakah digraph tersebut termasuk digraph sederhana? a. Vertex = {u,v,w,x}, edge ={uv,vw,vx,wx} b. Vertex = {1,2,3,4,5,6,7,8}, edge ={12,22,23,34,35,67,68,78}
Ketetanggaan dan Insidensi
Definisi 4.3 Vertex v dan w pada suatu digraph adalah bertetangga jika mereka dihubungkan dengan sebuah arc e. Sebuah arc yang menghubungkan vertex v ke vertex w disebut arc yang insiden dari v dan insiden ke w. Vertex v insiden ke e dan vertex w insiden dari e.
Sebagai contoh pada Gambar 4.1, vertex u dan x bertetangga, vertex w insiden dari arc 2
dan arc 5 serta insiden ke arc 3 dan arc 4. Arc 6 insiden ke dan dari vertex x.
Latihan 4.2 Mana dari pernyataan ini yang sesuai dengan digraph berikut.
a. Vertec v dan w bertetangga b. Vertec v dan x bertetangga c. Vertex u insiden ke arc 2 d. Arc 5 insiden dari vertex v
3
Isomorfisma
Sesuai dengan definisi digraph, sebuah digraph ditentukan secara keseluruhan dengan
mengetahui vertex dan arc pada digraph tersebut. Sehingga, dua digraph adalah digraph yang sama
jika mereka memiliki vertex dan arc yang sama.
Definisi 4.4 Dua digraph C dan D adalah isomorfik jika D dapat diperoleh dengan memberikan label pada vertex C , jika terdapat korespondensi satu-satu antara vertex di D dengan vertex di C, sehingga jumlah arc yang menghubungkan pasangan vertec di C sama dengan jumlah arc yang menghubungkan pasangan vertec yang berkoresponden di D dalam hal jumlah maupun arahnya.
Gambar 4.2 Contoh dua digraph yang isomorfik
Misalnya pada Gambar 4.2 ditunjukan, dua digraph C dan D yang tidak sama, namun
isomorfik, karena kita bisa memberi label yang sama pada vertex digraph C untuk mendapatkan
digraph D, dengan korespondensi satu-satu berikut :
C↔D u↔2 v↔3 w↔4 x↔1
Semua arc pada C juga berkoresponden dengan arc di D, misalnya dua arc yang menghubungkan u
dan v berkoresponden dengan dua arc yang menghubungkan vertex 2 ke vertex 3 di D.
Latihan 4.3 1. Dengan melakukan pelabelan kembali terhadap vertex, tunjukan bahwa pasangan digraph
berikut adalah isomorfik.
4
2. Apakah kedua digraph berikut isomorfik? Jika iya, temukan korespondensi satu-satu yang sesuai antara vertex pada digraph pertama dan digraph kedua. Jika tidak, jelaskan mengapa tidak ada korespondesi satu-satu yang sesuai.
Kadang-kadang, kita tidak diharuskan atau tidak perlu untuk melabeli suatu digraph. Pada
kasus ini kita menghilangkan label tersebut dan mendapatkan suatu digraph yang disebut digraph
tidak berlabel. Sebagai contoh digraph tidak berlabel ditunjukan pada Gambar 4.3.
Gambar 4.3 Contoh digraph tidak berlabel
Digraph tidak berlabel pada Gambar 4.3 berkoresponden dengan tiga digraph isomorfik yang
ditunjukan oleh Gambar 4.4. Dua digraph tidak berlabel dapat dikatakan isomorfik, jika kedua
digraph tersebut dapat dilabeli pada vertex-nya sehingga keduanya menjadi digraph yang sama.
Gambar 4.4 Digraph isomorfik yang berkoresponden dengan digraph tidak berlabel
Latihan 4.4 Dengan memberi label yang sesuai, tunjukan bahwa digraph tidak berlebel ini adalah isomorfik.
5
Subdigraph dan Underlying Graph
Definisi 4.5 Suatu subdigraph dari digraph D adalah sebuah digraph di mana semua vertex-nya adalah vertex dari D dan semua arc-nya adalah arc dari D.
Sebagai contoh pada Gambar 4.5 menggambarkan sebuah digraph D dan tiga buah
subdigraph-nya.
Gambar 4.5. Contoh sebuah digraph dan subdigraph-nya
Latihan 4.5 Mana dari digraph berikut yang merupakan subdigraph dari digraph D.
Ide dari subdigraph juga dapat diperluas untuk konsep digraph tidak berlabel. Pada Gambar
4.6 ditunjukan digraph dan subdigraph dari digraph tidak berlabel C.
Gambar 4.6 Contoh digraph tidak berlabel dan subdigraph-nya
6
Latihan 4.6 Mana dari digraph berikut yang merupakan subgraph dari digraph tak berlabel C?
Perlu juga untuk kita memahami tentang konsep underlying graph dari sebuah digraph
sebagai berikut.
Definisi 4.6 Underlying graph dari digraph D adalah graph yang diperoleh dengan mengganti setiap arc pada digraph D dengan edge tak berarah.
Sebagai contoh pada Gambar 4.7 ditunjukan sebuah digraph dan underlying graph-nya.
Gambar 4.7 Digraph dan underlying graph-nya
Derajat Titik
Definisi 4.7 Dalam sebuah digraph, derajat keluar sebuah vertex adalah jumlah arc yang insiden dari vertex tersebut, dan derajat masuk sebuah vertex adalah jumlah arc yang insiden ke vertex tersebut. Setiap loop memberi kontribusi 1 pada derajat masuk dan 1 untuk derajat keluar.
Sebagai contoh tinjau Gambar 4.8 yang menunjukan sebuah digraph dengan enam vertex.
Gambar 4.8 Ilustrasi untuk derajat vertex sebuah digraph
7
Digraph pada Gambar 4.8 memiliki,
derajat masuk u = 1, derajat keluar u = 0,
derajat masuk x =0 derajat keluar x =0
derajat masuk v =3, derajat keluar v =1
derajat masuk y =2 derajat keluar y =6
derajat masuk w =2 derajat keluar w =1
derajat masuk z =2 derajat keluar z = 2
Kadang kita membutuhkan daftar derajat vertex pada suatu digraph dan menuliskannya
dengan barisan terurut naik. Jika terdapat dua vertex yang memiliki derajat sama, maka
pengulangan nilai tetap dituliskan. Contohnya digraph pada Gambar 4.8 memiliki barisan derajat
masuk (0,1, 2,2, 2,3) dan barisan derajat keluar (0,0, 1,1, 2,6)
Definisi 4.8 Barisan derajat masuk pada sebuah digraph D adalah barisan yang diperoleh dengan mendaftar derajat masuk vertex pada D dengan urutan naik, dengan pengulangan jika perlu. Barisan derajat keluar pada sebuah digraph D didefinisikan secara analog.
Latihan 4.7 1. Tulislah barisan derajat pada digraph berikut.
2. Tulislah jumlah arc, jumlah derajat masuk, dan jumlah derajat keluar semua vertex dalam
digraph pada bagian 1. Apa yang dapat kamu simpulkan?
Handshaking dilemma
Teorema 4.1 : Handshaking dilemma Pada setiap digraph, jumlah dari semua derajat keluar dan jumlah dari semua derajat masuk sebuah vertex sama dengan jumlah arc-nya.
Pada setiap digraph, setiap arc memiliki dua ujung, ia menyumbang tepat 1 untuk jumlah
derajat masuk, dan 1 untuk derajat keluar.
8
Latihan 4.8 Gunakan handshaking dilemma untuk membuktikan bahwa pada setiap digraph, jika vertex yang memiliki derajat keluar yang ganjil jumlahnya ganjil, maka jumlah vertex yang memiliki derajat masuk yang ganjil jumlahnya juga ganjil,
Path dan Cycle
Definisi 4.9 Suatu walk dengan panjang k dalam digraph adalah urutan k arc dengan bentuk uv,vw,wx,…,yz. Walk ini dinotasikan dengan uvwx…yz dan disebut sebagai walk antara u dan z. Suatu trail adalah walk dimana semua arcnya berbeda, namun vertecnya tidak harus berbeda. Suatu path adalah walk yang baik arc maupun vertex-nya harus berbeda.
Contohnya untuk digraph pada Gambar 4.9, vwxyvwyzu adalah walk dengan panjang 9 dari v
ke u yang memuat vertex v,w,y, dan z dua kali. Walk uvwyvz merupakan sebuah trail namun bukan
path, karena vertex v muncul dua kali, sedangkan walk vwxyz yang tidak memiliki vertex yang sama
adalah sebuah path.
Gambar 4.9 Ilustrasi untuk trail dan path sebuah digraph
Definisi 4.10 Suatu walk tertutup pada sebuah digraph adalah urutan arc dengan bentuk uv,vw,wx,…,yz.zu, yang berawal dan berakhir pada vertex yang sama. Suatu trail tertutup merupakan walk tertutup di mana semua arc-nya berbeda. Sebuah cycle adalah walk tertutup di mana semua arc dan semua vertex diantaranya berbeda. Sebuah walk atau trail adalah terbuka jika ia berawal dan berakhir di vertex yang berbeda.
Pada digraph dalam Gambar 4.9, walk tertutup uvwyvzu adalah trail tertutup yang bukan
merupakan cycle, sedangkan trail tertutup zz, wxw, vwxyv dan uvwxyzu semuanya merupakan cycle.
Dalam menjelaskan walk tertutup, kita memperbolehkan vertex manapun menjadi titik awal.
Contohnya pada segitiga vwyv dapat ditulis sebagai wyvw atau yvwy.
9
Latihan 4.9 Untuk digraph berikut, tulislah : a. Semua path dari t ke w. b. Semua path dari w ke t. c. Sebuah trail tertutup dengan panjang 8 yang
memuat t dan z d. Semua cycle yang memuat t dan w.
Seperti pada graph, kita memakai konsep sebuah path untuk menjelaskan apakah sebuah
digraph terhubung atau tidak. Ingat kembali bahwa sebuah graph terhubung jika ia berada dalam
satu kesatuan yang berarti selalu ada sebuah path di antara setiap pasangan vertex. Untuk digraph,
terdapat dua istilah dengan definisi yang berbeda sebagai berikut.
Definisi 4.11 Sebuah digraph disebut digraph terhubung jika underlying graph-nya adalah sebuah graph terhubung. Sebuah graph terhubung kuat jika ada sebuah path yang menghubungkan setiap pasangan vertex pada graph tersebut.
Terdapat tiga tipe digraph yang ditunjukan pada Gambar 4.10. Digraph (a) tidak terhubung,
karena underlying graph-nya adalah graph yang tidak terhubung. Digraph (b) adalah digraph
terhubung namun tidak terhubung kuat. Hal ini karena tidak semua pasangan vertex dihubungkan
oleh sebuah path, misalnya vertex z dan vertex y. Digraph (c) adalah digraph yang terhubung kuat,
karena terdapat path yang menghubungkan setiap pasang vertex.
Gambar 4.10 Ilustrasi untuk digraph terhubung
10
Latihan 4.10 Klasifikasikan setiap digraph berikut menjadi digraph tidak terhubung, terhubung, atau terhubung kuat.
Digraph Euler dan Digraph Hamilton
Definisi 4.12 Sebuah digraph terhubung adalah digraph Euler juka ia memiliki sebuah trail tertutup yang memuat semua arc. Sebuah graph terhubung adalah digraph Hamilton jika ia memiliki sebuah cycle yang memuat semua vertex.
Sebagai contoh, perhatikan graph pada Gambar 4.11.
Graph (a) merupakan digraph Euler dan juga digraph Hamilton. Trail Euler yang mungkin adalah
a b c d e f b g c e g f a. Cycle Hamilton yang mungkin adalah : a b c d e g f a.
Graph (b) merupakan digraph Euler, namun bukan digraph Hamilton. Trail Euler yang mungkin
adalah : b c g f e g b
Graph (c) merupakan digraph Hamilton, namun bukan digraph Euler. Cycle Hamilton yang mungkin
adalah : b c d e g f b.
Graph (d) bukan merupakan digraph Euler maupun digraph Hamilton.
Gambar 4.11 Ilustrasi untuk digraph Euler dan digraph Hamilton
11
Latihan 4.11 1. Tentukan setiap digraph berikut apakah termasuk digraph Euler dan/atau graph Hamilton,
tulis trail Euler dan cycle Hamilton jika ada.
2. Tebaklah syarat cukup dan syarat perlu untuk sebuah digraph agar menjadi digraph Euler yang
melibatkan derajat masuk dan derajat keluar setiap vertex 3. Gunakan kondisi yang didapatkan pada bagian 2, untuk mengecek digraph pada bagian 1,
apakah termasuk digraph Euler atau bukan.
Teorema 4.2 Sebuah digraph terhubung adalah digraph Euler jika dan hanya jika pada setiap vertex, derajat keluarnya sama dengan derajat masuknya.
Teorema 4.3 Sebuah digraph Euler dapat dibagi menjadi beberapa cycle. Tidak ada dari cycle tersebut yang memiliki arc yang sama.
Studi Kasus
Ecology
Ketika mempelajari hubungan antar hewan, tumbuhan dan lingkungannya, ahli ekologi
biasanya menggunakan sebuah digraph yang dikenal sebagai rantai makanan seperti ditunjukan
pada Gambar 4.12. Pada digraph tersebut, vertex mewakili spesies yang sedang diteliti, dan arc dari
species A ke species B, menandakan bahwa A memakan B.
Gambar 4.12 Contoh sebuah rantai makanan
12
Untuk menjelaskan rantai makanan lebih lanjut, ahli ekologi memperkenalkan sebuah graph
yang menjelaskan spesies mana yang saling berkompetisi memperebutkan makanan. Graph seperti
ini disebut dengan graph kompetisi atau niche overlap graph. Pada graph ini, vertex mewakili setiap
spesies dan edge yang menghubungkan vertex menjelaskan bahwa kedua spesies tersebut memakan
mangsa yang sama. Gambar 4.13 menunjukan graph Kompetisi untuk digraph rantai makanan pada
Gambar 4.12. Representasi seperti ini berguna untuk menjelaskan bahwa spesies yang diwakili
dengan vertex yang bertetangga, cenderung memiliki reaksi yang sama terhadap faktor lingkungan
tertentu seperti suhu, kelembapan, ketinggian dan lain-lain.
Gambar 4.13 Contoh sebuah graph kompetisi pada bidang ekologi
Latihan 4.12 Gambarlah graph kompetisi dari rantai makanan berikut.
Jaringan Sosial
Pada jaringan sosial yang direpresentasikan oleh graph, kita mendapatkan suatu hubungan
social yang simetris, misalnya x menyukai y jika hanya jika y menyukai x. Ketika kita bekerja pada
situasi hubungan yang tidak simetris, maka kita menggunakan digraph bertanda. Contoh
representasi digraph bertanda untuk jaringan sosial ditunjukan pada Gambar 4.14. Catat bahwa arc
negatif dari x ke y tidak sama dengan arc positif dari y ke x.
13
Gambar 4.14 Digraph bertanda dalam jaringan sosial
Digraph bertanda dapat digunakan untuk permasalahan sosial yang melibatkan sistem yang
kompleks dan terdiri dari sejumlah variabel yang berubah dan saling mempengaruhi. Sering kali kita
ingin meramalkan perkembangan masa depan ketika kita hanya mengetahui sejumlah informasi.
Untuk situasi seperti ini, digraph bertanda dapat dipakai dengan mudah dan dapat menghasilkan
kesimpulan yang benar. Sebagai contoh suatu sistem pada Gambar 4.14 menunjukan konsekuensi
penggunaan energi.
Gambar 4.15 Representasi digraph bertanda pada suatu sistem sosial
Pada Gambar 4.15 kita dapat melihat arc pu ditandai positif, karena kenaikan jumlah
populasi menyebabkan kenaikan jumlah penggunaan energi. Arc ur ditandai negatif, karena
semakin banyak energy yang digunakan, maka biaya per unitnya makin murah. Pada sistem
tersebut juga digambarkan tidak ada arc dari j ke r, karena kenaikan jumlah lapangan kerja tidak
memiliki efek langsung pada harga unit listrik.
Pada graph tersebut, kita juga dapat memperhatikan cycle yang terbentuk. Sebagai contoh
cycle puqp. Pada cycle ini, peningkatan populasi p menyebabkan peningkatan penggunaan energi u,
ini kemudian menyebabkan penurunan kualitas lingkungan q, yang akhirnya menyebabkan
penurunan angka populasi p. Dalam cycle seperti ini, di mana peningkatan variable p akhirnya
menyebabkan penurunan variabel yang sama, disebut cycle dengan feedback negatif. Di sisi lain,
peningkatan kapasitas energy c, menyebabkan peningkatan jumlah pabrik f, sehingga menyebabkan
peningkatan energi yang dipakai u, yang akhirnya juga menyebabkan kapasitas energi c meningkat
pula. Cycle cfuc, di mana peningkatan suatu variabel akhirnya menyebabkan peningkatan variabel
yang sama, di sebut cycle dengan feedback positif.
Untuk melihat bagaimana menentukan cycle dengan feedback positif atau negatif,
perhatikan bahwa, setiap cycle dengan feedback positif memiliki jumlah arc negatif yang genap,
sedangkan cycle dengan feedback negatif memiliki jumlah arc negatif yang ganjil. Pada Gambar 4.15,
dengan menghitung jumlah arc bertanda negatiff, kita dapat melihat bahwa cycle uqpu adalah cycle
dengan feedback negatif, sedangkan cycle cruc, cfuc, rur dan cfjpuc semuanya memiliki feedback
positif.
14
Latihan 4.13 Daftarlah sebanyak mungkin cycle dengan feedback positif dan negatif pada digraph bertanda berikut.
Rotating Drum Problem
Salah satu masalah pada bidang telekomunikasi (muncul juga pada bidang kriptografi dan
desain mesin cuci) adalah masalah rotasi drum pada teleprinter. Permukaan dari drum yang berotasi
dibagi menjadi enam belas bagian seperti ditunjukan pada Gambar 4.16. Area yang memiliki
bayangan menunjukan material yang terkonduksi. Kita merepresentasikan posisi drum dengan
empat digit bilangan biner, a, b, c, dan d.
Gambar 4.16 Pembagian permukaan drum berrotasi
Bagian posisi drum, a, b, c dan d bisa jadi terisolasi atau tidak terisolasi. Sebagai contoh,
pada Gambar 4.16 menunjukan a, c dan d tidak terisolasi. Bagian yang tidak terisolasi memberikan
sinyal yang direpresentasikan dengan angka 1, dan bagian yang terisolasi memberikan sinyal yang
direpresentasikan dengan angka 0.
Agar enam belas posisi ini dapat direpresentasikan secara unik dengan empat digit kode
biner abcd, setiap posisi harus ditandai sedemikian rupa sehingga terdapat enam belas kode biner
empat digit abcd yang muncul. Sebagai contoh, untuk Gambar 4.16 di mana a, c dan d tidak terisolasi
ditunjukan dengan kode biner 1011. Drum diputar berlawanan arah jarum jam secara berurutan dan
memberikan susunan barisan bilangan biner berikut.
0110,1100,1001,0010,0100,1000,0000,0001,
0011,0111,1111,1110,1101,1010,0101,1011.
15
Semua barisan bilangan biner empat digit tersebut berbeda dan merepresentasikan semua
posisi dalam drum. Untuk memperoleh barisan ini dan solusi lain, kita membangun sebuah digraph
dengan delapan vertex dan berkoresponden dengan bilangan biner tiga digit berikut.
000,001,010,011,100,101,110,111
dengan arc dari setiap vertex abc ke vertex bc0 dan bc1. Seperti ditunjukan pada Gambar 4.17
Gambar 4.17 Representasi digraph untuk masalah rotating drum
Digraph yang terbentuk adalah graph Euler, karena memiliki derajat masuk dan derajat
keluar sama dengan 2. Trail Euler yang ada memberikan solusi pada masalah rotasi drum. Sebagai
contoh, kita kita dapat memakai trail Euler berikut.
101 → 011 → 110 → 100 → 001 → 010 → 100 → 000 →
000 → 001 → 011 → 111 → 111 → 110 → 101 → 010 → 101
Kita dapat menyederhanakan bentuk 101 → 011 → 110 dengan 10110 sehingga diperoleh barisan
sebagai berikut
1011001000011110.
Solusi ini memberikan susunan sirkular posisi yang ditunjukan pada Gambar 4.18.
Gambar 4.18 Solusi untuk masalah rotating drum
Dengan menggunakan cara yang sama, kita dapat mencari solusi untuk masalah drum
berotasi dengan pembagian 32, 64 dan seterusnya.
Latihan 4.14 Temukan trail Euler yang berbeda pada Gambar … yang dapat membangun sebuah solusi untuk masalah drum berotasi dengan enam belas bagian.
16
Ranking Tournament
Sebuah turnamen adalah sebuah digraph yang graph underlying-nya merupakan graph
komplit. Sebagai contoh Gambar 4.19 menunjukan turnamen dengan tiga dan empat buah titik.
Digraph seperti ini dapat dipakai untuk merekam pemenang dalam sebuah turnamen round robin di
mana setiap pemain bermain dengan semua pemain lainnya. Sebagai contoh dalam turnamen (a), a
mengalahkan d dan c, dan b mengalahkan c. Dalam turnamen (d), c mengalahkan a, d dan b, b
mengalahkan a dan d, dan a mengalahkan d.
Gambar 4.19 Contoh digraph turnamen round robin
Turnamen juga dapat muncul dalam konteks lain seperti perbandingan pasangan metode, di
mana kita membandingkan sejumlah komoditas dengan melakukan test secara berpasangan.
Sebagai contoh, Gambar 4.20 membandingkan enam tipe makanan anjing yang kelezatannya ditest
secara berpasangan pada sejumlah anjing. Masalah yang muncul adalah bagaimana komoditas ini
kita dapat kita ranking berdasarkan data pilihan yang ada.
Gambar 4.20 Contoh digraph perbandingan pasangan komoditas
Untuk beberapa turnamen, kita tidak mendapatkan kesulitan dalam melakukan perankingan.
Kita dapat mengurutkan ranking dengan cara melihat vertex mana yang mengalahkan vertex lainnya.
Misalnya dalam turnamen (a) dan (d) kita dapat melakukan ranking seperti ditunjukan pada Gambar
4.21.
Gambar 4.21 Contoh perankingan sebuah turnamen
17
Sayangnya dalam contoh praktis perankingan yang konsisten semacam ini jarang terjadi.
Sebagai contoh dalam turnamen (b), a mengalahkan b, b mengalahkan c dan c mengalahkan a,
sehingga kita tidak bisa membuat ranking dari ketiga pemain ini secara langsung. Ketidak-
konsistenan ini juga terjadi pada contoh perbandingan makanan anjing pada Gambar 4.20.
Makanan anjing Woofoo lebih dipilih dari pada Doggo, Doggo lebih dipilih daripada Joocy-chunks,
dan Joocy-chunks lebih dipilih daripada Woofoo. Untuk turnamen semacam ini, kita harus
menemukan metode alternatif yang bisa meranking partisipan atau komoditas ini.
Pada kondisi ini, tidak ada metode yang sepenuhnya memuaskan, namun metode yang
sering dipakai dalam kondisi praktis adalah dengan mencari sebuah path yang memuat semua
vertex, seperti path semi-Hamilton. Untuk setiap turnamen, setidaknya ada sebuah path semi-
Hamilton semacam ini dan dapat kita gunakan untuk menjadi dasar perankingan. Sebagai contoh,
dalam turnamen (c), ranking yang mungkin adalah a,b,d,c dan b,c,a,d. Sedangkan untuk masalah
makanan anjing, ranking yang dapat dibuat adalah :
Woofoo, Doggo, Joocy-chunks, Waggo, Slurp, Bitey-bits
dan
Bitey-bits, Joocy-chunks, Woofoo, Doggo, Waggo, Slurp.
Ketika kita sudah memiliki daftar dari semua ranking yang mungkin, kita dapat mengambil
pertimbangan lain. Pertimbangan tersebut digunakan untuk menentukan ranking mana yang paling
baik dan cocok dipakai untuk memenuhi tujuan perankingan kita.
Latihan 4.15 Berapa buah ranking yang mungkin dibuat pada turnamen berikut.