Graf Planar

Graf Planar
Presented by Kelompok 3 2A 2023

) ) ) ) ) ) ) ) )
OUR TEAM
) ) ) ) ) ) ) ) )
Andien Defani Aditya Lesamana Ayu Dewi Dwinanda Aulia
Elinda Yuniati Fajriah Dwi Lestari

Griet Greis
Definisi Graf Planar
Graph G disebut Graph Planar jika G
dapat digambar pada bidang datar
sedimikian sehingga sisi-sisinya tidak
ada yang saling berpotongan kecuali
mungkin pada titik-titik dari sisi-sisi
tersebut. Perlu di perhatikan bahwa belum tentu suatu graf yang secara kasat mata
terlihat sisi-sisinya saling berpotongan tidak planar. Graf tersebut mungkin
saja planar, karena graf tersebut dapat digambarkan kembali dengan cara
berbeda yang sisi-sisinya tidak saling berpotongan. Perhatikan graf K4.
) ) ) ) ) ) ) ) ) CONTOH GRAF PLANAR DAN TIDAK PLANAR
) ) ) ) ) ) ) ) )
Chapter 1
) ) ) ) ) ) ) ) )
) ) ) ) ) ) ) ) )
Graf Planar Graf tidak Planar
Graf Planar
Graf tidak Planar

Graf tidak Planar
Rumus Euler
Digunakan untuk menghitung jumlah
wilayah (f) pada graf planar sederhana
n - e + f = 2 atau
f=e-n+2
Dengan:
e = banyaknya sisi
n = banyaknya titik/simpul
Pada gambar disamping, e = 11, n = 7,
dan f = 6 maka 7 - 11 + 6 = 2
Contoh soal:
Misalkan suatu graf memiliki 24 buah simpul, masing-masing

simpul berderajat 4. Representasi planar dari graf tersebut
membagi bidang datar menjadi sejumlah wilayah. Berapakah
banyak wilayah yang terbentuk?
Jawaban
Diketahui:
n = jumlah simpul = 24, maka jumlah derajat seluruh simpul = 24 x 4 = 96
Menurut lemma jabat tangan,

jumlah derajat = 2 x e
sehingga,
e = jumlah derajat/2 = 96/2 = 48
Dari rumus euler, n - e + f = 2

maka, f = 2 - 24 + 48 = 26
Jadi, banyak wilayah yang terbentuk yaitu 26 buah.

ketidaksamaan Euler
pada graf planer sederhana terhubung dengan f buah wilayah, n (n≤3) buah
simpul, dan e buah sisi (e >2) (amsumsinya : setiap wilayah pada graf planer
di batasi oleh minimal 3 sisi) selalu berlaku ketidaksamaan euler:
e ≤ 3n-6
ketidaksamaan ini dapat di gunakan untuk menunjukan keplanaran

suatu graf sederhana
jika sebuah graf planar maka ia memenuhi ketidaksamaan euler,sebaliknyan

jika tidak planar maka ketidaksamaan itu tidak di penuhi.
Teorema Jordan
Kurva jordan pada suatu bidang datar (Bidang Euclid)

membagi bidang tersebut menjadi 2 bagian terpisah yaitu
bagian dalam dan bagian luar dengan kurva jordan sebagai
batasnya.
Kurva Jordan
Kurva Jordan adalah kurva tertutup sederhana (Simple closed curve).

Contoh dari kurva jordan adalah: Lingkaran, segitiga, segiempat,

jejergenjang dan semua segi-n adalalah kurva jordan.
Kurva Jordan
Jika J adalah kurva Jordan pada
bidang maka bagian dari bidang
yang tertutup oleh J disebut
interior J dan dilambangkan
dengan int J. Demikian pula bagian
dari bidang yang terletak di luar J
disebut eksterior J dan
dilambangkan dengan ext J.
Teorema Kuratowski
Sebuah graf adalah tidak planar jika dan hanya jika ia memuat
semua subgraf homomorphosis K3,3 atau K5
Apa itu K-3,3 ?
Sifat Graf Kuratowski
Kedua graf Kuratowski adalah graf teratur

Kedua graf Kuratowski adalah graf tidak-planar .
Penghapusan sisi menyebabkannya menjadi graf planar
Graf Kuratowski pertama adalah graf tidak-planar dengan
jumlah simpul minimum, dan graf Kuratowski kedua adalah
graf tidak-planar dengan jumlah sisi minimum
Contoh
Perbedaan graf planar & graf bidang
Aplikasi graf Planar
Pengaplikasian graf planar pada kehidupan nyata adalah

ketika kita membuat Intregrated circuit (IC). IC ini sendiri adalah
suatu bahan semi konduktor yang berisi gabungan dari jutaan
transistor, dioda, resistor dan kapasitor. Pada intinya IC
merupakan sebuah otak atau rangkaian utama dalam sistem
elektronika.
Lantas apa hubungannya
dengan graf planar ?
Pada perancangan IC, jalur jalur dalam rangkaiannya tidak

boleh bertabrakan atau tumpang tindih, jika terjadi
persilangan maka akan ada interferensi yang tidak diinginkan
Rangkaian yang mengalami interferensi arus akan mengalami
malfungsi. Oleh karena itu, dalam perancangan jalur IC kita
memerlukan teori graf planar agar jalur-jalur IC dapat
dihubungkan tanpa adanya persilangan antara kedua jalur.
rangkaian
planar
Question
Time

Graf Planar

Diunggah oleh

Hak Cipta:

Format Tersedia

Graf Planar

Diunggah oleh

Informasi Dokumen

Hak Cipta

Format Tersedia

Bagikan dokumen Ini

Bagikan atau Tanam Dokumen

Opsi Berbagi

Apakah menurut Anda dokumen ini bermanfaat?

Apakah konten ini tidak pantas?

Hak Cipta:

Format Tersedia

Graf Planar

Diunggah oleh

Hak Cipta:

Format Tersedia

Graf Planar

Presented by Kelompok 3 2A 2023

Andien Defani Aditya Lesamana Ayu Dewi Dwinanda Aulia

Elinda Yuniati Fajriah Dwi Lestari

Graf Planar Graf tidak Planar

Graf tidak Planar

Misalkan suatu graf memiliki 24 buah simpul, masing-masing

Menurut lemma jabat tangan,

Dari rumus euler, n - e + f = 2

Jadi, banyak wilayah yang terbentuk yaitu 26 buah.

ketidaksamaan ini dapat di gunakan untuk menunjukan keplanaran

jika sebuah graf planar maka ia memenuhi ketidaksamaan euler,sebaliknyan

Kurva jordan pada suatu bidang datar (Bidang Euclid)

Contoh dari kurva jordan adalah: Lingkaran, segitiga, segiempat,

Kedua graf Kuratowski adalah graf teratur

Pengaplikasian graf planar pada kehidupan nyata adalah

Pada perancangan IC, jalur jalur dalam rangkaiannya tidak

Anda mungkin juga menyukai