3-FLOWS DALAM GRAF CAYLEY PADA GRUP NILPOTENT
PROPOSAL TUGAS AKHIR
Oleh Dinny Fitriani BP. 0810432039
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS ANDALAS 2011
Daftar Isi
Daftar Isi
ii
I
PENDAHULUAN
1
I.1
Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
I.2
Perumusan Masalah
. . . . . . . . . . . . . . . . . . . . . . . . .
4
I.3
Pembatasan Masalah . . . . . . . . . . . . . . . . . . . . . . . . .
4
I.4
Tujuan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
I.5
Sistematika Penulisan . . . . . . . . . . . . . . . . . . . . . . . . .
5
II LANDASAN TEORI
6
II.1 Definisi dan Terminologi dalam Teori Graf . . . . . . . . . . . . .
6
II.2 Grup Abelian dan Nilpotent serta graf Cayley . . . . . . . . . . .
8
III 3-FLOWS DALAM GRAF CAYLEY PADA GRUP NILPOTENT 13
ii
I PENDAHULUAN
I.1
Latar Belakang Teori graf pertama kali diperkenalkan pada tahun 1736 oleh seorang ma-
tematikawan terkenal Swiss yang bernama Leonhard Euler. Teori graf pertama muncul untuk memecahkan teka-teki masalah Jembatan Konigsberg yang sangat sulit dipecahkan pada masa itu. Konigsberg adalah suatu kota di Prusia bagian timur Jerman. Seiring perkembangan zaman dan kemajuan teknologi, aplikasi teori graf telah merambah disiplin ilmu lainnya dan membantu memudahkan orang untuk menyelesaikan permasalahan. Penggunaan graf ditekankan untuk memodelkan persoalan. Teori graf juga sangat berguna untuk mengembangkan model-model yang terstruktur dalam berbagai situasi. Sejak itu, teori graf berkembang seiring dengan ditemukannya masalah-masalah dalam kehidupan yang dapat diselesaikan dengan teori graf, seperti masalah jaringan listrik, jaringan telepon, jaringan komputer, jalan penghubung antar kota dan lain sebagainya. Dugaan dari suatu flow pada suatu graf tergolong pada konsep penting dari teori graf sementara dengan banyak aplikasi, baik pada teori graf maupun di luar teori graf. Secara khusus, suatu nowhere-zero k -flow pada suatu graf G adalah suatu orientasi di G dan suatu penugasan nilai 1, . . . , k − 1 ke sisi berarah di G sedemikian hingga Hukum Kirchhoff dipenuhi, yaitu, jumlah flow yang masuk 1
sama dengan jumlah flow yang keluar. Suatu nowhere-zero A-flow, dimana A adalah sebarang grup Abelian, didefinisikan serupa. Pada kasus ini, nilai flow adalah non-zero element di A. Suatu pengkajian yang sistematis dari nowhere-zero flows dimulai dengan seminal paper[8] dari Tutte dimana, tiga konjektur berikut. Konjektur 5-Flow: Setiap graf tanpa jembatan memiliki suatu nowherezero 5-flow. Konjektur 4-Flow: Setiap graf tanpa jembatan tanpa Petersen minor mengandung suatu nowhere-zero 4-flow. Konjektur 3-Flow: Setiap graf tanpa jembatan tanpa 3-edge-cuts mengandung suatu nowhere-zero 3-flow. Jelas bahwa suatu graf dengan suatu jembatan tidak bisa memiliki suatu nowhere-zero k -flow untuk sebarang k. Di sisi lain, tidak jelas apakah terdapat suatu batas ”universal” hingga n sedemikian hingga setiap graf tanpa jembatan mengandung suatu nowhere-zero n-flow. Pertanyaan apakah k = 5 memenuhi kondisi pada konjektur belum terjawab. Batas 5 masih menjadi kemungkinan terbaik karena graf Petersen sebagai suatu minor dan tidak memiliki nowhere-zero 4-flow. Sekalipun jika benar, konjektur 4-flow tidak akan menjadi kemungkinan terbaik sebagaimana setiap graf lengkap dengan paling sedikit 10 titik memuat graf Petersen sebagai suatu minor dan memiliki suatu nowhere-zero 3-flow([4] halaman 134). Graf kubik tanpa jembatan yang tidak memiliki 4-flow disebut snarks. Oleh
2
karena itu, Konjektur 4-Flow untuk graf kubik menyatakan bahwa setiap snark yang memuat graf Petersen sebagai suatu minor. Lagipula, Jaeger menunjukkan bahwa setiap graf 4-edge terhubung mengandung suatu nowhere-zero 4-flow. Catat bahwa sebarang graf transitif-titik dari valency k adalah k -edge terhubung. Itu mengikuti bahwa setiap graf transitiftitik dari valency 4 memiliki suatu nowhere-zero 4-flow. Konsep dari suatu graf Cayley pertama kali diperkenalkan pada tahun 1878 oleh Cayley. Karena graf Cayley adalah transitif-titik, graf Cayley dari valency paling sedikit empat mengandung suatu nowhere-zero 4-flow. Tutte membuktikan bahwa terdapat suatu keterhubungan yang kuat antara k -flows dan A-flows. Suatu graf mengandung suatu nowhere-zero k -flow jika dan hanya jika graf tersebut mengandung suatu nowhere-zero A-flow untuk suatu grup Abelian A. Karena jumlah dari dua A-flows adalah juga suatu A-flow, kadang-kadang lebih mudah untuk mengkonstruksi A-flows daripada k -flows. Secara alami, hal yang sama tidak diaplikasikan untuk nowhere-zero A-flows. Teorema lainnya menyatakan bahwa jika suatu graf G memiliki suatu nowhere-zero flow dengan paling banyak k nilai berbeda, graf G tersebut juga memiliki suatu Zk+1 -flow. Untuk k ≥ 5, hal ini adalah aplikasi trivial dari teorema 6-flow Seymour. Ketika k ≤ 4, bukti didasarkan pada suatu permasalahan teori bilangan yang disebut ”Lonely Runner Conjecture”. Konjektur lain yang dikenal adalah bahwa sebarang graf Cayley dari valency paling sedikit empat memiliki suatu cycle Hamilton. Itu mengikuti dari keterhubungan antara Zk -flows dan k -flows bahwa sebarang graf dengan suatu
3
cycle Hamiltonian mengandung suatu nohwere-zero 4-flow. Sayangnya, kita tidak dapat menarik kesimpulan bahwa graf Hamiltonian memiliki suatu nowhere-zero 3-flow. Pada konteks ini kita menyebutkan konjektur penyangkal Babai yang menyebutkan bahwa tidak hanya terdapat suatu graf Cayley yang bukan Hamiltonian, tapi untuk beberapa konstanta c ≥ 0, terdapat banyak graf transitif-titik yang tak terhingga, sekalipun graf Cayley, tanpa cycle yang panjangnya lebih besar dari (1 − c)n, n menjadi order dari graf. Faktanya, terdapat suatu graf Cayley yang bukan Hamiltonian. Poto˘ cnik [6] memperumum hasil untuk graf yang mengandung suatu aksi transitif-vertex dari suatu grup yang dapat dipecahkan (tidak termasuk graf Petersen).
I.2
Perumusan Masalah Adapun masalah yang dibahas dalam tugas akhir ini adalah bagaimana
mengkaji keberadaan nowhere-zero 3-flow pada graf Cayley di grup nilpotent dari valency paling sedikit empat.
I.3
Pembatasan Masalah Penulisan pada tugas akhir ini akan difokuskan untuk pembahasan tentang
keberadaan nowhere-zero 3-flow pada graf Cayley di grup nilpotent dari valency paling sedikit empat.
4
I.4
Tujuan Tujuan dari penulisan ini adalah untuk mengkaji keberadaan nowhere-zero
3-flow pada graf Cayley di grup nilpotent dari valency paling sedikit empat.
I.5
Sistematika Penulisan Sistematika penulisan ini terdiri dari tiga bab, yakni :
BAB I
:
Bab ini berisikan latar belakang, perumusan masalah, pembatasan masalah, tujuan dan sistematika penulisan.
BAB II
: Bab ini berisikan teori-teori yang akan digunakan dalam menyelesaikan permasalahan yang dibahas pada penulisan ini.
BAB III
:
Bab ini berisikan pembahasan mengenai permasalahan yang dibahas beserta hasilnya.
BAB IV
:
Pada bab ini berisikan tentang kesimpulan dari penelitian dan saran bagi penelitian selanjutnya.
5
II LANDASAN TEORI
Dalam bab ini akan diperkenalkan beberapa konsep dasar yang berkaitan dengan permasalahan yang telah dikemukakan di Bab I. Definisi dan terminologi dalam teori graf disajikan pada Subbab 2.1, kemudian pada Subbab 2.2 diuraikan tentang grup Abelian dan nilpotent serta graf Cayley.
II.1
Definisi dan Terminologi dalam Teori Graf Graf adalah suatu lipat empat G = (V, D, L, I) dimana D = D(G) dan
V = V (G) adalah himpunan hingga tak kosong yang terpisah, I → V adalah suatu pemetaan surjektif, dan L adalah suatu permutasi di D. Anggota dari D dan V adalah anak panah dan titik, berturut-turut, I adalah fungsi terkait yang menugaskan untuk setiap anak panah titik awalnya dan L adalah fungsi balikan anak panah dimana L(x) = x−1 . Orbit dari grup hLi pada D adalah sisi di K. Kita tidak mengizinkan L(x) = x. Valency dari suatu titik v, ditulis sebagai val(v), adalah banyaknya sisi yang berkaitan dengan v. Graf dimana semua titiknya memiliki valency yang sama disebut graf reguler. Suatu graf 3-reguler disebut kubik. Banyaknya titik dari suatu graf G adalah order nya, ditulis sebagai |G|. Graf dikatakan hingga, tak hingga, dan lain-lain tergantung pada ordernya. Untuk graf kosong (∅, ∅) kita sederhanakan dengan menulis ∅. Suatu graf
6
dengan order 0 atau 1 disebut trivial. Suatu lintasan adalah suatu graf tak kosong P = (V, E) dari formula V = {x0 , x1 , . . . , xk }
E = {x0 x1 , x1 x2 , . . . , xk−1 xk }
dimana semua xi berbeda. Banyaknya sisi dari suatu lintasan adalah panjangnya, dan lintasan dengan panjang k ditunjukkan dengan P k . Jika P = {x0 . . . xk−1 } adalah suatu lintasan dan k ≥ 3 maka graf C := P + xk−1 x0 disebut suatu cycle. Sebuah jalan di G adalah sebuah barisan hingga tak nol W = v0 e1 v1 e2 v2 · · · ek vk yang suku-sukunya berupa titik-titik dan sisi-sisi, sedemikan sehingga, untuk 1 ≤ i ≤ k, ujung-ujung dari ei adalah vi−1 dan vi . Bilangan bulat k adalah panjang dari W. Suatu graf tak kosong G dikatakan terhubung jika sebarang dua titiknya dihubungkan oleh suatu lintasan di G. Sebuah graf H adalah sebuah subgraf dari G (ditulis H ⊆ G) jika V (H) ⊆ V (G), E(H) ⊆ E(G), dan ψH adalah pembatasan dari ψG untuk E(H). Misal G = (V, E) suatu graf. Suatu subgraf maksimal terhubung disebut suatu komponen dari G. Sebuah titik yang memisahkan dua titik lainnya pada komponen yang sama disebut suatu cutvertex, dan suatu sisi yang memisahkan ujung-ujungnya disebut suatu jembatan. Jika G = M X adalah suatu subgraf dari graf lain Y, kita sebut X suatu minor dari Y dan ditulis X 4 Y . Jika |G ≥ 3| maka sebarang jalan adalah suatu cycle: suatu Hamilton cycle di G. Jika G memiliki Hamilton cycle, itu disebut Hamiltonian.
7
II.2
Grup Abelian dan Nilpotent serta graf Cayley Misal A adalah suatu grup Abelian dengan notasi tambahan. Suatu fungsi
f : D(X) → A adalah suatu A-flow pada X jika dua kondisi berikut dipenuhi: (i) f (x−1 ) = −f (x), untuk setiap anak panah x ∈ D(X); (ii) Σx∈D(u) f (x) = 0, untuk setiap titik u ∈ V (X). Jika f (x) 6= 0 untuk setiap anak panah x, f disebut suatu nowhere-zero A-flow pada X. Suatu Z-flow yang mengambil nilai di {1, . . . , (k − 1)} disebut suatu nowhere-zero k-flow. Graf Cayley berguna dalam teori keterhubungan jaringan. Diberikan suatu grup G dengan suatu anggota identitas 1 dan suatu barisan S = {s1 , s2 , . . . , sn } dari anggota G − {1} sedemikian hingga S −1 = S, anak panah dari Cay(G,S ) adalah pasangan terurut (g, si ) dimana g ∈ G dan si ∈ S. Anak panah (g, si ) memiliki titik awal g dan titik akhir gsi , dan L(g, si ) = (gsi , s−1 i ). Barisan S disebut barisan Cayley. Catat bahwa suatu graf dikatakan terhubung jika dan hanya jika anggotaanggota S membangkitkan G. Namun, dalam tulisan ini kita memperbolehkan graf Cayley tidak terhubung. Graf Cayley adalah simetris. Mereka adalah transitif titik dan oleh karena itu reguler. Sebagaimana yang telah disebutkan sebelumnya, setiap graf Cayley dengan valency paling sedikit empat mengandung suatu nowhere-zero 4-flow. Juga, semua graf Cayley pada grup yang dapat dipecahkan mengandung nowherezero 4-flows. Semua grup pada tulisan ini diasumsikan hingga. Suatu subgrup H dari 8
suatu grup G adalah normal, ditunjukkan oleh H £ G, jika gHg −1 ⊆ H untuk setiap g ∈ G. Yaitu, jika H invariant di bawah semua automorphism inner. Jika H adalah invariant di bawah semua automorphism, maka H disebut suatu karakteristik subgrup di G. Lemma 2.1. Misal G adalah suatu grup dengan suatu subgrup normal H. Jika K £ G dan K ⊆ H, maka K £ H dan H/K £ G/K. Pusat dari suatu grup G, ditunjukkan dengan Z(G), adalah suatu subset dari semua anggota sedemikan hingga gh = hg untuk setiap h ∈ G. Pusat memainkan peranan penting dalam pengkajian dari suatu struktur grup. Catat bahwa hal itu adalah suatu karakteristik subgrup di G. Diantara grup dengan suatu pusat tak kosong, suatu peranan penting dimainkan oleh p-grup. Untuk sebarang bilangan prima p, suatu p-grup adalah suatu grup dari order menjadi suatu kekuatan dari p. Karena order dari suatu subgrup membagi order dari grup, sebarang subgrup dari suatu p-grup adalah juga suatu p-grup. Itu mengikuti bahwa sebarang grup hasil bagi dari suatu p-grup adalah suatu p-grup juga. Banyak sifat struktural dari grup hingga tergantung pada p-subgrup dari suatu graf yang diberikan. Diberikan suatu grup G, suatu p-Sylow subgrup dari G adalah sebarang p-grup yang maksimal dengan respek pada pencantuman. Suatu grup G disebut nilpotent jika grup tersebut memiliki suatu deret normal 1 = G0 £ G1 £ . . . £ Gn−1 £ Gn = G 9
sedemikian hingga Gj+1 /Gj ≤ Z(G/Gj ) untuk sebarang j. Sedemikan suatu deret normal disebut suatu deret pusat di G. Panjang terpendek dari deret nilpotent dari suatu grup disebut kelas nilpotency di G. Teorema 2.2. Suatu grup nilpotent adalah isomorfik ke suatu product berarah dari subgrup Sylownya. Faktanya, setiap grup nilpotent adalah isomorfik ke suatu product berarah dari p-grup. Grup nilpotent memiliki sifat yang mirip ke p-grup. Mereka memiliki suatu pusat tak kosong dan sebarang subgrup dari suatu grup nilpotent adalah nilpotent. Lagipula, sebarang grup hasil bagi dari grup nilpotent adalah juga nilpotent. Teorema 2.3. Kelas dari grup nilpotent adalah dekat di bawah pengambilan subgrup, hasil bagi dan product berarah. Akhirnya kita mendefinisikan grup yang dapat dipecahkan, suatu kelas dari grup yang memuat semua grup nilpotent dan Abelian. Suatu grup G disebut dapat dipecahkan jika memiliki suatu deret normal 1 = G0 ¥ G1 ¥ . . . ¥ Gn−1 ¥ Gn = {1} dengan grup faktor Abelian Gi+1 /Gi untuk i di {1, . . . , n}. Sedemikian suatu deret normal disebut suatu deret yang dapat dipecahkan di G. Terdapat suatu pendekatan alternatif untuk grup yang dapat dipecahkan yang lebih panjang, bagaimanapun, membuat beberapa sifat berguna yang lebih mudah untuk menarik kesimpulan. Pertama, kita perkenalkan istilah commutator. Misal G adalah suatu grup dan g, h ∈ G. Commutator dari g dan h adalah 10
[g, h] = ghg −1 h−1 . 0
Subgrup commutator di G, ditunjukkan dengan G , G(1) atau [G, G] adalah subgrup di G yang dibangkitkan oleh commutator dari anggotanya. Sedemikan suatu subgrup juga disebut subgrup derived di G. Secara induktif, kita bisa mendefinisikan G(2) sebagai subgrup commutator dari G(1) , G(3) sebagai subgrup commutator dari G(2) , dan seterusnya. Subgrup G(i) adalah subgrup derived ke-i dari G. Subgrup commutator di grup memiliki beberapa sifat menarik. Pertama, [g, h] = e jika dan hanya jika g dan h commute. Oleh karena itu, G adalah Abelian 0
jika dan hanya jika G(1) trivial. Secara umum, subgrup G mengukur commuta0
tivity dari suatu grup. G terkecil adalah subgrup yang lebih commutative. Misal α adalah suatu automorphism di grup G. Catat bahwa α([g, h]) = α(ghg −1 h−1 ) = α(g)α(h)α(g −1 α(h−1 ) = [α(g), α(h)] 0
0
Oleh karena itu, α(G ) = G untuk sebarang automorphism α. Mudah untuk melihat bahwa G(m) adalah suatu karakteristik subgrup dari grup G untuk sebarang bilangan bulat m. Sekarang, kita siap untuk memperkenalkan deskripsi alternatif dari grup yang dapat dipecahkan. Teorema 2.4. Suatu grup dapat dipecahkan jika dan hanya jika untuk beberapa G(k) adalah trivial k ∈ N. Sebagai suatu konsekuensi dari teorema ini, sebarang grup yang dapat dipecahkan memiliki suatu karakteristik subgrup Abelian G(k−1) . Teorema berikut 11
adalah salah satu yang memperbolehkan kita untuk menggunakan induksi pada pembuktian nantinya. Teorema 2.5. Kelas dari semua grup yang dapat dipecahkan adalah dekat di bawah pengambilan subgrup, grup hasil bagi dan product berarah. Kita akan mengakhiri bagian ini dengan teorema berikut yang memperhatikan teori grup. Teorema 2.6. Setiap grup Abelian adalah isomorfik ke suatu product berarah dari grup cyclic.
12
III 3-FLOWS DALAM GRAF CAYLEY PADA GRUP NILPOTENT
Untuk mengkaji keberadaan nowhere-zero 3-flow pada graf Cayley di grup nilpotent dari valency paling sedikit empat pada penulisan ini, akan digunakan lema-lema berikut: Lemma 3.1. Misal G adalah suatu grup dan H suatu subgrup normal di G. Misal S adalah suatu barisan Cayley dengan irisan kosong dengan H. Jika Cay(G/H,S/H) memiliki suatu nowhere-zero 3-flow, maka Cay(G,S) juga memiliki suatu nowherezero 3-flow. Lemma 3.2. Misal G adalah suatu grup hingga dan misal H £ G adalah suatu subgrup normal Abelian dari order genap. Maka G memuat suatu pusat involution. Adapun teorema yang ingin dibuktikan adalah sebagai berikut. Teorema 3.3. Misal G adalah suatu grup dengan suatu subgrup normal Abelian H. Misal Cay(G,S) adalah suatu graf Cayley dengan valency paling sedikit 4 sedemikian hingga terdapat suatu involution di S ∩ H. Maka Cay(G,S) memiliki suatu nowhere-zero 3-flow. Teorema 3.4. Setiap graf Cayley Cay(G,S) pada grup nilpotent dengan valency paling sedikit 4 memiliki suatu nowhere-zero 3-flow.
13
DAFTAR PUSTAKA
[1] J. A. Bondy dan U.S.R.Murty, Graph Theory with Applications. Macmillan, London, (1976). [2] L. Babai, Automorphism groups, isomorphism, reconstruction di Handbook of Combinatorics (R. L. Graham, M. Grt¨schel dan L. Lov´ asz, dkk). Elsevier Scince, Amsterdam, (1955), 1447-1540. [3] W. Bienia, L. Goddyn, P. Gvozdjak, A. Sebo, M. Tarsi, Flows, View-Obstructions and the Lonely Runner, J. Combin Theory Ser. B 72 (1998), 1-9. [4] R. Diestel, Graph Theory. Springer Verlag, New York, (2000). [5] W. Imrich and R. Skrekovski, A theorem on integer flows on Cartesian product of graphs, J. Graph Theory 43 (2003), 93-98. [6] P. Poto˘ cnik, Edge-colourings of cubic graphs admitting a solvable vertextransitive group of automorphisms, J. Combin Theory Ser B 91 (2004), 289300. [7] J. Shu and C.-Q. Zhang, Nowhere-zero 3-flows in products of graphs, J. Graph Theory, 2005. [8] W. T. Tutte, A contribution on the theory of chromatic polynomial, Canad. J. Math. Soc. 51, (1954)80-81.
14
