Showing posts with label Teori Graf. Show all posts

Pewarnaan Graph dan Algoritma Welsh Powell

Definisi Pewarnaan Graf (Coloring Graph)

Masalah pewarnaan graf adalah memberikan warna pada elemen-elemen tertentu dari graf yang tunduk pada batasan-batasan tertentu. Pewarnaan titik adalah masalah pewarnaan graf yang paling umum. Soalnya, diberikan m warna, temukan cara mewarnai simpul dari suatu graf sedemikian rupa sehingga tidak ada dua simpul bertetangga yang diwarnai menggunakan warna yang sama.

Bilangan Kromatik

Bilangan Kromatik adalah banyaknya warna minimum yang diperlukan untuk mewarnai simpul-simpul suatu graf G sedemikian rupa sehingga tidak ada dua simpul bertetangga yang memiliki warna yang sama dilambangkan dengan x(G).

Teorema Bilangan Kromatik pada Subgraf bagian : Jika H adalah subgraf dari G,χ(H)≤χ(G).

Bukti: Setiap pewarnaan G memberikan pewarnaan yang tepat untuk H, hanya dengan memberikan warna yang sama pada simpul-simpul H yang mereka miliki di G. Ini berarti bahwa H dapat diwarnai dengan warna (G), bahkan mungkin lebih sedikit.

Teorema Pewarnaan Graf Komplit (Complete Graph): Jika G adalah graf lengkap dengan n titik (Kn) maka χ(n)=n.

Bukti: Karena G merupakan graf lengkap maka tiap titiknya berderajat n-1. Pilih sembarang titik v untuk diwarnai maka untuk mewarnai titik lain yang bertetangga memerlukan n-1 warna. Sehingga banyak warna n-1+1=n warna.

Teorema Graf Nol (Null Graph) : Jika G adalah graf nol maka χ(G)=1.

Bukti: Karena G graf nol maka tidak akan ada titik yang bertetangga sehingga hanya butuh satu warna untuk semua titik di G.

Teorema Graf Bipartisi : G graf bipartisi jika dan hanya jika χ(G).

Bukti: Himpunan titik V(G) dibagi menjadi dua himpunan bagian V1 dan V2. Pilih salah satu himpunan bagian V1, karena setiap titik pada himpunan bagian V1 tersebut tidak bertetangga maka hanya perlu menggunakan 1 warna begitu juga dengan V2. Kemudian tiap titik di V1 bertetangga di V2 sehingga V1 dan V2 memiliki warna yang berbeda sehingga χ(G)=2.

Teorema Graf Sikel: Jika G graf sikel Cn maka χ(G)=2 untuk n genap dan 3 untuk n ganjil.

Bukti: Untuk sikel genap, titik titik pada G dapat diwarnai selang seling sehingga hanya dibutuhkan 2 warna. Selanjutnya untuk sikel ganjil n, n-1 genap sehingga dapat selang seling, tetapi ada titik ke n yang terhubung dengan titik 1 dan n-1 yang memiliki 2 warna berbeda sehingga pada titik n memerlukan warna ke 3.

Teorema Derajat Terbesar: Misalakn G graf sederhana dengan derajat terbesar Δ(G), maka χ(G)≤ Δ(G)+1.

Teorema Graf Planar : Pada Graf Planar G dapat diwarnai oleh 4 warna.

Algoritma Welsh Powell

Dalam teori graf, pewarnaan simpul adalah cara memberi label pada setiap simpul individu sedemikian rupa sehingga tidak ada dua simpul bertetangga yang memiliki warna yang sama. Tapi kita perlu mencari tahu jumlah warna yang kita butuhkan untuk memenuhi kondisi yang diberikan. Tidak diinginkan untuk memiliki banyak variasi warna atau label. Jadi, Kami memiliki algoritma yang disebut algoritma welsh Powell yang memberikan warna minimum yang kami butuhkan. Algoritma ini juga digunakan untuk mencari bilangan kromatik suatu graf. Ini adalah pendekatan serakah berulang.

Algoritma Welsh Powell terdiri dari Langkah-langkah berikut:

