matematika diskrit

MATEMATIKA DISKRIT
TEORI GRAF DAN APLIKASINYA
PEMBAHASAN:NETWORK

OLEH
VIVI FEBRIYANTI
NIM 52014

Dosen pembimbing: Prof. Dr Ahmad Fauzan,M.Pd, M.Sc

PROGRAM PASCA SARJANA UNIVERSITAS NEGERI PADANG
PROGRAM STUDI TEKNOLOGI PENDIDIKAN
KONSENTRASI PENDIDIKAN MATEMATIKA
TAHUN AJARAN 2009/2010
NETWORKS

1. PENGERTIAN NETWORKS

Sebuah network N = (V(N), I(N)) adalah sebuah graph-berarah sederhana berhubung lemah yang setiap busurnya dikaitkan dengan bilangan real non negatif. Bilangan real non negatif yang dikaitkan pada busur (vi ,vj), atau disingkat (i,j), pada network N disebut kapasitas busur (vi,vj), dan dilambangkan dengan c(vi ,vj ) atau disingkat c(i,j). Titik s di Network N disebut titik sumber jika id(s)= 0 dan sebuah titik t di network N disebut titik tujuan jika 0d(t) = 0, sedangkan titik lain di network N disebut titik-titik antara.
Contoh:
Network N dengan titik sumber vs dan titik tujuan vt dapat dilihat pada gambar. 1 berikut

Keterangan:
v1 dan v2 titik antara pada Network N
Busur adalah : (vs, v1) atau (s.1), (v1, v2) atau (1,2), (v1,vt) atau (1,t), (vs,v2) atau (s,2), (v2,vt) atau (2,t)
Kapasitas busur: (vs, v1) atau (s.1) adalah c(s,1) =3
Kapasitas busur: (v1, v2) atau (1,2) adalah c(1,2) = 2
Kapasitas busur: (v1,vt) atau (1,t) adalah c(1,t) = 5
Kapasitas busur: (vs,v2) atau (s,2) adalah c(s,2) = 4
Kapasitas busur: (v2,vt) atau (2,t) adalah c( 2, t) = 6.

Misalkan X dan Y dua himpunan bagian V(N) pada network N. Himpunan semua busur N yang berawal di X dan berujung di Y dilambangkan dengan B(X,Y). Total kapasitas semua busur di B(X,Y) dilambangkan dengan c (X,Y) dengan demikian:
jika X ={vs ,v1} dan Y = {v2,vt }, maka B(X,Y} ={(s,2),(1,2),(1,t)} dan
c(X,Y) =c(s,2)+c(1,2)+c(1,t) = 4 + 2 + 5 = 11.
jika B(X,Y) = ɸ dan c(X,Y) = 0.
jika X = {v1,vt} dan Y={v2} , maka B(X,Y) = {(1,2)} dan c(X,Y) = c(1,2) = 2
jika B(X,Y) = {(v2,vt)} dengan c(Y,X) = c(2,t) =6

