Dalam komputasi, graf adalah sekumpulan simpul yang dihubungkan oleh tautan. Perbedaan utama antara pohon dan graf adalah bahwa pohon memiliki satu simpul akar, sedangkan graf memiliki lebih dari satu simpul akar. Anda seharusnya sudah memiliki pengetahuan dasar tentang struktur data pohon sebelum datang ke sini, karena konsep di sana, akan digunakan di sini dengan sedikit atau tanpa penjelasan. Jika Anda tidak memiliki pengetahuan itu, maka bacalah tutorial berjudul, Tutorial Struktur Data Pohon untuk Pemula, di tautan https://linuxhint.com/tree_data_structure_tutorial_beginners/.
Simpul dalam graf disebut simpul (jamak – simpul). Kadang-kadang masih disebut simpul; itu juga bisa disebut titik. Tautan dalam graf disebut edge. Kadang-kadang masih disebut tautan; itu juga bisa disebut garis.
Grafik dengan banyak Fitur
Gambar ini menunjukkan grafik dengan banyak fitur:
Lingkaran (disk) adalah simpul. Setiap garis lurus atau garis lengkung atau lingkaran adalah tepi.
Fitur Grafik
Puncak
Titik adalah objek. Itu bisa berupa rumah; itu bisa menjadi seseorang; itu bisa menjadi kata benda abstrak; itu bisa berupa objek apa pun yang dapat Anda pikirkan.
Tepian
Tepi adalah koneksi (hubungan) antara dua simpul; koneksi mungkin abstrak.
Lingkaran
Loop adalah edge yang menghubungkan vertex dengan dirinya sendiri.
Ujung Panah
Pertimbangkan dua orang: Yohanes dan Petrus. Jika John meminjamkan Peter $100, dan jika John dan Peter adalah vertex, maka lending edge akan mengarah ke Peter. Jika kedua pasangan lupa bahwa Peter berhutang pada John, dan Peter meminjamkan John $100, maka di ujung lain dari sisi yang sama, sebuah panah akan mengarah ke John. Jika Peter meminjamkan tetapi $75 kepada John dan bukan $100, maka sisi yang berbeda akan menghubungkan Peter dengan John. Tepi kedua ini akan memiliki panah yang mengarah ke John. Dalam kasus kedua, ada dua sisi, dengan satu panah masing-masing, menunjuk ke arah yang berlawanan.
Titik di mana sebuah sisi menunjuk, adalah sebuah titik kepala untuk sisi tersebut. Simpul dari mana sebuah tepi keluar, adalah simpul ekor.
Kejadian
Sebuah edge menghubungkan dua vertex. Tepi dikatakan datang pada kedua simpul. Tepi tidak perlu memiliki panah. Kedua simpul tersebut dikenal sebagai titik akhir dari edge. Dimungkinkan untuk memiliki graf di mana sebuah simpul tidak termasuk dalam sisi mana pun, tetapi itu tidak akan dipertimbangkan dalam tutorial ini.
Grafik Tidak Berarah
Tepi bisa berupa panah, atau tidak bisa. Graf yang tidak memiliki sisi panah adalah graf tak berarah. Tepi dapat diwakili oleh garis lurus atau kurva atau loop.
Grafik yang Disutradarai
Graf yang setiap rusuknya berupa panah (arah) adalah graf berarah. Tepi panah dapat diwakili oleh garis lurus dengan panah atau kurva dengan panah atau loop dengan panah.
Tidak adanya arah pada sisi graf tak berarah, berarti setiap sisi pada graf tak berarah adalah dua arah.
Derajat sebuah Verteks
Banyaknya rusuk yang bersisian pada suatu simpul adalah derajat dari simpul tersebut. Sebuah loop memiliki dua insiden pada sebuah simpul, sehingga loop dihitung dua kali.
Orde sebuah Grafik
Orde suatu graf adalah banyaknya simpul pada graf tersebut.
Multigraf
Multigraf adalah graf, dimana untuk beberapa pasang simpul terdapat lebih dari satu sisi. Multigraf tak berarah adalah graf yang sisi-sisinya tidak memiliki arah (bukan panah). Multigraf berarah adalah multigraf yang setiap rusuknya berupa panah, dan untuk pasangan simpul yang memiliki lebih dari satu panah, satu simpul adalah ekor dari panah tersebut, dan simpul lainnya adalah kepala dari panah yang sama. Diagram berikut menunjukkan multigraf tak berarah:
Lebih dari satu sisi (yaitu sisi ganda) untuk sepasang simpul juga disebut sisi paralel.
Gemetar
Quiver adalah multigraph yang memungkinkan loop (satu atau lebih loop). Beberapa multigraf tidak mengizinkan loop.
Grafik Sederhana
Graf sederhana adalah graf yang tidak ada dua pasang simpul yang memiliki sisi ganda. Loop tidak diperbolehkan dalam grafik sederhana.
Grafik Kosong
Graf kosong adalah graf yang tidak memiliki simpul sehingga tidak memiliki sisi.
Grafik Campuran
Graf campuran adalah graf yang beberapa sisinya berupa panah, dan yang lainnya tidak; dengan kata lain: beberapa tepi memiliki arah, dan yang lain tidak diarahkan.
Grafik berbobot
Dimungkinkan untuk memiliki grafik di mana angka, yang dikenal sebagai bobot, ditetapkan untuk setiap tepi. Beberapa sisi memiliki angka yang sama, tetapi angkanya umumnya berbeda. Graf seperti ini disebut graf berbobot. Angka-angka untuk grafik tertentu dapat mewakili panjang atau biaya (harga) atau besarnya beberapa macam, tergantung pada masalahnya.
Indegree dan Outdegree
Kosakata, derajat masuk, dan derajat keluar hanya berlaku untuk grafik berarah. Grafik mungkin atau mungkin bukan multigraf. Grafik mungkin atau mungkin tidak memiliki loop.
Banyaknya anak panah yang terhubung ke sebuah simpul adalah derajat masuk dari simpul tersebut. Anak panah dengan satu anak panah memiliki ujung kepala dan ujung ekor. Jumlah ekor yang terhubung ke sebuah simpul adalah derajat keluar dari simpul tersebut.
Catatan: Graf dengan sisi ganda untuk pasangan simpul, di mana sisi ganda berada dalam arah yang berlawanan, tidak dibahas dalam tutorial ini.
Representasi Perangkat Lunak dari Grafik
Sebuah grafik dapat direpresentasikan dalam perangkat lunak seperti yang digambarkan pada diagram. Grafik juga dapat direpresentasikan dalam perangkat lunak dengan matriks matematika (array dua dimensi). Salah satu matriks tersebut disebut matriks adjacency.
Matriks Kedekatan
Matriks ketetanggaan adalah matriks persegi. Judul untuk baris adalah semua simpul, ditulis dalam urutan menaik. Judul kolom masih sama, ditulis dalam urutan menaik. Penghitungan baris atau kolom suatu matriks dimulai dari 1 dan bukan nol seperti halnya array. Saat mengidentifikasi elemen dalam matriks, nomor baris ditulis terlebih dahulu sebelum nomor kolom.
Untuk graf tak berarah, setiap entri (elemen) dalam matriks ketetanggaan adalah jumlah sisi yang menghubungkan dua simpul yang bersesuaian. Sebuah loop harus dihitung dua kali. Untuk graf berarah, setiap entri dalam matriks ketetanggaan adalah jumlah sisi yang keluar dari simpul baris dan memasuki simpul kolom yang bersesuaian atau merupakan jumlah sisi yang keluar dari simpul kolom dan memasuki simpul baris yang bersesuaian. Pilihannya adalah programmer. Dalam situasi ini (dalam kasus apapun), sebuah loop masih harus dihitung satu kali.
Catatan: Grafik adalah diagram yang merupakan struktur data tersendiri. Matriks adjacency juga merupakan struktur data dalam dirinya sendiri.
Graf Tak Berarah dan Matriks Ketetanggaan
Diagram berikut menunjukkan grafik tidak berarah dan matriks ketetanggaan yang sesuai:
Diagonal utama suatu matriks adalah diagonal dari kiri atas ke kanan bawah. Suatu matriks tak berarah simetris terhadap diagonal utama. Entri matriks untuk baris A dan kolom C adalah 1, artinya ada satu sisi yang menghubungkan simpul A dan simpul C. Entri matriks untuk baris C dan kolom B adalah 3, artinya ada 3 sisi yang menghubungkan simpul C dan simpul B. entri lain juga dijelaskan.
Jumlah entri untuk baris memberikan jumlah tepi (derajat) untuk simpul yang sesuai. Jumlah entri baris A adalah 2, artinya 2 s
isi terhubung ke simpul A. Jumlah entri baris B adalah 6, artinya 6 sisi terhubung ke simpul B. Sisa entri dijelaskan dengan cara yang sama.
Grafik Berarah dan Matriks Ketetanggaan
Diagram berikut menunjukkan grafik berarah dan matriks ketetanggaan yang sesuai:
Matriks ketetanggaan untuk graf berarah belum tentu simetris terhadap diagonal utama. Entri matriks untuk baris A dan kolom C adalah 1, artinya satu sisi keluar dari titik A ke titik C. Entri matriks untuk baris C dan kolom B adalah 3, artinya 3 sisi keluar dari titik C ke titik B. Entri lainnya sama dijelaskan.
Jumlah entri untuk kolom memberikan derajat masuk untuk simpul (kolom). Jumlah entri untuk suatu baris memberikan derajat keluar untuk simpul (baris). Jumlah entri untuk kolom A adalah 1, artinya satu sisi mengarah ke simpul A. Jumlah entri untuk baris B adalah 2, artinya 2 sisi keluar dari simpul B. Sisa entri dijelaskan dengan cara yang sama.
Operasi Grafik
Struktur data, seperti grafik, terdiri dari sekumpulan nilai data atau sekumpulan objek, ditambah hubungan antar objek, ditambah operasi (fungsi) antar objek. Hubungan dalam suatu graf ditunjukkan oleh sisi-sisinya. Untuk itu, grafik harus memiliki setidaknya operasi berikut:
berdekatan (G, x, y)
G berarti grafik. Operasi ini memverifikasi apakah sebuah edge menghubungkan vertex x dan vertex y. Nilai dan posisi entri dalam matriks menunjukkan koneksi tepi (dan jenisnya).
tetangga (G, x)
Operasi ini mengembalikan daftar semua simpul yang terhubung langsung ke simpul x. Nilai dan posisi entri dalam matriks menunjukkan koneksi tepi.
hapus_vertex(G, x)
Operasi ini menghilangkan sebuah simpul, x dari sebuah graf. Jika simpul tidak memiliki tepi, tidak ada masalah. Namun, jika simpul tersebut memiliki tautan, maka tautan (sisi) harus dihilangkan juga. Nilai dan posisi entri dalam matriks menunjukkan keberadaan simpul tertentu. Jika sebuah simpul dihilangkan, matriks harus disesuaikan kembali.
tambahkan_vertex(G, x)
Ini menambahkan simpul, x tanpa menambahkan tepi, atau mengganti simpul yang memiliki tepi tetapi telah dihapus. Nilai dan posisi entri dalam matriks menunjukkan keberadaan simpul tertentu. Jika sebuah simpul ditambahkan, matriks harus disesuaikan kembali.
tambah_tepi(G, x, y)
Operasi ini menambahkan sebuah edge baru antara vertex x dan vertex y jika edge tersebut tidak ada. Nilai dan posisi entri dalam matriks menunjukkan keberadaan tepi tertentu. Jika tepi ditambahkan, matriks harus disesuaikan kembali.
hapus_tepi(G, x, y)
Operasi ini akan menghapus tepi antara simpul x dan simpul y jika tepi ada di sana. Nilai dan posisi entri dalam matriks menunjukkan keberadaan tepi tertentu. Jika tepi dihilangkan, matriks harus disesuaikan kembali.
get_vertex_value(G, x)
Operasi ini mengembalikan nilai, v terkait dengan simpul, x. Untuk mencapai ini, Anda memerlukan himpunan bagian kekuatan untuk label titik dan nilainya.
set_vertex_value(G, x, v)
Operasi ini memberikan nilai baru, v untuk nilai yang terkait dengan simpul, x. Untuk mencapai ini, Anda memerlukan himpunan bagian kekuatan untuk label titik dan nilainya.
Beberapa grafik mengasosiasikan nilai ke tepinya juga. Grafik tersebut membutuhkan operasi tambahan berikut:
get_edge_value(G, x, y)
Operasi ini mengembalikan nilai, v terkait dengan tepi, (x, y). Untuk mencapai ini, Anda memerlukan himpunan himpunan bagian kekuatan untuk edge dan nilainya.
set_edge_value(G, x, y, v)
Operasi ini memberikan nilai baru, v untuk nilai yang terkait dengan tepi, (x, y). Untuk mencapai ini, Anda memerlukan himpunan himpunan bagian kekuatan untuk edge dan nilainya.
Kesimpulan
Graf adalah himpunan simpul yang terhubung dengan sisi. Suatu graf dapat berarah atau tidak berarah.
Chrys
Chrysanthus Forcha
Discoverer of mathematics Integration from First Principles and related series. Master’s Degree in Technical Education, specializing in Electronics and Computer Software. BSc Electronics. I also have knowledge and experience at the Master’s level in Computing and Telecommunications. Out of 20,000 writers, I was the 37th best writer at devarticles.com. I have been working in these fields for more than 10 years.
View all posts
