TEORI MATRIKS DAN TEORI GRAFIK

Oleh :

Prof. Dr. Abdullah  M. Jaubah, S.E., M.M.

Pendahuluan

Teori grafik merupakan  bagian dari matematika atau bagian dari teori matriks. karena matriks dapat dipakai untuk mencipta grafik. Teori matriks dan teori grafik dikembangkan sebelum komputer ditemukan, dicipta, dan dikembangkan. Tingkat perkembangan komputer telah memungkinkan pengembangan perangkat lunak komputer untuk mencipta matriks dan matriks yang telah dicipta itu kemudian dipakai untuk mencipta grafik sesuai dengan teori grafik.

Teori grafik tradisional dapat dikelompokkan  ke dalam teori grafik berarah dan teori grafik tidak berarah. Teori grafik berarah dicipta berdasar atas teori matriks sedangkan teori grafik tidak berarah dicipta tidak memakai teori matriks atau tidak berdasar atas matematika.

Teori grafik modern berdasar atas teori matriks dan perangkat lunak komputer. Salah satu perangkat lunak komputer yang dapat dipakai untuk mencipta matriks adalah Ucinet 6 for Windows dan matriks yang dicipta ini kemudian dipakai dalam Netdraw untuk mencipta grafik sesuai dengan teori grafik berarah.  Pendekatan ini sangat berbeda dengan pendekatan yang dipakai dalam teori grafik tradisional karena contoh-contoh yang terkandung dalam buku-buku teori grafik tradisional lebih banyak menyajikan contoh grafik tidak berarah contoh grafik tidak berdasar atas matematika atau tidak berdasar atas teori matriks.

Grafik  tidak berarah berbeda dengan grafik berarah. Grafik biasa mengandung himpunan simpul (vertex atau node) dan himpunan hubungan (edge, link). Hubungan antara dua simpul, dalam grafik tidak  berarah, diwakili oleh titik atau lingkaran kecil dan garis tanpa anak panah. Grafik berarah diwakili oleh titik dan garis  dengan anak panah. Perbedaan antara garis tanpa anak panah dan garis dengan anak panah memainkan peranan penting karena garis tanpa anak panah mengandung interpretasi yang sangat tidak jelas dan sangat sulit diinterpretasikan karena tiap garis tanpa anak panah dapat ditafsirkan dalam tiga kemungkinan berbeda.

Perangkat lunak komputer

Salah seorang peserta workshop tentang Pajek menjelaskan bahwa Pajek telah diberikan oleh para pengajar dari Manchaster University. Para pelatih Pajek itu adalah para ahli Indonesia yang memberikan kuliah dan melakukan penelitian pada Manchaster University. Peserta juga menjelaskan bahwa Pajek dapat diunduh melalui Internet. Usaha mengunduh Pajek berhasil dilakukan akan tetapi tatkala dilaksanaan maka grafik tidak dapat disajikan. Usaha mengunduh Ucinet 6 for Windows dan NetDraw berhasil dilakukan. Contoh-contoh arsip data dapat dilaksanakan dan grafik dapat disjikan. Langkah ini dilakukan dalam tahun 2012. Usaha mengunduh Pajek dilakukan lagi setelah tiga bulan dan berhasil menyajikan grafik dari pelaksanaan Pajek tersebut. Paket program lain diunduh juga seperti paket program SocNetV, Gephi, Mage dan dapat dilaksanakan. Ucinet 6 for Windows dan Netadraw adalah paket progrm  paling unggul di antara paket program lain.

Buku-buku tentang analisis jaringan sosial diunduh dan dipakai sebagai bahan studi dan penghayatan analisis jaringmean sosial.

Borgatti, S.P., Everett, M.G, dan Freeman, L.C. (2002) telah mencipta dan mengembanngkan Ucnet 6 for Windows : Software for Social Network Analysis

Borgatti, S.P (2002) telah mencipta dan mengembangkan Netdraw : Software for Network Visualization.

