## DETERMINAN GRAF KNESER
Hanna Dewi Marina Hutabarat Universitas Negeri Medan
Surel : hanahutabarat@unimed.ac.id
Abstract :  Determinat of Kneser  Graph. Kneser Graph  is  kind of  simple graph with no loop and no parallel edge. Kneser Graphs ) , ( k n K could be present  with matrix. In this article, we will discuss about Kneser Graph, how to present  it with adjacency matrix, the determinant of the matrix. We will show that the determinant of the adjacency matrix is always zero. Using cornice determinant, the determinant of Kneser Graphs matrix could counting more easily for nxn matrix with n>4.
Keywords : Kneser Graphs, Adjacency Matrix, Determinant.
Abstrak  :  Determinan  Graf  Kneser .  Graf  Kneser  merupakan  graf  sederhana karena  tidak  memiliki  lup  dan  tidak  memiliki  sisi  parallel.  Graf  Kneser
) , ( k n K
dapat  disajikan  dalam  bentuk  matriks.  Dalam  artikel  ini,  akan  dibahas tentang graf Kneser, penyajiannya dalam matriks ketetanggaan dan determinan dari matriks  tersebut.  Akan  ditunjukkan  bahwa  determinan  dari  matriks  ketetanggaan sebuah  graf  Kneser  selalu  nol.  Pencarian  determinan  graf  kneser  menggunakan metode  cornice  determinan,  dimana  metode  ini  diperuntukkan  untuk 5  n yang merupakan  metode  tercepat  dalam  pencarian  determinan  matriks.  Hal  ini dikarenakan graf kneser yang cenderung memiliki titik yang banyak.
Kata kunci : Graf Kneser, Matriks Ketetanggaan, Determinan

## PENDAHULUAN
Graf Kneser pertama kali dikenalkan oleh seorang ahli matematika kebangsaan  Jerman,    Martin  Kneser pada  tahun  1955.  (Kneser,  1955) membuat  dugaan  bahwa  ketika  n-sub himpunan  dari  sebuah (2n+k)-himpunan dibagi atas (k+1) kelas, maka kedua sub himpunan  yang  tidak  saling  beririsan berada pada kelas yang sama. Kemudian dugaan Kneser ini dibuktikan oleh Lovasz (1978) dengan memperkenalkan sebuah kelas graf yang bernama Graf Kneser dengan mengambil  dua  bilangan  bulat  positif  n dan k untuk melambangkan graf Kneser ) , ( k n
K (Scheinerman  and  Ullman 2011,  pp. 31-32),  dan  alternative  bukti juga  diberikan  oleh  Bárány  (1978). Namun  Lovasz  juga  menambahkan bahwa  bilangan  kromatik  dari  graf kneser  ini  sama  dengan 2  k yang
artinya  bahwa  dugaan  Kneser  ini  akan selalu salah jika banyak kelas meningkat
ke 2  k . Graf Kneser yang dilambangkan dengan ) , ( k n K merupakan graf sederhana karena tidak memiliki lup dan sisi parallel. Dengan k n , adalah bilangan  bulat  positif,  k-sub  himpunan dari } , , 1 { n  dan dua titiknya dikatakan terhubung jika dan hanya jika irisan  dari  sub  himpunan  bagian  yang berkorespondensi  dengan  dua  titik tersebut  merupakan  himpunan  kosong.
Karena  itu ) , ( k n K memiliki       k n
banyak  titik, 2              k n k k n banyak
sisi  dan  setiap  titik  memiliki  tepat
Vol. 4 (3) Juni 2020, hlm. 255-260 p-ISSN: 2548 – 8856 | e-ISSN: 2549 - 127X
       k k n tetangga (Godsil, C. and Royle,
G.(2001) . Valencia-Pabon  &  Vera  (2005)  dalam artikelnya menunjukkan bahwa diameter dari graf kneser sama dengan 1 ] 2 / ) 1 [(    k n k .
Jika   2 / 1 2 5 1 3 2      k k k n , maka Graf Kneser ) , ( k n K selalu mengandung  Cycle  Hamiltonian  (Chen, 2003).  Graf  Kneser  dikatakan  graf komplit  jika  setiap  titik  terhubung dengan  semua  titik  dalam  graf  tersebut.
Graf  komplit  dengan  n  titik  adalah  graf Kneser ) 1 , ( n K . Dengan
keistimewaannya, graf Kneser mendapat
perhatian  para  matematikawan  dalam meneliti. Benjian & Wang (2012) dalam jurnlanya  membahas  tentang  nilai  eigen dari graph Kneser. Nilai eigen berhubungan  erat  dengan  determinan suatu  graf.  Namun  pada  tulisan  ini,
determinan  yang  dimaksud  hanyalah berdasarkan  matriks  ketetanggaannya saja. Hutabarat M (2015) dalam artikelnya mambahas bagaimana mencari  subgraf  biclique  maksimal  dari matriks  ketetanggaan  dari  Graf  Kneser. Disampaikan  bahwa  pencarian  sub biclique  nya  dapat  ditenukan  dengan menggunakan pola tertutup dari matriksnya.
Berikut adalah contoh dari graf Kneser.
Sumber. Mathworld.wolfram.com/KneserGraph.

## METODE
Matriks
Matriks merupakan salah satu
cara  dalam  menyajikan  data.  Dalam aljabar,  matriks  digunakan  untuk
menyajikan data dari banyak
persamaan.  Dalam  teori  graf,  matriks juga dapat digunakan dalam menyajikan  data  dari  sebuah  graf. Disini,  akan  kita  gunakan  untuk menyajikan  data  dari  graf  dalam  hal ini matriks ketetanggaan.
Defenisi  :  Matriks  ketetanggaan  dari graf adalah matriks nxn, disimbolkan  dengan ,  yang elemen-elemen  nya ,  sebagai berikut : Matriks  ketetanggaan  selalu merupakan matriks persegi. Ini dikarenakan  matriks  ketetanggaan merupakan ekspresi untuk menunjukkan  keterhungan  sebuah titik  terhadap  semua  titik  pada  graf termasuk terhadap titik itu sendiri.
Misal  untuk  graf  Kneser ) 1 , 7 ( K yang merupakan graf komplit karena  terhubung  kesemua  titik  pada graf.
Matriks  ketetanggaan  dari  graf  diatas
adalah
Graf  Kneser  merupakan  graf sederhana  tanpa  lup  dan  sisi  paralel yang mengakibatkan nilainya
hanyalah 0 dan 1.
Untuk  Sebuah  graf  berbobot, matriks  yang  disajikan  dari  graf tersebut bukanlah matriks ketetanggaan, namun nya
merupakan nilai dari bobot dari setiap sisi pada graf. Determinan Dalam bidang aljabar, determinan adalah  nilai  yang  dapat  dihitung  dari unsur suatu matriks persegi. Determinan merupakan factor penskalaan transformasi yang digambarkan oleh matriks. Determinan dari sebuah matriks dapat dicari dengan banyak cara. Penggunaannya  metode  disesuaikan dengan  kebutuhan  atau  jenis  matriks yang  ingin  dicari  determinannya. Sejalan dengan perkembangan pengetahuan, metode mencari determinan  dari  sebuah  graf  semakin banyak. 1. Untuk matriks 2x2 Penentuan determinannya sangat sederhana : Det Beberapa sifat yang mengikuti adalah :
a. Jika  dua  baris  matriks  A sama, maka det(A)=0 b. Jika  matrik  B  diperoleh dari  matriks  A  dengan menambah  suatu  baris dengan  K  kali  baris  yang lain.  Maka  det  (B)  =  Det
(A)
c. Det (A)=Det (A t )
2. Untuk Matriks 3x3
Penentuan determinannya bisa menggunakan cara a. b. Eliminasi  Gauss.  Yaitu dengan  cara  mereduksi sampai menolkan segitiga bawah  atau  segitiga  atas. Setelah  itu  maka  hasil kali nilai diagonalnya merupakan nilai determinannya (Zaini, 2016) Contoh : Direduksi menjadi
Sehingga  nilai  det  (A)=  - Det  (D)  =  -  [(-2)x2x4,5] =18. c. Sarrus.  Dikenal  dengan metode anyaman, dilakukan dengan cara : 3. Untuk Matriks nxn, n>3
a. Ekstension Sarrus [8] Dalam jurnalnya, Sobamowo  menunjukkan pengembangan metode sarrus  untuk  pencarian matriks 4x4 b. Cornice  determinan.  [9] Dalam jurnalnya, Gjonbalaj & Salihu menemukan cara menghitung determinan utk  matriks  nxn,  n>4. Dengan menggunakan Determinan

## PEMBAHASAN
Determinan  Matriks  Ketetanggaan
Dari Graf Kneser
Penentuan  determinan  untuk matriks ketetanggaan dari graf Kneser yang cenderung mempunyai titik yang banyak disarankan langsung menggunakan metode Cornice Determinan  karena  dianggap  lebih sederhana penggunaannya.
Dari  ciri-ciri  graf  Kneser  yang  tidak mempunyai lup maka nilai
Untuk  Graf  Kneser  komplit,  misal
determinan dengan cornice maka Ini  dikarenakan  semua  nilai =  1 sehingga  bila  dikalikan  hasilnya  akan sama dengan nol. Dengan rumus Karena nilai . Untuk  semua  orde  pada  matriks ketetanggaan  dari  Graf  Kneser,  nilai akan  selalu  sama  dengan
nol. Hal ini berlaku untuk semua Graf Kneser.
Berdasarkan  ini,  maka  dapat disimpulkan  bahwa  untuk  matriks ketetanggaan  dari  setiap  Graf  Kneser determinan  dari  matriks  adjacency atau  matriks  ketetanggaannya  akan selalu sama dengan 0 Hal  ini  tidak  berlaku  bagi  matriks berbobot Graf Kneser. Akan dilakukan penelitian lebih lanjut untuk hal ini .

## KESIMPULAN
Komponen  matriks  ketetanggaan dari    suatu  graf  Kneser  akan  selalu
memiliki nilai . Ini
mengakibatkan suatu ketentuan bahwa  nilai  determinan  dari  matriks ketetanggan  dari  setiap  Graf  Kneser akan  selalu  sama  dengan  0  juga.  Ini sejalan  dengan  matriks  identitas, dimana  semua  nilai dan memiliki  determinan  sama dengan 1. DAFTAR RUJUKAN Kneser, M. (1955) "Aufgabe 300." Jahresber. Deutsch. Math.-Verein 58. Lovász, L.(1978) "Kneser's Conjecture, Chromatic Numbers  and  Homotopy." J. Comb. Th. A 25, 319-324. Bárány,  I.  (1978),  "A  Short  Proof  of Kneser's Conjecture." J. Comb. Th. A 25, 325-326. Scheinerman,  E. R.  and  Ullman, D. H. Fractional Graph Theory  A  Rational  Approach to the Theory of Graphs. New
York: Dover, 2011.
Mario  Valencia-Pabon,  Juan-Carlos Vera (2005), “On The Diameter  of  Kneser  Graphs”, Discreate Mathemetics ELSEVIER Volume 305, Issue 1-3, Pages 383-385 . Chen, Ya -Chen (2003), “Triangle-free Hamiltonian  Kneser  Graph”,
Journal of Combinatorial Theory,  Series  B,  89(1),  doi: 10.1016/S0095-
8956(03)00040-6
BenjianLv, KaishunWang (2012) “The eigenvalues of  q-Kneser Graph”, Discrete Mathematics ELSEVIER Volume 312,
Issue 6, 28 March 2012, Pages 1144-1147.

## H . D.  Marina  Hutabarat  (2015)  “
Menentukan  subgraf  biclique maksimal  dengan  pasangan pola tertutup pada graf Kneser”., Jurnal Kharismatika, vo.1.no.2 2015.
Zaini  (2016)  Determinan  matriks
persegi  dan  non  persegi.
Uwais inspirasi Indonesia.

## A . Brouwer, W. Haemers (2011)
Spectra of Graphs Springer.
Sobamowo  M.G  (2016),  “On  The
Extension  of  Sarrus’  Rule  to nxn (n>3) matrics : Development of New Method for  the  Computation  of  the Determinant of 4x4 Matrix”International  Journal of  Engineering  Mathematics, Vol 2016, https://doi.org/10.1155/2016/9 382739