BUJURSANGKAR LATIN ORTHOGONAL DAN DESAIN BLOK

MATEMATIKA DISKRIT LANJUT

DESAIN BLOK

BUJURSANGKAR LATIN ORTHOGONAL

                                                                         

DAFTAR ISI

Halaman Judul .................................................................................................  i

Kata Pengantar ................................................................................................  ii

Daftar Isi .........................................................................................................  iii

A.      Bujursangkar Latin Orthogonal ...........................................................  1

B.       Desain Blok .............................................................................................  2

1.      Definisi Desain Blok ..........................................................................  3

2.      Hubungan Antara Parameter b, v, r, k, ........................................  5

3.      Matriks Insiden Desain Blok............................................................. 10

4.      Desain Simetris.................................................................................... 14

5.      Mengkonstruksi Desain Baru Dari Desain Yang Ada.................... 20

Daftar Pustaka

A.      BUJUR SANGKAR LATIN ORTHOGONAL

            Misalkan A = (a_ij) dab B = (b_ij) dua bujursangkar latin masing-masing berordo n, atau disingkat BSL-n. Kita sebut A dan B saling ortogonal jika semua pasangan terurut (aij, bij) berbeda. Misalnya, BSL-4 (a) dan (b) pada Tabel 5.2.1 saling ortogonal. Sedangkan BSL-4 (c) dan (d) tidak ortogonal karena pasangan (2,4) tampak dua kali, sekali pada posisi-(2,2) dan sekali pada posisi-(3,3).

                                                                  

            (a)                                 (b)                                    (c)                                      (d)

Tabel 5.2.1: Sekumpulan BSL-4

            Sebuah himpunan yang anggota-anggotanya BSL-n sedemikian hingga setiap pasang BSL-n dalam himpunan tersebut saling ortogonal disebut keluarga bujursangkar latin orthogobnal disingkat KBSLO. Pertanyaan utama yang muncul adalah: Untuk r dan berapa, terdapapat KBSLO yang berisi sebanyak r buah BSL-n?

Sebelum menjawab pertanyaan tersebut, berikurt diberikan beberapa contoh kegunaan darai rancangan bujursangkar latin orthogonal.

Contoh 5.2.2:

Penetesan kualitas kain untuk pakaian. Box dan kawan-kawan (1978) melakukan percobaan menguji kualitas kain sebagai bahan utama pakaian, dengan mesin tes tertentu. Dengan mesin ini, empat lembar kain material dapat digosok bersamaan dengan menggunakan empat kertas gosok berbeda, dan kemudian pesusutan berat dari masing-masing kain dapat diukur. Terdapat empat baki di label A, B, C, dan D dalam mesin digunakan sebagai tempat pakaian yang uji kualitasnya dan setiap baki tersebut dapat diletakkan di slah satu posisi yang mungkin P1, P2, P3, dan P4. Dalam percobaan ini empat jenis kain atau perlakuan, dilabel 1, 2, 3, dan 4, dibandingkan dengan kualitasnya. Peneliti ingin mengontrol pengaruh-pengaruh dari empat baki, empat posisi yang berda dalam mesin, empat pengoperasian, dan empat jenis kertas gosok. Suatu klasifikasi-empat dari satuan-satuan percobaan menuntut penggunaan bujursangkar latin beranggotakan tiga bujursangkar latin ordo empat. Misalkan digunakan empat jenis kertas gosok, namakan α, β, δ, γ  masing-masing dipotong menjadi empat bagian sama, dan guanakan setiap bagian dalam satu satuan percobaan. Terdapat empat pengoperasian, R1, R2, R3, dan R4 masing-masing meguji empat jenis kain kain dengan baki berbeda dalam posisi berbeda dengan potongan kertas gosok berbeda. Dalam hal ini dapat digunakan KBSLO ordo-4 berikut

            R1  R2 R3  R4                             R1  R2 R3  R4                             R1  R2 R3  R4

                                                    

                   (a)                                                (b)                                                  (c)

Tabel 5.2.2:  (a) Rancangan BSL untuk jenis kain

                     (b) Rancangan BSL untuk baki

                     (c) Rancangan BSL untuk kertas gosok

           