Usaha mengumulkan bahan bacaan terus dilakukan dan pada tahun 2014 berhasil mengunduh disertasi yang ditulis oleh Stephen Peter Borgatti (1989) dengan judul Regular Equivalence in Graphs, Hypergraphs, and Matrices, pada California University, Irvine dengan : Committee in charge :

Professor Linton C. Freeman, Chair, Professor John F. Boyd, Professor A. Kimbal Romney, dan Professor Douglas R. White

Studi dan penghayatan atas isi disertasi ini dilakukan dan hasil dari studi dan penghayatan ini telah merangsang untuk mengumpulkan buku-buku tentang teori matriks dan teori grafik. Banyak buku tentang teori matrik dan teori grafik telah dapat dikumpulkan dan dipakai sebagai bahan studi dan penghayatan atas teori matriks dan teori grafik akan tetapi mengalami kekecewaan dan ketidakpuaasan karena banyak contoh memakai grafik tidak berarah dibanding dengan contoh penyajian grafik berarah dan matriks juga jarang sekali disajikan. Contoh-contoh grafik itu kemudian dipakai dengan memanfaatkan Ucinet 6 for Windows dan Netdraw. Hasil yang diperoleh ternyata lebih canggih daripada hasil yang disajikan dalam buku-buku teori grafik tersbut karena dapat memakai 21 jenis warna, bukan hanya empat warna di samping beberapa ketangguhan lain.

Buku-buku tentang teori grafik memakai matriks akan tetapi grafik yang disajikan mengandung kesalahan karena matriks yang dipakai adalah matriks untuk mencipta grafik berarah akan tetapi penyajiannya adalah grafik tidak berarah sehingga secara konseptual grafik yang disajikan mengandung kesalahan.

Contoh Kesalahan Penyajian Grafik

Prio Handoko (2020) dalam tulisannya yang berjdul An Introduction To Graph, menyajikan grafik dan matriks sebagai berikut :

Kesalahan yang dialami di sini adalah matriks yang dipakai merupakan matriks untuk mencipta grafik berarah akan tetapi grafik yang disajikan di sini adalah grafik tidak berarah. Kesalahan serupa ini terdapat dalam banyak buku tentang teori grafik. Kesalahan ini dialami karena perangkat luna komputer tidak dimanfaatkan.

Matriks di atas adalah sebagai beerikut :

 A0B1C2D3E4
A001010
B110101
C201011
D310101
E401110

Grafik, berdasar atas matriks di atas, dapat dicipta. Hasil penciptaan grafik ini disajikan secara otomatis sebagai berikut :

Kesalahan yang dialami di sini adalah matriks yang dipakai merupakan matriks untuk mencipta grafik berarah akan tetapi grafik yang disajikan di sini adalah grafik tidak berarah. Kesalahan serupa ini terdapat dalam banyak buku tentang teori grafik. Kesalahan ini dialami karena perangkat luna komputer tidak dimanfaatkan.

Matriks di atas adalah sebagai beerikut :

 A0B1C2D3E4
A001010
B110101
C201011
D310101
E401110

Grafik, berdasar atas matriks di atas, dapat dicipta. Hasil penciptaan grafik ini disajikan secara otomatis sebagai berikut :

Grafik yang dicipta bukan grafik tidak berarah akan tetapi grafik berarah sehingga penyajian grafik oleh Prio Handoko itu mengandung kesalahan dan kesalahan ini disebar jika Prio Handoko menyajikan kepada para mahasiswa. Penyajian lain adalah sebagai berikut :

Matriks yang dipakai adalah sama akan tetapi grafik yang dicipta adalah berbeda. Grafik yang dicipta ini adalah sebagai berikut :

 A0B1C2D3E4
A001010
B110101
C201001
D300101
E400000

Grafik, berdasar atas matriks di atas dapat dicipta dan hasil penciptaan ini sangat berbeda dengan penyajian grafik yang dilakukan oleh Prio Handoko di atas.

Simpul E4 tidak mempuyai hubungan dengan simpul A0 sebagaimana tercermin dalam matriks bahwa simpul E4 tidak mempunyai hubungan dengan simpul A0 sedangkan grafik dari Prio Handoko mengandung hubungan dua arah antara simpul A0 dan simpul E4. Grafik tersebut juga mengandung kesalahan.

