GRAFIK TIDAK BERARAH DAN GRAFIK BERARAH

Pendahuluan

Reinhard Diestel (2000) dalam bukunya yang berjudul Graph Theory : Electronic Edition 2000 yang terdiri dari 12 bab, lebih banyak menyajikan contoh-contoh grafik tidak berarah daripada contoh-contoh grafik berarah.

Pembahasan mengenai grafik tidak berarah mengandung contoh-contoh yang lebih banyak daripada contoh-contoh grafik berarah. Hal ini dapat dibuktikan dari pembahasan mengenai teori grafik yang dilakukan oleh J. A. Bondy dan U. S. R Murty (2008) dalam buku mereka yang berjudul GraphTheory. Buku ini terdiri dari 21  bab dan contoh-contoh mengenai grafik tidak berarah mencakup contoh dalam 19 bab dan contoh-contoh grafik berarah hanya dalam 2 bab. Matriks juga sangat sedikit dipakai.

Pemakaian contoh-contoh grafik tidak berarah lebih banyak daripada pemakaian contoh-contoh grafik berarah dan penyajikan matiks adalah sangat sedikit diikuti pula dalam bebrapa buku tentang bahan ajar teori grafik yang telah diterbitkan di Indonesia.

Wikipedia mengandung pembahasan mengeai teori grafik. Pembahasan ini mencerminkan bahwa :

          ““Wikipedia, dalam pembahasan ini, menyajikan grafik tidak berarah dan Teori graf atau teori grafik dalam matematika dan ilmu komputer adalah cabang kajian yang mempelajari sifat-sifat “graf” atau “grafik”. Ini tidak sama dengan “Grafika“. Graf merupakan sekumpulan objek terstruktur di mana beberapa pasangan objek mempunyai hubungan ataupun keterkaitan tertentu.[1] Secara informal, suatu graf adalah himpunan benda-benda yang disebut “simpul” (vertex atau node) yang terhubung oleh “sisi” (edge) atau “busur” (arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan “simpul”) yang dihubungkan oleh garis-garis (melambangkan “sisi”) atau garis berpanah (melambangkan “busur”). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan “gelang” (loop).”[1]\

Grafik tidak berarah telah disajikan sebagai berikut :

Wikipedia, juga menyajikan grafik berarah. Grafik berarah telah disajikan sebagai berikut :

Teori grafik memakai titik-titik dan garis-garis. Titik-titik mewakili objek-objek dan garis-garis mewakili hubungan-hubungan (edges, links) antara objek-objek tersebut. Psrbedaan antara  grafik tidak berarah dan grafik berarah, ditinjau  dari sudut diagram, terletak pada garis. Grafik tidak berarah memakai garis tanpa anak panah dan grafik berarah memakai garis dengan anak panah. Perbedaan ini mengandung banyak perbedaan lain.

Matematika merupakan dasar dari teori grafik. Matriks, secara khusus, merupakan dasar dari teori grafik. Pemakoiaian matriks  tentang teori grafik dan bahan ajar teori grafik.

Perangkat Lunak Komputer

Banyak perangkat lunak komputer telah dikembangkan untuk analisis jaringan sosial dan untuk teori grafik akan tetapi perangkat lunak komputer Ucinet 6 for Windows dan Netdraw dapat dipakai untuk analisis jaringan sosial dan untuk mencipta dan menyajikan matriks dan grafik dalam teori grafik. Para penulis buku teori grafik dan bahan ajar teori grafik belum memakai perangkat lunak komputer untuk teori grafik.

Matriks, Penciptaan dan Penyajian Grafik

Ucinet 6 for Windows dan Netdraw  dipakai untuk analisis jaringan sosial dan untuk mencipta matriks. Matriks yang dicipta dengan Ucinet ini dapat dipakai untuk mencipta grafik dengan cara memakai Netraw. Matriks dan grafik yang dicipta ini sesuai dengan teori grafik berarah, karena grafik tidak berarah tidak mengandung dasar matematika dan matriks.

Studi dan penghayaran teori grafik berarah dapat dilakukan melalui pemakaian Ucinet 6 for Windows dan Netdraw sehingga setiap penyajian akan mencakup matriks dan grafik.

Beberapa Contoh

Matriks contoh kesatu dari Wikipedia adalah sebagai berikut :

Tabel GD1a

Grafik dapat dicipta sebagai berikut :

Gambar GD1a

Matriks contoh kedua dari Wikipedia adalah sebagai berikut :

Tabel GD1b

Grafik dapat dicipta sebagai berikut:

Gambar GD1b