B.       DESAIN BLOK

Teori desain muncul pertama kali melalui karya R.A. Fisher and F. Yates pada tahun 1930. Mereka termotivasi oleh pertanyaan desain percobaan lapangan di bidang pertanian. Penerapan teori ini sekarang sangat luas, banyak terminologi masih menghubungkan dengan asal usulnya.

Dalam percobaan pertanian, misalkan diinginkan untuk membandingkan hasil varietas v yang berbeda dari biji-bijian. Hal ini mungkin akan ada interaksi antara lingkungan (jenis tanah, curah hujan, drainase, dll) dan berbagai biji-bijian yang akan mengubah hasil. Jadi, blok b (set plot percobaan) yang dipilih, di mana lingkungan cukup konsisten di seluruh blok. Dalam jenis percobaan, di mana lingkungan tidak mungkin menjadi faktor, blok dapat dibedakan sebagai plot yang menerima pengobatan tertentu (misalnya, diberikan suatu jenis pupuk). Dengan cara ini, klasifikasi plot percobaan ke dalam blok dan varietas dapat digunakan setiap kali ada dua faktor yang mungkin mempengaruhi hasil.

Teknik ini jelas akan tumbuh berbagai jenis plot (varietas) di setiap blok, mungkin, untuk eksperimen besar ini terlalu mahal atau tidak praktis. Untuk mengatasi hal ini, salah satu cara dengan menggunakan blok yang lebih kecil yang tidak mengandung semua varietas. Sekarang masalahnya adalah salah satu perbandingan, untuk meminimalkan efek dari kesempatan karena blok tidak lengkap, kami ingin merancang blok sehingga bahwa probabilitas dari dua varietas yang dibandingkan (yaitu yang di blok yang sama) adalah sama untuk semua pasangan. Sifat ini disebut keseimbangan dalam desain.

Titik dan garis di bidang Euclidan merupakan contoh lama dari struktur insiden. Pada umumnya, insiden struktur dapat dijelaskan oleh dua set abstrak (disebut set titik dan set blok) dan hubungan biner antara titik dan blok. Memaksakan kondisi keteraturan tertentu pada insiden struktur terbatas mengarah ke konsep desain kombinatorial yang mencakup      2-desain, desain simetris dan grafik.

Pada bagian ini kita bahas konsep dan sifat-sifat dasar serta terapan dari desain blok. Kita awali dengan definisi berikut. Dalam matematika kombinatorial, desain blok adalah satu himpunan dengan keluarga himpunan bagian (subset diulang diperbolehkan satu kali) yang anggotanya dipilih untuk memenuhi beberapa jenis himpunan yang dianggap berguna untuk aplikasi tertentu. Aplikasi ini berasal dari banyak variasi, termasuk desain eksperimental, geometri terbatas, pengujian perangkat lunak, kriptografi, dan geometri aljabar. Banyak variasi telah diperiksa, namun yang paling intens dipelajari adalah desain blok tak lengkap (BIBDs atau 2-desain) yang secara historis terkait dengan masalah statistik dalam desain eksperimen.

1.        DEFINISI DESAIN BLOK

Desain adalah kerangka bentuk atau rancangan memiliki arti "proses untuk membuat dan menciptakan obyek baru. Sedangkan blok adalah deretan beberapa bagian yang tidak terpisah-pisah.

Sebuah desain blok pada himpunan V dengan v elemen (varitas) adalah sebuah koleksi himpunan B yang beranggotakan himpunan-himpunan bagian dari V, sedemikian sehingga setiap anggota B, disebut blok, memuat k elemen. Selanjutnya, misalkan b menyatakan banyaknya blok di B. Jika setiap elemen V muncul tepat di dalam r blok dan setiap pasang elemen V muncul bersama-sama tepat di dalam , dan ditulis Desain-( b, v, r, k, ).

Sebuah desain blok pada V disebut lengkap, jika setiap bloknya sama  dengan V; dan tak lengkap, jika sebaliknya. Desain blok tak lengkap balance sering disingkat BIBD (Balanced Incomplete Block Design)

