RIVANANDA-STTPLN

Graf Planar (Planar Graph) dan Graf Bidang (Plane Graph)      Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong (bersilangan) disebut graf planar, jika tidak, maka ia disebut graf tak-planar.    K4 adalah graf planar: K5 adalah graf tidak planar: Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan disebut graf bidang (plane graph). Aplikasi Graf Planar Persoalan utilitas (utility problem)    Aplikasi Graf Planar ·          Perancangan IC (Integrated Circuit) ·          Tidak boleh ada kawat-kawat di dalam ICboard yang saling bersilangan  dapat menimbulkan interferensi arus listrik  malfunction ·          Perancangan kawat memenuhi prinsip graf planar Misalkan graf sederhana planar memiliki 24 buah simpul, masing-masing simpul berderajat 4. Representasi planar dari graf tersebut membagi bidang datar menjadi sejumlah wilayah atau muka. Berapa banyak wilayah yang terbentuk? Jawaba

GRAF      Graf  (graph) adalah himpunan benda-benda yang disebut  simpul (vertex atau node) yang terhubung oleh  sisi  (edge) atau  busur  (arc). Graf trival (satu titik tampa sisi satu pun) Jenis graf antara lain : 1. Berdasarkan ada tidaknya sisi ganda     a. graf sederhana     b. graf tidak sederhana         1)graf ganda (multigraf)         2)graf semu(pseudograf) adalah graf yang mengandung gelang (loop)            graf sedrehana --> graf ganda            graf ganda -x-> graf sederhana 2. Berdasarkan orientasi arah     a. Graf tak berarah (undirect graf) adalah graf yang orientasi sisinya tidak mempunyai arah     b. Graf berarah(direct graf) adalah graf orientasi sisinya mempunyai arah         sisi yang berarah Terminologi dasar ----------------------------- 1. Bertetangga (adjacent) adalah 2 buah graf yang terhubung langsung dengan sebuah sisi. 2. Bersisian (insident) adalah sembarang sisi yang bersisian dengan simpul u dan v 3. Simpul terpencil (isol

Definisi Pohon dan Hutan   Pohon (tree) telah digunakan sejak tahun 1857 oleh matematikawan Inggris yang bernama Arthur Cayley untuk menghitung jumlah senyawa kimia.Silsilah keluarga biasanya juga digambarkan pasa bentuk pohon. Pohon (tree) adalah merupakan graf yang tak berarah terhubung yang tidak memuat sirkuit sederhana. D iagram pohon dapat digunakan sebagai alat untuk memecahkan masalah dengan menggambarkan semua alternative    pemecahan. Jadi, dapat disimpulkan bahwa pohon adalah suatu graph yang banyak vertexnya sama dengan n (n>1), jika : ~  Graph tersebut tidak mempunyai lingkar (cycle free) dan banyaknya rusuk (n-1). ~ Graph tersebut terhubung . Contoh   :   Berikut   adalah   beberapa   sifat   pohon   : 1. Misalkan  G   merupakan   suatu   graf   dengan   n   buah   simpul   dan   tepat   n   –   1   buah   sisi. 2. Jika   G   tidak   mempunyai   sirkuit   maka   G   merupakan   pohon. 3. Suatu   pohon   dengan   n  buah   simpul   mempunyai   n

ALJABAR BOOLEAN 1.1 Definisi Aljabar Boolean Misalkan B adalah himpunan yang didefinisikan pada dua operator biner, + dan  × , dan sebuah operator uner, ’. Misalkan 0 dan 1 adalah dua elemen yang berbeda dari B. Maka, tupel <B,+, ., ‘,0,1> disebut aljabar Boolean jika untuk setiap a, b, c  Î  B berlaku aksioma berikut: 1. Identitas (i)   a + 0 = a (ii) a  ×  1 = a 2. Komutatif (i) a + b = b + a (ii) a  ×  b = b . a 3. Distributif (i)   a  ×  (b + c) = (a  ×  b) + (a  ×  c) (ii) a + (b  ×  c) = (a + b)  ×  (a + c) 4. Komplemen Untuk setiap a  Î  B terdapat elemen unik a‘ Î  B sehingga (i)   a + a’ = 1 (ii) a  ×  a’ = 0 1.2 Aljabar Boolean Dua-Nilai ·          Merupakan aljabar Boolean yang paling popular, karena aplikasinya luas. ·          Pada aljabar 2-nilai: (i) B = {0, 1}, (ii) operator biner: + dan  × , operator uner: ’ (iii) Kaidah untuk operator biner dan operator uner: (iv) Keempat aksioma di atas dipenuhi 1.3