Tentukan derajat setiap simpul
Daftar simpul dalam urutan derajat menurun.
Warnai simpul pertama dengan derajat terbesar dengan warna 1.
Pindah ke bawah daftar dan warnai semua simpul yang tidak terhubung ke simpul berwarna, dengan warna yang sama.

Ulangi langkah 4 pada semua simpul yang tidak diwarnai dengan warna baru, dalam urutan derajat yang menurun hingga semua simpul diwarnai.

Dengan memulai dengan derajat terbesar, kami memastikan bahwa simpul dengan jumlah konflik tertinggi dapat ditangani sedini mungkin.

Definisi Graf Eulerian

Lintasan Euler atau Eulerian path melalui graf adalah lintasan yang daftar sisinya memuat setiap sisi graf tepat satu kali.

Lintasan Euler yang berawal dan berakhir pada simpul yang sama disebut sirkuit Euler. Graf Euler adalah graf yang memiliki sirkuit Euler.

Teorema Graf Euler

Kasus Umum: Graf tak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan memiliki nol atau dua simpul yang berderajat ganjil. Jika tidak ada simpul yang berderajat ganjil, maka grafnya adalah Euler.

Berdasarkan teorema diatas akan didapatkan teorema dibawah:

Jika suatu graf terhubung dan setiap simpul berderajat genap, maka ia memiliki setidaknya satu sirkuit Euler.

Jika suatu graf terhubung dan memiliki tepat dua simpul berderajat ganjil, maka graf tersebut memiliki paling sedikit satu lintasan Euler (biasanya lebih). Setiap jalur tersebut harus dimulai pada salah satu simpul derajat ganjil dan berakhir di simpul lainnya.

Jumlah derajat semua simpul dari suatu graf sama dengan dua kali jumlah sisi (dan karenanya harus bilangan genap).

Cara Mencari Lintasan Sirkuit Euler / Eulerian

Pastikan bahwa setiap simpul dalam jaringan memiliki derajat genap.
Mulailah rangkaian Euler di sembarang simpul dalam jaringan.
Saat Anda memilih tepi, jangan pernah menggunakan tepi yang merupakan satu-satunya koneksi ke bagian jaringan yang belum Anda kunjungi.
Beri label tepi dalam urutan yang Anda tempuh dan lanjutkan ini sampai Anda telah melakukan perjalanan di sepanjang setiap tepi tepat satu kali dan Anda berakhir di simpul awal.

Definisi Graf Hamiltonian

Lintasan Hamilton atau Hamiltonian melalui suatu graf adalah lintasan yang daftar simpulnya berisi setiap simpul dari graf tepat satu kali, kecuali jika lintasannya adalah sirkuit, dalam hal ini simpul awal muncul untuk kedua kalinya sebagai simpul terminal/akhir. Jika lintasannya berupa sirkuit, maka disebut sirkuit Hamilton. Graf Hamilton adalah graf yang memiliki sirkuit Hamilton.

Teorema Hamilton

Grafik lengkap pasti memiliki sirkuit Hamilton.

Graf lengkap dengan N simpul adalah (N-1)! sirkuit Hamilton. Karena setengah dari sirkuit adalah bayangan cermin dari setengah lainnya, sebenarnya hanya ada setengah dari banyak sirkuit unik ini.

Cara mengatasi Travelling Salesman Problem (TSP)

Masalah penjual keliling adalah masalah di mana Anda membayangkan bahwa penjual keliling melakukan perjalanan bisnis. Dia mulai di kota asalnya (A) dan kemudian perlu melakukan perjalanan ke beberapa kota yang berbeda untuk menjual barang dagangannya (kota lainnya adalah B, C, D, dll.). Untuk menyelesaikan TSP, Anda perlu menemukan cara termurah bagi penjual keliling untuk memulai di rumah, A, bepergian ke kota lain, dan kemudian pulang ke A di akhir perjalanan. Ini hanya menemukan sirkuit Hamilton dalam grafik lengkap yang memiliki bobot keseluruhan terkecil. Ada beberapa algoritma yang berbeda yang dapat digunakan untuk memecahkan masalah jenis ini.

