DIGRAFF CAYLEYY DARI GRRUP

Skripssi

PRO

Di

OGRAM ST

FA

iajukan untu

Mempe

Prog

Rosa

TUDI MAT

AKULTAS

UNIVERS

Y

uk Memenuuhi Salah Saatu Syarat

roleh Gelarr Sarjana Saains

gram Studi MMatematikaa

Oleh:

alia Gustari Eksi Utamii

NIM: 053114007

TEMATIKKA JURUSAAN MATEEMATIKA

S SAINS DAAN TEKNOLOGI

SITAS SANNATA DHAARMA

YOGYAKAARTA

20099

CAYLEY DIGRAPHHS OF GROOUPS

Thesis

 

MATHE

Presen

EMATICS S

SCI

nted as Parti

To Obtai

Rosa

Stude

STUDY PR

ENCE AN

SANATA

Y

ii 

ial Fulfillm

n the Sarjan

In Mathem

By:

alia Gustari

ent Number:

ROGRAM

D TECHN

DHARMA

YOGYAKA

2009

ent of the RRequirementts

na Sains Deegree

matics

Eksi Utamii

: 0531140077

MATHEMMATICS DEEPARTMEENT

NOLOGY FFACULTY

A UNIVERRSITY

ARTA

9

HALAMAN PERSEMBAHAN

Skripsi ini penulis persembahkan kepada:

Yesus Kristus & Bunda Maria

(Pegangan hidup penulis dalam setiap langkah),

Yohanes Chrisostomus Pramonco Hardioto & Elisabet Sri Rahayu

(Orang tua penulis),

Keluarga Besar Program Studi Matematika Universitas Sanata Dharma

(Khususnya mahasiswa angkatan 2005),

Albertus Aditya Budi Nugroho

(Gembulz),

Semua Pihak yang telah membantu terbentuknya skripsi ini.

v  

vii 

 

ABSTRAK

Digraf Cayley dari grup adalah gambaran grafis dari suatu grup yang

diberikan oleh himpunan pembangkitnya. Digraf ini menyediakan metode untuk

menggambarkan suatu grup, dan menghubungkan dua cabang penting dari

matematika modern yaitu grup dan graf. Digraf Cayley dari grup digunakan untuk

melihat orde dari beberapa elemen grup dan untuk menentukan nilai dari sebarang

hasil kali dari pembangkit atau inversnya.

Terdapat lintasan atau sirkuit Hamilton dalam digraf Cayley dari grup

tertentu. Lintasan Hamilton dalam digraf Cayley dari grup digunakan untuk

membuat grafik komputer dari pola perulangan tipe Escher pada bidang

hiperbolik.

viii 

 

ABSTRACT

The Cayley digraphs of groups are graphical representation of a group

given by a set of generators. These digraphs provide a method of visualizing a

group, and connect two important branches of modern mathematics, i. e. groups

and graphs. The Cayley digraphs of groups are used to see the order of some

elements of a group and to determine the value of any product of the generators or

their inverses.

There are Hamiltonian paths or circuits in Cayley digraphs of certain

groups. Hamiltonian paths in Cayley digraphs of groups are used to create

computer graphics of Escher-type repeating patterns in the hyperbolic plane.

x 

 

KATA PENGANTAR

Puji dan syukur kepada Tuhan Yang Maha Esa atas rahmat-Nya sehingga

penulis dapat menyelesaikan skripsi ini. Skripsi ini ditulis untuk memenuhi salah

satu syarat memperoleh gelar sarjana sains Program Studi Matematika.

Selama penulisan skripsi ini penulis menyadari bahwa banyak pihak yang

telah berperan besar dalam memberikan dukungan, bimbingan, maupun kerjasa-

manya. Oleh karena itu, penulis mengucapkan banyak terima kasih kepada:

1. Ibu M. V. Any Herawati, S.Si., M.Si., selaku dosen pembimbing skripsi

yang telah membimbing dan mendampingi penulis selama penulisan skripsi

ini.

2. Bapak Yosef Agung Cahyanta, S.T., M.T., selaku Dekan Fakultas Sains dan

Teknologi.

3. Ibu Lusia Krismiyati Budiasih, S.Si., M.Si., selaku Ketua Program Studi

Matematika dan dosen penguji yang telah memberikan koreksi dan saran

kepada penulis.

4. Romo Prof. Dr. Frans Susilo, SJ, selaku Dosen Pembimbing Akademik dan

dosen penguji yang telah memberikan koreksi dan saran kepada penulis.

5. Bapak Z. Tukija dan Ibu Erma Linda S. R. yang telah banyak membantu

dalam proses administrasi.

6. Perpustakaan Paingan Universitas Sanata Dharma dan seluruh karyawannya

yang telah banyak membantu dalam penyediaan bahan dan fasilitas selama

penulisan skripsi ini.

7. Bapak Y. C. Pramonco H. dan Ibu E. Sri Rahayu, selaku orang tua penulis

yang selalu mendukung penulis.

8. Teman-teman mahasiswa angkatan 2005 Program Studi Matematika.

9. Semua pihak yang telah membantu selama penulisan skripsi ini dan belum

tersebutkan namanya.

xi 

 

Penulis berharap semoga skripsi ini dapat memberikan manfaat bagi se-

mua orang yang membacanya. Apabila terdapat kesalahan penulisan dan ucapan,

penulis mohon maaf yang sebesar-besarnya.

Penulis

  

DAFTAR ISI

Halaman

HALAMAN JUDUL ………………………………………………………….. i

HALAMAN JUDUL DALAM BAHASA INGGRIS …...……………….…… ii

HALAMAN PERSETUJUAN PEMBIMBING ………………………………. iii

HALAMAN PENGESAHAN ………………………...………………………. iv

HALAMAN PERSEMBAHAN ………………………………………………. v

PERNYATAAN KEASLIAN KARYA ………………………………………. vi

ABSTRAK ………………………………………………………….………… vii

ABSTRACT ……………………………………………………………...…… viii

LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH

UNTUK KEPENTINGAN AKADEMIS ………………………………….….. ix

KATA PENGANTAR ………………………………………………………… x

DAFTAR ISI ………………………………………………………………….. xii

DAFTAR TABEL …………………………………………………………….. xiv

DAFTAR GAMBAR …………………………………….………..……….…. xv

BAB I PENDAHULUAN ………………………………….………...……..… 1

A. 1

B. Rumusan Masalah ……………………….………………...………... 3

Latar Belakang Masalah …………….……………………………….

Batasan Masalah …………………………….…………...……...…..

Manfaat Penulisan ………………………………………………...…

Sistematika Penulisan ………………………………….……...…….

Teori Grup …………………………….……………………….....….

2. Grup Berhingga dan Subgrup …………….…………….…….…

4. Grup Siklik dan Pembangkit ………………….…….……….…. 12

C. 3

D. Tujuan Penulisan ………………………………….……...…………. 4

E. 4

F. Metode Penulisan ………………………………………………….... 4

G. 5

BAB II TEORI GRUP DAN TEORI GRAF ……………………………...….. 7

A. 7

1. Grup ………………………………..……………………...……. 7

10

3. Darab Langsung ……………………………...….…………...…. 12

xii  

  

xiii  

5. Grup Permutasi …………..……………………….……….....….

8. Homomorfisma dan Isomorfisma ……………………………….

Graf Berarah Atau Digraf ……………………….………...….…

RAF CAYLEY DARI GRUP …………………………...………

tasan dan Sirkuit Hamilton Dalam Digraf Cayley dari Grup …....

BAB VI AP

AFIK KOMPUTER DARI POLA PERULANGAN TIPE

tode Escher …………………………………………………

UTUP …………………………….……………….……...…

an ………………………………………..…………………

DAFTAR PUSTAKA ……………………………………………...………….

19

6. Grup Dihedral ……...…………….……………………….…….. 26

7. Koset, Teorema Lagrange, Subgrup Normal, dan Grup Faktor ... 30

35

B. Teori Graf …………………………………………….……...…….... 37

1. 37

2. Lintasan dan Sirkuit Hamilton ………………….…...…...…….. 39

BAB III DIG 43

A. Digraf Cayley dari Grup ……………………………………….……. 43

B. Lin 52

LIKASI DIGRAF CAYLEY DARI GRUP UNTUK MEMBUAT

GR

ESCHER PADA BIDANG HIPERBOLIK …….……………………. 63

A. Me ……. 63

B. Metode Douglas Dunham …………………………….……………... 67

BAB V PEN …… 74

A. Kesimpulan …………………………………………….…...….……. 74

B. Sar .……. 75

76

  

DAFTAR TABEL

Halaman

Tabel 2. 1 Beberapa Contoh Grup ………………………………………........ 9

Tabel 2. 2 Tabel Operasi untuk ………………………….…………........… 18

Tabel 2. 3 Tabel Operasi untuk ……….………………….……………....… 24

Tabel 2. 4 Grup Selang-seling untuk Permutasi Genap dari {1, 2, 3, 4} ...... 26

Tabel 2. 5 Tabel Operasi untuk …………………………………….……… 29

xiv  

  

DAFTAR GAMBAR

Halaman

Gambar 2. 1 Graf G …………………………………………………………... 38

Gambar 2. 2 Graf Berarah G ………………….……………………………… 39

Gambar 2. 3 Graf Sederhana yang Memuat Lintasan dan Sirkuit ……..….…. 40

Gambar 2. 4 Salah Satu Penyelesaian Teka-Teki “Perjalanan Keliling

Dunia” …………………………………………………...……… 42

Gambar 2. 5 Graf Sederhana G1, G2, dan G3 …………………………………. 42

Gambar 3. 1 Digraf Cay({1}: ) ………………………………………….…… 45

,

Gambar 3. 6 Digraf Cay({(12)(34), (123)}: ) ………………..……….......… 49

Da

53

Gambar 3. 10

), dan (a,

0), ( 1)}: ……

, 1)}:

Gambar 3. 15 Digraf Cay({(r, 0), (f, 0), (e, 1)}: ) ………….…….…. 62

Poincare pada Bida

65

Gambar 4. 3

Gambar 3. 2 Digraf Cay({(1, 0), (0, 1)}: ) ………………..………….. 46

Gambar 3. 3 Digraf Cay( : ) ………………………...……………… 47

Gambar 3. 4 Digraf Cay({(12), (123)}: ) …………………………………… 48

Gambar 3. 5 Digraf Cay({(12), (13)}: ) ……………………….……………. 48

Gambar 3. 7 Digraf Cay({a, b}: ) ……………………………...…….……… 50

Gambar 3. 8 Digraf Cay({a, b}: ) ……………………………...…………… 51

Gambar 3. 9 Lintasan Hamilton lam Digraf Cay({(1, 0), (0, 1)}: )

dari (0, 0) ke (2, 1) ………………………………...………..…..

Sirkuit Hamilton Dalam Digraf Cay({a, b}: ) ………...…..…. 53

Gambar 3. 11 Digraf Cay({(1, 0), (0, 1)}: ) …………...……………. 55

Gambar 3. 12 Simpul (a, b), ( 1, 1 1) ………………….. 55