Grafik dasar ketiga dapat dicipta. Beberaa grafik  lain dapat dicipta dari grafik tidak berarah yang disajikan dalam Wikipedia akan tetapi di sini disajikan hanya satu grafik saja.

Matriks contoh ketiga dari Wikipedia adalah sebagai berikut :

Tabel GD1c

Grafik dapat diccipta sebagai berikut :

Gambar GD1c

Matriks contoh keempat dari Wikipedia  merupakan  salah satu contoh dari matriks contoh tidak dasar. Hal ini berarti bahwa suatu grafik tidak berarah mengandung beberapa peluang berbeda sesuai dengan persepsi yang dipakai.

Tabel GD1d

Grafik dapat dicipta sebagai berikut :

Grafik ini berbeda dengan grafik yang akan dicipta karena grafik ini mmerupakan grafik tidak berarah sedangkan grafik yang akan dicipta merupakan grafik berarah. Grafik tidak berarah tidak mungkin dicipta memakai matriks sehingga grafik tidak berarah merupakan hasil penciptaan tidak berdasar atas matematika dan tidak berdasar atas matriks. Para penyusun buku teori grafik dan bahan ajar teori grafik tidak akan mampu menyusun matriks untuk mencipta grafik tidak berarah. Matriks yang dicipta di sini adalah matriks untuk grafik berarah dan hubungan antara simpul-simpul merupakan hubungan dua arah. Contoh ini biasa dipakai untuk mendeskripsikan tiga rumah yang memperoleh pelayanan listrik, gas, dan air.

Grafik di atas disajikan tanpa matriks. Matriks dari grafik di atas dapat dicipta sebagai berikut :

Tabel GD2

Grarik dicipta sebagai berikut :

Gambar GD2

Reinhard Diestel (2000) dalam bukunya yang berjudul Graph Theory : Electronic Edition 2000 antara lain menyajikan contoh sebagai berikut :

Grafik di atas terdiri dari 8 smpul tanpa label. Grafik di atas karena tidak berarah maka matriks dapat dicipta menurut persepsi penulis sendiri. Salah satu persepsi disajikan di bawah ini akan tetapi beberapa persepsi lain masih dapat dilakukan. Matriks dicipta sebagai berikut :

 ABCDEdiGH
A01110000
B10100101
C11011001
D10101000
E00110100
F01001010
G00000101
H01100010

-Tabel GD3

Grafik dapat dicipta sebagai berikut :

Gambar GD3

Jumlah dari hubungan dari suatu lintasan (path) adalah panjang dari lintasan tersebut. Grafik ini mengandung beberapa siklus.

Matriks di bawah ini mencerminkan konsep pohon. Konsep pohon dan hutan biasa dibahas dalam buku-buku tentang teori grafik yang mencerminkan grafik tanpa siklus dan tanpa gelung atau gelang. Pembahasan mengenai gelung atau gelang (loop)  dalam teori grafik merupakan konsep yang tidak jelas karena mencerminkan hubungan suatu simpul dengan simpul itu sendiri. Matriks tidak mungkin dicipta untuk mencerminkan loop. Hal ini berarti bahwa pemakaian konsep loop dalam teori grafik tidak berdasar atas matematika dan matriks.

Tabel GD4

Grafik dapat dicipta. Berbagai bentuk grafik pohon telah disajikan dalam buku-buku teori grafik termasuk pula konsBentukep hutan. Bentuk pohon terdapat juga yang mencerminkan konsep hirarki. Bentuk struktur organisasi juga terdapat. Bentuk grafik pohon, berdasar atas  matriks di atas dapat disajikan sebagai berikut :

Gambar GD4a

R.B. Bapat dalam bukunya yang berjudul Graphs and Matrices. Judul dnbuku in8i lebih tepat dinamakan Matrices and Graphs.

Contoh-contoh  antara lain disajikan sebagai berikut :

Contoh di atas merupakan contoh dari grafik tidak berarah berdasar atas matriks yang disajikan di bawah grafik tersebut. Pemakaian matriks tersebut adalah sebagai berikut :

Tabel GD5

Penciptaan grafik adalah sebagai berikut :

Gambar GD5

R.B. Bapat telah melakukan kesalahan dalam penyajian grafik tidak berarah dari matriks bersangkutan karena pemakaian matriks tersebut akan mencipta grafik berarah, bukan mencipta grafik tidak berarah.

Contoh matriks dan grafik lain adalah sebagai berikut :

Matriks di atas, jika dilaksanakan, maka hasil pelaksanaan bukan grafik tidak berarah seperti disajikan di atas akan tetapi grafik berarah yang mencerminkan siklus sebagimana disajikan di bawah ini.

 v1v2v3v4v5v6v7v8