Contoh:

Desain blok lengkap

(a)     Misalkan  dengan blok

Maka B = { , sehingga desain-( b, v, r, k, )= desain-( 1, 3, 3, 1, )

(b)     Misalkan  dengan blok

Maka B = { , sehingga desain-( b, v, r, k, )= desain-( 1, 4, 4, 1, )

Desain blok tak lengkap

(a)     Misalkan  dengan blok

Maka
𝐵= , sehingga desain-( b, v, r, k, )= desain-( 7, 7, 3, 3, )

(b)     Misalkan  dengan blok

Maka
𝐵= , sehingga desain-( b, v, r, k, )= desain-( 4, 4, 3, 3, )

2.        HUBUNGAN ANTARA PARAMETER b, v, r, k,

Pada bagian ini kita bicarakan hubungan antara parameter-parameter b, v, r, k,  dari suatu desain-( b, v, r, k, ).

Teorema 2.1:

Dalam desain-( b, v, r, k, ) berlaku .

Bukti:

Karena terdapat b blok dan tiap blok berisi k elemen, banyaknya pasangan berurutan yang berisikan sebuah blok dan sebuah elemen dari blok tersebut adalah bk. Tetapi, karena setiap elemen dari V harus muncul di dalam r block, maka terdapat vr pasang beurutan yang berisikan sebuah blok yang memuat elemen tersebut. Perhatikanlah bhwa setiap pasangan berurutan kedua didapat dari pasangan pertama dengan mengubah urutannya. Sehingga kedua bilangan bk dan vr harus sama. Teorema terbukti.

Contoh:

(a)     Misalkan  dengan blok

, sehingga desain-( b, v, r, k, ) = desain-( 5,5,3,3,2)

Maka

    

(b)     Misalkan  dengan blok

, sehingga desain-( b, v, r, k, )= desain-( 5,5,2,2,1)

Maka

     

Teorema 2.2

Memberikan sebuah syarat perlu adanya sebuah desain-( b, v, r, k, ). Sebuah syarat perlu lainnya diperlihatkan dalam teorema berikut.

Teorema 2.3

Pada desain-( b, v, r, k, ) berlaku

                r(k-1) = (v-1)

Bukti:

Pandang sebuah elemen i dari V. Bilangan r(k-1) menyatakan hasil kali dari banyaknya blok di mana elemen i muncul dengan banyaknya elemen lain di setiap blok yang memuat elemen i. Sehingga r(k-1) menyatakan banyaknya pasangan (i,j) muncul di blok yang sama (setiap kali pasangan muncul, dihitung sekali).

Bilangan (v-1) adalah hasil kali dari banyaknya kali (seringnya) setiap pasangan (i,j) muncul di setiap blok dengan banyaknya kemungkinan j. Sehingga (v-1) menyatakan banyaknya pasangan (i,j) muncul di blok yang sama (setiap kali pasangan muncul dihitung satu kali). Dengan demikian r(k-1)= (v-1), dan teorema terbukti.

Sebagai akibat dari teorema di atas kita peroleh teorema berikut.

Contoh:

(a)     Misalkan  dengan blok

Maka
𝐵= , sehingga desain-( b, v, r, k, )= desain-( 7, 7, 3, 3, )

 r(k-1)= (v-1)

·         r(k-1

·         (v-1)

Terbukti r(k-1)= (v-1)

(b)   Misalkan  dengan blok

Maka
𝐵= , sehingga desain-( b, v, r, k, )= desain-( 4, 4, 3, 3, )

r(k-1)= (v-1)

·         r(k-1

·         (v-1)

Terbukti r(k-1)= (v-1)

Teorema 2.4

Dalam sebuah BIBD berlaku

Bukti:

Karena desain tak lengkap,

Dari teorema 2.2 diketahui,

ekuivalen dengan

Sehingga r >

Dengan demikian teorema terbukti.

Contoh:

(a)   Misalkan  dengan blok

Maka
𝐵= , desain-( b, v, r, k, )= desain-( 7, 7, 4, 4, )

Karena  Sehingga

(b)   Misalkan  dengan blok

Maka
𝐵= , desain-( b, v, r, k, )= desain-( 7, 7, 3, 3, )

Karena  Sehingga

Selanjutnya kita ingin meninjau hubungan antara parameter b dan v dalam                        desain-(b, v, r, k, ). Untuk keperluan tersebut, perlu diperkenalkan matriks insiden dari sebuah desain.

3.    MATRIKS INSIDEN DESAIN BLOK

Setiap desain blok punya matriks insiden. Misal suatu desain pada V = { } punya b blok . pandang sebuah matriks A=(  berordo v x b, yang baris-barisnya dilabeli dengan elemen-elemen V dan kolom-kolomnya dilabeli dengan blok-blok dari desain dengan;

Matrik A yang didefinisikan seperti di atas disebut matriks insiden dari desain blok.

Contoh:

Desain-(7,7,3,3,1) dalam contoh 1 (a) mempunyai matriks insiden sebagai berikut:

1

                                                                                      

2

3

4

5

6

7

                                                             

Sudah kita singgung di atas, bahwa setiap desain blok memiliki matriks insiden. Sebaliknya, kita ingin mengetahui kapan sebuah matriks merupakan matriks insiden dari sebuah blok?

Sebuah matriks v x b yang unsur-unsurnya 0 atau 1 dengan  adalah matriks insiden dari desain-( b, v, r, k, ) dengan b, v, r, k,  < 0 jika dan hanya jika:

(i)                 Setiap kolom mempunyai elemen 1 sebanyak k >0

(ii)              Setiap baris mempunyai elemen 1 sebanyak r > 0

(iii)            Di setiap dua baris berbeda, terdapat tepat  kolom di mana kedua elemen di kolom tersebut adalah 1.

Lemma 3.1;

Jika H adalah matriks insiden dari desain-( b, v, r, k, ) maka , di mana  adalah transpose dari A, I matriks identitas berordo v x v dan J adalah matriks berordo v x v dan setiap elemennya 1.

Bukti:

Misalkan A=(  dan =( , maka adalah “hasil kali dalam” dari baris ke-i dari A dengan kolom ke-j dari A^T.

Sehingga

Untuk i = j.

Sehingga  menyatakan banyaknya blok di mana elemen 1 terletak. Dengan demikian .

Untuk i j

Sehingga menyatakan banyaknya blok di mana elemen 1 dan j keduanya menjadi anggota blok tersebut. Dengan demikian 

Jadi

Lemma terbukti.

Sekarang kita buktikan bahwa banyaknya blok dalam suatu desain-( b, v, r, k, ) tidak boleh kurang dari banyaknya elemen dari himpunan V. Dan hasil ini dikenal sebagai ketaksamaan Fisher.

Lemma 3.2: (Ketaksamaan Fisher, 1940)

                        Dalam desain-( b, v, r, k, ) berlaku b .

Bukti:

Kita gunakan kontradiksi untuk membuktikan teorema ini.

Andaikan b < v, dan misal A adalah matriks insiden dari desain-( b, v, r, k, ).

Karena b < v, kita bisa menambahkan sebanyak v-b kolom-kolom nol ke A, menghasilkan matriks bujursangkar B berordo v x v. Jelas bahwa hasil kali dalam dua baris B yang bersesuaian. Sehingga .

Ini berakibat:

Det (  Det (

Karena B memuat kolom nol, maka =0, sehingga

Det (          ....( 3.1)

Dari Lemma 5.3.4

         ....( 3.2)

Karena Pengurangan dengan kolom pertama dari kolom-kolom yang lain dalam matriks di ruas kanan (5.3.2), tidak akan mengubah nilai determinan (operasi-operasi kolom dalam matriks tidak mengubah determinan), diperoleh:

    ... (3.3)

Selanjutnya, penambahan baris pertama dengan semua baris-baris yang lain dalam matriks di ruas kanan (3.3), tidak mengubah nilai determinan. Sehingga diperoleh:                        

  ...(3.4)

Karena semua elemen matriks di ruas kanan (3.4) yang terletak di atas diagonal utama adalah nol, maka determinan dari matriks tersebut sama dengan hasil kali semua elemen yang terletak di diagonal utama matriks tersebut. Dengan demikian diperoleh:

       ................( 3.5)

Dari (3.1) dan (3.5) kita peroleh

          ................( 3.6)

Karena r,v, dan  positif,

                   ................( 3.7)

Selanjutnya, karena , Teorema (3.3), maka

                       ................( 3.8)

Dari (3.7) dan (3.8) kita peroleh,

Bertentangan dengan (3.6). jadi pengandaian b < v salah. Dengan demikian teorema terbukti.

4. DESAIN SIMETRIS

Dalam Teorema 3.2 telah kita tunjukkan bahwa dalam desain-  berlaku   b ≥ v. Apabila b = v, maka desain tersebut disebut desain simetris. Jika b = v, dari Teorema 2.1 kita peroleh k = r. Jadi dalam desain simetris, berlaku k = r. sebagai contoh, desain-desain dalam contoh  3.1 adalah desain-desain simetris. Desain simetris sering pula disebut desain- .

Teorema 4.1 : 

Dalam desain-  dengan v genap, bilangan k –  adalah bilangan kuadrat sempurna.

Bukti :

Misal A adalah matriks insiden dari sebuah desain-- . Dapat ditunjukkan bahwa,

(i)                 A dan   adalah bujur sangkar matriks dengan

det A = det , dan

(ii)              Det

Sehingga,

  (4.1)

Karena det A adalah bilangan bulat, maka  bilangan bulat. Selanjutnya, karena v genap dan   bilangan bulat, maka   harus bilangan kuadrat sempurna. Teorema terbukti

DESAIN HADAMARD

Desain--  dengan v = 4m - 1, k = 2m – 1,  = m - , untuk suatu m, disebut desain Hadamard dimensi m. pertanyaan utama disini adalah sebagai berikut :

Untuk m berapa desain-(4m – 1, 2m – 1, m – 1) ada?

            Akan ditujukan bahwa  terdapat desain-(4m – 1, 2m – 1, m – 1). Untuk tujuan tersebut, perlu diperkenalkan matriks Hadamard.

            Sebuah matriks bujur sangkar H berordo n disebut matriks Hadamard jika unsur-unsur H adalah 1 atau -1 ; dan  , di mana  adalh transpose dari H dan I adalah matriks identitas berordo n. sebagai contoh, matriks H berikut adalah Hadamard.

         (4.2)

Mudah dicek bahwa

HH^T

            Kiranya jelas (dari definisi) bahwa untuk matriks Hadamard H berordo n berlaku :

(i)                 Hasil kali dari baris i dengan dirinya sendiri adalah n.

(ii)              Hasil kali dalam baris i dengan baris ke j, untuk i ≠     j, adalah nol.

Matriks Hadamard H disebut ternormalisir jika elemen-elemen H pada baris dan kolom pertama semuanya positif (+1). Misalnya, matriks H berikut adalah matriks hadamard normal.

Lemma 4.2 : Jika H adalah matriks Hadamard, maka  juga matriks Hadamard.

Bukti : Karena

                             

Maka ;

Karena   =   masing-masing bujur sangkar,

Ekuivalen dengan

Dengan demikian  adalah matriks Hadamard.

Salah satu sifat penting dari matriks Hadamard normal disajikan dalam di Lemma berikut :

Lemma 4.3:

Jika H adalah matriks Hadamard normal berordo n > 2, maka n = 4m, untuk suatu m. Lebih lanjut, setiap baris (kolom), kecuali yang pertama, memiliki tepat 2m elemen +1 dan tepat 2m elemen -1; dan untuk setiap dua baris (kolom), selain yang pertama, terdapat m kolom (baris) dalam mana kedua baris (kolom) memiliki elemen +1.

Bukti :

Misal H adalah matriks hadamard normal berordo n. Akan dibuktikan hasil-hasil yang menyangkut baris saja, karena hasil-hasil yang menyangkut kolom mengikuti hasil-hasil yang menyangkut baris.

            Karena H normal, elemen-elemen H pada baris pertama semuanya 1. Karena “hasil kali dalam” baris pertama dengan sebarang garis yang lain adalah nol, setiap baris (selain baris pertama) harus memiliki elemen +1 dan -1 sama banyak. Dengan demikian n harus genap.

            Pandang sebuah baris dari H yang bukan baris pertama, tanpa mengurangi keumuman, missal baris itu baris kedua. Elemen-elemen +1 dan elemen-elemen -1 pada baris kedua ini sebanyak, yaitu  . Sekarang pertukarkan kolom-kolom dari matriks H sedemikian hingga elemen-elemen pada baris kedua punya pola sebagai berikut : ke  elemen pertama bertanda + dan ke  elemen lainnya bertanda -; seperti terlihat pada bagan dibawa ini :

 

 

Pertukaran ini jelas tidak mengubah ordo dari matriks atau banyaknya +1 dalam tiap baris ataupun banyaknya kolom dimana dua baris memiliki unsure 1. Untuk selanjutnya, perhatikan baris i ≠ 1, 2 pada matriks yang baru. Didalam   elemen pertama baris ke 1 terdapat x elemen 1 dan  elemen -1. Begitu pula, didalam  elemen pada baris ke-i selebihnya, terdapat y elemen 1 dan  elemen -1. Karena “hasil kali dalam” dari baris pertama dengan baris i adalah nol,

     (*)

Begitu pula ‘hasil kali dalam” dari baris kedua dengan baris i adalah nol, maka ;

Ekuivalen dengan     (**)

Dari (*) dan (**) diperoleh:

Ekuivalen dengan n = 4x. jadi n adalah kelipatan 4. Dengan demikian bagian pertama dari lemma terbukti.

Selanjutnya, setiap baris kecuali baris pertama memiliki  = 2x elemen +1 dan  = 2x elemen -1. Begitupula, pada baris kedua dan ke i, i  1, 2, terdapat tepat x kolom dimana kedua baris ini memiliki elemen 1. Dengan mengganti baris kedua dengan ke j, j  1, 2. Lengkaplah bukti dari lemma tersebut.

Sekarang, kita gunakan lemma di atas untuk membuktikan teorema berikut.

Teorema 4.4

Untuk m = 2^k, k > 1, terdapat Desain –(4m – 1, 2m – 1, m – 1).

Bukti:

Misalkan H adalah matriks Hadamard normal ordo n. Didefenisikan matriks H₁ sebagai berikut

H₁ =

Jelaskan H₁ adalah matriks Hadamard normal ordo 2n, karena setiap elemen H₁ adalah 1 atau -1. Setiap elemen yang terletak di baris (kolom) pertama adalah 1; hasil kali dalam sebuah baris dengan dirinya sendiri adalah 2n; dan hasil kali dalam sebuah baris dengan baris yang lain adalah nol.

Karena terdapat matriks Hadamard normal ordo 2, yaitu

Maka terdapat matriks Hadamard normal berordo 2^t, t > 1. Dengan demikian, untuk m = 2k, k > 1, terdapat matriks Hadamard normal berordo 4m. Sekarang, misalkan K adalah matriks Hadamard normal ordo 4m. Selanjutnya konstruksi matriks A dengan menggunakan matriks K dengan cara sebagai berikut:

(i)     Hapus semua elemen K yang terletak di baris pertama maupun di kolom pertama, kemudian

(ii)  Setiap elemen -1 diganti dengan 0 (nol).

Perhatikan bahwa matriks A berordo (4m – 1)x(4m -  1). Menurut Lemma 5.2.8, banyak elemen 1 di setiap baris (kolom) K adalah 2m. Karena K normal, maka setiap elemen di baris (kolom) pertama adalah 1, sehingga setiap elemen baris (kolom) A memuat elemen 1 tepat sebanyak 2m – 1. Selanjutnya, menurut Lemma 5.3.8, disetiap pasang baris (kolom) K terdapat tepat m kolom (baris) dimana elemen 1 terletak di kedua baris (kolom) tersebut. Sehingga di setiap pasang baris (kolom) A, terdapat tepat m – 1 kolom (baris) dimana elemen 1 terletak di kedua baris (kolom) tersebut. Dengan demikian A adalah matriks insiden dari desain –(4m – 1, 2m – 1, m – 1). Teorema terbukti.

Perhatikan, di dalam bukti terkandung prosedur yang sistematis dan sederhana untuk mengkonstruksi desain –(4m – 1, 2m – 1, m – 1), untuk suatu m = 2k, k > 1. Misalnya untuk k = 1, diperoleh m = 2, sehingga menurut teorema di atas terdapat Desain –(7, 3, 1). Bagaimana mengkonstruksi sebuah desain –(7, 3, 1) pada himpunan V = {1, 2, 3, 4, 5, 6, 7}?

Perhatikan matriks Hadamard normal berikut,

H =

Dari matriks H dibentuk matriks Hadamard normal K berikut

K =  =

Selanjutnya kita bentuk matriks A dari K dengan cara mengghapus baris pertama dan kolom petama dari K, dan ganti setiap elemen -1 dengan 0 (nol). Perhatikan bahwa matriks A adalah matriks insiden dari desain –(7, 3, 1). Sehingga,

{{2,4,6},{1,4,5},{3,4,7},{1,2,3},{2,5,7},{1,6,7},{3,5,6}}

Sebuah desain –(7, 3, 1) pada himpunan V = {1, 2, 3, 4, 5, 6, 7}.

A =

5.   MENGKONSTRUKSI DESAIN BARU DARI DESAIN YANG ADA

Cara yang paling mudah untuk mendapatkan desain baru dari desain yang sudah ada ialah dengan mengambil p “jiplakan/copy” dari masing-masing blok dalam desain –(b, v, r, k, ) diperoleh desain –(pb, v, pr, k, p ). Misalnya, dari sebuah desain –(4, 4, 3, 3, 2) pada V = {1, 2, 3, 4} berikut

{{1,2,3},{2,3,4},{3,4,1},{4,1,2}}

Diperoleh sebuah desain –(8, 4, 6, 3, 4) pada V = {1, 2, 3, 4} berikut {{1,2,3},{2,3,4},{3,4,1},{4,1,2},{1,2,3},{2,3,4},{3,4,1},{4,1,2}}.

Teorema 5.1

Dalam sebuah desain –(v, k, ), setiap dua blok memiliki tepat  elemen sekutu.

Dengan menggunakan Teorema 5.1, kita buktikan teorema berikut.

Teorema 5.2

Jika B₁, B₂, ..., B_v merupakan blok-blok Desain –(v, k, ) pada himpunan varitas X, maka untuk sembarang i, B₁ – B_i, B₂ – B_i, ..., B_i-1 – B_i, B_i+1 – B_i, ..., B_v – B_i adalah blok-blok Desain (v -1, v – k, k, k - , ) pada himpunan varitas X – B_i.

Bukti:

Jika terdapat v – 1 blok dan v – k varitas. Dari Teorema 5.1, setiap blok Bj – Bi memiliki k –  elemen. Setiap varitas di dalam X – Bi muncul di dalam k blok pada desain semula dan karenanya juga muncul di dalam k blok pada desain yang baru. Begitu juga setiap pasang varitas di dalam X – Bi muncul bersama – sama di  blok pada desain semula dan karenanya di  blok pada desain baru. Dengan demikian teorema terbukti.

Contoh

Perhatikan contoh Desain –(7, 3, 1) pada himpunan varitas X = {1, 2, 3, 4, 5, 6, 7} berikut,

B₁ = {1, 2, 4}, B₂ = {2, 3, 5}, B₃ = {3, 4, 6}, B₄ = {4, 5, 7}, B₅ = {5, 6, 1},

B₆ = {6, 7, 2}, B₇ = {7, 1, 3}

Misalkan Bi = {3, 4, 6}. Maka blok berikut

{1, 2}; {2, 5}; {5, 7}; {1, 5}; {2, 7}; {1, 7}

membentuk Desain –(6, 4, 3, 2, 1) pada himpunan {1, 2, 5, 7}.

Teorema 5.3

Jika B₁, B₂, ..., B_v, blok-blok Desain –(v, k, ) pada himpunan varitas X, maka untuk sembarang i, B₁  B_i, B₂  B_i, ..., B_i-1  B_i, B_i+1  B_i, ..., B_v  B_i adalah blok-blok dari Desain (v -1, v – k, k, k - , ) pada himpunan varitas B_i.

Bukti:

Jelas terdapat v – 1 blok dan k varitas. Berdasarkan Teorema menyatakan bahwa setiap blok B_j  B_i memiliki  elemen. Sebuah varitas di B_i muncul di k blok pada desain semula, katakan B_j1, B_j2, ..., B_jk-1, B_i. Sehingga varitas tersebut muncul di k -1 blok pada desain baru, yaitu:

B_j1  B_i, B_j2  B_i, ..., B_jk  B_i.

Selanjutnya setiap pasang elemen di B_i muncul secara bersama-sama di  blok pada desain semula, katakan

B_j1, B_j2, ..., B_jk-1, B_i

Sehingga persamaan elemen tersebut secara bersama-sama akan muncul di  – 1 blok pada desain baru, yaitu:

B_j1  B_i, B_j2  B_i, ..., B_jk  B_i.

Dengan demikian teorema terbukti.

Contoh:

Terdapat desain –(15, 7, 3), sehingga menurut teorema diatas terdapat desain –(14, 7, 6, 3, 2) blok-blok desain –(15, 7, 3) pada himpunan varitas V = {1, 2, 3, 4, ..., 15} adalah sebagai berikut:

B₁={2, 4, 6, 8, 10, 12, 14}; B₆ = {1, 6, 7, 8, 9, 14, 15};     B₁₁ = {3, 4, 7, 9, 10, 13, 15}

B₂={1, 4, 5, 8, 9, 12, 13};   B₇ = {3, 5, 6, 8, 11, 13, 14};   B₁₂ = {1, 2, 3, 12, 13, 14, 15}

B₃={3, 4, 7, 8, 11, 12, 15}; B₈ = {1, 2, 3, 4, 5, 6, 7};         B₁₃ = {2, 5, 7, 9, 11, 12, 14}

B₄={1, 2, 3, 8, 9, 10, 11};   B₉ = {2, 4, 6, 9, 11, 13, 15};    B₁₄ = {1, 6, 7, 10, 11, 12, 13}

B₅={2, 5, 7, 8, 10, 13, 15}; B₁₀ = {1, 4, 5, 10, 11, 14, 15}; B₁₅ = {3, 5, 6, 9, 10, 12, 15}

Misalkan B_i = {1, 2, 3, 8, 9, 10, 11}. Maka blok-blok dari desain –(14, 7, 6, 3, 2) pada himpunan varitas;

B₁ = {1, 2, 3, 8, 9, 10, 11} adalah sebagai berikut:

{2,8,10};{1,8,9};{3,8,11};{2,8,10};{1,8,9};{3,9,11};{1,2,3};{2,9,11};{1,10,11};{3,9,10};{1,2,3};{2,9,11};{1,10,11};{3,9,10}.

Perhatikan bahwa desain ini mempunyai blok-blok “berulang”. Jika diambil satu blok saja dari setiap blok yang berulang, akan diperoleh desain –(7, 3, 1).

DAFTAR PUSTAKA

Budayasa, I. K. 2008. Matematika Diskrit. Surabaya: Unesa University Press

Budayasa, I. K. 1995. Matematika Distkrit I. Surabaya: Unesa University Press

Cameron, P. J. And Van Lint, J.HA. 1991. Design, Graphs, Codes and their Links, Cambridge University Press, Cambridge, U.K.

Sharma, V.K. 2004. Balanced Incomplete Block Designs. New Delhi: I.A.S.R.I Library Avenue

Cherowitzo, William. 2005. Combinatorial Designs: Balanced Incomplete Block Designs. www-math.ucdenver.edu/. Diakses pada tanggal 1 Maret 2013.