LODIKA DAN ALGORITMA : TEORI GRAF (rangkuman)

Selasa, 21 Februari 2017

Teori Graf (mata kuliah Logika dan algoritma) catatan kuliah

teori graf

POHON (TREE)

Didefinisikan sebagai graf terhubung yang tidak mengandung sirkuit. Karena merupakan graf terhubung,  maka pohon selalu terdapat jalur (path) yang menghubungkan setiap dua simpul dalam pohon.

HUTAN (FOREST)

Adalah graf yang tidak mengandung sirkuit,  maka pohon adalah yang terhubung.

Sehingga perlu di ingat Suata graf G disebut terhubung apabila untuk setiap dua simpul dari graf G selalu terdapat jalur yang menghubungkan kedua simpul tersebut.

SIRKUIT (CYCLE)
Adalah suatu lintasan tertutup dengan derajat setiap simpul dua.

• 》 struktur pohon adalah salah satu kasus dalam graf. penerapannya pada teori struktur data.
• 》 daun adalah titik di dalam pohon yang berderajat satu (1). titik dalam pohon yang berderajat > 1 disebut titik cabang.
• 》 suatu pohon dengan titik memiliki (n-1) garis.

POHON RENTANGAN  (SPANNING TREE)

Adalah suatu sub graf G yang mengandung semua simpul dari G dan merupakan suatu pohon.

Graf G = n simpul dan m ruas

Spanning tree =  n simpul dan n-1 ruas

Karena pohon dengan n simpul membuat (n-1) sisi maka untuk mendapat kan Spanning tree dari suatu graf terhubung G dengan n simpul dan Q sisi dilakukan dengan cara menghapus ( Q-n+1) sisi.

POHON BERAKAR ( ROOTED TREE )

Adalah pohon yang satu buah simpulnya di perlakukan adar dan sisi-sisinya di beri arah sehingga menjadi graf berarah.

Pohon berakar adalah graf berarah (digraf) T yang mempunyai dua syarat, yaitu:

• *bila arah sisi pada T diabaikan,  hasil graf tidak berarah nya merupakan sebuah pohon.
• * ada titik tunggal R.

TERMINOLOGI POHON BERAKAR

• ~ Anak (child atau children) dan orangtua (parent)
• ~ Lintasan (path)
• ~ Saudara kandung (sibling)
• ~ upa pohon ( subtree )
• ~ Derajat (digree)
• ~ Daun (leaf)
• ~ simpul dalam (internal node)
• ~ Aras (level) atau tingkat
• ~tinggi (height) atau kedalaman (depth)

PENJELASAN

Derajat setiap simpul adalah jumlah upapohon(jumlah anak)  pada simpul tersebut.
Derajat maksimum dari semua simpul merupaka derajat pohon itu sendiri.
Daun adalah simpul yang berderajat nol ( atau tidak mempunyai anak)
Simpul dalam adalah simpul yang mempunyai anak.
Arah maximum dari suatu pohon disebut tinggi atau kedalaman pohon.

POHON BINER (BINARY TREE)

• adalah pohon berakar yang setiap titiknya memilki paling banyak dua anak dan setiap anak ditunjuk sebagai anak kiri dan anak kanan.
• pada pohon biner setiap pohon mungkin memilki satu atau dua anak. Anak kiri  digambarkan di sebelah kiri dan dibawah orang tuanya,  serta anak kanan di sebelah kanan di bawah orang tuanya.
• pohon biner digunakan dalam ilmu komputer untuk mengolah data.

Sifat utama pohon biner

• jika pohon mempunyai simpul sebanyak n, maka banyak nya ruas (edge) adalah (n-1).
• mempunyai simpul khusus yang di sebut akar (root), jika simpul tersebut memiliki derajat keluar=O dan derajat masuk =0.
• mempunyai simpul yang di sebut sebagai daun C leaf, jika simpul tersebut berderajat keluar =O  dan berderajat ,
• setiap simpul mempunyai lingkaran ( level) yang dimulai dari rut yang levelnya=0 sampai dengan level n pada daun paling bawah. Simpul yang mempunyai level yang sama di sebut bersaudara (brother/sibling)
• pohon mempunyai ketinggian, kedalaman (neight) yang merupakan level tertinggi
• pohon mempunyai berat (weight) yang merupakan banyaknya daun pada pohon.

***Sekian-Semoga bermanfaat***

;-)

Labels: LOGIKA DAN ALGORITMA SEM.1

Thanks for reading LODIKA DAN ALGORITMA : TEORI GRAF (rangkuman). Please share...!