Algoritma Brute Force

Daftar semua kemungkinan sirkuit Hamilton dari grafik.
Untuk setiap sirkuit, temukan bobot totalnya.
Sirkuit dengan bobot total paling kecil adalah sirkuit Hamilton yang optimal.

Algoritma Tetangga Terdekat (Nearest-Neighbor Algorithm)

Pilih simpul sebagai titik awal.
Dari titik awal pergi ke simpul dengan tepi dengan bobot terkecil. Jika ada lebih dari satu pilihan, pilih secara acak.
Lanjutkan membangun sirkuit, satu per satu simpul dari antara simpul yang belum dikunjungi.
Dari simpul terakhir, kembali ke titik awal.

Algoritma Tetangga Terdekat Berulang (Repetitive Nearest-Neighbor Algorithm)

Biarkan X menjadi sembarang simpul. Terapkan Algoritma Tetangga Terdekat dengan menggunakan X sebagai titik awal dan hitung total biaya rangkaian yang diperoleh.
Ulangi proses tersebut dengan menggunakan setiap simpul lain dari graf sebagai simpul awal.
Dari sirkuit Hamilton yang didapat, pertahankan yang terbaik. Jika ada titik awal yang ditunjuk, tulis ulang rangkaian ini dengan titik tersebut sebagai titik referensi.

Algoritma Tautan Termurah (Cheapest-Link Algorithm)

Pilih link dengan bobot terkecil terlebih dahulu (jika ada seri, pilih salah satu secara acak). Tandai tepi yang sesuai dengan warna merah.
Pilih tautan termurah berikutnya dan tandai tepi yang sesuai dengan warna merah.
Lanjutkan memilih tautan termurah yang tersedia. Tandai tepi yang sesuai dengan warna merah kecuali jika a) menutup sirkuit atau b) menghasilkan tiga tepi yang keluar dari satu simpul.
Ketika tidak ada lagi simpul untuk dihubungkan, tutup sirkuit merah.

Definisi Pohon (Tree) dapa Teori Graph

Graf terhubung tak berarah G disebut pohon jika penghapusan salah satu sisinya membuat G terputus. Sekumpulan pohon Tree disebut hutan (forest).

Dalam teori graf, tree adalah graf tak berarah, terhubung, dan asiklik. Dengan kata lain, graf terhubung yang tidak memuat satu siklus pun disebut pohon.

Sebuah pohon mewakili struktur hierarkis dalam bentuk grafik. Elemen-elemen pohon disebut simpulnya dan tepi pohon disebut cabang. Sebuah pohon dengan n simpul memiliki (n-1) sisi.

Daun pada pohon adalah simpul berderajat 1 atau setiap simpul yang tidak memiliki cabang ke bawah disebut daun.

Sifat-sifat Tree Pohon

Setiap pohon pada dua atau lebih simpul memiliki setidaknya satu simpul daun.

Simpul yang berada di bagian atas pohon dikenal sebagai akar pohon.

Item data yang tersisa dibagi menjadi himpunan bagian yang terpisah-pisah yang disebut sebagai subpohon.

Pohon itu diperluas dari atas ke arah bawah.

Graf T adalah pohon jika dan hanya jika antara setiap pasangan simpul berbeda dari T terdapat lintasan yang unik.

Sebuah pohon dengan n simpul memiliki tepat n−1 cabang atau sisi.

Sebuah pohon dengan simpul berderajat k≥1 memiliki setidaknya k simpul daun. Secara khusus, setiap pohon dengan setidaknya dua simpul memiliki setidaknya dua simpul daun.

Sebuah titik potong pada graf terhubung G adalah sebuah titik yang penghilangannya memutuskan graf tersebut. Setiap graf terhubung memiliki simpul daun yang bukan merupakan titik potong.

Elemen elemen pada Tree

Edge – Garis yang menghubungkan dua node.

Level – Sebuah pohon dipartisi menjadi beberapa level sedemikian rupa sehingga simpul akar berada pada level 0. Kemudian, anak-anak terdekatnya berada di level 1, dan anak-anak terdekatnya berada pada level 2 dan seterusnya hingga terminal atau simpul daun.

