Phenquestions
Sebuah simpul dalam graf disebut simpul (jamak - simpul). Kadang-kadang masih disebut simpul; itu juga bisa disebut titik. Tautan dalam graf disebut sisi. Kadang-kadang masih disebut tautan; itu juga bisa disebut garis.
Grafik dengan banyak Fitur
Angka 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.
Tepi
Tepi adalah koneksi (hubungan) antara dua simpul; hubungannya mungkin abstrak.
lingkaran
Loop adalah edge yang menghubungkan vertex dengan dirinya sendiri.
Tepi Panah
Pertimbangkan dua orang: Yohanes dan Petrus. Jika John meminjamkan Peter $100, dan jika John dan Peter adalah simpul, maka sisi pinjaman akan mengarah ke Peter. Jika kedua pasangan lupa bahwa Peter berutang kepada 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 masing-masing satu panah, menunjuk ke arah yang berlawanan opposite.
Titik di mana sebuah tepi menunjuk, adalah sebuah puncak kepala untuk tepi itu. Simpul dari mana sebuah tepi keluar, adalah simpul ekor.
Kejadian
Sisi menghubungkan dua simpul. 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 bukan milik 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 di mana setiap sisinya adalah 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, di mana untuk beberapa pasang simpul, ada lebih dari satu sisi. Multigraf tak berarah adalah graf yang sisi-sisinya tidak memiliki arah (bukan panah). Multigraf berarah adalah multigraf di mana setiap sisinya adalah 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 (i.e. beberapa tepi) untuk sepasang simpul juga disebut tepi 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 tanpa simpul sehingga tidak memiliki sisi.
Grafik Campuran
Graf campuran adalah graf yang beberapa sisinya berupa panah, dan yang lainnya bukan; dengan kata lain: beberapa tepi memiliki arah, dan yang lain tidak diarahkan.
Grafik tertimbang
Dimungkinkan untuk memiliki grafik di mana angka, yang dikenal sebagai bobot, ditetapkan untuk setiap sisi. 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 dari beberapa jenis, 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 inderajat dari simpul tersebut. Panah dengan satu anak panah memiliki ujung kepala dan ujung ekor. Banyaknya ekor yang terhubung ke suatu simpul adalah derajat keluar dari simpul tersebut.
Catatan: Graf dengan banyak sisi untuk pasangan simpul, di mana banyak sisinya berlawanan arah, tidak dibahas dalam tutorial ini.
Representasi Perangkat Lunak dari Grafik
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 bujur sangkar. Judul untuk baris adalah semua simpul, ditulis dalam urutan menaik. Judul kolom masih sama, ditulis dalam urutan menaik. Penghitungan baris atau kolom 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 lingkaran harus dihitung dua kali. Untuk graf berarah, setiap entri dalam matriks ketetanggaan adalah jumlah sisi yang keluar dari simpul baris dan masuk ke simpul kolom yang bersesuaian atau jumlah sisi yang keluar dari simpul kolom dan memasuki simpul baris yang bersesuaian. Pilihannya ada pada programmer. Dalam situasi ini (apa pun kasusnya), sebuah loop masih harus dihitung sekali.
Catatan: Grafik adalah diagram yang merupakan struktur data tersendiri. Matriks ketetanggaan 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 terdepan 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 rusuk yang menghubungkan simpul C dan simpul B. Entri lainnya dijelaskan dengan cara yang sama.
Jumlah entri untuk baris memberikan jumlah tepi (derajat) untuk simpul yang sesuai. Jumlah entri baris A adalah 2, artinya 2 sisi terhubung ke simpul A. Jumlah entri baris B adalah 6, artinya 6 sisi terhubung ke simpul B. Entri lainnya 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 berangkat dari titik C ke titik B. Entri lainnya dijelaskan dengan cara yang sama.
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 diarahkan ke titik A. Jumlah entri baris B adalah 2, artinya 2 sisi keluar dari simpul B. Entri lainnya 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 artinya 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) juga harus dihilangkan. 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 tepi baru antara simpul x dan simpul y jika tepi 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 menghilangkan tepi antara simpul x dan simpul y jika tepinya ada. 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 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 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 satu set kekuatan himpunan bagian untuk tepi 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 set kekuatan himpunan bagian untuk tepi dan nilainya.
Kesimpulan
Graf adalah himpunan simpul yang terhubung dengan sisi. Suatu graf dapat tidak berarah atau berarah. Tepinya mungkin tidak terarah atau terarah or. Loop mungkin ada atau tidak ada dalam grafik. Apa yang harus Anda pelajari selanjutnya adalah set, power set, dan multiset yang terkait dengan grafik. Setelah itu, Anda harus mempelajari berbagai jenis grafik, seperti grafik berorientasi, grafik reguler, grafik lengkap, grafik bipartit, grafik turnamen, grafik jaringan aliran, dll.
Chrys
Tentang Penulis
Chrysanthus Forcha
Penemu Integrasi matematika dari Prinsip Pertama dan deret terkait. Gelar Master dalam Pendidikan Teknis, yang mengkhususkan diri dalam Elektronika dan Perangkat Lunak Komputer. BSc Elektronik. Saya juga memiliki pengetahuan dan pengalaman di tingkat Magister Komputasi dan Telekomunikasi. Dari 20.000 penulis, saya adalah penulis terbaik ke-37 di devarticles.com. Saya telah bekerja di bidang ini selama lebih dari 10 tahun.
Lihat semua posting