Gambar 3. 13 Digraf Cay({(1, 0, ) ……...……………. 57

Gambar 3. 14 Digraf Cay({(r, 0), (f, 0), (e ) ……...……………. 61

Gambar 4. 1 Teselasi Segitiga Dalam Model Cakram ng

Hiperbolik …………………………………….………………… 64

Gambar 4. 2 Cetakan Asli Circle Limit I Milik Escher ………………………

Terjemahan Komputer dari Desain Dalam Cetakan Circle Limit I

Milik Escher ……………………………………………………. 66

Gambar 4. 4 Graf Cayley dari Grup [6, 4] dengan Lintasan Hamilton ….…… 69

xv  

  

xvi  

Gambar 4. 5 Supermotif Pusat untuk Circle Limit I …………………...…….. 70

Gambar 4. 6 Lintasan Hamilton Dalam Graf Koset dari [6, 4] ………...…….. 71

Gambar 4. 7 Pohon Perentang Dalam Graf Koset [6, 4] …………….……….. 72

  

BAB I

PENDAHULUAN

A. Latar Belakang Masalah

Dunia matematika memiliki berbagai macam cabang di dalamnya. Dari

berbagai macam cabang tersebut, di antaranya adalah aljabar abstrak dan

matematika diskret. Aljabar abstrak dan matematika diskret mempelajari topik-

topik yang berbeda. Dalam aljabar abstrak dibahas mengenai grup, ring, lapangan,

beserta sifat-sifatnya. Sedangkan dalam matematika diskret dibahas mengenai

relasi, graf, aljabar Boole, dan kombinatorik. Di antara topik-topik tersebut

terdapat dua topik yang cukup menarik, yaitu grup dan graf.

Ketika membicarakan tentang aljabar abstrak atau struktur aljabar, hal

pertama yang muncul adalah grup. Grup menjadi topik yang sangat penting dalam

aljabar abstrak karena topik ini dibahas pertama kali dalam banyak buku aljabar

abstrak. Grup dan sifat-sifatnya juga mendasari topik-topik yang dibahas

selanjutnya dalam aljabar abstrak, seperti ring dan lapangan. Begitu juga dalam

digraf Cayley dari grup, grup menjadi topik yang sangat penting karena akan

dibentuk penggambaran dari suatu grup dengan menggunakan himpunan

pembangkitnya.

Salah satu topik yang dibahas dalam teori graf dan digunakan dalam

digraf Cayley dari grup yaitu graf berarah atau digraf. Graf berarah atau digraf

merupakan himpunan berhingga dari titik-titik, yang disebut vertex atau simpul,

1  

2  

dan himpunan busur berpanah, yang disebut arc atau busur, yang menghubungkan

beberapa vertex atau simpul. Digraf dapat digunakan untuk menyatakan relasi

antara unsur-unsurnya (simpul dan busur). Digraf memiliki peranan yang sangat

penting dalam digraf Cayley dari grup karena menjadi bentuk penggambaran dari

suatu grup.

Grup dan graf adalah dua cabang penting dalam matematika modern.

Antara grup dan graf dihubungkan dalam satu topik yaitu digraf Cayley dari grup.

Gagasan ini mula-mula didapatkan oleh seorang matematikawan bernama Arthur

Cayley pada tahun 1878. Digraf Cayley dari grup merupakan gambaran grafis dari

suatu grup yang diberikan oleh himpunan pembangkitnya. Sebenarnya digraf

Cayley dari grup merupakan topik yang sangat menarik tetapi tidak semua buku

aljabar memuat topik ini. Digraf Cayley dari grup menyediakan metode untuk

menggambarkan suatu grup sehingga grup dapat lebih mudah dipahami karena

adanya gambaran nyata berupa digraf.

Misalkan G adalah grup berhingga dan S adalah himpunan pembangkit

untuk G. Digraf Cayley dari grup G dengan himpunan pembangkit S, yang

dinotasikan dengan Cay(S:G), dapat didefinisikan sebagai berikut.

1. Setiap elemen dari G adalah simpul dari Cay(S:G).

2. Untuk x dan y di G, terdapat sebuah busur dari x ke y jika dan hanya

jika xs = y untuk suatu s S.

Digraf Cayley dari grup melibatkan dua teori penting, yaitu teori grup

dan teori graf. Beberapa pokok bahasan dalam teori grup yang berhubungan

dengan topik ini antara lain grup siklik dan pembangkit, grup permutasi, grup

  

3  

dihedral, darab langsung. Sedangkan beberapa pokok bahasan dalam teori graf

yang berhubungan dengan topik ini antara lain graf berarah atau digraf, lintasan

dan sirkuit Hamilton. Pembahasan mengenai lintasan dan sirkuit Hamilton

berhubungan dengan syarat perlu dan syarat cukup sangat penting dalam

membahas digraf Cayley dari grup. Lintasan dan sirkuit Hamilton akan digunakan

dalam pengaplikasian digraf Cayley dari grup.

B. Rumusan Masalah

Pokok permasalahan yang akan dibahas dalam skripsi ini antara lain:

1. Apakah yang dimaksud dengan digraf Cayley dari grup?

2. Apa saja landasan teori yang dibutuhkan untuk membentuk digraf

Cayley dari suatu grup?

3. Bagaimana membentuk digraf Cayley dari suatu grup?

4. Bagaimana aplikasi digraf Cayley dari grup?

C. Batasan Masalah

Batasan masalah dalam skripsi ini antara lain:

1. Membahas mengenai digraf Cayley yang terbentuk dari suatu grup.

2. Membahas aplikasinya, yaitu untuk membuat grafik komputer dari

pola perulangan tipe Escher pada bidang hiperbolik, tetapi tidak

menyertakan algoritmanya.

  

4  

D. Tujuan Penulisan

Skripsi ini bertujuan untuk memenuhi salah satu persyaratan untuk

memperoleh gelar Sarjana Sains dalam bidang matematika. Selain itu, tujuan dari

penulisan skripsi ini adalah:

1. Mempelajari tentang pembentukan digraf Cayley dari suatu grup.

2. Mengetahui aplikasi digraf Cayley dari grup.

E. Manfaat Penulisan

Manfaat yang diharapkan dari penulisan skripsi ini adalah:

1. Dapat memahami mengenai pembentukan digraf Cayley dari suatu

grup.

2. Dapat mengetahui tentang aplikasi digraf Cayley dari grup.

F. Metode Penulisan

Penulisan skripsi ini menggunakan metode studi pustaka, yaitu dengan

menggunakan buku-buku, jurnal-jurnal, dan makalah-makalah yang telah

dipublikasikan dalam media cetak maupun internet sehingga dalam skripsi ini

tidak ditemukan hal baru.

  

5  

G. Sistematika Penulisan

BAB I PENDAHULUAN

A. Latar Belakang Masalah

B. Rumusan Masalah

C. Batasan Masalah

D. Tujuan Penulisan

E. Manfaat Penulisan

F. Metode Penulisan

G. Sistematika Penulisan

BAB II TEORI GRUP DAN TEORI GRAF

A. Teori Grup

1. Grup

2. Grup Berhingga dan Subgrup

3. Darab Langsung

4. Grup Siklik dan Pembangkit

5. Grup Permutasi

6. Grup Dihedral

7. Koset, Teorema Lagrange, Subgrup Normal, dan Grup

Faktor

8. Homomorfisma dan Isomorfisma

B. Teori Graf

1. Graf Berarah Atau Digraf

2. Lintasan dan Sirkuit Hamilton

  

6  

  

BAB III DIGRAF CAYLEY DARI GRUP

A. Digraf Cayley dari Grup

B. Lintasan dan Sirkuit Hamilton Dalam Digraf Cayley dari Grup

BAB IV APLIKASI DIGRAF CAYLEY DARI GRUP UNTUK

MEMBUAT GRAFIK KOMPUTER DARI POLA PERULANGAN

TIPE ESCHER PADA BIDANG HIPERBOLIK

A. Metode Escher

B. Metode Douglas Dunham

BAB V PENUTUP

A. Kesimpulan

B. Saran

BAB II

TEORI GRUP DAN TEORI GRAF

A. Teori Grup

1. Grup

Definisi 2. 1

Misalkan G adalah himpunan. Operasi biner pada G adalah fungsi yang

mengawankan setiap pasangan terurut elemen-elemen di G dengan suatu elemen

di G.

Dengan kata lain, operasi biner pada himpunan S adalah suatu

pemetaan dari ke S. Untuk setiap di , elemen dari S

dinotasikan dengan . Operasi biner memasangkan sebarang a dan b

elemen-elemen dari S dengan elemen dari S. Dengan demikian, dapat

dikatakan bahwa operasi adalah operasi biner pada S jika operasi tersebut

, ,

tertutup dalam S, yaitu adalah elemen dari S.

Contoh 2. 1

Misalkan dan · adalah operasi biner biasa dari penjumlahan dan perkalian

dalam , dan misalkan | . Tentukan apakah H tertutup terhadap

(a) penjumlahan dan (b) perkalian.

7  

8  

Untuk bagian (a), hanya dibutuhkan pengamatan bahwa 1 dan

di H, tetapi bahwa 1 4 dan 5 . Sehingga H tidak tertutup

terhadap penjumlahan.

1

2 4 5

bahwa , sehingga H tertutup terhadap perkalian.

Definisi 2. 2

Misalkan G adalah himpunan tak kosong bersama dengan operasi biner (biasa

disebut perkalian) yang mengawankan ke setiap pasangan terurut , elemen-

elemen di G dengan suatu elemen di G dinotasikan dengan . G adalah grup

terhadap operasi ini jika tiga sifat berikut dipenuhi.

untuk semua a, b, c di

titas. Terdapat sebuah elemen e (disebut identitas) di G sedemikian

pat b di G (disebut invers dari a)

Jika suatu grup mempunyai sifat komutatif sedemikian hingga

untuk setiap pasangan elemen-elemen a dan b di grup G, maka dapat dikatakan

grup tersebut adalah grup komutatif atau grup Abel.

Untuk bagian (b), andaikan dan . Menggunakan pengertian

bahwa r dan s di H, dapat dilihat bahwa harus terdapat bilangan bulat n dan m di

sedemikian hingga dan . Akibatnya, .

Dengan karakteristik elemen di H dan kenyataan bahwa , ini berarti

1) Asosiatif. Operasi bersifat asosiatif jika

G.

2) Iden

hingga untuk semua a di G.

3) Invers. Untuk setiap elemen a di G terda

sedemikian hingga .

9  

Beberap

Elemen

s Grup

Abel

a contoh grup diberikan dalam Tabel 2. 1 di bawah ini.

Tabel 2. 1

Beberapa Contoh Grup

Grup Operasi Identitas Bentuk Inver

penjumlahan 0 k –k ya

perkalian 1 m/n,

m, n>0

n/m ya

penjumlahan

mod n

0 k n–k ya

perkalian 1 x 1/x ya

GL(2, F) perkalian

matriks

1 01 ,

ad–bc≠0

0

tidak

U( dengan

fpb(k, n

elesaian untuk

kx=1 mod n

han

antar

(0, ..., 0) (a1, ..., an) (–a1, –a2, ..., –an) ya

SL(2, F) perkalian 1 0 ,

ad–bc=1

tidak

n) perkalian

mod n

penjumla

1 k,

)=1

peny ya

komponen

matriks 0 1

Keterangan

adalah himpunan bilangan bulat;

:

10  

adalah bilangan rasional positi

adalah himpunan bilangan bulat modulo n;

adalah himpunan bilangan real tak nol;

GL(2, F) adalah himpunan matriks 2 2 dengan entri-entrinya bilangan real dan

determinannya tak nol;

U(n) adalah himpunan bilangan bulat k yang kurang dari n dan , 1

untuk 1

| , , . . . , ;

2

real), (bilangan kompleks), atau (bilangan bulat

t seba ng dari , , , atau .

Definisi 2. 3

Banyaknya elemen dari suatu grup G (berhingga atau tak hingga), dinotasikan

dengan | |, disebut orde dari G. Jika | | berhingga, maka G disebut grup

erhingga dan jika | | tak hingga, maka G disebut grup tak hingga.

0, 1, 2, … , 1 untuk 1 adalah n atau | | dan

adalah grup berhingga karena | | berhingga sehingga adalah grup Abel

berhingga karena juga adalah grup Abel.

himpunan f;

;

adalah himpunan , , . . . ,

SL(2, F) adalah himpunan matriks 2 dengan entri-entrinya dari (bilangan

rasional), (bilangan

modulo p dengan p bilangan prima) dan determinannya 1;

F dapa ra

2. Grup Berhingga dan Subgrup

b

Contoh 2. 2

Orde dari

11  

Definisi 2. 4

Orde dari suatu elemen a dalam sutu grup adalah bilangan bulat positif terkecil

n sedemikian hingg . Dalam notasi penjumlahan menjadi

G

a . Jika

tidak terdapat bilangan bulat seperti itu, maka a dikatakan mempunyai orde tak

hingga. Orde dari suatu elemen a dinotasikan dengan | |.

, 9 terhadap operasi penjumlahan

modulo 10, karena 1 · 2 2, 2 · 2 4, 3 · 2 6, 4 · 2 8, 5 · 2 0, dapat

wa |2| 5. Dengan cara yang sama, dapat ditunjukkan bahwa

Definisi 2. 5

Jika H adalah himpunan bagian dari grup G dan H adalah grup terhadap operasi

dari G, maka H disebut subgrup dari G, dinotasikan dengan H ≤ G atau G ≥ H.

atau G > H berarti H ≤ G tetapi H ≠ G, subgrup ini disebut subgrup

bgrup dari G yang

ejati dar . Jika { adalah elemen identitas dari G

t subg

disebut dari G.

Contoh 2. 4

Satu-satunya subgrup sejati tak trivial dari 0, 1, 2, 3 adalah {0, 2}.

Contoh 2.3

Dengan mengingat grup 0, 1, 2, …

diketahui bah

|0| 1, |7| 10, |5| 2, |6| 5.

Notasi H < G

sejati dari G. Sedangkan, su terdiri dari G atau dirinya sendiri

disebut subgrup tak s i G e} , maka

subgrup {e} disebu rup trivial dari G, sedangkan subgrup yang bukan {e}

subgrup tak trivial

Perhatikan bahwa {0, 3} bukan subgrup dari , karena {0, 3} tidak tertutup

terhadap penjumlahan. Sebagai contoh, 3 3 2 dan 2 0, 3 .

12  

3. Darab Langsung

Definisi 2. 6

Misalkan {G1, G2, ..., Gn} adalah himpunan berhingga dari grup. Darab langsung

1 2 Gn, ditulis sebagai … , adalah himpunan semua

i adalah elem i

, … , dengan dilakukan

engan operasi pada Gi.

5, 7 , 10 1, 3, 7, 9 ,

9 , 7, 1 , 7, 3 , 7,

sedangkan dua komponen kedua dikerjakan den

modulo 10.

4. Grup Siklik dan Pembangkit

Invers dari suatu elemen a dari suatu grup dinotasikan dengan .

Notasi ini digunakan untuk suatu grup terhadap operasi perkalian.

dari G , G , ...,

pasangan terurut n komponen dengan komponen ke- en dari G .

Dengan simbol, … , , … , | , di mana

, , … , , , … , ,

d

Contoh 2. 5

8 1, 3,

8 10 1, 1 , 1, 3 , 1, 7 , 1, 9 , 3, 1 , 3, 3 , 3, 7 , 3, 9 , 5, 1 ,

5, 3 , 5, 7 , 5, 7 , 7, 9 .

Hasil kali (3, 7)(7, 9) = (5, 3), karena dua komponen pertama dikerjakan dengan

perkalian modulo 8, gan perkalian

13  

Definisi 2. 7

Jika n adalah bilangan bulat positif, maka digunakan untuk menunjukkan hasil

kali dari a dan dirinya sendiri untuk n faktor, yaitu · · … ·

.

Jika 0, maka , dengan e adalah elemen identitas di grup tersebut. Jika

a .

Jika

Teorema 2. 1

ika a adalah suatu elemen dari suatu grup dan m, n adalah bilangan bulat, maka

eksponen berikut.

Bukti:

Akan dibuktikan menggunakan prinsip induksi matematis.

Untuk n positif.

Persamaan tersebut benar untuk n = 1, karena

. Andaikan persamaan tersebut benar untuk n = k, berarti

. Kemudian akan dibuktikan persamaan tersebut benar

untuk n = k + 1. Perhatikan bahwa

.

n adalah bilangan bulat negatif, mak

· · , maka .

J

berlaku hukum

1) .

2) .

1) Misalkan m tetap dan n variabel.

a)

14  

b) Untuk n negatif.

Akan dibuktikan persamaan tersebut benar untuk n = −k dengan

kan bahwa . Perhati

· · … ·

· · … ·

.

Dengan cara yang sama, dapat dibuktikan untuk n tetap dan m variabel.

2) Misalkan m tetap dan n variabel.

a) Untuk n positif.

Persamaan tersebut benar untuk n = 1, karena

. Andaikan persamaan tersebut benar untuk n =

k, berarti . Kemudian akan dibuktikan persamaan tersebut

benar untuk

.

b) Untuk n negatif.

engan

Dengan cara yang sama, dapat dibukti

n = k + 1. Perhatikan bahwa

Akan dibuktikan persamaan tersebut benar untuk n = −k d

. Perhatikan bahwa

.

kan untuk n tetap dan m variabel.

■

15  

Contoh 2. 6

, , , .

Jika G adalah sua

Bukti:

(ab)(b-1a-1) = ((ab)b-1)a-1 (hukum asosiatif)

= (a(bb-1))a-1 (hukum asosiatif)

Sama halnya dengan (b-1a-1)(ab) = e. Karena itu, dengan definisi (aa-1 = a-1a = e

)-1 = b-1a-1.

■

Definisi 2. 8

grup siklik jika terdapat elemen a di G sedemikian hingga

} disebut

himpunan pembangkit dari G. Notasi menyatakan bahwa G adalah grup

bangkit a.

adalah grup siklik dengan pembangkit 1 dan –1.

odulo n adalah grup siklik dengan pembangkit 1 dan 1 1.

Tidak seperti yang hanya mempunyai dua pembangkit, dapat mempuny

lebih dari satu pembangkit bergantung pada n yang diberikan.

Teorema 2. 2

tu grup, maka (ab)-1 = b-1a-1 untuk semua a dan b di G.

= (ae)a-1 = aa-1 = e.

),

(ab

Grup G disebut

| . Elemen a tersebut disebut pembangkit dari G dan {a

siklik dengan pem

Contoh 2. 7

Grup terhadap penjumlahan

Demikian juga untuk , grup 0, 1, 2, … , 1 untuk 1 terhadap

penjumlahan m

ai

16  

Misalkan 1 3 5 7 . Untuk memeriksanya, sebagai

3 8, … a

8, … 2, 4, 6, 0 .

a

bgrup il dari G yang mem

h G, mak

terdapat himpunan berhingga | yang membangkitkan G, maka G

dikatakan dibangkitkan secara berhingga dan ditulis | . Jika

1, 2, … , , maka , , … , .

Teorema 2. 3

Jika G adalah grup dan en subgrup

G yang dibangkitkan oleh | tepatnya adalah elemen-elemen dari G yang

berupa hasil kali berhingga dari pangkat bulat dari ai, di mana suatu pangkat ai

tertentu dapat terjadi beberapa kali dalam hasil kali tersebut.

Menurut Definisi 2. 8, H adalah subgrup terkecil dari G yang memuat | .

H dan

contoh, 3 , perhatikan bahwa 3 3, 3 3 8, 3 3

dalah himpunan 3, 6, 1, 4, 7, 2, 5, 0 . Sehingga 3 adalah

pembangkit dari . Tetapi 2 bukan pembangkit dari karena 2

2, 2 2 8, 2 2 2

Definisi 2. 9

Misalk n G adalah grup dan untuk dengan I adalah sebarang

himpunan indeks. Su terkec uat | disebut

subgrup yang dibangkitkan oleh | . Jika subgrup ini adala a

| dikatakan membangkitkan G dan ai disebut pembangkit dari G. Jika

untuk , maka elemen-elem H dari

Bukti:

Akan dibuktikan bahwa K = H, berarti harus dibuktikan bahwa K H K.

17  

Andaikan K menyatakan himpunan dari semua hasil kali berhingga dari pangkat

bulat dari ai. Misalkan … . Maka dan

· · … ·

, karena sifat-sifat subgrup. Sehingga

. … . Maka K H

tkan bahwa K adalah subgrup dari H yang memuat | , maka

ali elem

osiatif. Misalkan

… . Sehingga

… …

.

Untuk , dengan Teorem

… … .

Sebagai contoh, (a1)3(a2)2(a1)-7 berada di K dan [(a1)3(a2)2(a1)-7]-1 = (a1)7(a2)-2(a1)-3

berada di K lagi.

H dan K memuat | karena

| , maka H K.

Akan diperliha

H K.

Perhatikan bahwa hasil k en di K adalah di K lagi. Misalkan,

… . Sehingga … .

Perhatikan juga bahwa hasil kali elemen di K memenuhi sifat as

…

…

… … .

Karena (ai)0 = e, diperoleh

a 2. 2 dapat diperoleh

Jadi, K adalah subgrup dari

sehingga | . Karena H adalah subgrup terkecil yang memuat

18  

Jadi, terbukti bahwa K = H.

■

Contoh 2. 8

1, 0 , 0, 1 artinya grup dibangkitkan oleh (1, 0) dan

Dengan menggunakan Teorema 2. 3, elemen-elemen dari grup

n(1, 0) + m(0, 1)| n, m } = {(0(1, 0) + 0(0, 1)), (0(1, 0) + 1(0, 1))

1(0 )), (0(1, 0) + 2(0, 1)), (2(1, 0) + 0(0, 1)),

)), …} = {(0, 0), (0, 1),

(1, 0), (1, 1), (2, 0), (2, 1)}.

dinyatakan dengan , , , , , , , . Tabel

Tabel Operasi untuk

(0, 1).