Derajat – Ini adalah jumlah subpohon dari sebuah simpul di pohon tertentu.

Depth – Ini adalah tingkat maksimum dari setiap simpul di pohon tertentu dan juga dikenal sebagai ketinggian.

Node terminal – Node level tertinggi adalah node terminal sementara node lain kecuali terminal dan node root dikenal sebagai node non-terminal.

Perbedaan Tree dan Graf

Pada tree pohon hanya ada satu jalur antara dua simpul sedangkan grafik dapat memiliki jalur searah dan dua arah antara node.

Pada pohon, ada tepat satu simpul akar, dan setiap anak hanya dapat memiliki satu orang tua. Sebaliknya, dalam grafik, tidak ada konsep simpul akar.

Sebuah pohon tidak dapat memiliki loop dan self-loop sedangkan graph dapat memiliki loop dan self-loop.

Grafik lebih rumit karena dapat memiliki loop dan self-loop. Sebaliknya, pohon sederhana dibandingkan dengan grafik.

Sebuah pohon dapat memiliki n-1 sisi. Sebaliknya, dalam grafik, tidak ada jumlah tepi yang ditentukan sebelumnya, dan itu tergantung pada grafik.

Pohon memiliki struktur hierarkis sedangkan grafik memiliki model jaringan.

Pohon Merentang (Spanning Tree)

Jika G adalah graf terhubung pada n simpul, pohon merentang pada G adalah subgraf dari G yang merupakan pohon pada n simpul. Setiap graf terhubung memiliki spanning tree.

Metode Spanning Tree

Kita dapat menemukan pohon merentang secara sistematis dengan menggunakan salah satu dari dua metode:

1. Metode pemotongan

Mulailah memilih graf melingkar apa pun di Grafik G.

Hapus salah satu tepi graf melingkar.

Ulangi proses ini sampai tidak ada lingkaran yang tersisa.

2. Metode membangun

Pilih tepi graf G satu per satu. Sedemikian rupa sehingga tidak ada siklus yang dibuat.

Ulangi proses ini sampai semua simpul dimasukkan.

Definisi Graf Isomorfik

Isomorfisme graf adalah fenomena keberadaan graf yang sama dalam lebih dari satu bentuk yang disebut graf isomorfik.

Graf G dan H bersifat isomorfik jika terdapat struktur yang mempertahankan korespondensi satu-satu antara simpul dan sisi. Dengan kata lain, kedua graf tersebut hanya berbeda nama sisi dan simpulnya saja, tetapi secara struktural ekuivalen

Syarat dan Kondisi Dua Graf Isomorfik

Untuk setiap dua grafik menjadi isomorfik, 4 kondisi berikut harus dipenuhi,yaitu:

Jumlah simpul pada kedua graf harus sama.
Jumlah rusuk pada kedua graf harus sama.
Urutan derajat kedua grafik harus sama.
Jika sebuah siklus dengan panjang k dibentuk oleh simpul { v1 , v2 , ….. , vk } dalam satu graf, maka sebuah siklus dengan panjang k yang sama harus dibentuk oleh simpul { f(v1) , f(v2) , ….. , f(vk) } di grafik lain juga.

4 kondisi di atas hanyalah kondisi yang diperlukan untuk setiap dua grafik menjadi isomorfik. Mereka sama sekali tidak cukup untuk membuktikan tetapi hanya menunjukan bahwa kedua grafik tersebut mungkin isomorfik. Jika keempat syarat tersebut memenuhi, maka tidak dapat dikatakan bahwa graf tersebut pasti isomorfik. Namun, jika ada syarat yang dilanggar, maka dapat dikatakan bahwa graf tersebut pasti tidak isomorfik.

Kondisi berikut adalah kondisi yang cukup untuk membuktikan dua graf isomorfik. Jika salah satu dari kondisi ini memenuhi, maka dapat dikatakan bahwa grafik tersebut pasti isomorfik.

