Abdussakir

Dzikir, Fikir, dan Amal Shaleh

Topik dalam Teori Graf

Posted by abdussakir on November 17, 2009

Pada tulisan ini akan disajikan beberapa topik kajian yang dapat diangkat sebagai penelitian atau tugas akhir berkaitan dengan teori graf. Topik-topik kajian ini merupakan topik yang sederhana yang dapat dijangkau oleh mahasiswa sarjana matematika atau pendidikan matematika.

A. Radius dan Diameter

Permasalahan yang banyak dibahas dalam teori graf berkaitan dengan radius dan diameter adalah menentukan order minimum (minimum order) suatu graf unisentral atau bisentral dengan radius r dan diameter d. Berdasarkan hubungan

rad(G) <= diam(G) <= 2 rad(G)

untuk setiap graf G, maka akan diperoleh beberapa kemungkinkan berikut.

  1. rad(G) = diam(G).
  2. diam(G) = 2 rad(G).
  3. rad(G) < diam(G) < 2 rad(G).

Untuk kemungkinan pertama dan kedua pada graf unisentral, telah dibahas dengan hasil berikut.

a. Jika G graf unisentral dengan rad(G) = diam(G) = r, maka order G adalah p = 1.

b. Jika G graf unisentral dengan rad(G) = r dan diam(G) = 2r, maka order minimum dari G adalah p = 2r + 1, untuk r bilangan asli.

Dengan demikian, masih ada kasus yang perlu diselesaikan yaitu menentukan order minimum graf unisentral atau disentral G dengan rad(G) = r dan r < diam(G) < 2r, untuk bilangan asli r.

B. Graf dan Matriks

Jika G graf, maka dapat dibuat matriks adjacency titik A(G), matriks incidency I(G), dan matriks adjacency sisi B(G). Misalkan a1, a2, …, an adalah nilai eigen berbeda dari A(G), dengan a1 > a2 > … > an, dan misalkan b1, b2, …, bn adalah banyaknya basis yang bersesuaian untuk masing-masing ai, i = 1, 2, …, n maka matriks berukuran 2 x n dengan baris pertama berisi nilai eigen a1, a2, …, an dan baris kedua berisi b1, b2, …, bn disebut SPECTRUM dari G.

Permasalahan yang dapat diteliti adalah tentukan spectrum dari berbagai jenis graf. Sampai sejauh ini, penelitian yang dilakukan mahasiswa matematika UIN Malang adalah spectrum dari graf komplit Kn, graf bipartisi komplit K(m,n), graf lintasan Pn, dan graf sikel Cn. Silahkan dicoba untuk graf roda Wn, graf garis suatu graf, atau graf dual suatu graf.

C. Matrix-Tree Formula

Jika G graf dengan order n dan himpunan titik {v1, v2, …, vn}, maka dapat dibuat matriks adjacency titik A(G) berorder nxn sesuai urutan pelabelan titik. Selain itu, dapat juga dibuat matriks diagonal D(G) = [dij] berordo nxn dengan unsur diagonal utama dii = deg(vi). deg(vi) adalah derajat titik vi di G. Matriks B = D(G) – A(G) disebut matrix-tree, dan sebarang mengambil nilai kofaktor dari B, akan sama dengan banyaknya pohon rentangan (spanning tree number) di G. Cara ini dikenal dengan sebutan Matrix-Tree Formula.

Permasalahan yang dapat diteliti adalah tentukan spanning tree number berbagai jenis graf. Sampai sejauh ini, penelitian yang dilakukan mahasiswa matematika UIN Malang adalah spanning tree number graf komplit Kn, graf bipartisi komplit K(m,n), graf lintasan Pn, graf sikel Cn, dan graf roda Wn. Silahkan dicoba untuk graf yang lain, graf garis suatu graf, graf dual suatu graf, atau pada graf hasil operasi dua graf atau lebih.

Selamat Mencoba.

2 Responses to “Topik dalam Teori Graf”

  1. imam said

    Gmn Pak, kalau spectrum dari graf baru yang sudah kita dapat atau topik graf yang lain, endingnya di rak perpustakaan atau dijadikan referensi bagi mahasiswa yang berkepentingan saja?, karena memang kajiannya teoritis dan bertujuan menambah konsep keilmuan dibidang itu…

  2. OP: I might be slow (lord knows I have been told lol) but that made absolutely no sense what so ever…

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

 
%d bloggers like this: