Matdis Graf

TI Politala Matdis 1C

    A.    Definisi Graf 

    Graf merupakan struktur diskrit yang terdiri himpunan sejumlah berhingga obyek yang disebut simpul

    (vertices, vertex) dan himpunan sisi (edges) yang menghubungkan simpul-simpul tersebut terdiri dari

    Graf digunakan untuk merepresentasikan objekobjek diskrit dan hubungan antara objek-objek tersebut.

     Notasi sebuah graf adalah G = (V, E), dimana :

      a.       V  merupakan   himpunan tak  kosong  dari  simpul-simpul  (vertices),   misalkan  V = { v1 , v2 , ... , vn } .

      b.      E merupakan  himpunan sisi – sisi  (edges) yang menghubungkan sepasang simpul,  misalkan E = {e1 , e2 , ... , en }

   B.    Jenis-jenis Graf

       Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:

     a.   Graf sederhana (simple graph) : Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. G1 pada Gambar 2 adalah contoh graf sederhana

        b.     Graf tak-sederhana (unsimple-graph) : Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph). G2 dan G3 pada Gambar 2 adalah contoh graf tak-sederhana 

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

       a.    Graf tak-berarah (undirected graph) : Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. 

      b.   Graf berarah (directed graph atau digraph) : Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah

   C.    Terminology Graf

        a.       Ketetanggaan (Adjacent)

              Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.

        b.   Bersisian (Incidency)

              Untuk sembarang sisi e = (v_j, v_k) dikatakan  e bersisian dengan simpul v_j , atau  e bersisian dengan simpul v_k.

        c.   Simpul Terpencil (Isolated Vertex)

              Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya.

        d.  Graf Kosong (null graph atau empty graph)

              Graf yang himpunan sisinya merupakan himpunan kosong (Nn)

        e.  Derajat (Degree)

             Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut Notasi: d(v)

        f.       Lintasan (Path)

             Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2,... , vn –1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), ... , en = (vn-1, vn) adalah sisi-sisi dari graf G.  

        g. Siklus (Cycle) atau Sirkuit (Circuit)

             Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus.

        h. Terhubung (Connected)

             Dua buah simpul v1 dan simpul v2 disebut terhubung jika terdapat lintasan dari v1 ke v2.  G disebut graf terhubung (connected graph) jika untuk setiap pasang simpul vi dan vj dalam himpunan V terdapat lintasan dari v_i ke v_j.  Jika tidak, maka G disebut graf tak-terhubung (disconnected graph).

        i.  Upagraf (Subgraph) dan Komplemen Upagraf

             Misalkan G = (V, E) adalah sebuah graf. G1 = (V1, E1) adalah upagraf (subgraph) dari G jika V1 ke V dan E1 ke E. Komplemen dari upagraf G1 terhadap graf G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = E - E1 dan V2 adalah himpunan simpul yang anggota-anggota E2 bersisian dengannya.

         j.  Upagraf Rentang (Spanning Subgraph)

             Upagraf G1 = (V₁, E₁) dari G = (V, E) dikatakan upagraf rentang jika V₁ =V (yaitu G₁ mengandung semua simpul dari G).

        k.  Cut-Set

             Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen.

         l. Graf Berbobot (Weighted Graph)

            Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot)

      Beberapa Graf Khusus :

         a.  Graf Lengkap (Complete Graph)

             Graf lengkap ialah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya. Graf lengkap dengan n buah simpul dilambangkan dengan Kn. Jumlah sisi pada graf lengkap yang terdiri dari buah simpul adalah n(n – 1)/2)

        b. Graf Lingkaran

            Graf lingkaran adalah graf sederhana yang setiap simpulnya berderajat dua. Graf lingkaran dengan n simpul dilambangkan dengan Cn.

        c. Graf Teratur (Regular Graphs)

            Graf yang setiap simpulnya mempunyai derajat yang sama disebut graf teratur. Apabila derajat setiap simpul adalah r, maka graf tersebut disebut sebagai graf teratur derajat r. Jumlah sisi pada graf teratur adalah nr/2.

       d.  Graf Bipartite (Bipartite Graph)

           Graf G yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V₁ dan V₂,  sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul di V₁ ke sebuah simpul di V₂ disebut graf bipartit dan dinyatakan sebagai G(V₁, V₂). 
     
    Materi lainnya :
     2. Representasi Graf & Graf Isomorfik
     http://anggrainidians.blogspot.com/2018/12/representasi-graf-matriksketetanggaan.html
     3. Graf Planar & Lintasan Euler
     https://cucusulaiman.blogspot.com/2018/12/graf-planar-planar-graph-dan-grafbidang.html
     4.  Lintasan Hamilton & Pewarnaan Graf
     https://yayadidiyadi.blogspot.com/2018/12/ti-politala-matdis-1c_11.html