adalah { ,

(1(1, 0) + 0(0, 1)), (1(1, 0) + , 1

(1(1, 0) + 2(0, 1)), (2(1, 0) + 1(0, 1)), (2(1, 0) + 2(0, 1

Contoh 2. 9

Grup kuarternion

operasi atau tabel Cayley untuk adalah sebagai berikut.

Tabel 2. 2

19  

Grup kuarternion juga dapat din ,

, . Dengan kata lain, dibangkitkan oleh a

yatakan dengan , |

dan b yang memenuhi

persamaan , , dan . Berikut ini akan diperlihatkan

ibangkitkan oleh a dan b tersebut.

5. rup Per utasi

Definisi 2. 10

ungsi : disebut satu-satu atau injektif jika dan hanya jika bila

m

setiap , terdapat sedemikian

ika adalah satu-satu dan pada.

bahwa d

G m

F

aka . Fungsi : disebut pada atau surjektif jika untuk

sehingga . Fungsi :

disebut korespondensi satu-satu atau bijektif j

20  

Contoh 2. 10

Fungsi : dengan bukan satu-satu karena 2 2 4

tetapi 2 2 dan tidak pada karena daerah hasilnya adalah himpunan bagian

jati dari semua bilangan tak negatif di . Akan tetapi : dengan

satu-satu dan pada .

Definisi 2. 11

Misalkan : dan : . Komposisi dan , dinotasikan dengan

, adalah pemetaan dari A ke C, dinotasikan dengan : ,

didefinisikan dengan untuk semua a di A.

Definisi 2. 12

Permutasi dari suatu himpunan A adalah fungsi bijektif dari A ke A.

Contoh 2. 11

utasi himp kan deng

2, α(2) = 3,

t dapat dinyatakan dengan cara lain, yaitu 12

23

31

44 dan

12

21

34

43 . Komposisi permutasi dikerjakan dari kanan ke kiri. Misalkan

1 2 31

44

12

21

34

43

13

22

34

41 . Sebagai contoh, 3 berada

= α(β(1))

a 2. 4

Jika A adalah suatu himpunan tak kosong dan SA adalah himpunan semua

permutasi dari A, maka SA merupakan suatu grup terhadap komposisi permutasi.

se

Misalkan perm α dan β dari unan {1, 2, 3, 4} dinyata an α(1) =

α(3) = 1, α(4) = 4 dan β(1) = 2, β(2) = 1, β(3) = 4, β(4) = 3. Permutasi

tersebu

2 3

di bawah 1, karena (αβ)(1) = α(2) = 3.

Teorem

21  

Bukti:

ktikan bahwa (SA, ◦) meAkan dibu menuhi tiga syarat di dalam Definisi 2. 2, yaitu

asosiatif, mempunyai elemen identitas, dan mempunyai elemen invers. Tetapi

sebelumnya akan dibuktikan bahwa (SA, ◦) tertutup terhadap komposisi permutasi.

Andaikan π1 dan π2 adalah permutasi dari A. Menurut teorema tentang komposisi

fungsi, m 1 2 a1, a2 A

π1 ◦ π2 bersifat satu-satu, j (a1) = (π1 ◦

a2. Akan dibuktikan bahwa π1 ◦ π2 bersifat satu-satu. Karena (π1 ◦

π1

bersifat satu-satu, berlaku π2(a1) = π2(a2), dan karena π2 bersifat satu-satu juga,

1 2. Terbukti bahwa (π1 ◦ π2)(a1) = (π1 ◦ π2)(a2) → a1 = a2. Oleh karena

1 2

1 2

setiap b A, terda

untuk setiap a’ A, terdapat a’’ A sehingga π2(a’’) = a’. Oleh karena itu, (π1 ◦

π2)(a’’) = π1(π2(a’’)) = π1(a’) = b, sehingga π1 ◦ π2 bersifat pada. Maka m

dari A. Terbukti bahwa π1 ◦ π2

A, (π1 ◦ (π2 ◦ π3))(a) = ((π1 ◦ π2) ◦ π3)(a). Misalkan a A. Berlaku (π1 ◦ (π2 ◦ π3))(a)

= π1((π2 ◦ π3)(a)) = π1(π2(π3(a)) = (π1 ◦ π2)(π3(a)) = ((π1 ◦ π2) ◦ π3)(a), sehingga

aka π ◦ π juga adalah fungsi dari A ke A. Misalkan .

Komposisi permutasi ika dipenuhi (π1 ◦ π2)

π2)(a2) → a1 =

π2)(a1) = (π1 ◦ π2)(a2), sehingga diperoleh π1(π2(a1)) = π1(π2(a2)). Karena

berlaku a = a

itu, π ◦ π bersifat satu-satu.

Akan dibuktikan bahwa π ◦ π bersifat pada, yaitu untuk setiap b A, terdapat a

A sehingga (π1 ◦ π2)(a) = b. Misalkan b A. π1 bersifat pada, berarti untuk

pat a’ A sehingga π1(a’) = b, dan π2 bersifat pada, berarti

enurut

Definisi 2.13, π1 ◦ π2 merupakan suatu permutasi

SA.

Akan dibuktikan bahwa (SA, ◦) memenuhi sifat asosiatif. Andaikan π1, π2, π3 SA.

Akan dibuktikan π1 ◦ (π2 ◦ π3) = (π1 ◦ π2) ◦ π3. Akan ditunjukkan, untuk setiap a

22  

diperoleh (π1 ◦ (π2 ◦ π3))(a) = ((π1 ◦ π2) ◦ π3)(a), untuk setiap a A. Jadi, menurut

Definisi 2. 11 diperoleh π1 ◦ (π2 ◦ π3) = (π1 ◦ π2) ◦ π3. Terbukti bahwa sifat asosiatif

dipenuhi.

Akan dibuktikan bahwa (SA, ◦) mempunyai elemen identitas. Permutasi i, di mana

i(a) = a, untuk setiap a A, merupakan elemen identitas di SA. Misalkan π SA

dan i permutasi identitas di SA. Akan dibuktikan bahwa π ◦ i = i ◦ π = π. Akan

ditunjukkan bahwa (π ◦ i)(a) = (i ◦ π)(a) = π(a), untuk setiap a A. Karena

berlaku i(a) = a, untuk setiap a A, diperoleh (π ◦ i)(a) = π(i(a)) = π(a) = i(π(a)) =

(i ◦ π)(a) sehingga (π ◦ i)(a) = (i ◦ π)(a) = π(a), akibatnya π ◦ i = i ◦ π = π. Terbukti

bahwa terdapat elemen identitas i SA, sehingga π ◦ i = i ◦ π = π.

Akan dibuktikan bahwa setiap elemen di (SA, ◦) mempunyai invers. Untuk setiap π

π

-1 -1 -1 -1 -1

Jadi, π ◦ π-1 dan π-1 ◦ π merupakan permutasi identitas dari himpunan A, sehingga

berlaku π ◦ π-1 = π-1 ◦ π = i. Terbukti bahwa untuk setiap π S , terdapat elemen

invers π-1 SA, sehingga π ◦ π-1 = π-1 ◦ π = i.

Jadi, terbukti bahwa S membentuk grup terhadap komposisi permutasi.

■

Grup permutasi dari suatu himpunan A adalah himpunan permutasi dari A yang

membentuk grup terhadap komposisi fungsi.

SA, terdapat elemen invers π-1 SA, yaitu permutasi yang membalik arah fungsi

, di mana untuk setiap a, a’ A, π(a’) = a ↔ π-1(a) = a’. Misalkan a, a’ A.

Karena berlaku i(a) = a, dan jika π(a’) = a maka π-1(a) = a’, akibatnya i(a) = a =

π(a’) = π(π (a)) = (π ◦ π )(a) dan i(a’) = a’ = π (a) = π (π(a’)) = (π ◦ π)(a).

A

A

Definisi 2. 13

23  

Definisi 2. 14

Misalkan A = {1, 2, …, n}. Himpunan semua permutasi dari A disebut grup

simetri berderajat n dan dinotasikan dengan Sn. Elemen dari Sn mempunyai bentuk

1 2

S m mpunyai 1 · … · 3 · 2 · 1 ! elemen.

1 3 2 2 1 3 3 2 1

Terdapat notasi lain yang biasa digunakan untuk menyatakan permutasi

1 2 3 4 5 6

. Siklis yang hanya mempunyai satu

tas dapat

ditulis α = (12)(346).

1 2 …… .

n e

Contoh 2. 12

Misalkan S3 menyatakan himpunan semua fungsi satu-satu dari {1, 2, 3} ke

dirinya sendiri. S3 terhadap komposisi fungsi adalah grup dengan enam elemen,

yaitu

1 2 31 2 3 , 1 2 3

2 3 1 , 1 2 33 1 2 ,

1 2 3 , 1 2 3 , 1 2 3 .

yang disebut notasi siklis. Misalkan permutasi 2 1 4 6 5 3 dalam

notasi siklis dinyatakan dengan α = (12)(346)(5) karena 1→2→2→1,

3→4→4→6→6→3, dan 5→5. Suatu pernyataan dari bentuk (α1, α2, …, αm)

disebut siklis dengan panjang m atau siklis-m

entri dapat dihilangkan atau tidak ditulis. Misalkan permutasi α di a

24  

Contoh 2. 13

Enam elemen dari S3 dalam notasi siklis dinyatakan dengan ε = (1)(2)(3) = (1), α

2 β = (1)(23)=(23), αβ = (12)(3) = (12), α2β = (13)(2) = (13).

S

Tabel 2. 3

Tabel Operasi untuk

(1) (12) (13) 3) (123) (132)

= (123), α = (132),

Jadi, 3 = {(1), (12), (13), (23), (123), (132)}. Tabel operasi atau tabel Cayley

untuk adalah sebagai berikut.

(2

(1) (1) (12) (13) (23) (123) (132)

(12) (12) (1) (132) (123) (23) (13)

(13) (13) (123) (1) (132) (12) (23)

(23) (23) (132) (123) (1) (13) (12)

(123) (123) (13) (23) (12) (132) (1)

(132) (132) (23) (12) (13) (1) (123)

Teorem

suatu hasil kali dari siklis

banyaknya genap, maka setiap dekomposisi α ke dalam suatu hasil kali dari siklis-

2 harus mempunyai siklis-2 yang jumlahnya genap.

Dengan simbol, jika α = β1β2 … βr dan α = γ1γ2 … γs, di mana β dan γ adalah

siklis-2, maka r dan s adalah keduanya genap atau keduanya ganjil.

a 2. 5

Jika suatu permutasi α dapat dinyatakan sebagai -2 yang

25  

Bukti:

ahwa β1β2 … βr = γ1γ2 … γs menyatakan ε = (γ1γ2 … γs)(β1β2 … βr)-1 =

γ1γ2 … γs βr-1 … β2

-1β1-1 = γ1γ2 … γs βr … β2β1, karena invers dari siklis-2 adalah

. Sehingga dengan lemma yang menyatakan bahwa jika ε = β1β2 …

r

■

uatu permuta ang da inyata ebagai l kali iklis g

aknya gen ang d permutasi genap tu pe yan t

takan sebagai hasil kali dari si ang banyaknya ganjil yang disebut

utasi gan

utasi genap dari bol dinotasikan dengan An

berderajat n.

An mempunyai !

Perhatikan b

dirinya sendiri

β , di mana β adalah siklis-2, maka r adalah genap (lemma dan buktinya dapat

dilihat dalam buku Contemporary Abstract Algebra, halaman 98-99), menjamin

bahwa s + r adalah genap. Ini menghasilkan bahwa r dan s adalah keduanya genap

atau keduanya ganjil.

Definisi 2. 15

S si y pat d kan s hasi dari s -2 yan

bany ap y isebut . Sua rmutasi g dapa

dinya klis-2 y

perm jil.

Definisi 2. 16

Grup perm n sim dan disebut grup

selang-seling

elemen.

Contoh 2. 14

Grup permutasi genap dari {1, 2, 3, 4} atau grup selang-seling diberikan dalam

tabel di bawah ini.

26  

Tabel 2. 4

Grup Selang-seling untuk Permutasi Genap dari {1, 2, 3, 4}

α1 α2 α3 α4 α5 α6 α7 α8 α9 α10 α11 α12

(1)=α1 1 2 3 4 5 6 7 8 9 10 11 12

(12)(34)=α2 2 1 4 3 6 5 8 7 10 9 12 11

(13)(24)=α 3 4 1 2 7 8 5 6 11 12 9 3 10

(14)(23)=α 4 3 2 1 8 7 6 5 12 11 10 9 4

(123)=α 5 8 6 7 9 12 10 11 1 4 2 3 5

(243)=α 6 7 5 8 10 11 9 12 2 3 1 4 6

(142)=α7 7 6 8 5 11 10 12 9 3 2 4 1

(134)=α 8 5 7 6 12 9 11 10 4 1 3 2 8

(132)=α 9 11 12 10 9 1 3 4 2 5 7 8 6

(143)=α10 10 12 11 9 2 4 3 1 6 8 7 5

(234)=α11 11 9 10 12 3 1 2 4 7 5 6 8

(124)=α12 12 10 9 11 4 2 1 3 8 6 5 7

6. Grup Dihedral

Definisi 2. 17

Simetri bidang dari bangun F pada bidang adalah fungsi bijektif dari bidang

tersebut ke dirinya sendiri yang memetakan F pada F dan mempertahankan jarak

(untuk sebarang titik p dan q pada bidang, jarak dari bayangan p ke bayangan q

sama dengan jarak p ke q).

27  

Teorema 2. 6

Himpunan semua simetri bidang dari bangun F dengan operasi komposisi

membentuk grup.

Bukti:

Akan dibuktikan bahwa komposisi simetri bidang dari bangun F bersifat tertutup.

isalkan π1 d 2 adalah sime id d ba n M ru r 2

π1 ◦ p n gsi ijek . S nju a n uk n w ◦

k jar . M lk a, dan (a, ar

, ( ◦ π )) (π2 (a) 2(π ))

(π ), π )) ren 2 a lah et

(a ren 1 a lah et

Te w ko osi sim F erupakan fungsi

bij e ertahankan jarak.

Ak ka ba k o im ri b ng ri b gu bersifat asosiatif.

M π n d si tri ang ari gu . Menurut Teorema

2. π ◦ = 1 ◦ ◦ e kti hw om e bid g d

ba s as tif

kan dibuktikan bahwa komposisi simetri bidang dari bangun F mempunyai

elemen identitas. Simetri bidang i dari bangun F, di mana i(a) = a, untuk setiap a

en identitas dalam himpunan semua simetri bidang dari

alkan π adalah simetri bidang dari bangun F dan i simetri bidang

identitas. Akan dibuktikan bahwa π ◦ i = i ◦ π = π. Akan ditunjukkan bahwa (π ◦

M an π tri b ang ari ngu F. enu t Teo ema . 4,

π2 meru aka fun b tif ela tny aka dib tika bah a π1 π2

mempertahan an ak isa an b F d b) adalah jarak ant a a

dengan b.

d((π2 ◦ π1)(a) π2 1)(b = d (π1 ), π 1(b

= d 1(a 1(b (ka a π da sim ri)

= d , b) (ka a π da sim ri)

rbukti bah a mp si etri bidang dari bangun m

ektif dan m mp

an dibukti n hwa omp sisi s et ida da an n F

isalkan π1, 2, da π3 a alah me bid d ban n F

4, π1 ◦ ( 2 π3) (π π2) π3. T rbu ba a k posisi sim tri an ari

ngun F ber ifat osia .

A

F, merupakan elem

bangun F. Mis

28  

i)(a) = (i ◦ π)(a) = π(a), untuk setiap a F. Karena berlaku i(a) = a, untuk setiap a

F, diperoleh (π ◦ i)(a) = π(i(a)) = π(a) = i(π(a)) = (i ◦ π)(a) sehingga (π ◦ i)(a) =

(i ◦ π)(a) = π(a), akibatnya π ◦ i = i ◦ π = π. Terbukti bahwa terdapat elemen

identitas i dalam himpunan semua simetri bidang dari bangun F, sehingga π ◦ i = i

π adalah simetri bidang dari bangun F,

terdapat elemen invers π-1 adalah simetri bidang dari bangun F, yaitu simetri

embalik arah simetri bidang π, di mana untuk setiap a, a’ F, π(a’)

uk setiap π dalam himpunan semua simetri bidang dari bangun F,

= i.

Definisi 2. 18

Grup yang terdiri dari semua simetri dari segi-n beraturan dengan operasi

komposisi disebut grup dihedral.

otasikan dengan Dn.

◦ π = π.

Akan dibuktikan bahwa setiap elemen dalam himpunan semua simetri bidang dari

bangun F mempunyai invers. Untuk setiap

bidang yang m

= a ↔ π-1(a) = a’. Misalkan a, a’ F. Karena berlaku i(a) = a, dan jika π(a’) = a

maka π-1(a) = a’, akibatnya i(a) = a = π(a’) = π(π-1(a)) = (π ◦ π-1)(a) dan i(a’) = a’

= π-1(a) = π-1(π(a’)) = (π-1 ◦ π)(a). Jadi, π ◦ π-1 dan π-1 ◦ π merupakan simetri

bidang identitas dari bangun F, sehingga berlaku π ◦ π-1 = π-1 ◦ π = i. Terbukti

bahwa unt

terdapat elemen invers π-1, sehingga π ◦ π-1 = π-1 ◦ π

Jadi, terbukti bahwa himpunan semua simetri bidang dari bangun F dengan

operasi komposisi membentuk grup.

■

Grup dihedral berorde 2n din

29  

Contoh 2. 15

, , , , , , , ’ adalah grup dihedral yang terdiri dari semua

imetri dari suatu bujursangkar atau persegi. (Keterangan: adalah rotasi 0°,

adalah rotasi 90°, adalah rotasi 180°, adalah rotasi 270°, adalah

pencerminan terhadap sumbu horisontal atau mendatar, adalah pencerminan

terhadap sumbu vertikal atau tegak, adalah pencerminan terhadap diagonal

tama, ’ adalah pencerminan terhadap diagonal yang lain.) Tabel operasi atau

tabel Cayley untuk adalah sebagai berikut.

Tabel 2. 5

Tabel Op

s

u

erasi untuk

’

’

’

’

’

’

’

’

’ ’

Grup dihedral dapat dinyatakan dengan | 0, 1;

0, 1, … , 1 yang memenuhi persamaan dan , dengan

30  

f adalah pencerminan terhadap garis vertikal untuk n ganjil dan pencerminan

terhadap garis horisontal untuk n genap, dan g adalah rotasi terhadap posisi awal

melalui sudut dengan arah berlawanan jalan jarum jam, untuk n > 2.

orema Lagrange, Subgrup Normal, dan Grup Faktor

Definisi 2. 19

, | ngan .

d

Ha aH| untuk menotasikan

banyaknya elemen dalam himpunan aH, dan |Ha| untuk menotasikan banyaknya

m himpunan Ha.

Contoh 2. 16

Misalkan G = 3 dan H {(1), (13 }. Maka oset-koset kiri dari H di G ah

(1) = {(1)(1), (1)(13)} = {(1), (13)} = {(13)(1), (13)(13)} = (13)H,

(12 = {(12)(1), (12)(13)} = {(12), (132) = {(132 (1), (132 (13)} = 32)H,

(23) = {(23)(1), (23)(13)} = {(23), (123)} = {(123)(1), (123)(13)}= (123)H.

Seda kan kos -koset anan dar H di G adalah

H ) = {(1)(1), (13)(1)} = {(1), (13)} = {(1)(13), (13)(13)} = (13)H,

H(12) = {(1)(12), (13)(12)} = {(12), (123)} = {(1)(123), (13)(123)} = (123)H,

7. Koset, Te

Misalkan G adalah grup dan H adalah himpunan bagian dari G. Untuk sebarang

himpunan dinotasikan de aH Secara analogi,

| dan | . Jika H adalah subgrup dari G, maka

himpunan aH disebut koset kiri dari H di G yang memuat a, sedangkan Ha di-

sebut koset kanan ari H di G yang memuat a. Dalam kasus ini, elemen a disebut

perwakilan koset dari aH (atau ). Kita menggunakan |

elemen dala

S = ) k adal

H

)H } ) ) (1

H

ng et k i

(1

31  

H 3) = {(1)(23), (13)(23)} = {(23), (132) = {(1)(1 ), (13) 32)}= (1 2)H.

Lemma 2. 1

Misalkan H adalah subgrup dari , dan m a dan b berada di G. Maka,

. a aH,

2. aH

3. aH = bH atau aH bH = ,

= bH jik

,

7. aH adalah subgrup dari G jika dan hanya jika a H.

ukti:

1. a = ae aH.

2. Untuk memeriksa sifat 2, pertama-tama andaikan bahwa aH = H. Maka

. Selanjutnya andaikan bahwa a H dan tunjukkan bahwa

tu enunjukka

a H dan h , dapat diketahui bahwa

, dengan sifat 2.

(2 } 32 (1 3

G isalkan

1

= H jika dan hanya jika a H,

4. aH a dan hanya jika a-1b H,

5. |aH| = |bH|,

6. aH = Ha jika dan hanya jika H = aHa-1

B

aH H dan H aH. Inklusi pertama diperoleh secara langsung dari ketertu-

pan H. Untuk m n bahwa H aH, misalkan h H. Maka, karena

H a-1h H. Sehingga

.

3. Untuk membuktikan sifat 3, andaikan bahwa aH bH ≠ dan buktikan

bahwa aH = bH. Misalkan x aH bH. Maka terdapat h1, h2 di H sedemi-

kian hingga x = ah1 dan x = bh2. Jadi, dan karena

, maka

32  

4. Perhatikan bahwa aH = bH jika dan hanya jika a-1aH = a-1bH. Sehingga H =

di H adalah

a-

a-

a bh1 = bh2. Jadi, f adalah fungsi

nisi 7. 1, ter-

ka

n bahwa aH = Ha jika dan hanya jika (aH)a-1 = (Ha)a-1, yaitu jika

-1

adalah suatu subgrup, maka aH memuat identitas e. Sehingga, aH

aH = eH = H. Sehingga dari sifat 2, di-

peroleh a H. Sebaliknya, jika a H, maka dengan sifat 2 lagi, aH = H. Ka-

rena H adalah subgrup dari G, maka aH adalah juga subgrup dari G.

■

i G, maka |H| membagi

|G|. Selain itu, banyaknya koset kiri (kanan) berbeda dari H di G adalah |G|/|H|.

Bukti:

Misalkan a H, a H, …, a H menyatakan koset kiri dari H di G yang saling beda.

Maka, untuk setiap a di G, kita mempunyai aH = aiH untuk suatu i. Dengan sifat 1

a-1bH, maka a-1b H, dengan sifat 2.

5. Akan dibuktikan bahwa korespondensi ah → bh untuk semua h

fungsi satu-satu dan pada dari aH ke bH. Misalkan f : aH → bH. Pertam

tama andaikan ah1 = ah2 aH dengan h1, h2 H. Karena G adalah grup, m

ka dengan kanselasi berlaku h1 = h2. Sehingg

satu-satu. Lalu untuk sebarang y, andaikan y bH. Menurut Defi

dapat h H sehingga y = bh. Tetapi h H menentukan ah aH. Ma

. Jadi, f adalah fungsi pada.

6. Perhatika

dan hanya jika aHa = H.

7. Jika aH

eH ≠ dan dengan sifat 3, diperoleh

Teorema 2. 7 (Teorema Lagrange)

Jika G adalah grup berhingga dan H adalah subgrup dar

1 2 r

33  

dari Lemma 7. 1, a aH. Sehingga setiap anggota dari G berada di salah satu dari

koset aiH. Dengan simbol, G = a1H … arH. Sekarang, sifat 3 dari lemma me-

nunjukkan bahwa gabungan ini adalah saling asing, sehingga |G| = |a1H| + |a2H| +

|H| untuk setiap … + |arH|. Akhirnya, karena |aiH| = i, diperoleh |G| = r|H|.

■

ormal dari G

semua a di G. Kita menotasikan ini dengan H G.

Untuk sebarang pencerminan f dan se-

Andaikan G adalah grup Abel dan na G adalah grup

erlaku untuk setiap , maka H adalah subgrup

Definisi 2. 20

Suatu subgrup H dari grup G disebut subgrup n jika aH = Ha untuk

Contoh 2. 17

Subgrup rotasi di Dn adalah normal di Dn.

barang rotasi g, diketahui fg = g-1f, sedangkan untuk sebarang rotasi g dan g’, di-

peroleh gg’ = g’g.

Teorema 2. 8

Jika G adalah grup Abel dan H adalah subgrup dari G, maka H adalah subgrup

normal dari G.

Bukti:

H adalah subgrup dari G. Kare

Abel, maka . Akibatnya, |

| . Karena ini b

normal dari G.

■

34  

Teorema 2. 9

Misalkan G adalah grup dan H suatu subgrup normal dari G. Himpunan G/H =

{aH|a G} adalah grup terhadap operasi (aH)(bH) = abH.

/H

ke G/H adalah benar-benar fungsi. Untuk melakukan ini, andaikan bahwa aH =

a’H dan bH = b’H. Maka a’ = ah dan b’ = bh untuk suatu h , h di H, dan oleh

karena itu ’ ’ . Di sini

digunakan sifat 2 dari Lemma 7. 1 dan kenyataan bahwa H G. Selanjutnya, eH

= H adalah elemen identitas, a-1H adalah invers dari aH, dan

. Ini membukti-

kan bahwa G/H adalah suatu grup.

■

Definisi 2. 21

Jika subgrup H dari G adalah normal, maka himpunan koset kiri (atau kanan) dari

H di G disebut grup faktor dari G oleh H (atau grup hasil bagi dari G oleh H).

Contoh 2. 18

dan H = 6 = {0, 6, 12}. Maka G/H = {0+H, 1+H, 2+H, 3+H,

himpunan G/H. Sehingga (5+H)+(4+H) = 5+4+H = 9+H =

Bukti:

Pertama-tama akan ditunjukkan bahwa operasinya terdefinisi dengan baik, yaitu

harus ditunjukkan bahwa korespondensi yang terdefinisi di atas dari G/H × G

1 2 1 2

Misalkan G =

4+H, 5+H}. Untuk menjelaskan bagaimana elemen-elemen grup dioperasikan,

sebagai contoh (5+H)+(4+H). Ini seharusnya menjadi salah satu dari enam elemen

yang terdaftar dalam

35  

3+6+H = 3+H, karena H menyerap semua kelipatan dari 6 dengan sifat 2 dari

omorfisma dan Isomorfisma

G ke grup adalah pemetaan dari

mempertahankan operasi grup, yaitu, ( G.

Definisi 2. 23

Suatu isomorfisma dari grup G ke grup adalah pemetaan satu-satu (atau

pada yang mempertahankan operasi grup, yaitu, (ab) = (a)

.

2. 19

emetakan x ke f dan y ke g. Akan dibuktikan bahwa

m

Misalnya , untuk setiap .

Lemma 7. 1.

8. Hom

Definisi 2. 22

Suatu homomorfisma dari grup G ke yang

ab) = (a) (b) untuk semua a, b di

fungsi) dari G

(b) untuk semua a, b di G. Jika terdapat isomorfisma dari G pada , dapat

dikatakan bahwa G dan adalah isomorfis dan ditulis

Contoh

Misalkan , | , dan | 0, 1;

0, 1, … , 1 . Buktikan bahwa .

Terdapat tiga persamaan yang dipenuhi di G oleh x dan y juga dipenuhi di H jika x

diganti f dan y diganti g, yaitu , . Maka terdapat pemetaan

: yang m adalah

isomorfisma, yaitu pemetaan yang satu-satu, pada, dan memenuhi syarat

ho omorfisma.

36  

: adalah satu-satu jika dan hanya jika , untu

. Misalkan dan . Maka

: adalah pada jika untuk setiap terdapat sedemikian hingga

. Jika H dibangkitkan oleh elemen-elemen dari {f, g}, maka sebarang

hasil kali pangkat bulat dari f dan g adalah bayangan dari hasil kali pangkat bulat

yang bersesuaian dari x dan y. Misalkan dan . Sehingga untuk

setiap terdapat sedemikian hingga .

: adalah homomorfisma jika dan hanya jika ,

untuk setiap , . Maka

.

Jadi, .

k

setiap ,

→ → →

→ .

37  

B. Teori Graf

1. Graf Berarah Atau Digraf

Definisi 2. 24

Graf terdiri dari himpunan tak kosong simpul V dan himpunan busur

E. Setiap busur mempunyai satu atau dua simpul terhubung dengannya dan simpul

itu disebut titik ujung dari busur tersebut. Suatu busur dikatakan terhubung

dengan titik ujung-titik ujungnya.

,

, , , , ,

, , , , , , , , , , ,

Definisi 2. 25

Dua simpul u dan v dalam suatu graf G disebut berdampingan di G jika u dan v

adalah titik ujung dari suatu busur di G. Jika e diasosiasikan dengan {u, v}, busur

e disebut menghubungkan simpul u dan v. Simpul u dan v disebut titik ujung dari

suatu busur yang diasosiasikan dengan {u, v}.

Definisi 2. 26

Suatu graf yang setiap busurnya menghubungkan dua simpul berbeda dan tidak

memuat dua busur menghubungkan pasangan simpul yang sama disebut graf

sederhana.

Contoh 2. 20

Graf terdiri dari himpunan simpul dan himpunan

busur . Graf seperti ini dapat

digambarkan secara geometris seperti berikut.

38  

Gambar 2. 1 Graf G

Sebagai contoh, busur {a, b} mempunyai simpul a dan b sebagai titik ujungnya

sehingga busur {a, b} dikatakan terhubung dengan simpul a dan b. Simpul a dan b

berdampingan di G dan misalkan {a, b} = f maka busur f menghubungkan simpul

a dan b. Graf di atas disebut sebagai graf tak berarah karena tidak memuat busur

berarah.

Definisi 2. 27

Graf berarah atau digraf terdiri dari himpunan tak kosong simpul V

dan himpunan busur berarah E. Setiap busur berarah berkaitan dengan pasangan

terurut simpul. Busur berarah yang berkaitan dengan pasangan terurut (u, v)

dikatakan berawal di u dan berakhir di v.

,

Definisi 2. 28

Jika (u, v) adalah suatu busur berarah dari graf G, u dikatakan berdampingan

dengan v dan v dikatakan berdampingan dengan u. Simpul u disebut simpul awal

dari (u, v), dan v disebut simpul akhir dari (u, v).

39  

Contoh 2. 21

Graf berarah terdiri dari himpunan simpul dan

himpunan busur berarah . Graf

seperti ini dapat digambarkan secara geometris seperti berikut.

, , , , ,

, , , , , , , , , , ,

Gambar 2. 2 Graf Berarah G

Sebagai contoh, busur (a, b) dikatakan berawal di a dan berakhir di b. Simpul a

dikatakan berdampingan dengan b dan b dikatakan berdampingan dengan a.

Simpul a disebut simpul awal dari (a, b) dan b disebut simpul akhir dari (a, b).

2. Lintasan dan Sirkuit Hamilton

Definisi 2. 29

Misalkan n adalah bilangan bulat tak negatif dan G adalah graf tak berarah.

Lintasan dengan panjang n dari u ke v di G adalah barisan dari n busur e1, ..., en

dari G sedemikian hingga e1 diasosiasikan dengan {x0, x1}, e2 diasosiasikan

dengan {x1, x2}, dan seterusnya, dengan en diasosiasikan dengan {xn-1, xn}, di

mana x0 = u dan xn = v. Jika grafnya sederhana, maka lintasan ini dinotasikan

dengan barisan simpul x0, x1, ..., xn. Lintasan adalah sirkuit jika berawal dan

berakhir pada simpul yang sama, atau jika u = v dan panjangnya lebih besar

40  

daripada nol. Lintasan atau sirkuit dikatakan melalui simpul x0, x1, ..., xn-1 atau

melintasi busur e1, e2, ..., en. Lintasan atau sirkuit adalah sederhana jika tidak

memuat busur yang sama lebih dari sekali.

Contoh 2. 22

Gambar 2. 3 Graf Sederhana yang Memuat Lintasan dan Sirkuit

Dalam graf sederhana di atas, barisan simpul a, d, c, f, e adalah lintasan sederhana

dengan panjang 4, karena {a, d}, {d, c}, {c, f}, dan {f, e} adalah semua busurnya.

Tetapi barisan simpul d, e, c, a bukan lintasan, karena {e, c} bukan busur. Barisan

simpul b, c, f, e, b adalah sirkuit dengan panjang 4, karena {b, c}, {c, f}, {f, e},

dan {e, b} adalah busur, dan lintasan ini berawal dan berakhir pada simpul b.

Lintasan a, b, e, d, a, b, yang panjangnya 5, bukan lintasan sederhana karena

memuat busur {a, b} dua kali.

Definisi 2. 30

Misalkan n adalah bilangan bulat non negatif dan G adalah graf berarah. Lintasan

dengan panjang n dari u ke v di G adalah barisan busur e1, e2, ..., en dari G

sedemikian hingga e1 diasosiasikan dengan (x0, x1), e2 diasosiasikan dengan (x1,

x2), dan seterusnya, dengan en diasosiasikan dengan (xn-1, xn), di mana x0 = u dan

xn = v. Jika grafnya sederhana, maka lintasan ini dinotasikan dengan barisan

41  

simpulnya x0, x1, ..., xn. Lintasan dengan panjang lebih besar daripada nol yang

berawal dan berakhir pada simpul yang sama disebut sirkuit. Lintasan atau sirkuit

disebut sederhana jika tidak memuat busur yang sama lebih dari sekali.

Definisi 2. 31

Lintasan sederhana di graf G yang melalui setiap simpul tepat sekali disebut

lintasan Hamilton dan sirkuit sederhana di graf G yang melalui setiap simpul tepat

sekali disebut sirkuit Hamilton. Lintasan sederhana x0, x1, ..., xn-1, xn di graf

adalah lintasan Hamilton jika dan

untuk 0 ≤ i < j ≤ n dan sirkuit sederhana x0, x1, ..., xn-1, xn, x0 (dengan n > 0) adalah

sirkuit Hamilton jika x0, x1, ..., xn-1, xn adalah lintasan Hamilton.

, , , . . . , ,

Teka-teki ini dapat diselesaikan dengan menemukan sirkuit pada graf

dalam Gambar 2. 4. Salah satu penyelesaian dari teka-teki tersebut juga

ditunjukkan dalam Gambar 2. 4.

Istilah lintasan dan sirkuit Hamilton muncul dari permainan yang disebut

Icosian puzzle, ditemukan pada tahun 1857 oleh matematikawan Irlandia, Sir

William Rowan Hamilton. Permainan ini terdiri dari dodekahedron kayu, yaitu

segibanyak dengan 12 segilima beraturan sebagai sisi, dengan pasak di setiap

simpul dari dodekahedron dan tali. Dua puluh simpul dari dodekahedron dinamai

dengan nama-nama kota berbeda di dunia. Tujuan dari teka-teki ini adalah dengan

berawal dari suatu kota dan berjalan sepanjang busur dari dodekahedron,

mengunjungi setiap 19 kota lain tepat sekali, dan berakhir dengan kembali pada

kota pertama. Selama perjalanan mengunjungi setiap kota ditandai menggunakan

tali dan pasak. Permainan ini disebut juga teka-teki “Perjalanan Keliling Dunia”.

42  

Gambar 2. 4 Salah Satu Penyelesaian Teka-Teki “Perjalanan Keliling Dunia”

Contoh 2. 23

Gambar 2. 5 Graf Sederhana G1, G2, dan G3

Graf G1 mempunyai sirkuit Hamilton, yaitu a, b, c, d, e, a. Graf G2 tidak

mempunyai sirkuit Hamilton, karena sebarang sirkuit yang memuat setiap simpul

harus memuat busur { 2 ilton,

a, b} dua kali, tetapi graf G mempunyai lintasan Ham

yaitu a, b, c, d. Graf G3 tidak mempunyai sirkuit Hamilton ataupun lintasan

Hamilton, karena sebarang lintasan yang memuat semua simpul harus memuat

satu dari busur {a, b}, {e, f}, dan {c, d} lebih dari sekali.

BAB III

DIGRAF CAYLEY DARI GRUP

Jika seseorang berpikir mengenai aljabar abstrak atau struktur aljabar,

maka hal pertama yang hadir dalam pikirannya adalah grup. Terdapat banyak grup

berbeda sebanyak cara menggambarkan grup ini. Salah satu cara menunjukkan

grup dan elemen pembangkitnya adalah dengan digraf Cayley. Digraf ini

merupakan perwakilan berupa gambar dari grup. Dari digraf ini telah hadir

penyelidikan tentang lintasan dan sirkuit Hamilton yang terdapat cukup banyak

digraf Cayley dengan sifat-sifat khusus di dalamnya.

A. Digraf Cayley dari Grup

Gagasan tentang digraf Cayley dari grup pertama-tama diperkenalkan

oleh seorang matematikawan bernama Arthur Cayley pada tahun 1878. Definisi

umum menyatakan bahwa digraf Cayley merupakan gambaran grafis dari grup

yang diberikan oleh himpunan pembangkit dan relasi. Digraf ini penting untuk

dipelajari karena menghubungkan teori graf dengan teori grup dan hubungan ini

menghasilkan sebuah metode untuk menggambarkan grup. Secara matematis

definisi digraf Cayley dari grup adalah sebagai berikut.

43  

44  

Definisi 3. 1

Misalkan G adalah grup berhingga dan S adalah himpunan pembangkit untuk G.

Digraf Cayley dari grup G dengan himpunan pembangkit S, yang dinotasikan

dengan Cay(S:G), dapat didefinisikan sebagai berikut. 

1) Setiap elemen dari G adalah simpul dari Cay(S:G).

2) Untuk x dan y di G, terdapat sebuah busur berarah dari x ke y jika dan hanya

jika xs = y untuk suatu s S.

Untuk membedakan pembangkit mana yang menghubungkan dua simpul

dalam suatu digraf, Cayley mengusulkan agar setiap pembangkit diberikan warna,

dan busur berarah yang menghubungkan x ke xs diwarnai dengan warna yang di-

berikan pada s. Ia menyebut gambar yang dihasilkan sebagai graf berwarna dari

grup tersebut (color graph of the group). Istilah ini kadang-kadang masih diguna-

kan. Dalam tulisan ini untuk membedakan pembangkit yang berbeda, akan digu-

nakan busur utuh, busur putus-putus, dan busur titik-titik. Secara umum, jika ter-

dapat suatu busur berarah dari x ke y, maka tidak perlu terdapat busur dari y ke x.

Anak panah yang berasal dari x dan menuju ke y menyatakan bahwa terdapat sua-

tu busur berarah dari x ke y.

Terdapat beberapa cara untuk menggambar digraf dari grup yang diberi-

kan oleh himpunan pembangkit tertentu. Akan tetapi, bukan penampilan dari di-

graf yang bersangkutan tetapi cara simpul terhubung. Hubungan ini secara khusus

ditentukan oleh himpunan pembangkit. Sehingga jarak antar simpul dan sudut

yang dibentuk oleh busur tidak mempunyai arti. Pada digraf Cayley dari grup da-

pat digunakan busur tak berpanah menghubungkan dua simpul x dan y yang me-

45  

nyatakan bahwa terdapat suatu busur dari x ke y dan suatu busur dari y ke x. Ini

terjadi jika himpunan pembangkit memuat anggota yang inversnya adalah dirinya

sendiri dalam grup tersebut. Sebagai contoh, pada Contoh 3. 2, pembangkit (0, 1)

inversnya adalah (0,1) dalam grup .

1

0, 1, 2, 3, 4, 5

Gambar 3. 1.

Contoh 3. 1

. 

adalah grup terhadap operasi penjumlahan dengan pembangkitnya adalah 1.

.

Invers dari 1 adalah 5 sehingga busurnya berpanah.

Digraf Cayley dari dengan pembangkit 1 atau Cay({1}: ) diperlihatkan dalam

 

Gambar 3. 1 Digraf Cay({1}: )

Contoh 3. 2

1, 0 , 0, 1 .

adalah grup terhadap operasi penjumlahan dan pembangkitnya adalah

(1, 0) dan (0, 1).

46  

0, 1, 2 0, 1

0, 0 , 0, 1 , 1, 0 , 1, 1 , 2, 0 , 2, 1

, ,

.

Invers dari (1, 0) adalah (2, 0) sehingga busurnya berpanah, invers dari (0, 1) ada-

lah (1, 0) sehingga busurnya tak berpanah.

Digraf Cayley dari dengan pembangkit (1, 0) dan (0, 1) atau Cay({(1, 0),

(0, 1)}:  ) diperlihatkan dalam Gambar 3. 2.

 

Gambar 3. 2 Digraf Cay({(1, 0), (0, 1)}: )  

Dengan digraf Cayley dari grup menjadi mudah untuk melihat orde dari

beberapa elemen grup, yaitu orde dari elemen identitas dan orde dari pembangkit

yang digunakan. Sebagai contoh, orde dari dalam grup yang diberikan dalam

Contoh 3. 3 adalah empat karena terdapat empat pemberhentian pada digraf

sebelum mencapai sebagai elemen identitas di .

Contoh 3. 3

, . 

adalah grup terhadap operasi komposisi dan pembangkitnya adalah dan .

, , , , , , , .

47  

Invers dari adalah sehingga busurnya berpanah, invers dari adalah

mbangkit dan atau Cay( , :  ) di-

am

sehingga busurnya tak berpanah.

Digraf Cayley dari dengan pe

perlihatkan dalam G bar 3. 3.

 

Gambar 3. 3 Digraf Cay( , :  )

Contoh 3. 4

123 .

adalah grup terhadap operasi komposisi fungsi dan pembangkitnya adalah (12)

dan (123).

1 , 12 , 13 , 23 , 123 , 132 .

Invers dari (12) adalah (12) sehingga busurnya tak berpanah, invers dari (123)

adalah (132) sehingga busurnya berpanah.

Digraf Cayley dari dengan pembangkit (12) dan (123) atau Cay({(12),

(123)}:  ) diperlihatkan dalam Gambar 3. 4.

12 ,

48  

 

Gambar 3. 4 Digraf Cay({(12), (123)}:  )

Contoh 3. 5

12 , 13 .

p terhadap operasi komposisi fungsi dan pembangkitnya adalah (12)

dan (13).

Invers dari (12) adalah (12) dan invers dari (13) adalah (13) sehingga busurnya tak

berpanah.

Digraf Cayley dari dengan pembangkit (12) dan (13) atau Cay({(12), (13)}:  )

diperlihatkan dalam Gambar 3. 5.

adalah gru

1 , 12 , 13 , 23 , 123 , 132 .

 

Gambar 3. 5 Digraf Cay({(12), (13)}:  )

49  

Contoh 3. 6

12 34 , 123 .

adalah grup terhadap operasi komposisi fungsi dan pembangkitnya adalah

(12)(34) dan (123).

Tabel operasi untuk dapat dilihat pada Tabel 2. 2.

Invers dari (12)(34) adalah (12)(34) sehingga busurnya tak berpanah, invers dari

(123) adalah (132) s

Digraf Cayley dari dengan pembangkit (12)(34) dan (123) atau Cay({(12)(34),

(123)}:  ) diperlihatkan dalam Gambar 3. 6.

ehingga busurnya berpanah.

 

Gambar 3. 6 Digraf Cay({(12)(34), (123)}:  )

Digraf Cayley menyediakan gambaran visual dari grup, sehingga lebih

mudah digunakan untuk menentukan nilai dari sebarang hasil kali dari

pembangkit dan inversnya. Sebagai contoh, hasil kali ab3ab-2 dari grup yang dibe-

rikan dalam Contoh 3. 7. Hanya perlu memulai dari simpul e dan mengikuti busur

50  

dari setiap simpul ke simpul selanjutnya seperti ditentukan dalam hasil kali yang

diberikan. Tentu saja, a-1 berarti kebalikan dari garis melintang busur a. (Penga-

matan seperti b-3=b juga membantu.) Mengikuti hasil kali dari awal sampai akhir

sehingga mendapatkan b.

Contoh 3. 7

, | , , .

adalah grup terhadap operasi perkalian dan pembangkitnya adalah a dan b

yang memenuhi persamaan , , dan .

, , ,

Invers dari a adalah a-1 = a3 dan invers dari b adalah b-1 = a2b sehingga semua bu-

surnya b

, , , , .

erpanah.

Digraf Cayley dari dengan pembangkit a dan b atau Cay({a, b}: ) diperli-

hatkan dalam Gambar 3. 7.

 

Gambar 3. 7 Digraf Cay({a, b}: )

51  

Contoh 3. 8

rhadap operasi komposisi dan pembangkitnya adalah a dan b

, , , , , , … .

Invers dari a adalah a-1 = a dan invers dari b adalah b-1 = b sehingga semua busur-

nya tak berpanah.

Digraf Cayley dari dengan pembangkit a dan b atau Cay({a, b}: ) diperli-

hatkan dalam Gambar 3. 8.

, | .

adalah grup te

yang memenuhi persamaan .

, , , , ,

Gambar 3. 8 Digraf Cay({a, b}: )

52  

B. Lintasan dan Sirkuit Hamilton Dalam Digraf Cayley dari Grup

Istilah lintasan dan sirkuit Hamilton muncul dari permainan yang dipopu-

lerkan oleh matematikawan Irlandia, Sir William Hamilton pada tahun 1859, keti-

ka ia menemukan teka-teki yang disebut “Berkeliling Dunia”. Gagasannya adalah

menamai 20 simpul dari dodekahedron beraturan dengan nama kota-kota terkenal.

Penyelesaian dari teka-teki ini adalah dengan berawal pada sebarang kota khusus

(simpul) dan bepergian “berkeliling dunia”, berpindah sepanjang busur dengan ca-

ra tertentu sehingga setiap kota lain dikunjungi tepat sekali sebelum kembali pada

titik semula. Salah satu penyelesaian untuk teka-teki ini diberikan dalam Gambar

2.4, dengan simpul dikunjungi dengan urutan yang ditunjukkan.

Dengan jelas, gagasan tersebut dapat digunakan pada sebarang digraf,

yaitu berawal pada suatu simpul dan mencoba melintasi digraf dengan berpindah

sepanjang busur dengan cara tertentu sehingga setiap simpul dikunjungi tepat se-

kali sebelum kembali pada simpul awal. (Pergi dari x ke y, harus terdapat suatu

simpul dari x ke y.) Rangkaian busur tersebut disebut sirkuit Hamilton pada digraf

tersebut. Barisan busur yang melalui setiap simpul tepat sekali tanpa kembali ke

titik awal disebut lintasan Hamilton. Selanjutnya akan dibahas tentang keberadaan

dari lintasan dan sirkuit Hamilton pada digraf Cayley.

Gambar 3. 9 menunjukkan lintasan Hamilton untuk digraf yang diberikan

pada Contoh 3. 2 dan Gambar 3. 10 menunjukkan sirkuit Hamilton untuk digraf

yang diberikan pada Contoh 3. 7.

53  

 

Gambar 3. 9 Lintasan Hamilton Dalam Digraf Cay({(1, 0), (0, 1)}: )

dari (0, 0) ke (2, 1)

Gambar 3. 10 Sirkuit Hamilton Dalam Digraf Cay({a, b}: )

1, 0 , 0, 1 :

1, 0 , 0, 1 :

m dan n adalah relatif prima dan keduanya lebih besar daripada 1, dan jika m dan

n adalah tidak relatif prima.

Terdapat lintasan Hamilton pada , tetapi

apakah terdapat sirkuit Hamilton pada digraf tersebut? Secara lebih umum, akan

diperiksa keberadaan sirkuit Hamilton pada , jika

54  

Teorema 3. 1 (Syarat Perlu)

1, 0 , 0, 1 : tidak mempunyai sirkuit Hamilton jika m dan n

Bukti:

ayley dalam sebagai ja-

ringan persegi panjang yang terkoordinasi. Andaikan terdapat sirkuit Hamilton

pada digraf tersebut dan (a, b) adalah suatu simpul yang sirkuitnya keluar secara

mendatar. (Jelas bahwa simpul tersebut ada.) Maka sirkuit yang harus keluar seca-

ra mendatar juga adalah ( 1, 1), dan sirkuit melalui (a, 1) dua kali, li-

hat Gambar 3. 12. Mengulang penjelasan tersebut, akan terlihat bahwa sirkuit

yang keluar secara mendatar dari setiap simpul adalah (a, b), ( 1, 1),

( 2, 2), …, yaitu , 1, 1 . Tetapi jika m dan n adalah relatif

prima, 1, 1 adalah seluruh grupnya. Dengan jelas, di sana tidak dapat menja-

di sirkuit Hamilton yang terdiri dari sepenuhnya gerakan mendatar.

adalah relatif prima dan lebih besar daripada 1.

Gambar 3. 11 menunjukkan gambaran digraf C

■

55  

Gambar 3. 11 Digraf Cay({(1, 0), (0, 1)}: )

Gambar 3. 12 Simpul (a, b), ( , ), dan (a, ) 1 1 1

1, 0 , 0, 1 :

Teorema 3. 2 (Syarat Cukup)

mempunyai sirkuit Hamilton jika n membagi m.

Bukti:

Katakan m = kn. Maka dapat dipandang sebagai k blok berukuran n × n.

(Lihat Gambar 3. 13 sebagai contoh.) Berawal dari (0, 0) dan meliputi simpul dari

bagian atas blok sebagai berikut. Gunakan pembangkit (0, 1) untuk bergerak

secara mendatar melintasi baris pertama sampai terakhir. Lalu gunakan

pembangkit (1, 0) untuk bergerak secara tegak lurus ke titik di bawahnya, dan

56  

meliputi titik sisanya pada baris kedua dengan bergerak secara mendatar.

Lanjutkan proses di atas sampai tiba di titik ( , 0), yaitu pojok kiri paling

bawah dari blok pertama. Selanjutnya, bergerak secara tegak lurus ke blok kedua

dan mengulang proses yang digunakan pada blok pertama. Lanjutkan proses ini

sampai dasar blok tercapai. Lengkapi sirkuit dengan bergerak tegak lurus kembali

ke (0, 0).

1

■

57  

Gambar 3. 13 Digraf Cay({(1, 0), (0, 1)}: )

58  

Perhatikan bahwa sirkuit yang diberikan dalam bukti Teorema 3. 2

mudah digambarkan tetapi agak tidak praktis untuk dibuat dalam kata-kata. Cara

yang sesuai untuk membuat lintasan atau sirkuit Hamilton adalah menentukan

simpul awal dan barisan pembangkit dengan urutan yang mana mereka dapat

digunakan. Dalam Contoh 3. 5, sebagai contoh, dapat berawal dari (1) dan

berganti pembangkit (12) atau (13) sampai kembali ke (1). Dalam Contoh 3. 3,

dapat berawal dari R0 dan berturut-turut menggunakan R90, R90, R90, H, R90, R90,

R90, H. Jika k adalah bilangan bulat positif dan a, b, …, c adalah barisan dari

elemen grup, dapat digunakan untuk menotasikan rangkaian dari k

ulangan dari barisan (a, b, …, c). Jadi, 2 dan 2

keduanya berarti R90, R90, R90, H, R90, R90, R90, H. Dengan notasi ini, dapat

dinotasikan sirkuit Hamilton yang diberikan dalam Teorema 3. 2 sebagai

, , … ,

, , , 3 ,

1 0, 1 , 1, 0 .

Teorema 3. 3

Jika s1, s2, …, sn adalah barisan pembangkit yang menentukan sirkuit Hamilton

yang berawal pada suatu simpul, maka barisan yang sama menentukan sirkuit

Hamilton yang berawal pada sebarang simpul.

Bukti:

Misalkan sirkuit Hamilton berawal pada simpul x. Maka dapat diketahui bahwa

simpul-simpul x, xs1, xs1s2, …, xs1s2…sn-1 adalah berbeda dan x = xs1s2…sn.

Sehingga jika digunakan barisan pembangkit yang sama tetapi berawal pada

59  

simpul y, maka dapat ditunjukkan bahwa y, ys1, ys1s2, …, ys1s2…sn-1 adalah

berbeda, dan y = ys1s2…sn.

■

Dari Teorema 3. 1, dapat diketahui bahwa terdapat digraf Cayley dari

grup Abel yang tidak mempunyai sirkuit Hamilton. Tetapi Teorema 3. 4

menunjukkan bahwa setiap digraf Cayley dari grup Abel mempunyai lintasan

Hamilton.

Teorema 3. 4

Misalkan G adalah grup Abel berhingga dan S adalah sebarang himpunan

pembangkit tak kosong untuk G. Maka Cay(S:G) mempunyai lintasan Hamilton.

Bukti:

Akan digunakan induksi matematis pada | . Jika | = 1, katakan S = {a} dan |

= m, maka digrafnya berupa lingkaran yang simpul-simpulnya dinamai dengan e,

a, a2, …, am-1. Dengan jelas, terdapat lintasan Hamilton untuk kasus ini.

| | |

|

|

| | | | | | | | 1

kali, adalah lintasan Hamilton pada Cay(S:G).

Sekarang andaikan bahwa | > 1. Pilih suatu . Misalkan T = S - {s}, yaitu T

adalah S dengan s dikeluarkan, dan himpunan . H adalah subgrup dari G

dan boleh sama dengan G atau H ≤ G. Karena | | < | dan H adalah grup Abel

berhingga, hipotesis induksi menjamin bahwa terdapat lintasan Hamilton (a1, a2,

…, ak) pada Cay(T:H).

Akan ditunjukkan bahwa (a1, a2, …, ak, s, a1, a2, …, ak, s, … , a1, a2, …, ak, s, a1,

a2, …, ak ), dengan a1, a2, …, ak terdapat / kali dan s terdapat /

60  

Karena S = T {s} dan T membangkitkan H, koset Hs membangkitkan grup

faktor G/H. (Karena G adalah grup Abel, grup ini ada.) Sehingga G/H = =

{Hs0, Hs1, Hs2, …, Hsn} = {H, Hs, Hs2, …, Hsn}. Karena itu, koset dari H adalah

elemen-elemen dari G/H, yaitu H, Hs, Hs2, …, Hsn, dan menurut Teorema

Lagrange, n = | /| . | | 1

, | ,

, 0 , , 0 , , 1 :

Karena (a1, a2, …, ak) adalah lintasan Hamilton pada Cay(T:H), berawal dari

elemen identitas dari G, lintasan yang diberikan oleh (a1, a2, …, ak) mengunjungi

setiap elemen dari H tepat sekali. Pembangkit s lalu memindahkannya ke suatu

elemen dari koset Hs. Berawal dari situ, lintasan (a1, a2, …, ak) mengunjungi

setiap elemen dari koset Hs tepat sekali. Lalu, s memindahkannya ke suatu elemen

dari koset Hs2, dan mengunjungi setiap elemen dari koset ini tepat sekali.

Melanjutkan proses tersebut, s berturut-turut memindahkan ke Hs3, Hs4, …, Hsn,

mengunjungi setiap simpul dalam masing-masing koset tersebut tepat sekali.

Karena setiap simpul dari Cay(S:G) adalah tepat salah satu koset Hsi,

mengakibatkan bahwa setiap simpul Cay(S:G) telah dikunjungi tepat sekali. Jadi,

diperoleh lintasan Hamilton.

■

Contoh 3. 9

Misalkan . Maka sirkuit Hamilton dalam

ditunjukkan dalam Gambar 3. 14.

61  

Gambar 3. 14 Digraf Cay({(r, 0), (f, 0), (e, 1)}: )

, | ,

, 0 , , 0 , , 1 :

1 , 0 , , 0 , 1 , 0 , , 1 .

Contoh 3. 10

Misalkan . Maka sirkuit Hamilton dalam

dengan m genap ditunjukkan dalam

Gambar 3. 15. Barisan pembangkit yang menemukan sirkuit adalah

62  

Gambar 3. 15 Digraf Cay({(r, 0), (f, 0), (e, 1)}: )

BAB IV

APLIKASI DIGRAF CAYLEY DARI GRUP UNTUK MEMBUAT

GRAFIK KOMPUTER DARI POLA PERULANGAN TIPE ESCHER

PADA BIDANG HIPERBOLIK

Selama lebih dari seratus tahun, para matematikawan telah menggambar

teselasi segitiga dalam model cakram Poincare pada bidang hiperbolik, dan

beberapa seniman telah menemukan inspirasi dalam pola ini. Seniman grafik

Belanda, M. C. Escher (1898-1972) adalah orang pertama yang paling mungkin

menjadi sangat terinspirasi. Ia menggunakan konstruksi penggaris dan jangka

klasik untuk membuat pola hiperboliknya. Kemudian Douglas Dunham, seorang

profesor ilmu komputer di Universitas Minnesota, Duluth, menggunakan grafik

komputer untuk membuat pola hiperbolik tersebut. Pertama-tama akan dijelaskan

bagaimana Escher menggambar teselasi yang mendasari polanya, lalu akan

digambarkan versi program komputer yang dapat menghasilkan desain tersebut.

A. Metode Escher

Pada tahun 1958, H. S. M. Coxeter mengirimkan kepada Escher salinan

karangannya yang berjudul “Crystal Symmetry and Its Generalizations” (Simetri

Kristal dan Generalisasinya). Dalam balasannya Escher menulis, “…some of the

text-illustrations and especially Figure 7, page 11, gave me quite a shock”

63  

64  

(…beberapa ilustrasi teks dan khususnya Gambar 7, halaman 11, sangat menge-

jutkanku).

Escher terkejut karena gambar itu menunjukkan padanya penyelesaian

yang sudah lama diinginkan untuk persoalannya tentang mendesain perulangan

pola yang motifnya menjadi lebih kecil ke arah limit sirkuler. Gambar 7 dalam

buku karangan Coxeter memuat pola segitiga kurva linear seperti ditunjukkan

dalam Gambar 4. 1 (tetapi tanpa perancah (scaffolding)). Tentu saja, pola itu dapat

diartikan sebagai teselasi segitiga dalam model cakram Poincare untuk bidang

hiperbolik.

Gambar 4. 1 Teselasi Segitiga Dalam Model Cakram Poincare pada Bidang Hi-

perbolik

Pokok dari model cakram Poincare adalah titik dalam dari lingkaran pada

bidang Euclid. Garis pada bidang hiperbolik dinyatakan dengan diameter dan

busur sirkuler yang adalah ortogonal untuk lingkaran. Escher dapat

65  

mengkonstruksi kembali busur sirkuler dalam gambar milik Coxeter dan lalu

menggunakannya untuk membuat pola lingkarannya yang pertama, Circle Limit I,

yang ia masukkan dalam suratnya kepada Coxeter, seperti ditunjukkan dalam

Gambar 4. 2. Gambar 4. 3 menunjukkan terjemahan komputer secara kasar dari

desain Circle Limit I.

Gambar 4. 2 Cetakan Asli Circle Limit I Milik Escher

66  

Gambar 4. 3 Terjemahan Komputer dari Desain Dalam Cetakan Circle Limit I

Milik Escher

Pusat dari busur sirkuler ortogonal berada di luar cakram dan disebut

kutubnya. Tempat semua kutub dari busur yang melalui titik dalam cakram adalah

garis yang disebut polar dari titik itu. Titik luar dalam Gambar 4. 1 adalah kutub

dari busur yang lebih besar, dan ruas garis luar yang menghubungkan mereka

adalah bagian dari polar titik potong busur itu. Gambar 4. 1 menunjukkan salah

satu titik dalam dan polarnya sebagai titik yang lebih besar dan garis tebal pada

sebelah kiri, busur sirkuler dan kutubnya dengan cara yang sama ditegaskan pada

sebelah kanan. Jaring luar dari kutub dan ruas polar terkadang disebut perancah

untuk teselasi. Kenyataan bahwa polar adalah garis dapat digunakan untuk

menghubungkan dengan konstruksi penggaris dan jangka dari teselasi segitiga.

Escher menggunakan cara tradisional untuk menggambar teselasi segitiga dalam

67  

model cakram Poincare, yaitu menggunakan teknik penggaris dan jangka yang

terkadang menunjukkan perancah.

Untuk bilangan bulat positif p dan q, dengan 1/p + 1/q < 1/2, terdapat

teselasi pada bidang hiperbolik oleh segitiga siku-siku dengan sudut lancip π/p

dan π/q. Segi banyak beraturan bersisi p, atau segi-p, dapat dibentuk dari 2p

segitiga di sekitar pusat teselasi. Segi-p ini membentuk teselasi beraturan {p, q}

oleh segi banyak bersisi-p, dengan q dari mereka bertemu pada masing-masing

puncak. Gambar 4. 5 menunjukkan teselasi {6, 4} (dengan pusat berupa kelompok

ikan). Dapat dilihat bahwa pada dasarnya Escher menggunakan teselasi {6, 4}

pada Circle Limit I.

B. Metode Douglas Dunham

Pada tahun 1980, Douglas Dunham memutuskan untuk mencoba

menggunakan grafik komputer untuk membuat kembali desain dalam masing-

masing dari empat cetakan Circle Limit milik Escher. Rupanya tantangan

utamanya adalah menemukan algoritma peniruan yang akan menggambar masing-

masing tiruan dari motif tepat sekali. Terdapat dua alasan untuk ini. Pertama,

waktu itu digunakan teknologi pencetak yang mencetak gambar dengan

menggerakkan suatu pena pada permukaan kertas, jadi penggambaran berkali-kali

dari motif yang sama dapat menyobek kertas. Efisiensi adalah alasan kedua,

jumlah motif meningkat secara eksponensial dari pusat, dan algoritma yang tidak

efisien mungkin menghasilkan penggandaan jumlah eksponensial.

68  

Selain itu, Dunham menginginkan algoritma peniruan untuk membangun

pola keluar yang rata dalam lapisan-lapisan sehingga akan menjadi tanpa tepi

yang bergerigi. Pada waktu itu, koleganya, Joseph Gallian, mempunyai beberapa

mahasiswa penelitian yang bekerja menemukan lintasan Hamilton dalam digraf

Cayley dari grup berhingga. Ia berpikir bahwa teknik mereka juga dapat

digunakan pada grup simetri tak hingga dari desain Circle Limit milik Escher.

Langkah pertama meliputi menemukan lintasan Hamilton dalam digraf

Cayley dari grup simetri untuk teselasi {p, q}. Ini dilakukan oleh David Witte,

salah satu mahasiswa penelitian Gallian. John Lindgren, seorang mahasiswa Uni-

versitas Minnesota, Duluth, melaksanakan algoritma komputer dan bersama

Dunham menerjemahkan lintasan yang ditemukan oleh Witte ke dalam pseudo-

FORTRAN.

Secara teknik, digraf Cayley dari grup mendefinisikan graf berarah, tetapi

dalam konstruksi ini invers dari masing-masing elemen s juga akan di S, jadi

untuk kesederhanaan boleh dianggap bahwa digraf Cayley-nya tak berarah.

Sebagai contoh, grup simetri dari teselasi {p, q} dinotasikan [p, q]. Grup simetri

itu sama dengan teselasi oleh segitiga siku-siku dengan sudut π/p dan π/q.

Himpunan pembangkit standar untuk grup [p, q] adalah {P, Q, R}, di mana P, Q,

dan R adalah pencerminan melewati sisi-sisi segitiga berlawanan sudut π/p, π/q,

dan π/2, berturut-turut, dalam salah satu segitiga seperti itu.

Di sini gambaran visual berguna untuk digraf Cayley dari grup [p, q] dan

lintasan Hamilton-nya. Daerah dasar untuk teselasi {p, q} adalah segitiga yang

saat bertindak dengan grup simetri [p, q] mempunyai teselasi itu sebagai orbitnya.

69  

Daerah dasar ini dapat diambil dari segitiga siku-siku yang terletak pada diameter

mendatar ke pusat cakram, dengan puncak π/p nya pada pusat cakram. Segitiga ini

dinamai dengan identitas [p, q]. Masing-masing segitiga dari teselasi lalu dinamai

dengan elemen grup yang mengubah bentuk daerah dasar ke segitiga itu. Sehingga

masing-masing segitiga menyatakan suatu elemen grup. Untuk menyatakan busur

dari digraf Cayley digambar ruas garis yang menghubungkan pusat dari sebarang

dua segitiga membagi suatu sisi. Jadi, terdapat tiga ruas garis keluar dari masing-

masing segitiga, masing-masing menyatakan pencerminan melewati satu sisi.

Gambar 4. 4 menunjukkan lintasan Hamilton dalam digraf Cayley dari

grup [6, 4] dengan himpunan pembangkit standar. Ruas garis tebal, hitam dan

abu-abu, menyatakan digraf Cayley, garis tipis menunjukkan teselasi segitiga.

Lintasan Hamilton terdiri dari ruas garis hitam tebal.

Gambar 4. 4 Graf Cayley dari Grup [6, 4] dengan Lintasan Hamilton

70  

Gambar 4. 5 Supermotif Pusat untuk Circle Limit I

Langkah kedua yang sebenarnya adalah untuk menemukan lintasan

Hamilton dalam graf Cayley dari grup simetri dari desain Circle Limit milik

Escher. Pertama-tama akan dibangun supermotif (pola segi-p) yang terdiri dari

semua motif yang berdekatan dengan pusat cakram. Supermotif untuk desain

Circle Limit I ditunjukkan dalam Gambar 4. 5.

Lalu langkah kedua terdiri dari menemukan lintasan Hamilton dalam graf

koset Cayley. Secara konsep, akan dibentuk koset dari grup simetri dari

supermotifnya. Lalu, secara analog dengan digraf Cayley biasa, didefinisikan

simpul menjadi koset dan mengatakan bahwa terdapat busur dari xH ke yH jika

yH = sxH untuk suatu s di S.

Sekali lagi, di sini gambaran visual berguna untuk graf koset. Simpul

dapat disamakan dengan segi-p dalam teselasi {p, q}. Segi-p pusat dinamai de-

71  

ngan H, dan sebarang segi-p yang lain dinamai dengan xH, di mana x adalah

sebarang elemen dari grup simetri yang memetakan segi-p pusat ke segi-p yang

lain tersebut. Dalam kasus ini himpunan pembangkit S terdiri dari kata-kata dalam

pembangkit dari grup simetri. Untuk masing-masing sisi dari segi-p pusat,

terdapat sekurang-kurangnya satu kata yang memetakan segi-p pusat melewati sisi

itu. Seperti sebelumnya, busur dari graf dinyatakan sebagai ruas garis di antara

pusat dari segi-p. Gambar 4. 6 dan 4. 7 menunjukkan graf koset dari subgrup [6,

4]. Sekali lagi, busur dari graf adalah garis tebal, hitam atau abu-abu, dan garis

tipis menunjukkan teselasi {6, 4}. Busur dari graf yang berwarna hitam dalam

Gambar 4. 6 menunjukkan lintasan Hamilton.

Gambar 4. 6 Lintasan Hamilton Dalam Graf Koset dari [6, 4]

72  

Gambar 4. 7 Pohon Perentang Dalam Graf Koset dari [6, 4]

Salah satu kelemahan dari metode ini adalah bahwa lintasan Hamilton

harus tersimpan dalam memori komputer. Ini bukan masalah serius, karena

lintasan dapat disandikan dengan bilangan bulat yang kecil. Metode itu pada

dasarnya bekerja dengan membentuk rangkaian simbol yang lebih panjang pada

pembangkit dari busur-busur lintasan Hamilton. Transformasi tersebut dinyatakan

dengan matriks bilangan real, yang membawa pada pembulatan galat setelah

terlalu banyak matriks telah dikalikan bersamaan untuk membentuk matriks

transformasi tertentu. Ini adalah masalah yang lebih serius.

Kedua masalah tersebut dihilangkan dengan menggunakan rekursi.

Sehingga yang diperlukan adalah menemukan pohon Hamilton atau lebih

tepatnya, pohon perentang dalam graf koset. Pohon tersebut melintang dengan

73  

mengubah secara rekursif melewati sisi tertentu dari segi-p tersebut. Sisi itu

ditentukan dengan kombinatorik yang hampir sederhana. Dengan metode ini

lintasan dari akar (segi-p pusat) ke segi-p tersebut secara otomatis tersimpan

dalam tempat rekursi. Demikian juga, kedalaman rekursi tidak pernah lebih dalam

daripada lusinan, jadi tidak terdapat pembulatan galat yang terlihat jelas dari

mengalikan transformasi. Busur dari graf yang berwarna hitam dalam Gambar 4. 7

menunjukkan pohon perentang dalam graf koset [6, 4].

  

BAB V

PENUTUP

A. Kesimpulan

Digraf Cayley dari grup berhingga G dengan himpunan pembangkit S

atau Cay(S:G) dibentuk dari setiap elemen G sebagai simpul dari digraf dan

terdapat sebuah busur berarah dari x ke y untuk x dan y di G jika dan hanya jika xs

= y untuk suatu s di S.

Jika terdapat lebih dari satu pembangkit, maka untuk membedakan pem-

bangkit yang berbeda digunakan busur utuh, busur putus-putus, dan busur titik-

titik. Dalam digraf Cayley dari grup dapat digunakan busur tak berarah. Busur tak

berpanah menghubungkan dua simpul x dan y menyatakan bahwa terdapat suatu

busur dari x ke y dan suatu busur dari y ke x. Ini terjadi jika himpunan pembangkit

memuat anggota yang inversnya adalah dirinya sendiri dalam grup tersebut.

Dengan digraf Cayley dari grup menjadi mudah untuk melihat orde dari

beberapa elemen grup, yaitu orde dari elemen identitas dan orde dari pembangkit

yang digunakan. Dengan digraf Cayley juga lebih mudah untuk menentukan nilai

dari sebarang hasil kali dari pembangkit atau inversnya.

Dalam digraf Cayley dari grup terdapat lintasan dan sirkuit Hamilton.

Sebagai syarat perlu adalah tidak mempunyai

sirkuit Hamilton jika m dan n adalah relatif prima dan lebih besar daripada 1.

1, 0 , 0, 1 :

74  

75  

1, 0 , 0, 1 :Sebagai syarat cukup adalah mempunyai sirkuit

Hamilton jika n membagi m.

Dari syarat perlu dapat diketahui bahwa terdapat digraf Cayley dari grup

Abel yang tidak mempunyai sirkuit Hamilton. Akan tetapi, setiap digraf Cayley

dari grup Abel berhingga G dengan himpunan pembangkit S atau Cay(S:G)

mempunyai lintasan Hamilton.

Digraf Cayley dari grup dapat digunakan untuk membuat grafik

komputer dari pola perulangan tipe Escher pada bidang hiperbolik.

B. Saran

Pembahasan aplikasi digraf Cayley dari grup yang telah dibahas dalam

skripsi ini dapat dilanjutkan dengan menyertakan algoritma yang digunakan untuk

membuat grafik komputer dari pola perulangan tipe Escher pada bidang

hiperbolik dan menjelaskan lebih lanjut mengenai algoritma tersebut.

76  

DAFTAR PUSTAKA

Dummit, D. S. & Foote, R. M. (1991). Abstract Algebra. Upper Saddle River: Prentice-Hall, Inc.

Dunham, D. (2003). Creating Repeating Hyperbolic Patterns−Old and New. Notices of The AMS. 50 (4): 452-455. 1 Desember 2008. <http://www.ams.org/notices/200304/fea-escher.pdf>

Fraleigh, J. B. (2003). A First Course in Abstract Algebra (7th ed). New York: Pearson Education, Inc.

Gallian, J. A. (1998). Contemporary Abstract Algebra (4th ed). Boston: Duluth Houghton Mifflin Company.

Herstein, I. N. (1996). Abstract Algebra (3th ed). Upper Saddle River: Prentice-Hall International, Inc.

Rosen, K. H. (2007). Discrete Mathematics and Its Applications (6th ed). New York: McGraw-Hill, Inc.

Schwalbe, P. & Averbeck, E. (2006). Cayley Digraphs of Groups. Winona State University. 17 September 2008. <http://course1.winona.edu/jdebnath/documents/SchwalbeAverbeck.pdf>