Kesalahan-kesalahan seperti yang dialami di atas juga terdapat dalam buku-buku teori grafik tradisional.

R. B. Bapat dalam bukunya yang berjudul Graphs and Matrices telah menyajikann grafik tidak brarah dan matriks sebagai berikut :

Matriks di atas adalah sebagai berikut :

 e1e2e3e4e5
e101110
e210100
e311011
e410101
e500110

Grafik, berdasar atas matriks di atas, adalah sebagai berikut :

Grafik ini adalah grafik berarah bukan seperti yang disajikan oleh Bapat yaitu grafik tidak berarah sehingga penyajian Bapat mengandung kesalahan.

Chandra Chekuri (2020) dalam memberikan kuliah mengenai Topics in Graph Algorith:ms antara lain menyajikan grafik dan matriks sebagai berikut :

Matriks dapat dicipta sebagai berikut :

 abcde
a01000
b00111
c10001
d00100
e00010

Grafik, berdasar atas matriks di atas, dapat dicipta sebagai berikut :

Chandra Chekuri  tel tah menyajikan matriks dan grafik secara tepat atau tidak mengandung kesalahan.

Dasar dari Teori Grafik

Dasar dari teori grafik terdiri dari empat dasar yaitu dasar dari teori grafik berarah edangkan gafik tidak berarah tidak mengandung dasar matematika dan tidak mengandung dasar teori matriks.

Contoh kesatu simpul A dan simpul B tidak mempunyai hubungan.  Matriks dapat disusun sebagai berikut :

 AB
A00
B00

Grafik dari matriks di atas dapat disajikan sebagai berikut :

Contoh kedua simpul A menghubungi simpul B akan tetapi simpul B tidak menghubungi simpul A.  Matriks dapat disusun sebagai berikut :

 AB
A01
B00

Grafik dari matriks di atas dapat disajikan sebagai berikut :

Contoh ketiga simpul B menghubungi simpul A akan tetapi simpul A tidak menghubungi simpul B.  Matriks dapat disusun sebagai berikut :

 AB
A00
B10

Grafik dari matriks di atas dapat disajikan sebagai berikut :

Contoh keempat simpul A menghubungi simpul A dan simpul B  juga menghubungi simpul A.

Matriks dapat disusun sebagai berikut :

 AB
A01
B10

Grafik dari matriks di atas dapat disajikan sebagai berikut :

Keempat contoh di atas merupakan dasar dari teori grafik berdasar atas teori matriks. Teori lain tidak terdapat termasuk teori yang menggambarkan grafik seperti di bawah ini :

Grafik di atas ini tidak berdasar atas teori matiks dan  juga tidak berdasar atas teori grafik. Contoh grafik seperti di atas banyak terdapat dalam buku-buku teori grafik. Para penulis buku teori grafik tidak akan mampu menjelaskan garis-garis antara pasangan simpul di atas, karena tiap garis mengandung tiga kemungkinan. Ketidakmampuan ini akibat dari matriks yang dipakai untuk mencipta grafik berarah itu tidak disajikan dan gradanfik berarah yang dicipta diubah menjadi grafik tidak berarah.

Usaha untuk mengungkap kerapuhan grafik tidak berarah, di bawah ini akan disajikan grafik tidak berarah dan matriks juga tidak disajikan. Simpul terdiri dari 40 simpul dan hubungan-hubungan. Jumlah simpul sengaja diperbanyak karena contoh-contoh grafik tidak berarah biasanya kurang daripada 40 simpul. Para penulis buku teori grafik tradisional tidak akan mampu menjawab pertanyaan tentang berapakah jummlah cliques dalam grafik di bawah ini dan berapakah jumlah simpul dari tiap clique tersebut?

Gagasan di atas berarti bahwa grafik tidak berarah yang biasa memakai garis tanpa anak panah merupakan teori grafik yang tidak layak dipakai karena mengandung kelemahan dan ketidakjelasan.

