graf

Graf

A.   Pengertian graf

Secara kasar, graf adalah diagram yang disebut informasi yang berbeda jika diinterpretasikan secara tepat. Dalam kehidupan sehari-hari, berbagai macam struktur yang ada. Tujuannya adalah sebagai visualisasi objek-objek agar lebih mudah dimengerti.

Teori graf adalah pokok bahasan yang sudah tua usianya, namun memiliki banyak terapan dalam kehidupan sehari-hari. Banyak yang terjadi di dunia nyata yang reprensentasi visual dari graf. Salah satu contoh reprensentasi visual dari graf adalah Peta.Selain itu, masih banyak hal lain dalam dunia nyata yang merupakan representasi visual dari graf.

Graf adalah himpunan simpul yang menawarkan dengan garis-garis (ruas). Setiap ruas diasosiasikan dengan tepat dua simpul. Secara matematis, graf didefinisikan sebagai berikut:

Graf G terjemahan sebagai pasangan himpunan (V, E) yang dalam hal ini:

V = himpunan tidak kosong dadi simpul-simpul ( simpul atau simpul ): {v ₁ , v ₂ , v ₃,…, v _n }.

E = himpunan sisi ( ujung atau busur ) yang mehubungkan dekorasi simpul: {e ₁, e ₂ , e ₃ ,…, e _n }.

Atau dapat menulis singkat dengan notasi G = (V, E). Jadi mungkin saja tidak memiliki sisi satu buahpun, tapi simpulnya harus ada, minimal satu. Graf yang hanya memiliki satu buah simpul tanpa sebuah sisipun dinamakan graf sepele.

Bentuk dasar dengan satu atau dua titik. Titik-titik tersebut dinamakan titik ujung. Garis yang hanya berhubungan dengan satu titik ujung disebut Loop . Dua garis yang berbeda yang sama disebut Garis paralel . Perlu dilihat bahwa garis, kelengkungan, dan titik-titik tidak berpengaruh dalam graf.

B.    Jenis-Jenis Graf

Berdasar ada atau tidaknya lingkaran atau seperti parallel pada umumnya graf, maka dapat digolongkan menjadi dua jenis:

1.     Graf sederhana (grafik sederhana).

Graf yang tidak memiliki lingkaran garis paralel.

2.     Graf tak sederhana (grafik tidak sederhana).

Graf yang memiliki lingkaran garis paralel.

Berdasarkan orientasi arah pada sisi, bisa umum dapat digolongkan menjadi:

1.     Graf berarah (graf berarah).

Graf yang setiap sisinya diberikan orientasi arah. PADA graf berarah, (v _k , v _j ) Dan (v _j, v _k ) menyatakan doa Unsur Yang BERBEDA, dengan kata lain (v _j, v _k ) (v _k , v _j ).

2.     Graf tak-berarah (graf tak berarah)

graf yang sisinya tidak memiliki arah orientasi. Urutan menggabungkan simpul yang disamakan dengan sisi tidak terlihat, dengan kata lain: (v _j, v _k ) = (v _k , _vj ).

C.    Terminologi Dasar

Tahu beberapa istilah penting yang membahas dengan graf. Ini adalah beberapa terminologi yang sering digunakan:

1.     Bertetangga (adjancent)

Dua buah simpul pada graf yang tak-berarah Gistrik yang bertetangga bila keduanya terhubung langsung dengan sebuah sisi. Dengan kata lain, v _jbertetangga DENGAN v _k  JIKA (v _j, v _k ) Adalah Sebuah Sisi PADA graf G.

2.     Bersisian (insiden)

Untuk sembarang sisi e = (v _j, v _k ) _, sisi eentu bersisian dengan simpul v _k dan simpul v _k .

3.     Derajat (gelar).

Derajat simpul pada graf tak-berarah adalah jumlah sisi yang bersisian dengan simpul tersebut. PADA graf berarah, derajat Simpul v dinyatakan DENGAN d _di(v) Dan D _keluar (v), Yang Dalam hal ini kami:

d _in (v) = derajat masuk (dalam derajat)

= jumlah simpul yang masuk ke simpul v

d _out (v) = derajat keluar (out-degree)

= jumlah simpul yamg keluar dari simpul v

d (v) = d _dalam (v) + d _keluar (v), d (v) menegaskan derajat simpul.

Berdasarkan tujuan kami yaitu mencari lintasan yang sempurna untuk sampai ke tujuan, akan ada gubahan ganda berarah berbobot. Anggaplah graf tersebut akan dimaksudkan sebagai berikut:

1.     Graf ganda

Graf ganda adalah graf yang memiliki lebih dari satu sisi untuk menghubungkan dua simpul. Pada graf di bawah, peluang graf yang memiliki sisi ganda. Sisi kanan ganda di bawah adalah sisi yang menghubungkan simpul A dan simpul B. karena terdapat dua sisi yang menghubungkan simpul A dan simpul B, maka graf itu dinamakan graf ganda

2.     Graf berarah

Graf yang setiap sisinya diberikan sensor arah disebut graf berarah. Graf yang setiap sisinya diberikan orientasi arah. PADA graf berarah, (v _k , v _j ) Dan (v _j, v _k ) menyatakan doa Unsur Yang BERBEDA, dengan kata lain (v _j, v _k ) (v _k , v _j ).

3.     Graf berbobot

Graf berbobot adalah graf yang mana setiap sisinya diberi harga (berat) atau Nilai. Bobot pada setiap sisi dapat mereprentasikan sesuatu, misalnya jarak, prioritas, harga, dan lain-lain.

4.     Graf Ganda Berarah Berbobot

Graf ganda berarah berbobot adalah gabungan dari salah graf di atas. Untuk lebih jelasnya, gambar di bawah ini akan memberikan gambaran tentang graf ganda berarah berbobot.

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 n 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 isomorfik

Adalah 2 buah graf yang sama hanya penggambaran secara geometri yang berbeda . Dua buah graf, G1 dan G2 dikatakan isomorfik jika terdapat

>>korespondensi satu-satu antara simpul-simpul keduanya dan antara sisisisi keduaya sedemikian sehingga hubungan kebersisian tetap terjaga.
>>Dengan kata lain, misalkan sisi e bersisian dengan simpul u dan v di G1,
maka sisi e’ yang berkoresponden di G2 harus bersisian dengan simpul u’
dan v’ yang di G2.
>>Dua buah graf yang isomorfik adalah graf yang sama, kecuali penamaan
simpul dan sisinya saja yang berbeda. Ini benar karena sebuah graf dapat
digambarkan dalam banyak cara.