v101000001
v210100000
v301010000
v400101000
v500010100
v600001010
v700000101
v810000010

Tabel GD6

Gambar GD6

Matriks dapat dicipta sebagai berikut :

 1234567
10110000
21000000
31001000
40010000
50000010
60000100
70000000
80010101

Tabel GD7

Grafik dapat dicipta sebagai berikut:

Gambar GD7

Penyajian di atas mengungkap kesalahan yang terkandung dalam pembahasan dari R.B. Bapat dalam bukunya.

Jorgen Bang, Jensen, Gregory Gutin (2007) dalam buku mereka yang berjudul Digraphs Theory, Algorithms and Applications,  menyajikan grafik berarah sebagai berikut :

Gambar GD7

Penyajian di atas mengungkap kesalahan yang terkandung dalam pembahasan dari R.B. Bapat dalam bukunya.

Jorgen Bang, Jensen, Gregory Gutin (2007) dalam buku mereka yang berjudul Digraphs Theory, Algorithms and Applications,  menyajikan grafik berarah sebagai berikut :

Gambar GD7

Penyajian di atas mengungkap kesalahan yang terkandung dalam pembahasan dari R.B. Bapat dalam bukunya.

Jorgen Bang, Jensen, Gregory Gutin (2007) dalam buku mereka yang berjudul Digraphs Theory, Algorithms and Applications,  menyajikan grafik berarah sebagai berikut :

Gambar GD7

Penyajian di atas mengungkap kesalahan yang terkandung dalam pembahasan dari R.B. Bapat dalam bukunya.

Jorgen Bang, Jensen, Gregory Gutin (2007) dalam buku mereka yang berjudul Digraphs Theory, Algorithms and Applications,  menyajikan grafik berarah sebagai berikut :

Gambar GD7

Penyajian di atas mengungkap kesalahan yang terkandung dalam pembahasan dari R.B. Bapat dalam bukunya.

Jorgen Bang, Jensen, Gregory Gutin (2007) dalam buku mereka yang berjudul Digraphs Theory, Algorithms and Applications,  menyajikan grafik berarah sebagai berikut :

Gambar GD7

Penyajian di atas mengungkap kesalahan yang terkandung dalam pembahasan dari R.B. Bapat dalam bukunya.

Jorgen Bang, Jensen, Gregory Gutin (2007) dalam buku mereka yang berjudul Digraphs Theory, Algorithms and Applications,  menyajikan grafik berarah sebagai berikut :

Buku Digraphs Theory, Algorithms and Applications lebih banyak menyajikan grafik berarah daripada grafik  tidak berarah akan tetapi sangat sedikit memakai matriks untuk mencipta grafik berarah tersebut. Contoh-contoh yang terkandung dalam buku ini adalah lebih banyak contoh grafik berarah daripada contoh grafik tidak berarah. Hal ini berarti bahwa buku ini dapat dipakai sebagai acuan utama dalam studi dan penghayatan teori grafik. Para penulis buku ini jarang menyajikan matriks dari grafik berarah yang dibahas. Contoh grafik akan lebih bermanfaat jika setiap grafik yang disajikan itu diawali dengan matriks bersangkutan sehingga lebih memperjelas interpretasi.

Matriks dari grafik berarah ini adalah sebagai berikut :

 x1x2x3x4x5x6x7
x10100000
x20010010
x30001000
x40000110
x510000a00
x60010001
x70001000

Tabel GD8

Grafik dapat dicipta sebagai berikut :

Gambar GD8

 Contoh kedua dari matriks adalah sebagai berikut :

Matriks dapat dicipta sebagai berikut :

Tabel GD8

Gambar GD8

Narsingh Deo (2016) telah menulis buku berjudul Graph Theory with Appications to Engineering & Computer Science. Beberapa contoh dalam buku ini akan dipakai di sini. Contoh-contoh yang dipakai di sini adalah contoh-contoh mengenai grafik tidak berarah  sehingga kritik dapat dilancarkan. Beberapa kritik dapat dilancarkan atas grafik tidak berarah tersebut. Contoh diambil dari buku tersebut dan Ucinet 6 for Windows serta Netdraw dipakai.

Grafik di atas merupakan grafik dari Spanning Tree. Grafik spanning tree merupakan konsep dalam teori grafik yang sering dibahas dalam buku-buku tentang teori grafik. Grafik di atas merupakan grafik tidak berarah. Matriks dapat disusun sebagai berikut:

Tabel GD9