2. PEMUTUSAN PADA NETWORKS
Misalkan N sebuah network dengan titik sumber s dan titik tujuan t . Misalkan himpunan X adalah himpunan bagian tak kosong dari V(N) dan Xt = V(N)-X. Jika s ϵ X dan t ϵ X1, maka himpunan busur B(X,X1) disebut sebuah pemutus-(s,t) dari Network N. Disebut demikian, karena penghapusan semua bususr B(X,X1) dari N, memutus semua lintasan berarah dari titik s ketitik t pada network N.
Misalkan A adalah himpunan titik antara pada Network dan A’ adalah sebuah himpunan bagian A. Jika X = {t} U A’, maka B(X,X1) sebuah pemutus –(s,t) pada N. Jadi banyaknya pemut us-(s,t) pada network N sama dengan banyaknya himpunan bagian dari himpunan A yaitu 2¬¬¬¬¬n dengan n = |A|.
Misalkan , network N pada gambar 1 memiliki 2 titik antara yaitu v1 dan v2, sehingga terdapat 22 = 4 pemutus-(s,t) pada N yaitu:
B({vs},{v1, v2, vt}) = {(s,1),(s,2)}
B({vs, v1}, {v2, vt}) = {(s,2),(1,2),(1,t)}
B({vs,v2},{v1, vt}) = {(s,1),(s,t)}
B({vs, v1,v2}, { vt}) = {(1,t),(2,t)}
Setiap pemutus-(s,t) pada network N mempunyai kapasitas. Pemutus-(s,t) yang mempunyai kapasitas terkecil disebut pemutus-(s,t) minimum. Masing-masing kapasitas dari keempat pemutus tersebut adalah:
c({vs},{v1,v2,vt}) = c(s,1) +c (s,2) = 3 +4 = 7;
c({vs,v1},{v2,vt}) = c(s,2) +c (1,2)+c(1,t) = 4+2+5 = 11;
c({vs,v2},{v1,vt}) = c(s,1) +c (2,t) = 3 +6 =9;
C({vs,v1,v2},{ vt}) = c(1,t) +c (2,t) = 5+6 = 11;
Tampak bahwa B({vs},{v1, v2, vt}) = {(s,1),(s,2)} dengan kapasitas 7 merupakan sebuah pemutus-(s,t) minimum pada network N.

3. KONSEP FLOW PADA NETWORKS
Misalkan N sebuah network dengan titik sumber s dan titik tujuan t. Jika v adalah sebuah titik N, maka himpunan semua busur N yang keluar dari titik v (meninggalkan titik v) dilambangkan dengan O(v) dan himpunan semua busur N yang menuju ke titik v, dilambangkan dengan I(v). Perhatikan network N dengan sumber s dan tujuan t pada gambar 2 berikut.

Keterangan
Terdapat dua busur N yang keluar dari titik vs yaitu :busur (vs, v1) dan
busur (vs, v2),
Tidak ada busur N yang menuju ketitik vs, sehingga O(vs) = {(vs, v1), (vs, v2)} dan I(vs) = {}.
Jika titik vs = s, busur (v1, v3) = (1,3). maka O(vs) = O(s)= {(s, 1), (s, 2)} dan I(vs) =I(s)={}.
O(1)=O(v1) = {(v1, v2), (v1, v3)}= {(1, 2), (1, 3)} dan I(1)=I(v1)={(vs,v1)}={(s,1)}
O(2)=O(v2)={(v2,v3),(v3,v4)}={(2,3),(2,4)}danI(2)=I(v2)={(vs,v2),(v1, 2),}={(s,1)}
O(3)= {(3, t)} dan I(3) = {(1,3),(2,3),(4,3)}.
O(4)= {(4, t),(4,3)} dan I(4) = {(2,4)}.
Sebuah flow di network N dari titik sumber s ketitik tujuan t adalah suatu fungsi f yang memetakan setiap busur (i,j) di N dengan sebuah bilangan non negatif yang memenuhi syarat-syarat berikut.

CATATAN:
Syarat (i) menyatakan bahwa nilai flow pada setiap busur N tidak pernah melebihi kapasitas busur tersebut.

Syarat (ii) menyatakan bahwa total nilai flow yang keluar dari titik sumber s sama dengan total nilai flow yang sampai dititik tujuan. Nilai ini yang selanjutnya disebut “nilai flow f” dari s ke t pada network N.

Syarat (iii) menyatakan bahwa untuk setiap titik antara pada N berlaku total flow yang meninggalkan titik x sama dengan total flow yang menuju titik x.

Jika nilai flow f dari titik sumber s ketitik tujuan t pada network N dimisalkan fs,t maka syarat (ii) dan (iii) diatas dapat ditulis sebagai berikut:

Network N pada gambar.2.
Sebuah flow f dari titik sumber s ketitik tujuan t dengan nilai 5 dapat dilihat pada gambar.3

Sebuah flow f1 dengan nilai 6 dapat dilihat pada gambar 4.

Keterangan:
Urutan pertama dari pasangan bilangan yang dikaitkan pada suatu busur N menyatakan kapasitas busur, dan urutan kedua dalam pasangan tersebut menyatakan nilai flow yang mengalir pada busur tersebut.

Nilai flow f1 lebih besar dari nilai flow f pada network N.
Flow f di network N pada gambar10.3. Jika X = {vs,v1} = {s,1} dan X1 = {2,3,4,t}, maka B(X,X1)={(s,2),(1,2)(1,3)} adalah sebuah pemutus-(s,t) pada N dengan kapasitas c(X,X1)=c(s,2)+c(1,2)+c(1,3) = 6+3+5 =14, dengan nilai flow f yaitu 5, tidak melebihi kapasitas pemutus-(s,t) B(X,X1).

Teorema 10.5
Misalkan N sebuah network dengan titik sumber s dan titik tujuan t. Jika f adlah sebuah flow dari s ke t pada N dengan nilai fs,t dan B(X,X1) sebuah pemutus-(s,t) pada N, maka fs,t = f(X,X1) – f(X1,X) ≤ c(X,X1)

Bukti:
Dari definisi flow, untuk titik sumber diperoleh
f({s},V)- f(V,{s} = fs,t

Atau
f({x},V)- f(V,{x}) = 0
untuk semua pemutus-(s,t) B(X,X1) maka

=[f({s},V) –f(V,{s}] + 0
=fs,t ……. (1)

= f(X,X)+f(X,X1) – {f(X,X) + f(X1,X)}
= f(X,X1)- f(X1,X) …… (2)
Karena nilai flow pada setiap busur tidak negatif, maka :
Sehingga

Karena nilai flow setiap busur N tidak melebih kapasitas busur, maka

Dari (1), (2), (3) dan (4) maka

Dalam matematika dan ilmu komputer, teori grafik adalah studi tentang grafik: struktur matematis digunakan untuk model hubungan antara objek-objek berpasangan. Sebuah “grafik” dalam konteks ini mengacu pada koleksi vertices atau ‘simpul’ dan koleksi sisi yang menghubungkan simpul.
Contoh: bagaimana sebuah relasi dalam sebuah grafik dapat terbentuk. Aplikasi yang akan digunakan adalah aplikasi AGNA dengan sample data yaitu hasil penelurusan penyebaran jawaban pada tugas HA.04 di kelas Matematika Diskrit B. Data yang ada adalah sebagai berikut (sesuai gambar):
Selanjutnya, berdasarkan gambar diatas kita masukkan nama-namanya sebagai node, dan diberi nilai atas hubungan antara masing-masing node. Lihat gambar dibawah ini:

Grafik menggambarkan bagaimana sebuah network dalam populasi kelas Matematika Diskrit. Dari grafik dapat disimpulkan beberapa hal yaitu:
1. Terdapat node yang tidak memiliki link/ koneksi dengan link yang lain, hal ini berarti mahasiswa yang bersangkutan bekerja sendiri (Degree in sekaligus Out).
2. Untuk node yang anak panah mengarah kedalam (degree in) berarti dia menerima hasil dari node yang lain. Sebaliknya jika anak panahnya mengarah keluar (degree out), maka dia adalah pihak yang memberi.
3. Terdapat kelompok-kelompok jaringan kecil yang terpisah dari jaringan yang lain. Dapat diartikan adanya proses memberi sekaligus menerima (diskusi).

4. Kemudian terdapat kecenderungan penyebaran secara bertingkat. Maksudnya adalah dari satu node disebarkan ke node-node yang lain. Dari node-node tersebut disebarkan ke node-node yang lain.
.
Kesimpulan:
Network (jaringan) yang terbentuk dalam kelas C, hampir meliputi seluruh kelas. Dalam jaringan tersebut masing-masing node memilih perannya masing-masing, baik itu pribadi (bekerja sendiri), diskusi, atau kerja sama dalam bentuk yang lain.

About vivifebriyantiwordpress

Guru SMA Negeri 1 Kamang Magek
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s