Dua graf dikatakan isomorfik jika dan hanya jika graf komplemennya isomorfik.
Dua graf dikatakan isomorfik jika matriks ketetanggaannya sama.
Dua graf dikatakan isomorfik jika sub-graf yang bersesuaian diperoleh dengan menghapus beberapa simpul dari satu graf dan gambar yang bersesuaian pada graf lainnya adalah isomorfik.

Definisi Graf Planar dan Graf Bidang (Planar Graf)

Suatu graf dikatakan planar jika graf tersebut dapat digambarkan pada suatu bidang tanpa ada sisi yang bersilangan. Gambar seperti itu disebut representasi planar graf.

Ketiga gambar diatas adalah graf K4 dan isomorfiknya merupakan contoh graf planar. Jika diperhatikan graf dikatakan planar jika salah satu isomorfiknya merupakan graf planar. Graf isomorfik yang digambarkan dengan sisi tidak menyilang satu sama lain disebut graf bidang (plane graph). Contoh Graf bidang adalah gambar ke 2 dan 3 dari K4.

Wilayah (Region) pada Graf Planar

Ketika graf planar digambar tanpa sisi-sisi yang bersilangan, sisi-sisi dan simpul-simpul dari graf tersebut membagi bidang menjadi daerah-daerah. Kami akan menyebut setiap wilayah sebagai wajah termasuk diluar graf. Graf K4 terdapat 4 wilayah. Wilayah pada planar disibolkan dengan f

Jumlah wajah tidak berubah bagaimanapun Anda menggambar grafik (selama Anda melakukannya tanpa tepi bersilangan), jadi masuk akal untuk menganggap jumlah wajah sebagai properti grafik planar.

Ada hubungan antara jumlah simpul (v), jumlah sisi (e) dan jumlah daerah (f) pada graf planar yang terhubung.

Untuk setiap graf planar terhubung dengan v simpul, tepi e dan wajah f, kita memiliki v−e+f=2 atau f=2-v+e.

Selain itu terdapat teorema lain yaitu:

Jika G adalah graf planar terhubung dengan e sisi dan v simpul, di mana v≥3, maka e≤3v-6. Juga G tidak dapat memiliki titik yang berderajat lebih dari 5.

Jenis Jenis Graf pada Teori Graph

Ada banyak jenis graf yang berbeda tergantung pada jumlah simpul, jumlah sisi, interkonektivitas, dan struktur keseluruhannya, beberapa jenis graf yang umum adalah sebagai berikut:

Graf Sederhana (Simple Graph)

Graf sederhana adalah graf yang tidak memiliki lebih dari satu sisi di antara dua simpul dan tidak ada sisi yang berawal dan berakhir pada simpul yang sama. Dengan kata lain graf sederhana adalah graf tanpa loop dan sisi ganda.

Graf Multi (Multi Graph)

Graf yang memiliki banyak sisi di antara setiap pasangan simpulnya atau terdapat sisi dari suatu simpul ke dirinya sendiri (loop) disebut graf multi.

Graf Berbobot (Weighted Graph)

Graf berbobot adalah graf yang sisi-sisinya diberi label dengan beberapa bobot atau angka.

Panjang suatu lintasan pada graf berbobot adalah jumlah bobot semua sisi pada lintasan tersebut.

Graf Berarah (Directed Graph) dan Tidak Berarah (Undirected Graph)

Graf berarah adalah graf yang memiliki sisi dengan arah. Sisi menunjukkan hubungan satu arah, di mana setiap sisi hanya dapat dilalui dalam satu arah.

Sedangkan, Graf tak berarah adalah graf yang memiliki sisi yang tidak memiliki arah. Tepi menunjukkan hubungan dua arah, di mana setiap tepi dapat dilalui di kedua arah.

Graf Terhubung (Connected Graph) dan Graf Tak terhubung (Disconnected Graph)

Graf terhubung adalah graf yang memiliki lintasan atau jalur dari titik mana pun ke titik lain dalam grafik.

Graf tak terhubung adalah graf yang titik-titik terpisah menjadi dua atau lebih grup yang berbeda, di mana tidak mungkin menghubungkan simpul dalam satu grup ke simpul di grup lain dengan melakukan perjalanan sepanjang serangkaian tepi.

Graf Nol (Null Graph)

Graf nol didefinisikan sebagai graf yang hanya terdiri dari simpul-simpul yang terisolasi. Ini berarti graf nol tidak memiliki sisi yang yang menghubungkan titik simpul pada graf. Graf nol dengan n simpul dinotasikan dengan Nn.

Graf Trivial

Graf trivial adalah graf yang hanya memiliki satu simpul.

Graf Reguler (Regular Graph)

Graf Reguler adalah graf yang derajat semua simpulnya sama. Jika derajat semua simpul adalah k, maka disebut graf beraturan k.

Graph Komplit (Complete Graph)

Graf yang setiap pasang simpulnya dihubungkan oleh tepat satu sisi disebut graf lengkap. Ini berisi semua kemungkinan tepi. Graf lengkap dengan n simpul mengandung tepat nC2 sisi dan diwakili oleh Kn.

Graph Sikel (Cycle Graph)

Graf dengan 'n' simpul (di mana, n>=3) dan 'n' tepi membentuk lingkaran 'n' dengan semua sisinya dikenal sebagai graf sikel. Graf yang mengandung setidaknya satu siklus di dalamnya dikenal sebagai graf siklik. Pada graf sikel, derajat setiap simpul adalah 2. Graf siklus yang memiliki n simpul dilambangkan dengan Cn.

Graph Lintasan (Path Graph)

Graf lintasan adalah sebuah pohon dengan dua simpul yang berderajat 1 dan satu simpul lainnya. simpul derajat 2. Oleh karena itu, graf jalur adalah graf yang dapat ditarik sehingga semua simpul dan tepinya terletak pada satu garis lurus.

Graph Roda (Wheel Graph)

Graf roda diperoleh dengan menghubungkan sebuah simpul ke semua simpul dari graf siklus. Dilambangkan dengan Wn, untuk n > 3 dimana n adalah jumlah simpul pada graf. Graf roda dengan n simpul berisi graf siklus dengan orde n – 1 dan semua simpul dari siklus terhubung ke satu simpul . Banyaknya rusuk pada graf Roda, Wn adalah 2n – 2.

Graf Bintang (Star Graf)

Graf bintang adalah jenis graf khusus di mana n-1 simpul memiliki derajat 1 dan satu simpul memiliki derajat n – 1. Ini terlihat seperti n – 1 simpul terhubung ke satu simpul pusat. Graf bintang dengan total n simpul disebut sebagai Sn.

Graph Platonik (Platonic Graph)

Graf platonik muncul dari lima benda padat: tetrahedron, oktahedron, kubus, dodecahedron, dan ikosahedron, di mana titik-titik graf sama dengan titik-titik padatan, dan sisi-sisi graf sama dengan sisi-sisi padatan . Tentu saja, graf-graf ini dapat diubah dalam berbagai cara selama setiap simpul terhubung dengan tepat.

Graph Bipartisi (Bipartite Graph)

Graf bipartisi adalah graf yang himpunan simpulnya dapat dipartisi menjadi dua himpunan sehingga sisi-sisinya hanya berada di antara himpunan, bukan di dalamnya.

Suatu graf G(V,E) disebut graf bipartisi jika himpunan titiknya V(G) dapat diuraikan menjadi dua himpunan bagian tak-kosong yang saling lepas V1(G) dan V2(G) sedemikian rupa sehingga setiap sisi e∈E(G) memiliki satu sambungan terakhir di V1(G) dan titik terakhir lainnya di V2(G).

Partisi V = V1∪V2 disebut bipartisi dari G.

Graph Bipartisi Komplit (Complete Bipartite Graph)

Graf bipartisi lengkap adalah graf bipartisi yang setiap simpul pada himpunan pertama dihubungkan dengan setiap simpul pada himpunan kedua dengan tepat satu sisi. Misal banyak titik pada kedua himpunan bagian pasrtisi adalah r dan s maka banyak titik adalah r+s dan banyak sisi adalah rs.

Merepresentasi Graf kedalam Matriks

Dalam teori graf, representasi graf adalah teknik untuk menyimpan graf ke dalam memori komputer.

Untuk merepresentasikan sebuah graf, kita hanya memerlukan himpunan simpul, dan untuk setiap simpul tetangga dari simpul tersebut (simpul yang terhubung langsung dengannya oleh sebuah sisi). Jika graf merupakan graf berbobot, maka bobot tersebut akan diasosiasikan dengan setiap sisinya.

Ada berbagai cara untuk merepresentasikan grafik secara optimal, tergantung pada kerapatan sisinya, jenis operasi yang akan dilakukan, dan kemudahan penggunaan.

Matriks Adjacency atau Keterhubungan

Matriks Adjacency adalah representasi sekuensial. Digunakan untuk merepresentasikan node mana yang terhubung satu sama lain. Yaitu apakah ada sisu yang menghubungkan titik-titk dalam graf.

Dalam representasi Matriks Adjacency ini, kita harus membangun matriks n×n A. Jika ada sisi dari titik i ke titik j, maka elemen yang sesuai dari A, aij = 1 (bisa lebih dari 1 jika sisi ganda) dan jika tidak aij= 0.

Jika ada graf berbobot maka alih-alih 1 dan 0, kita dapat menyimpan bobot sisinya.

Kelebihan: Representasi lebih mudah diterapkan dan diikuti.

Kekurangan: Dibutuhkan banyak ruang dan waktu untuk mengunjungi semua tetangga dari sebuah simpul, kita harus melintasi semua simpul dalam grafik, yang memakan waktu cukup lama.

Contoh Matriks Adjacency

Matriks Adjacency Graf Tidak Berarah

Matriks Adjacency Graf Berarah

Matriks Adjacency Graf Berbobot

Matriks Incidence atau kebersisian

Dalam representasi matriks Insiden, grafik dapat direpresentasikan menggunakan matriks ukuran: jumlah total simpul × jumlah total tepi.

Artinya, jika suatu graf memiliki 4 simpul dan 6 rusuk, maka graf tersebut dapat direpresentasikan menggunakan matriks kelas 4×6. Dalam matriks ini, kolom mewakili tepi dan baris mewakili simpul.

Matriks ini diisi dengan 0 atau 1 atau -1 (untuk graf berarah). Di mana,

0 digunakan untuk mewakili tepi baris yang tidak terhubung ke simpul kolom.
1 digunakan untuk mewakili tepi baris yang terhubung sebagai tepi keluar ke simpul kolom.
-1 digunakan untuk mewakili tepi baris yang terhubung sebagai tepi masuk ke simpul kolom.

Contoh Matriks Incidence

Graf, Subgraf dan Komplemen Graf

Teori graf merupakan cabang matematika yang mempelajari jaringan titik-titik yang dihubungkan oleh garis. Subjek teori graph berawal dari masalah matematika rekreasi, tetapi telah berkembang menjadi area penelitian matematika yang signifikan, dengan aplikasi dalam kimia, riset operasi, ilmu sosial, dan ilmu komputer.

Sejarah teori graf dapat ditelusuri secara khusus ke tahun 1735, ketika matematikawan Swiss Leonhard Euler memecahkan masalah jembatan Königsberg. Masalah jembatan Königsberg adalah teka-teki lama tentang kemungkinan menemukan jalur di atas setiap satu dari tujuh jembatan yang membentang di sungai bercabang yang mengalir melewati sebuah pulau, tetapi tanpa melintasi jembatan apa pun dua kali. Euler berpendapat bahwa tidak ada jalan seperti itu. Pembuktiannya hanya melibatkan referensi ke susunan fisik jembatan, tetapi pada dasarnya dia membuktikan teorema pertama dalam teori graph.

Definisi Graf

Graf G merupakan pasangan dua himpunan yaitu V(G) himpunan tak kosong yang anggotanya disebut titik dan E(G) himpunan yang anggotanya disebut sisi.

Dari definisi diatas dapat disimpulkan bahwa graf adalah kumpulan titik-titik yang dihubungkan oleh garis dari titik satu ke titik lainnya.

Unsur dan Elemen Graf

Berdasarkan definisi graf, graf memiliki dua elemen yaitu titik dan sisi.

Titik dapat disebut juga vertex, simpul, point, atau node. Titik dalam graf yang dapat mewakili persimpangan jalan, daratan, atau lokasi umum, seperti "kantor" atau "sekolah". Titik sering dihubungkan oleh sisi.

Sisi dapat disebut juga edge, rusuk, ruas atau line. Sisi merupakan garis yang menghubungkan pasangan titik. Sisi dapat mewakili hubungan fisik antara lokasi, seperti jalan, atau hanya bahwa ada rute yang menghubungkan dua lokasi, seperti penerbangan maskapai.

Loop adalah jenis sisi atau garis khusus yang menghubungkan titik ke dirinya sendiri. Loop tidak banyak digunakan dalam grafik jaringan jalan.

Sisi ganda, merupakan dua atau lebih garis yang memiliki 2 ujung titik yang sama. Dalam graf tak berarah, dua atau lebih sisi yang bersinggungan dengan dua simpul yang sama, atau dalam graf berarah, dua atau lebih sisi dengan kedua simpul ekor yang sama dan simpul kepala yang sama.

Adjacent (terhubung/bertetangga), dua titik dikatakan bertetangga, jika terdapat sisi atau garis yang menghubungkan kedua titik tersebut. Di sini, kedekatan simpul dipertahankan oleh sisi tunggal yang menghubungkan kedua simpul tersebut. Dalam suatu graf, dua sisi dikatakan bertetangga, jika terdapat sebuah titik persekutuan di antara kedua sisi tersebut. Titik dengan loop "melihat" dirinya sebagai titik yang berdekatan dari kedua ujung sisi sehingga menambahkan dua, bukan satu ke derajat.

Incident (bersisian), sebuah titik bersisian dengan suatu sisi jika titik tersebut adalah salah satu dari dua titik yang dihubungkan oleh sisi tersebut. Insidence adalah pasanga simpul dan merupakan titik tepi.

Isolated vertex (Titik terisolasi) adalah titik yang tidak memiliki sisi atau garis yang menghubungkan titik tersebut dengan titik lainnya.

Lintasan atau Path merupakan rute di sepanjang tepi graf. Sebuah jalur dapat mengikuti satu sisi secara langsung di antara dua titik, atau mungkin mengikuti beberapa sisi melalui beberapa titik.

Orde atau order suatu graph adalah jumlah simpul atau titik dalam graf tersebut (Orde=n[V(G)]).

Ukuran atau size suatu graph adalah jumlah sisi dalam graf tersebut (Size=n[E(G)]).

Definisi Subgraf

Misalkan G=(V,E) dan H=(W,F) graf. H dikatakan subgraph dari G jika W⊆V dan F⊆E.

Subgraf adalah Graf yang titik dan sisinya merupakan himpunan bagian dari graf lain. Subgraph bisa didapatkan dengan menghapus sisi atau titik pada suatu graf.

Sebuah subgraf dapat dibentuk dengan menghapus sisi atau sebuah sub himpunan dari E(G). Subgraf juga didapat dengan menghapus titik atau sub himpunan dari V(G) dengan menghapus juga sisi yang bersisian (incident) dengan titik yang dihapus.

Komplemen Graf

Komplemen atau invers dari graf G adalah graf H dimana graf H memiliki simpul-simpul yang sama dengan graf G sehingga dua simpul berbeda dari H bertetangga jika dan hanya jika keduanya tidak bertetangga di G.

Misalkan suatu graf lengkap memiliki titik anggota himpunan V sisi yang merupakan anggota himpunan E. Misalkan G adalah graf dengan titik himpunan V dan sisi yang anggota E1 dimana E1 adalah sub himpunan dari E. Misalkan juga graf H memiliki titik himpunan V dan sisi E2 merupakan subhimpunan E dimana E2=E-E1. Graf H disebut komplemen atau inverst graf G.

Komplemen subgraf dari graf G adalah graf yang diperoleh dari G dengan menghapus semua sisi yang ada pada subgraf.