Grafik dapat dicipta sebagai berikut :

Gambar GD9

Narsingh Deo juga banyak menyajikan grafik tidak berarah daripada menyajikan grafik berarah sehingga buku ini juga mengandung kelemahan dan ketidakjelasan. Contoh lain dari grafik tidak berarah adalah sebagai berikut:

Matriks dapat dicipta sebagai berikut :

abcdefghi
a011100000
b001100000
c000100000
d000010111
e000001001
f000000111
g000000000
h000000001
i000000100

Tabel GD10

Grafik berarah dapat dicipta sebagai berikut :=

Gambar GD10

Contoh lain dari grafik tidak brerarah adalah sebagai berikut :

Contoh grafik tidak berarah ini lebih rumit daripada contoh-contoh lain sehingga penyajian matriks untuk mencipta grafik berarah ini dilakukan secara hati-hati.

Matriks dapat dicipta sebagai berikut :

ABCDEFGHIJKL
A011000011100
B001000000100
C000110000111
D000010000111
E000001100000
F000000100000
G000000110000
H000000001000
I100000000000
J000000011010
K000000110001
L000011110000

Tabel GD11

Grafik berarah dapat dicipta sebagai berikut 

Gambar GD11

Narsingh Deo banyak menyajikan grafik tidak berarah. Beberapa contoh telah disajikan dan dipakai untuk mencipta matriks dan grafik berarah sesuai dengan persepsi yang dipakai oleh penulis.

Hasmawati (2015) telah menulis Bahan Ajar Teori Grafik untuk Prodi Matematika Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Hasanuddin.

Hasmawati sangat banyak memberikan contoh grafik tidak berarah dan salah satu contoh adalah sebagai berikut :

Salah satu matriks dari contoh ini dapat dipersepsikan dan dicipta sebagai berikut :

 ABCDEFG
A0110001
B1010001
C1100001
D0000111
E0001011
F1001101
G1111110

Tabel GD12

Salah satu alternatif dari beberapa matriks dapat dipakai untuk mencipta grafik di bawah ini:

Gambar GD12

Hasmawati juga memberikan contoh lain tanpa label dan grafik ini juga merupakan grafik tidak berarah sehingga dapat dipersepsikan dalam berbagai bentuk grafik berarah sebagaimana telah disajikan dalam contoh grafik tidak berarah yang terdapat dalam Wikipedia. Grafik yang disajikan oleh Hasmawati adalah sebagai berikut :

Matriks untuk mencipta grafik berarah antara lain adalah matrik yang terdiri dari 17 simpul dan enam belas hubungan.

Tabel GD13

Grafik dapat dicipta sebagai berikut :

Ganbar GD13

Hasmawati juga menyajkan matriks dengan nama-nama baris berbeda dengan nama-nama kolom. Matriks seperti ini biasa dinamakkan matriks 2-mode yang berbeda dengan matrks 1-mode.

Matriks ini akan dipakai di sini.

Tabel GD14

Grafik yang dicipta adalah sebagai berikut :

Gambar GD14

Nama-nama baris muncul sedangkan nama-nama kolom tidak muncul.

Nama-nama baris dan nama-nama kolom jika sama maka akan menyajikan matriks sebagai berkut:

Tabel GD15

Grafik yang dicipta adalah sebagai berikut :

Gambar GD15

Pembahasan Hasmawati dalam bukunya banyak mengandung kelemahan dan ketidakjelasan karena banyak memakai grafik tidak berarah.

Sri Rahayuningsih (2018) telah menulis buku berjudul Teori Graf dan Penerapannya. Grafik tidak berarah banyak dipakai dan disajikan dalam buku ini. Penyajian beberapa matriks terdapat juga dan disajikan setelah penyajian grafik bersangkutan.

Tabel GD16

Grafik berarah dapat dicipta sebagai berikut :

Gambar GD17

Tabel GD17

Grafik berarah  dapat dicipta sebagai berikut :

Gambar GD17

Matriks di atas dipakai untuk membuktikan kesalahan penyajian grafik tidak berarah dari matriks di atas.

Tabel GD18

Matriks dapat dicipta sebagai berikut

Gambar GD18

Rinaldi Munir dalam Matematika Diskrit antara lain menyajikan grafik dan matriks sebagai berikut:

Grafik ini dikutik dari Narsing Deo dalam bukunya yang berjudul Graph Theory with Applications to Engineering & Computer Science

Tabel GD19

Gambar GD19

Matriks tersebut bukan untuk mencipta grafik tidak berarah akan tetapi untuk mencipta grafik berarah sebagaimana disajikan di atas ini.