Matriks yang disajikan selalu dipakai untuk mencipta grafik berarah bukan untuk mencipta grafik tidak berarah. Pemakaian matriks untuk mencipta grafik berarah jika dipakai  akan tetapi grafik tidak berarah yang dicipta secara manual maka kesalahan dalam penyajian grafik itu dapat dibuktikan sejalan dengan perkembangan teknologi komputer dan perkembangan perangkat lunak kompuer untuk maksud tersebut.

Pembahasan mengenai grafik tidak berarah juga tercermin dalam Buku Ajar Teori Grafik yang disusun oleh Hasmawati, dam beberapa pengajar lain.

Rangkuman

Matematika dan teori Matriks memainkan peranan penting dalam pengembangan teori grafik berarah. Teori grafik tidak berarah merupakan teori grafik tidak berdasar atas matematika dan tidak berdasar atas  teori matriks. Matriks yang disajikan dalam teori grafik akan selalu menci0=pta grafik berarah dan  selalu tidak mencipta grafik tidak berarah. Kesalahan-kesalahan dalam teori grafik tradisional terutama dalam pembahasan mengenai grafik tidak berarah.

Daftar Pustaka

Abuja, Ravindra K., Maganti, Thomas L, dan Olin, James B. 1993.  Network Flows, Prentice Hall.

Bakakrisnan, R dan K. Ranganathan.2012. A Textbook of Graph Theory. Springer

Balakrishnan, V. K. 1995. Theory and Problems of Combinatorics. MacGraw Hill.

Behzad, M. dan Chartrand, G. 1971, Introduction  to the Theory of Graphs. Allyn and Bacon.

Berge, C. 1958. Theory of Graphs and Its Applications. John Wiley & Sons

Berge, C. 1973. Graphs and Hypergraphs.  North Holland

Bondy, J. A. dan Murty, U.S.R.1976. Graph Theory with Applications North Holland., Stephen P

Borgatti, Stephen Peter. 1989. Regular Equivalence in Graphs, Hypergraphs, and Matrices. University of California, Irevine.

Chartrand, G. 1977. Introduction to Graph Theoy. Dover Publications, Inc.

Chartrand, G., dan  Lesnia  nston, Inc.wank, L. 1979. Graph and Digraph.  Wadsworth & Brooks/Cole. And

Kerlinger, Fred. N.1986. Foundation of Behavioral Reseaech.Holth Rinehart and Winston.

Littlejohn, Stephen W. dan Karen A/ Foss. 2011. Theories of Human Communication.waveland Press, Inc.

Monge, Peter R., dan Noshir Contractor.2003. Theories og Communication Networks. Oxford University Press.

Narsing Deo. 1974. Graph Theory with Applications to Engineering & Computer Science. Dover Publication, Inc.

Wasserman, Stanley; Katherine Faust. 1998. Social network analysis : methods and applications. Cambridge University Press.

Perangkat Lunak Komputer

Borgatti, S.P., Everett, M.G., Freeman, L.C. 2002. Ucinet 6 for Windows : Software for Social Network Analysis. Analytic Tchnology.

Borgatti, S.P. 2002. NetDraw : Networki Visualization.Analytic Tchnology

Dumitru C iubatii. 2005. Graph Magic 2.1.

Author: abdullahmjaubah

Saya pernah menulis buku tentang Sistem Administrasi Keuangan Negara yang diterbitkan oleh Bratara Karya Aksara dan buku C Basic Pedoman Penyusunan Program Komputer yang diterbitkan oleh Gramedia. Pelatihan yang pernah diikuti adalah Program Perencanaan Nasional di Jakarta, Export Training Program. Pelatihan Supply and Material Management dan Training The Trainer yang diselenggarakan oleh Royal Institure of Public Administration di Inggris, Manajemen Proyek di Virginia Polytechnique and State University di Amerika Serikat, latihan di Economic Development Institute-World Bank, dan Advanced Training the Trainer di Kanada.

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 )

Connecting to %s

%d bloggers like this: