Materi MatDis (Matematika Diskrit) : Graf

1. Definisi Graf
    Graf adalah tidak adanya sisi satu buah pun namun memiliki simpul, minimal adanya simpul satu.

2. Jenis-jenis Graf
    Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka secara urutan graf dapat          digolongkan menjadi dua jenis :

•      Graf Sederhana

               adalah graf yang tidak mengandung gelang maupun sisi-ganda. Pada graf sederhana, sisi                     adalah pasangan terurut. Jadi menuliskan sisi (u, v) sama saja dengan (v, u). Graf sederhana                 dapat juga diartikan himpunan tidak kosong simpul-simpul dan himpunan pasangan tak                       terurut yang disebut sebagai sisi.

• Graf Tak Sederhana

           adalah graf yang mengandung sisi ganda atau gelang. Ada dua macam graf tak sederhana,                   yaitu

1.          Graf Ganda

                   adalah graf yang mengandung sisi ganda. Sisi ganda yang menghubungkan sepasang                           simpul bisa lebih dari dua buah. Sisi ganda dapat diasosiasikan sebagai pasangan tak                           terurut yang sama. Serta dapat juga diartikan yang terdiri dari himpunan tidak kosong                           simpul-simpul dan himpunan ganda yang mengandung sisi ganda. Setiap graf sederhana                       juga adalah graf ganda tetapi tidak setiap graf ganda merupakan graf sederhana.

     

       2.         Graf Semu

               

                   adalah graf yang mengandung gelang. Graf semu lebih umum daripada graf ganda                               karena  sisi pada graf semu dapat terhubung ke dirinya sendiri.

Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis :

1. Graf Tak Berarah 

          adalah graf yang sisinya tidak mempunyai orientasi arah. Pada graf tak berarah, urutan                        pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi (u, v) = (v, u) adalah sisi              yang sama.

  

       2. Graf Berarah

           adalah graf yang setiap sisinya diberikan orientasi arah. Sisi berarah disebut dengan busur.                 Pada graf berarah, (u, v) dan (v, u) menyatakan dua buah busur yang berbeda. Untuk busur (u,             v), simpul v dinamakan simpul asal dan simpul v dinamakan simpul terminal.

TERMINOLOGI DASAR

1. Bertetangga

          Duah buah simpul dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah                  sisi.

       2. Bersisian

           Untuk sembarang sisi e = (u, v), sisi e dikatakan bersisian dengan simpul u dan simpul v.

       3. Simpul Terpencil

           adalah simpul yang tidak mempunyai sisi yang bersisian dengannya ataupun tidak satupun                   bertetangga dengan simpul-simpul lainnya.

        4. Graf Kosong

            adalah graf yang himpunan sisinya merupakan himpunan kosong.

         5. Derajat

             Derajat suatu simpul pada graf tak berarah adalah jumlah sisi yang bersisian dengan simpul                 tersebut.

             Notasi : d(v) menyatakan derajat simpul v
             Simpul yang berderajat satu disebut anting-anting. Dengan kata lain, anting-anting hanya                     bertetangga dengan sebuah simpul.

         6. Lintasan

             adalah barisan berselang-seling simpul-simpul dan sisi-sisi. Istilah lain untuk lintasan adalah               jalur. Simpul dan sisi yang dilalui di dalam lintasan boleh berulang. Sebuah lintasan                           dikatakan lintasan sederhana jika semua simpulnya berbeda. Lintasan yang berawal dan                     berakhir pada simpul yang sama disebut lintasan tertutup sedangkan lintasan yang tidak                     berawal dan berakhir pada simpul yang sama disebut lintasan terbuka. Panjang lintasan                     adalah jumlah sisi dalam lintasan tersebut.

       7. Siklus atau Sirkuit

            adalah lintasan yang berawal dan berakhir pada lintasan yang sama. Panjang sirkuit adalah                  jumlah sisi di dalam sirkuit tersebut.

        8. Terhubung

             Dikatakan terhubung jika terdapat lintasan dari u ke v diantara dua buah simpul u dan simpul               v. Jika dua buah simpul terhubung maka pasti simpul yang pertama dapat dicapai dari simpul               yang kedua. Jika setiap pasang simpul di dalam graf terhubung maka graf tersebut dikatakan               graf terhubung.

          9. Upagraf dan Komplemen Upagraf

          10. Upagraf Merentang

          11. Cut-Set

                Cut-Set atau jembatan adalah himpunan sisi yang apabila dibuang dari graf menyebabkan                    graf tersebut tidak terhubung.

          12. Graf Berbobot

                adalah graf yang setiap sisinya diberi sebuah harga (bobot).

             
BEBERAPA GRAF SEDERHANA KHUSUS

1. Graf Lengkap

          adalah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya.

       2. Graf Lingkaran

           adalah graf sederhana yang setiap simpulnya berderajat dua.

       3. Graf Teratur

            adalah graf yang setiap simpulnya mempunyai derajat yang sama.

        4. Graf Bipartit

            adalah himpunan simpulnya dapat dikelompokkan menjadi dua himpunan bagian.


REPRESENTASI GRAF

1. Matriks Ketetanggaan

          Karena matriks ketetanggaan hanya berisi 0 dan 1, maka matriks tersebut dinamakan matriks              nol-satu. Selain dengan angka 0 dan , elemen matriks dapat juga dinyatakan dengan nilai false            (menyatakan 0) dan true (menyatakan 1). Matriks ketetanggaan untuk graf sederhana dan tidak            berarah selalu simetri sedangkan untuk graf berarah matriks ketetanggaannya belum tentu                    simetri. Selain itu, diagonal utamanya selalu nol karena tidak ada sisi gelang.

      2. Matriks Bersisian

          Matriks bersisian menyatakan kebersisian simpul dengan sisi. Baris menunjukkan label simpul sedangkan kolom menunjukkan label sisinya. Matriks bersisian dapat digunakan untuk mempresentasikan graf yang mengandung sisi ganda atau sisi gelang.

      3. Senarai Ketetanggaan

          Senarai ketetanggaan menganumerasi simpul-simpul yang bertetangga dengan setiap simpul di dalam graf.


GRAF ISOMORFIK

adalah dua buah graf yang sama tetapi secara geometri berbeda. Syarat-syarat dua buah graf isomorfik :

1. Mempunyai jumlah simpul yang sama.
2. Mempunyai jumlah sisi yang sama.
3. Mempunyai jumlah simpul yang sama berderajat tertentu.