Nama : Ahmadin Falah Daniswara
Nim : 250605110064
Kelas :C
Prodi : Teknik Informatika
Graph
Dalam Matematika, grafik yakni representasi bergambar dari data apa pun secara
terorganisir. Grafik menunjukkan hubungan antara besaran variabel. Dalam teori graf,
graf mewakili himpunan objek, yang dalam beberapa hal terkait satu sama lain. Objek
pada dasarnya adalah konsep matematika, yang dinyatakan dengan simpul atau simpul
dan hubungan antara pasangan simpul, dinyatakan dengan sisi.
Jenis Jenis Grafik :
pada dasarnya grafik berdasarkan arah edge terdiri dari dua jenis, berarah dan tidak
berarah
A. Grafik Terarah
Terdiri dari sekumpulan simpul yang dihubungkan oleh sisi sisinya dimana
tiap sisi memounyai arah yang terkait dengan
B. Grafik Tak Terarah
Didefinisikan dimana himpunan node dihubungkan bersama yang semua
sifat sisinya memiliki dua arah,untuk rumusnya
Adapun jenis grafik lainya seperti :
Grafik Berdasarkan Bobot diantaranya Weighted Graph (berbobot) dan
Unweighted Graph (tak berbobot)
Rumus Berbobot :
Rumus Tak Berbobot :
Grafik Berdasarkan Struktur yakni Simple Graph,Multigraph
Complete Graph (Kn),Cycle Graph (Cn) dan Tree
Adapun Grafik yang umum digunakan diantaranya :
Tree
Pengertian :
Struktur data grafik non linier yang tak berarah terhubung yang tak memuat sirkuit
sederhana dan tersusun dari kumpulan simpul (nodes) yang saling terhubumg oleh sisi
(edges)
Ada juga istilah Hutan yaitu kumpulan pohon yang saling lepas atau grafik tidak
terhubung,tak mengandung sirkuit
Pohon Merentang yaitu pohon yang diperoleh dengan memutus sirkuit di graf
Setiap graf terhubung mempunyai paling sedikit satu pohon merentang contoh pohon
merentang pada jaringan komputer
Pohon Merentang Minimum atau spanning tree
Contoh dalam bidang informatika :
Langkah 1: ambil sisi dari graf G yang berbobot minimum, masukkan ke dalam
T.
Langkah 2: pilih sisi (u, v) yang mempunyai bobot minimum dan bersisian
dengan simpul di T, tetapi (u, v) tidak membentuk sirkuit di T. Masukkan (u, v)
ke dalam T.
Langkah 3: ulangi langkah 2 sebanyak n – 2 kali
Ciri ciri :
- Tidak ada siklus / cycle
- Terhubung , ada satu node khusus sebagai root
- Hubungan bersifat hierarkis
Jenis Jenis Tree
A. Pohon berakar ( Rooted Tree )
Ada satu node sebagai root setiap root punya 1 parent (node yang punya anak)
yang satu buah simpulnya diperlakukan sebagai akar dan sisi-sisinya diberi
arah sehingga menjadi graf berarah
Keterangan : Anak (child atau children) dan Orangtua (parent) b, c, dan d
adalah anak-anak simpul a, a adalah orangtua dari anak anak itu
Lintasan (path) :
Lintasan dari a ke j adalah a, b, e, j. Panjang lintasan dari a ke j adalah 3.
Saudara kandung (sibling)
f adalah saudara kandung e, tetapi g bukan saudara kandung e, karena orangtua
mereka berbeda
Derajat sebuah simpul adalah jumlah upapohon (atau jumlah anak) pada simpul
tersebut. Derajat a adalah 3, derajat b adalah 2, Derajat d adalah satu dan
derajat c adalah 0. Jadi, derajat yang dimaksudkan di sini adalah derajat-keluar.
Derajat maksimum dari semua simpul merupakan derajat pohon itu sendiri.
Pohon di atas berderajat 3
Daun / Leaf :
Simpul yang berderajat nol (atau tidak mempunyai anak) disebut daun. Simpul
h, i, j, f, c, l, dan m adalah daun.
Simpul dalam
Simpul yang mempunyai anak disebut simpul dalam. Simpul b, d, e, g, dan k
adalah simpul dalam.
Aras atau Tingkat :
B. Binary Tree
Pohon ini disetiap node hanya memiliki maksimal 2 anak : yaitu anak kanan
dan kiri
C. Full Binary Tree
Cirinya punya dua anak atau tidak punya anak sama seklai (leaf)
D. Complete Binary Tree / Ordered Tree
Pohon yang diisi dari kiri ke kanan , Semua level atau tingkat terisi penuh
kecuali level terakhir, sedangkan Ordered Tree
Urutan disetiap anak pohon memilitki arti ,posisi anak tidak bisa ditukar ,ini
hampir sama dengan binary tree
E. General Tree
Pohon yang umum dimana setiap node bisa punya anak berapapun dan tidak
dibatasi
F. Balanced Tree
Pohon seimbang dimana perbedaan tinggi antara subtree kiri dan kanan
berbeda 1 tingkat setiap node
G. Perfect Binary Tree
Pohon yang semua internal node punya 2 anak dan semua lear berada pada
level yang sama
H. Full k-ary Tree
Pohon dimana setiap simpul internal memiliki tepat anak k anak
k = jumlah anak per simpul internal
Simpul internal = simpul yang memiliki anak
Simpul daun (leaf node) = simpul tanpa anak
Memiliki ciri yakni ,semua simpul tidak memiliki anak (daun) bisa seimbang
bisa tidak tergantung pada level daun
I. Skewed / Degenerate Tree
Pohon biner yang setiap simpulnya memiliki satu anak ,cirinya tak ada simpul
yang memiliki 2 anak, semua anak bisa dari satu sisi kanan ataupun kiri salah
satu arah saja.