Jurnal Ilmiah “DUNIA ILMU” Vol.2 No.1 Maret 2016
RANDOM SUBGRAPH Oleh: Lena Rosdiana Pangaribuan, S.Pd, M.Si Abstrak Tesis ini mempelajari suatu random even subgraph dari graph finite G dengan bobot edge yang secara umum p ∈ (0,1). Tesis ini menggambarkan bagaimana random even subgraph diperoleh dari ukuran random cluster tertentu di G dan menganjurkan algoritma sampling berdasarkan coupling-from-the-past (cftp). Bagian-bagian dari graph akan dibahas dan dihubungkan pada SchrammLöwner Evolutions (SLE). Adapun tujuan dari penelitian ini adalah untuk menentukan random even subgraph dari suatu graph finite G = (V, E) dengan menggunakan algoritma sampling. Pada tahapan akhir, algoritma yang digunakan berdasarkan pada algoritma sampling untuk menentukan suatu random even subgraph.
Kata Kunci: Random even subgraph , algoritma sampling
1. Pendahuluan
V(F) ⊆ V(G) , E(F) ⊆ E(G), dan 𝜓
1.1 Latar Belakang Masalah
F adalah batasan dari 𝜓 G ke E(F). Sehingga dapat dikatakan bahwa G
Suatu graph G adalah pasangan
terdiri dari F atau F terdapat di G dan
terurut (V(G), E(G)) yang terdiri dari
ditulis G ⊇ F atau F ⊆ G, secara
himpunan V(G) vertex dan himpunan
berurut. (Bollobas, 1984)
E(G) yang disjoint dari V(G) yaitu edge, yang secara bersama-sama
Adapun
contoh
random
merupakan fungsi incident 𝜓G yang
subgraph dari graph finite yakni
mengaitkan dengan setiap edge di G
subgraph dari graph lengkap yang
yang merupakan pasangan urut dari
vertexnya (V) diperoleh dengan cara
vertex di G (Bondy dan Murty,
menghapus
2007). Secara umum, suatu graph F
dengan peluang 1 – p dan pertama
dikatakan subgraph dari graph G jika
sekali diperkenalkan oleh Erdös dan
123
edge
secara
bebas
Jurnal Ilmiah “DUNIA ILMU” Vol.2 No.1 Maret 2016
Rényi pada tahun 1960. Mereka
himpunan
menunjukkan
p
digunakan lagi sebagai gabungan
diskalakan sebagai (1 + ∈)V , ada
edge-point dari cycle. (Grimmet,
suatu peralihan fase pada ∈ = 0 yang
2009)
bahwa
ketika -1
genap
F
bisa
tidak
dalam pengertiannya bahwa ukuran Dalam
dari komponen yang paling besar
menentukan
random
adalah 𝜃(log V). Random even
subgraph ini diperlukan suatu model
subgraph dari suatu graph yang finite
yang cocok untuk memilih subgraph
G dengan bobot edge yang secara
yang acak. Sekilas akan dibahas
umum mengarah pada p ∈ (0,1).
model
Grimmet (2009).
peluangnya. Di sisi lain, random
tersebut
dengan
ukuran
subgraph G diperoleh secara acak Random
even
subgraph
dari
(random)
planar lattice mengalami suatu fase
setiap
1
dan edge
bebas
menghapus
dengan
peluang
peralihan dengan nilai parameter 2 pc
(kemungkinan) 1 – p dan 𝜌p adalah
, di mana pc adalah titik kritis dari q
aturan dari random subgraph yang
= 2 model random-cluster di dual
berlaku jika genap. Suatu model di G
lattice. Setiap graph akan dibahas
mempunyai bentuk ruang dan juga
dan
memiliki
dihubungkan
dengan
SLE
ukuran
suatu
peluang.
(Schramm-Löwner
Evolutions).
Ukuran random-cluster di G dengan
Tujuannya
mengetahui
parameter p dan q = 2 yang
random even subgraph dari graph
digambarkan secara umum untuk q >
yang finite G = (V, E) dan untuk
0, namun hanya bersifat pada kasus q
menunjukkan
= 2.
adalah
bagaimana
menggunakan subgraph. Suatu subset F dari E disebut genap, jika untuk
Hampir semua informasi yang
semua x ∈ V , x berincident dengan
mungkin
jumlah anggota F genap. Subgraph
bahwa subgraph dari beberapa host
(V, F) dikatakan genap jika F genap,
graph
dan ditulis ℇ untuk himpunan dari
mempunyai
semua subset genap F di E. Ini
yang
merupakan
memiliki
acuan
bahwa
setiap
124
kita
(graf
dapat menyatakan
asal)
sering
ukuran-ukuran
menjadi
penghalang
informasi
yang
kali besar atau tidak
Jurnal Ilmiah “DUNIA ILMU” Vol.2 No.1 Maret 2016
lengkap.
Pertanyaannya
𝜌p(F) =
adalah
1
𝑝 𝐹 (1 − 𝑝) 𝐸\𝐹 , F ∈
𝑍𝐸
apakah random subgraph dari graph
ℰ
yang diberikan harus ada atau tidak.
dimana ΖE = Ζ𝐺𝐸 𝑝 .
(2.1)
Random subgraph Gp dari graf G terjadi apabila setiap edge di Gp
Mencari
bebas menghapus setiap edge dengan
juga
Misalkan 𝜙𝑝 adalah product measure
dengan peluang 1 – p.
dengan density p pada bentuk ruang = {0,1}E. Untuk 𝜔 ∈ dan 𝑒 ∈ 𝐸,
1.2.Tujuan
dikatakan 𝜔-open jika 𝜔(𝑒) = 1 dan
Tujuan dari penelitian ini adalah
𝜔-closed
untuk menentukan random even
dengan
untuk
yang
lainnya.
Misalkan 𝜕𝜔 adalah himpunan dari
subgraph dari graph yang finite G = E)
dapat
menggunakan cara sebagai berikut.
peluang p, dan membuang edge
(V,
𝜌p
vertex
menggunakan
𝑥∈𝑉
yang
berincident
dengan jumlah edge ganjil pada 𝜔-
algoritma sampling.
open. Sehingga 2. Uraian Teoritis
𝜌𝑝 (𝐹) = 𝜙
2.1.Random Even Subgraph
𝜙 𝑝 (𝜔 𝐹 ) 𝑝 (𝜕𝜔
= ∅)
,
F∈ℰ
(2.2)
Suatu subset F di E dikatakan
dimana 𝜔𝐹 adalah bentuk edge yang
genap jika, untuk semua 𝑥 ∈ 𝑉,
himpunan edge terbukanya adalah F.
terhadap
Dengan kata lain, 𝜙𝑝 digambarkan
jumlah anggota F genap. Sehingga
sebagai random subgraph G yang
subgraph (V, F) dikatakan genap jika
diperoleh secara acak dan bebas
dimana
F
genap
𝑥
berincident
dan
ℰ ditulis
menghapus
sebagai
setiap
edge
dengan
himpunan dari semua subset genap F
peluang (kemungkinan) 1 – p dan 𝜌𝑝
di E. Dikatakan standar jika setiap
merupakan
himpunan genap F bisa dihapus dari
subgraph yang berlaku jika genap.
gabungan edge-disjoint di cycle-nya.
(Grimmet, 2009)
aturan
dari
random
Misalkan p ∈ [0, 1) , maka random 2.2.Finite Graph
even subgraph G dengan parameter p
Suatu graph dikatakan finite
dapat ditunjukkan sebagai berikut :
apabila suatu graph dengan jumlah yang finite di vertex dan edge-nya.
125
Jurnal Ilmiah “DUNIA ILMU” Vol.2 No.1 Maret 2016
Jika graph memiliki n vertex dan
modul tambahan cara pada {0,1}E ,
tidak memiliki kelipatan edge atau
sehingga
graph yang loop, maka graph finite
pengambilan
merupakan
pada himpunan edgenya : F1 + F2 =
subgraph
dari
graph
diterjemahkan perbedaan
sebagai simetris
F1 ∆ F2 untuk F1, F2 ⊆ E.
komplit Kn. Suatu graph yang tidak finite disebut dengan infinite. Jika
Family dari even subgraph G
setiap vertex memiliki derajat yang
merupakan bentuk dari subspace ℰ
finite, maka graph itu disebut sebagai
pada ruang vektor {0,1}E , sehingga
daerah yang finite. (Biggs, 1993)
F1 + F2 = F1 ∆ F2 dikatakan genap jika F1 dan F2 juga genap. (Pada
Pada kasus p = 𝜌p(F)
persamaan 𝑝) 𝐸\𝐹 , setiap
dimana even
1
=
𝑍𝐸
1
(cycle space) Ζ1 pada ℤ2 -homology
𝑝 𝐹 (1 − ∈
F
subgraph
kenyataannya, ℰ adalah ruang cycle
pada
2
di G sebagai suatu kompleks yang
ℰ,
sederhana). Pada khususnya, jumlah
memiliki
even subgraph di G sama dengan
peluang yang sama, sehingga 𝜌1
2c(G) , dimana c(G) = dim(ℰ) ; dengan
2
dikatakan
sebagai
random
even
demikian c(G) adalah jumlah cycle
subgraph yang uniform di G. Peluang yang
dipilih
p
=
1 2
bebas di G, dan diperoleh : c(G) = 𝐸 − 𝑉 + 𝑘(G)
karena
memberikan hasil pada persamaan 𝜌p, sedangkan jika p = 1 akan
Preposisi 1. Misalkan C1, . . . , Cc
memberikan
bernilai
adalah himpunan maksimal dari
0.Sehingga random subgraph dapat
cycle bebas di G. Misalkan 𝜉1 , . . .
diperoleh sebagai berikut. Pertama-
, 𝜉𝑐
tama
variabel
hasil
identifikasikan family dari
adalah bebas dari random (sebagai
contoh,
hasil
lemparan koin yang adil). Sehingga
semua spanning subgraph di G = (V,
𝑖 𝜉𝑖 𝐶𝑖
E) dengan family 2E dari semua
merupakan random even
subset di E. Family ini dapat
subgraph yang uniform di G.
diidentifikasikan lebih lanjut dengan
Bukti : C1, . . . , Cc adalah basis dari
{0,1}E = ℤ𝐸2 dan dengan demikian
ruang vektor ℰ di atas ℤ2 .
ruang vektornya (vector space) diatas ℤ2 ; sebagai tambahannya adalah 2
126
Jurnal Ilmiah “DUNIA ILMU” Vol.2 No.1 Maret 2016
Salah
satu
cara
yang
prosedur random sampling dari suatu
dilakukan dalam memilih C1, . . . , Cc
n
adalah dengan memanfaatkan dalil
network (jaringan). Pilih edge secara
yang berikutnya. Pada dalil yang
acak dari jaringan, lalu perluas
berikutnya,
subgraph
akan
menggunakan
vertex
subgraph
secara
pada
suatu
berulang-ulang
spanning subforest di G yang berarti
dengan memilih edge tetangganya
suatu maximal forest di G, yaitu
secara
gabungan spanning tree dari setiap
subgraph n.
acak
hingga
membentuk
komponen di G. Untuk setiap pilihan acak dari Preposisi 2. Misalkan (V, F) adalah
suatu edge, dalam memilih suatu
spanning subforest di G. Setiap
edge sebaiknya ukuran subgraph
subset X di E \ F dapat diselesaikan
diperluas dari pertama, kemudian
dengan kekhususan Y ⊆ F pada
siapkan
himpunan edge genap EX = X ∪ Y ∈
(calon) edge, lalu lakukan pemilihan
ℰ. Memilih random subset yang
edge secara acak dari daftar itu
uniform X ⊆ E \ F akan memberikan
sendiri. Jadi, contoh subgraph dapat
suatu random even subgraph yang
digambarkan
uniform EX juga di G.
himpunan vertex n dan semua edge
Bukti : Setiap edge 𝑒𝑖 ∈ E \ F dapat
yang terhubung diantara vertex pada
diselesaikan dengan edge di F pada
original network (tidak hanya edge
cycle yang unik Ci ; dimana cycle ini
yang
merupakan dasar dari ℰ dan hasilnya
perluasan).
seperti pada dalil 1. (Grimmet dan
untuk sampling yang tidak uniform.
daftar
semua
kandidat
sebagai
dipilih
suatu
dengan
proses
Penilaian yang
tepat
Janson, 2009) Suatu subgraph yang spesifik adalah suatu himpunan n yang
2.3.Sampling Subgraph Contoh-contoh
terhubung dengan vertex dalam suatu
algoritma
subgraph n dari pemilihan edge
jaringan.
Peluang
dari
sampling
secara acak yang terhubung dengan
subgraph
spesifik
yang
berbeda
suatu
dalam
himpunan
dicapai.Selanjutnya
n
dapat
jaringan
tidaklah
sama
meskipun mempunyai topologi yang
digambarkan
127
Jurnal Ilmiah “DUNIA ILMU” Vol.2 No.1 Maret 2016
sama. Untuk menilai ini, kita akan
Dalam hal ini algoritma yang akan
menghitung
dipergunakan
peluangnya
P,
dari
adalah
algoritma
sampling subgraph yang spesifik.
sampling yang tujuannya pemilihan
Setiap jenis subgraph akan menerima
random subgraph ini sesuai dengan
skor / nilai. Kemudian, kita akan
yang diinginkan. Dapat dikatakan
menambah skor berat W =
1 𝑝
ada
untuk
batasannya
dalam
memilih
random subgraph dari graph yang
skor jenis subgraph yang relevan. Ini
ada.
diulang untuk mendapatkan jumlah 4. Hasil Penelitian
banyaknya sampel spanning tree.
4.1. Random Even Subgraph Dengan demikian, kita dapat
Random even subgraph dengan
menghitung konsentrasi semua jenis subgraph
menurut
parameter p [0, 1) didefinisikan
skor/nilainya.
dari persamaan 𝜌p(F) =
Untuk contoh subgraph n, himpunan
1 𝑍𝐸
𝑝 𝐹 (1 −
terurut n – 1 edge dipilih berulang-
𝑝) 𝐸\𝐹 untuk suatu graph finite G =
ulang secara acak. Sedangkan untuk
(V,
menghitung
dari
memasangkan model random-cluster
perlu
q = 2 dan random even subgraph di
peluang
G. Misalkan p [0, 2] dan 𝜔 sebagai
(kemungkinan) himpunan terurut n –
realisasi model random cluster di G
1 edge yang menuju pada sampling
dengan parameter 2p dan q = 2.
subgraph. Kashtan et al (2004)
Misalkan R = (V, 𝛾) sebagai random
sampling memeriksa
peluangnya subgraph, semua
P
kita
E).
Selanjutnya
bagaimana
1
even subgraph yang uniform di (V, 𝜂(𝜔)).
3. Metode Penelitian
1
Metode penelitian ini secara
Teorema 4.1. Misalkan p [0, 2].
ringkas seperti berikut ini. Pertama
Graph R = (V, γ) adalah random
sekali buat suatu graph yang terdiri
even
subgraph
di
G
dengan
dari vertex dan edge. Kemudian dari
parameter p.Bukti : Misalkan g ⊆ E
graph ini, pilih subgraph-nya secara
genap dan c(𝜔) = c(V, 𝜂(𝜔))
acak. Untuk memilih subgraph yang
merupakan jumlah cycle bebas pada
acak digunakan suatu algoritma.
open subgraph,
128
Jurnal Ilmiah “DUNIA ILMU” Vol.2 No.1 Maret 2016
ℙ 𝛾=𝑔 𝜔 = 2−𝑐
dikatakan
𝜔
jika 𝑔 ⊆ 𝜂 𝜔 0 yang lain
W-genap
jika
setiap
komponen dari (V, H) terdiri dari jumlah anggota dari W genap. Misalkan W ≠ ∅ adalah himpunan
sehingga
vertex G dengan derajat ganjil, ℙ 𝛾=𝑔 =
sehingga, secara khusus, E adalah
−𝑐 𝜔 𝜔 :𝑔⊆𝜂(𝜔 ) 2
𝜙2𝑝,2 (𝜔)
W-genap. Asumsikan Ω𝑊 = {𝜔 ∈ Ω : 𝜂 𝜔 adalah W-genap}. Untuk 𝜔 ∈
(4.1)
Ω𝑊 ,
Jika c(𝜔) = 𝜂 𝜔 − 𝑉 + 𝑘(𝜔) ,
1 2
ℙ 𝛾=𝑔 2𝑝
(1
− 2𝑝)
2
𝑝𝜂
∝
𝑘 𝜔
𝜔
terbuka
merupakan titik akhir tepat satu path.
𝜔 − 𝑉 +𝑘 𝜔
(1 − 2𝑝) 𝐸\𝜂
Ditulis 𝑃𝜔 =
𝜔
𝜔 :𝑔⊆𝜂(𝜔 )
𝑖 𝑖 𝑃𝜔
.
Misalkan r = 2(1 – p), dan 𝑊 misalkan 𝜙𝑟,2 adalah ukuran random
[𝑝 + (1 −
= 2𝑝)] 𝐸\𝑔 𝑝 𝑔
cluster pada Ω dengan parameter r =
𝑝 𝑔 (1 − 𝑝)] 𝐸\𝑔
g ⊆ E.
dan q = 2 bersyarat pada kejadian ,
𝑊 Ω 𝑊 . Ambil sample dari 𝜙𝑟,2 untuk
(4.2)
memperoleh subgraph (V, 𝜂(𝜔)) ,
1
Misalkan p (2, 1). Jika G
dengan memilih suatu random even subgraph yang uniform (V, 𝛾).
genap, maka contoh dari 𝜌𝑝 dengan sampling
non-self-intersecting
di W, sehingga setiap anggota di W
1 2𝜂
disjoint
dengan titik akhir nyata yang terletak
𝜔 :𝑔⊆𝜂(𝜔 ) 𝐸\𝜂 𝜔
yang
𝑊 , dari 𝜂 𝜔 , yang merupakan
path
∝
subset
𝑃𝑖 = 𝑃𝜔𝑖 , dimana i = 1, 2, . . . ,
maka :
𝜂 𝜔
pilih
(pengambilan)
1
pertama
Teorema 4.2. Misalkan p (2 , 1).
suatu subgraph (V, 𝐹 ) dari 𝜌1−𝑝 dan
Graph S = (V, E \ (γ ∆ Pω )) adalah
komplemennya (V, 𝐸 \ 𝐹 ) memiliki
suatu random even subgraph di G
distribusi 𝜌𝑝 . Jika G ganjil, maka
dengan parameter p.
akan disesuaikan seperti berikut ini. Untuk W ⊆ V dan H ⊆ E ; H
129
Jurnal Ilmiah “DUNIA ILMU” Vol.2 No.1 Maret 2016
Diberikan himpunan egde genap f ⊆
Teorema 4.1. dan teorema 4.2.
dapat
digabungkan
sebagai
E, sehingga diperoleh F = f jika
berikut. Dengan mempertimbangkan
pemilihan pertama 𝜔 Ω𝑊 dengan
model yang dibangun dengan satu
𝜂(𝜔) ⊇ 𝑓 ∆ 𝐴 dan kemudian (𝑃𝜔
parameter 𝑝𝑒 (0,1) untuk setiap
telah terpilih) pilih 𝛾 sebagai even
edge 𝑒 E. Misalkan A = {𝑒 E :
subgraph 𝑓 ∆ 𝐴 ∆ 𝑃𝜔 . Karena itu,
1
𝑝𝑒 > 2}. Didefinisikan bahwa 𝑟𝑒 =
untuk setiap 𝜔 Ω𝑊
2𝑝𝑒 jika 𝑒 ∉ A dan 𝑟𝑒 = 2(1 – 𝑝𝑒 ) jika
𝜂(𝜔) ⊇ 𝑓 ∆ 𝐴,
𝑒 A. (Jadi 0 < 𝑟𝑒 ≤ 1). Misalkan
ℙ 𝐹 = 𝑓 𝜔 = 2−𝑐(𝜔) .
W = WA adalah himpunan vertex A∝
jumlah edge ganjil di A. Sample 𝜔
2−𝑐
𝜔
𝜙𝒓,2 (𝜔)
2−𝑐
𝜔
2𝑘
𝜔 :𝜂 (𝜔)⊇𝑓∆𝐴
dari ukuran random-cluster dengan
∝
parameter r = (𝑟𝑒 : 𝑒 E) dan q = 2,
𝑟𝑒𝜔
𝑤
𝜔 :𝜂 (𝜔)⊇𝑓∆𝐴
menjadi W-genap,
− 𝑟𝑒
misalkan Pω (untuk W = WA) , dan
2− 𝜂
− 𝑟𝑒
Teorema 4.3. Graph S = (V,
𝑟𝑒𝜔
𝜔
− 𝑟𝑒
𝜌𝒑 .Bukti : Misalkan F = 𝛾 ∆ 𝑃𝜔 ∆ 𝐴
𝑒∈𝑓∆𝐴
𝜂(𝜔) ⊇ 𝛾 ∆ 𝑃𝜔 =
𝑟𝑒 2
𝜔 𝑒
1
1− 𝜔 𝑒
=
merupakan hasil dari himpunan edge
1
1− 𝜔 𝑒
𝜔 :𝜂 (𝜔)⊇𝑓∆𝐴 𝑒∈𝐸
subgraph di G dengan distribusi
𝑒
𝑒∈𝐸
=
𝛾 ∆ 𝑃𝜔 ∆ 𝐴) adalah random even
1
𝑒∈𝐸
𝜔 :𝜂 (𝜔)⊇𝑓∆𝐴
uniform (V, 𝛾) pada (V, 𝜂(𝜔)).
𝑒
1− 𝜔 𝑒
∝
sample random even subgraph yang
sehingga
diperoleh
ℙ 𝐹=𝑓
ganjil, sebagai contoh, titik akhir dari
sehingga 𝜂 𝜔
dengan
𝑟𝑒 2
1− 𝑒∉𝑓∆𝐴
𝑟𝑒 2
𝐹 ∆ 𝐴.
Dengan 1e yang merupakan fungsi
(4.3)
indikator pada kejadian {𝑒 ∈ 𝑓}, dapat ditulis kembali seperti berikut Selanjutnya, jika F genap,
maka
𝐹∆𝐴
mempunyai
ini :
derajat
ganjil tepat pada vertexnya W = WA , karena itu pers. (4.3) menunjukkan bahwa
𝜔
Ω𝑊
diperlukan. 130
Jurnal Ilmiah “DUNIA ILMU” Vol.2 No.1 Maret 2016
dimana 𝑁(h) adalah jumlah subgraph
ℙ 𝐹=𝑓 ∝ 𝑒∉𝐴
−
𝑟𝑒 2
𝑟𝑒 2
1𝑒
1−1𝑒
di atas, 𝑁 = 2 − 𝑉 +𝑘() dimana
𝑟𝑒 2
1−1𝑒 𝑒∈𝐴
= 𝑝𝑒
genap di (V, h). Seperti pembuktian
1 1−1𝑒
𝑝𝑒
𝑒∉𝐴
1−1𝑒 𝑒∈𝐴(𝑝𝑒 )
= 𝑝𝑒
𝑟𝑒 2
1−
1𝑒
1𝑒
𝑘() adalah jumlah komplemen dari (V, h).
1− 1𝑒
1 − 𝑝𝑒 𝑝𝑒
𝑒∉𝐴
Suatu edge 𝑒 dari graph
1𝑒
disebut cyclic jika edge tersebut 1−
termasuk di dalam beberapa cycle
1−1𝑒
suatu graph. ∝ 𝜌𝒑 (𝑓).
Corollary : Untuk 𝑝 ∈ 0,
(4.4)
1 2
dan
𝑒 ∈ 𝐸, 𝜌𝑝 (e terbuka) = Ini
bertentangan
dengan
1 2
𝜙2𝑝,2 (e adalah
suatu cyclic edge di graph terbuka)
dengan Teorema 4.1. Ambil random
Dengan menghitung di atas
even subgraph (V, F) di G = (V, E)
𝑒 ∈ 𝐸, dapat disimpulkan bahwa
1
dengan parameter p ≤ 2 . Untuk
rata-rata
jumlah
edge
terbuka
setiap 𝑒 ∉ 𝐹, dapat ditentukan suatu
dibawah 𝜌𝑝 adalah setengah dari
warna random bebas, biru dengan
rata-rata jumlah cyclic edge dibawah
peluang p / (1 – p) dan merah untuk
𝜙2𝑝,2 .Bukti : Misalkan 𝜔 ∈ Ω dan 𝒞
yang lainnya. Misalkan H diperoleh
adalah maximal family dari cycle
dari F dengan menambahkan di
bebas 𝜔. Misalkan R = (V, 𝛾) adalah
semua edge biru.
random even subgraph yang uniform di (V, 𝜂(𝜔)) , suatu tafsiran yang
Teorema 4.4. Graph (V, H) memiliki
menggunakan Dalil 2.2 dan 𝒞 .
aturan 𝜙2𝑝,2 .
Untuk 𝑒 ∈ 𝐸, misalkan Me adalah
Bukti : Untuk ⊆ 𝐸 ,
jumlah
ℙ(𝐻 = ) ∝ 𝑝
𝐽 ⊆, 𝐽 genap 1−𝑝
𝐽
𝑝
\𝐽
1−𝑝
1−2𝑝
𝐸\
1−𝑝
elemen
dari
𝒞
yang
memasukkan e. Jika Me ≥ 1, maka jumlah cycle Me pada 𝛾 yang telah terpilih dalam susunan/bentuk pada
∝ 𝑝 1 − 2𝑝
𝐸\
𝑁
𝛾 adalah sama seperti penggunaan
,
genap atau ganjil. Oleh karena itu,
(4.5)
131
Jurnal Ilmiah “DUNIA ILMU” Vol.2 No.1 Maret 2016
1
ℙ 𝑒∈𝛾𝜔 =
bagaimana menyesuaikan teknik cftp
jika 𝑀𝑒 ≥ 1
2
0 jika 𝑀𝑒 = 0
pada beberapa situasi.
(4.6)
Misalkan E adalah suatu himpunan finite tak kosong dan 𝜇
4.2.Sampling Even Subgraph
adalah ukuran peluang pada product Seperti
dinyatakan
diawal
space Ω = {0, 1}E. Dikatakan 𝜇
bahwa Teorema 4.1 memberikan
monoton
suatu cara yang sistematis pada
dengan
𝜂𝑝 dengan p ≤ the-past
(cftp)
ukuran 1 2
decreasing
peluang
(respectively,
non-
increasing) dimana 𝜉 ∈ Ω. Dimana,
. Coupling-from-
1𝑒 adalah fungsi indikator yang
digunakan
edge-nya e adalah terbuka dan 𝜉𝑒
untuk memberi contoh pada ukuran
adalah bentuk yang diperoleh dari 𝜉
random-cluster 𝜙2𝑝,2 , kemudian
pada E \ {e}. Untuk 𝑒 ∈ 𝐸, 𝜓 ∈ Ω,
melepaskan koin secara adil sekali
dan b = 0,1 , maka 𝜓𝑒𝑏 ditulis sebagai
untuk setiap anggota dari beberapa
bentuk yang sesuai dengan 𝜓 pada e
himpunan bebas yang maksimal dari
dan memperoleh nilai b pada e.
cycle
kembali
Secara standar cftp mungkin dapat
implementasi
digunakan untuk sample dari 𝜇 jika 𝜇
G.
hanya
anti-
monoton) jika 𝜇 1𝑒 𝜉𝑒 adalah non-
sampling even subgraph di G yang sesuai
(respectively,
Diingatkan
bahwasannya (pelaksanaan)
ini
adalah monoton dan akan dijelaskan
berdasarkan pada periode waktu T
bagaimana menyesuaikan apabila 𝜇
secara acak yang bagian akhirnya
adalah
dibatasi
distribusi
mekanisme diusulkan sebagai hasil
geometri ; yang berakhir dengan
dalam sample yang tepat dari 𝜇 tanpa
oleh
dari
cftp
suatu
peluang 1 dengan suatu sample yang
asumsi
tepat dari target distribusi. Sedikit lebih rumit ketika p >
1
anti-monoton.
apapun
dari
Suatu
(anti-
)monotonicity. Mekanisme ini dapat
dan G tidak
digunakan dalam kerangka umum
hanya genap, sehingga dilihat dari
yang lebih banyak pada “bounding
situasinya ukuran random cluster
chain”, akan tetapi tidak sesuai
digunakan dalam Teorema 4.2 dan
dalam pekerjaannya, karena pada
4.3 baik monoton maupun anti-
kenyataannya Ω adalah partially
monoton. Kemudian akan dicari
ordered (orde sebagian).
2
132
Jurnal Ilmiah “DUNIA ILMU” Vol.2 No.1 Maret 2016
Misalkan 𝑆𝜇
= {𝜔 ∈ Ω :
tidak berada dalam 𝑆𝜇 dan pada
𝜇 𝜔 > 0} , subset dari Ω yang
akhirnya diperoleh :
mana 𝜇 adalah strictly positive
μ 1𝑒 𝜉𝑒
(benar-benar positif) dan asumsikan
(4.7)
increasing dan 1 ∈ 𝑆𝜇 , dimana 1 bentuk
0)
max
μ 1𝑒 𝜓𝑒 : 𝜓𝑒 ≥ 𝜉𝑒 , 𝜓𝑒1 ∈ 𝑆𝜇
secara sederhana bahwa 𝑆𝜇 adalah
(respectively,
=
dimana 𝜉𝑒1 ∉ 𝑆𝜇 .
menunjukkan
untuk ‘semua bernilai 1’
Misalkan
(respectively, ‘semua bernilai 0’).
(𝑒𝑛 , 𝑈𝑛 )
adalah
barisan yang independent (bebas).
Asumsi ini dikatakan valid pada
Asumsikan (𝐴𝑛 , 𝐵𝑛 ∶ 𝑛 ≥ 0) adalah
pengaturan sekarang ini (current
Markov chain dengan state space Ω2
setting) , tetapi tidak dapat digunakan
dan (𝐴0 , 𝐵0 ) = (0, 1). Anggap
untuk semuanya seperti berikut ini.
(𝐴𝑛 , 𝐵𝑛 ) = (𝜉 , 𝜂) dimana 𝜉 ≤ 𝜂.
Dimulai dengan contoh Gibbs
Buat (𝐴𝑛+1 , 𝐵𝑛+1 ) = (𝜉′ , 𝜂′) dimana
yang biasa/lazim digunakan untuk 𝜇.
𝜉′(𝑓) = 𝜉(𝑓) , 𝜂′(𝑓) = 𝜂(𝑓) untuk
Ini
𝑓 ≠ 𝑒𝑛+1
adalah
suatu
discrete-time
Markov chain G = (Gn : n ≥ 0) pada state space Ω. Anggap Gn =
𝜉.
𝑈𝑛+1 ≤ 𝛼 , 𝜂′(𝑒) = 1 jika dan hanya jika
juga variabel random U dengan
Kemudian Gn
+ 1
pada
[0,
𝑈𝑛+1 ≤ 𝛽 ,
1].
= 𝜉′ dimana 𝜉′(𝑓) dimana
untuk 𝑓 ≠ 𝑒 dan 𝜉′(𝑒) =
𝑒 = 𝑒𝑛+1 .
𝜉′(𝑒) = 1 jika dan hanya jika
E sudah terpilih, sebut saja 𝑒, dan
uniform
dimana
Diperoleh :
Secara uniform distribusi anggota di
distribusi
,
0 jika U > μ 1𝑒 𝜉𝑒 . 1 jika U ≤ μ 1𝑒 𝜉𝑒
𝛼 = 𝛼 𝜉 ,𝜂 = min μ 1𝑒 𝜓𝑒 : 𝜉𝑒 ≤ 𝜓𝑒 ≤ 𝜂𝑒 ,
Aturan
transisi
baik
digunakan 𝛽 = 𝛽 𝜉 ,𝜂 =
jikalau 𝜉𝑒1 ∈ 𝑆𝜇 . Ini baik sekali digunakan
dalam
max μ 1𝑒 𝜓𝑒 : 𝜉𝑒 ≤ 𝜓𝑒 ≤ 𝜂𝑒 .
memperluas
(4.8)
definisi dari susunan/bentuk yang
133
Jurnal Ilmiah “DUNIA ILMU” Vol.2 No.1 Maret 2016
Sehingga 𝛼 ≤ 𝛽 , kita mempunyai
Pada kejadian ini, proses A yang
𝜉′ ≤ 𝜂′.
rendah mendapat nilai 1 setelah intervalnya
Rantai (A, B) dimulai pada
lewat,
sehingga
perpaduannya ada. Kejadian yang
waktu yang negatif (negative times),
sesuai dengan interval waktu yang
merupakan cara yang ditentukan oleh
berbeda
cftp. Misalkan T adalah waktu
dikatakan
bebas
(independent), dimana bagian akhir
perpaduan (coalescence time). Lebih
dari waktu T tidak lebih besar
tepatnya lagi, untuk 𝑚 ≥ 0, misalkan
daripada geometri.
(𝐴𝑘 𝑚 , 𝐵𝑘 𝑚 ∶ −𝑚 ≤ 𝑘 ≤ 0) menunjukkan bahwa rantai dimulai
Misalkan G = (V, E) adalah
dengan 𝐴−𝑚 𝑚 = 0 , 𝐵−𝑚 𝑚 = 1 ,
graf finite, dan W ⊆ V merupakan
yang menggunakan suatu barisan
himpunan vertex tak kosong dengan
0 −∞
𝑊 genap. Misalkan r = (𝑟𝑒 ∶ 𝑒 ∈ 𝐸)
random
yang
fixed
𝑒𝑛 , 𝑈𝑛
untuk semua 𝑚, dan diperoleh
adalah jumlah vektor dari (0, 1] dan asumsikan
T = min { m ≥ 0 : 𝐴0 𝑚 , 𝐵0 𝑚 } ,
random
(4.9)
cluster
sebagai
ukuran
di
dengan
G
parameter edge r dan q ≥ 1.
sehingga 𝐴0 𝑇 , 𝐵0 𝑇 .
Kemudian sebagai
Jika 𝑆𝜇 increasing
Teorema 4.5.
Dari
persamaan 𝜂 𝐸, 𝜇 > 0
dimana
anti-monoton. Kejadian 𝑆𝜇
𝑆𝜇
dan
dengan
terdapat
𝜂=
(increasing) dan 1 ∈
definisi
(4.7),
kejadian
sedemikian
𝜙𝑟,𝑞 ditulis graph
𝑊 bahwa 𝜙𝑟,𝑞 baik monoton maupun
dan 𝐴0 𝑇 memiliki aturan 𝜇. :
𝑊 𝜙𝑟,𝑞 untuk
terbuka adalah W-genap dan catatan
dan 1 ∈ 𝑆𝜇 , maka 𝑃 𝑇 < ∞ = 1
Bukti
𝜙𝑟,𝑞
mudah
dapat
meningkat 𝑆𝜇 . Oleh
sehingga
karena itu, Teorema 4.5 dapat juga
μ 1𝑒 𝜉𝑒 ≥ 𝜂 untuk semua 𝑒 ∈ 𝐸 dan
𝑊 digunakan pada ukuran 𝜇 = 𝜙𝑟,𝑞 .
𝜉 ∈ Ω. Pada setiap panjang interval
Grimmet dan Janson (2009)
waktu yang diberikan 𝐸 , terdapat peluang positif yang utuh yang barisannya
(𝑒𝑖 , 𝑈𝑖 )
memenuhi
𝐸 = 𝑒𝑖 dan 𝑈𝑖 < 𝜂 untuk semua 𝑖.
134
Jurnal Ilmiah “DUNIA ILMU” Vol.2 No.1 Maret 2016
1
ukuran peluang 𝜂𝑝 dengan 𝑝 ≤ 2.
5. Kesimpulan Dalam
penelitian
ini
Sehingga
dapat
hanya
dengan
disimpulkan beberapa hal sebagai
menggunakan cftp inilah untuk
berikut :
memberi contoh (sample) pada ukuran random cluster 𝜙2𝑝,2 .
1. Subgraph (V, F) dikatakan genap jika F-nya genap dan ditulis ℇ
DAFTAR PUSTAKA
untuk himpunan semua subset
Biggs N.L., (1993), Algebraic Graph
genap F di E. F ⊆ E dikatakan genap jika untuk semua 𝑥 ∈ 𝑉, dimana 𝑥 berincident terhadap
Theory,2nd
ed.,
Cambridge,
England
:
Cambridge
University Press, p. 161.
jumlah anggota F genap. Bollobás
2. Random even subgraph dengan
B.,
(1984),
Random
parameter p [0, 1) didefinisikan
Graphs, 2nd ed., Cambridge,
dari suatu persamaan 𝜌p(F) =
Baton Rouge.
1 𝑍𝐸
𝑝 𝐹 (1 − 𝑝) 𝐸\𝐹
untuk suatu
Bollobás B., Grimmet G., Janson S., (1996), The Random Cluster
graph finite G = (V, E). 3. Jika peluangnya p = setiap
even
1
Model On The Complete
, maka
2
subgraph
Graph, Math. Stat., 104, 283-
akan
317.
memiliki peluang yang sama, sehingga 𝜌1 dikatakan sebagai
Bondy J.A. dan Murty U.S.R.,
2
random
even
subgraph
(2007),
yang
Graph
Theory,
Springer, Berlin.
uniform di G. 1
4. Misalkan p ∈
,1 ,
jika G
Borgs C., Chayes J.T., Hofstad R.,
genap, maka sampel dari 𝜌𝑝
Slade G., dan Spencer J.,
dengan
pertama
(2004), Random Subgraphs Of
subgraph (V, 𝐹 ) dari 𝜌1−𝑝 dan
Finite Graphs : I. The Scaling
komplemennya (V, E\𝐹 ) memiliki
Window Under The Triangle
2
sampling
distribusi
𝜌𝑝 .
subgraph
di
Sampling G
Condition, New York.
even
menggunakan
135
Jurnal Ilmiah “DUNIA ILMU” Vol.2 No.1 Maret 2016
Chung F., Horn P., dan Lu L., (2002),
The
Giant
In
A
Random Subgraph Of A Given Graph, California. Clark L., (2002), Random Subgraphs Of
Certain
Graph Powers,
IJMMS 32:5 , 285-292. Grimmett G. dan Janson S., (2009), Random
Even
Graphs,
Electron. J. Combin. 16. Grimmett G. dan Kesten H., (1984), Random Electrical Networks On Complete Graphs II : Proofs, J. Lond. Math. Soc., 30, 171-192. Kashtan N., Itzkovitz S., Milo R., dan Alon U., (2004), Efficient Sampling
Algorithm
Estimating
For
Subgraph
Concentrations And Detecting Network
Motifs,
Bioinformatics, 20, 1746-1758. Soshnikov A. dan Sudakov B., (2003),
On
Eigenvalue
Of
The
Largest
A
Random
Subgraph Of The Hypercube, Comm. Math. Phys., 239, 5363.
136