Tabel GD20

Grafik berarah dapat dicipta sebagai berikut :

Gambar GD20

Kesalahan Rinaldi Munir terkandung dalam penyajian dua grafik tidak berarah. Dua matriks yang dipakai oleh Rinaldi Munir adalah matriks untuk mencipta grafik berarah bukan untuk mencipta grafik tidak berarah. Matriks yang dipakai adalah matriks untuk mencipta grafik berarah. Perkuliahan matematika diskrit akan lebih bermakna jika mampu membuktikan matriks untuk mencipta grafik tidak berarah.

Rinaldi Munir telah secara tepat menyajikan dua matriks yang sama untuk menentukan isomorfik atau non-isomorfik dengan label berbeda.

Penentuan isomorfik atau non-isomorfik akan sulit dilakukan hanya berdasar atas dua grafik karena grafik yang sama dapat dicipta beberapa penyajian berbeda jika Netdraw dipakai. Gambar GD11 sebagai contoh dapat dipakai untuk mencipta grafik sebagai berikut :

Kesatu :

Kedua

Ketiga

Keempat

Keempat grafik di atas merupakan isomorfik karena matriks dari keempat grafik tersebut adalah sama.

Rangkuman

Penulis, dalam menyusun tulisan ini, telah memakai buku-buku tentang teori grafik dan bahan ajar teori grafik dari Wikipedia, J. A. Bondy dan U.S.R. Murty, Reinhard Diestel, Jorgen Bang, Jensen dan Gregory Gutin, Narsin Deo, Hasmawati, Sri Rahayuningsih, dan Renaldi Munir.

Pemakaian buku-buku dan bahan ajar teori grafik ini dimaksud untuk mengukap dan membuktikan kesalahan-kesalahan yang terlandung dalam buku-buku dan bahan ajar teori grafik tersebUut dengan memanfaatkan Ucinet 6 for Windows untuk mencipta amatriks dan Netdraw untuk mencipta grafik sesuai dengan teori grafik berdasar atas matriks tersebut.

Hasil-hasil pembuktian ini mengungkap bahwa grafik tidak berarah disusun tidak berdasar atas matematika, tidak disusun berdasar atas matriks.

Matriks yang dipakai dalam buku-buku dan bahan ajar teori grafik mengandung kesalahan karena matriks tersebut disusun  untuk mencipta grafik berarah, bukan untuk mencipta grafik tidak berarah karena grafik tidak berarah tidak mungkin dicipta dengan memanfaatkan grafik.

Penyebaran kesalahan-kesalahan dalam pembahasan teori grafik harus dihentikan dan diganti dengan penyebaran kebenaran melalui pembahasan teori grafik secara benar. Para penyusun buku dan bahan ajar teori grafik tidak akan mampu membuktikan matriks dari grafik tidak berarah.

Penulis mengharap tanggapan atas kritik  ini terutama dari para penulis buku dan bahan ajar teori grafik. Matriks yang dipakai telah dibuktikan bukan untuk grafik tidak berarah akan tetapi untuk grafik berarah.

Permata  Regency, 5 Maret 2022                                                    

Daftar Pustakat.

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

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

Bang, Jorsen dan Gregory Gutin Jensen.2007. Digraphs Theory, Algorithms, and Applications. Berlin : Spinger-Verlag.

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., dan  Lesnia  nston, Inc.wank, L. 1979. Graph and Digraph.  Wadsworth & Brooks/Cole. And

Chartrand, G. dan Ping. Zhang.2012 A First Cource In Graph Theory. New York : Dover Publications, Inc.

Dooren, Paul Van. 2009. Graph Theory and Appliction. Dublin : UCL.

Hismawati. 2015. Bahan Ajar Teori Grafik. Prodi Matematika Juurusan Matematika Fakultas Matematika Dan Ilmu Pengetahuan Alam Universitas Hasanuddin

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

Lipschtz, Seymour dan Marc Lipson. 2007. Discrete Mathematics. Third Edition. New York : McGraw-Hill

Littlejohn, Stephen W. dan  A. Karen 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.

Rinaldi Munir. Graf : Bahan Kuliah IF2120 Matematika Diskrit.

Rosen, Kenneth H. 2007. Discrete Mathematics and Its Applications. Seventh Ediion. New York : McGraw-Hill

Sri Rahayuningsih.2018. Teori Graf dan Penerapannya. Malang : Univrrsitas Wisnuwardhana Press.

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

Wilson, Robin J. 1998. Introducton to Graoh Theory. Fourth Edition. Essex, England : Addition Wesley Longman Limited.

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

%d bloggers like this: