Memasang web service twitter pada blog kita

Pada postingan ini saya akan menjelaskan bagaimana cara untuk memasang web service (dalam hal ini jejaring sosial twitter) pada blog kita.

1. Pertama-tama, kalian login dahulu ke twitter kalian.
2. Setelah login,  pilih menu 'Settings' pada icon sudut kanan atas.

3. Pilih menu "Widgets", kemudian klik tombol "Create New".

4. Selanjutnya, pilih akun twitter yang ingin kita tampilkan di blog, kemudian atur tata letak serta tampilan web service yang akan ditampilkan nantiya, jika sudah, kita klik tombol "Create Widget".

5. Kemudian akan muncul sebuah preview web service yang nantinya akan ditampilkan di blog kita beserta script HTML yang ada dibawahnya. Langsung saja copas script tersebut.

6. Masuk ke blog, pilih menu "Tata Letak".

7. Kemudian pada menu Tata Letak, klik "Tambahkan Gadget" untuk memasang web service pada blog.

8. Lalu jendela baru akan terbuka, kemudian cari pilihan "HTML/Javascript".

9. Dan, "paste"kan script yang telah kita copy tadi ke dalam teks editor. Jika sudah, kita klik tombol "Simpan".

10. Dan web service Twitter telah terpasang pada blog kalian.

Time Published : 02.22 WIB.
Rating : 7/10.

Mengenal microdata: Cara memasang microdata pada blogspot

Setelah pada post sebelumnya saya telah menjelaskan apa itu microdata beserta syarat dan ketentuannya, sekarang pada post ini saya akan menjelaskan bagaimana cara untuk memasang microdata pada blogspot anda. Microdata yang akan saya pasang ini adalah microdata yang berisi waktu suatu postingan dibuat beserta rating postingan tersebut. Oke, langsung saja kita ke tutorialnya.

1. Pertama-tama, login ke blogger kalian.
2. Pada halaman utama, klik icon bergambar kertas dan pilih opsi 'Template'.

 3. Setelah itu klik tombol 'Edit HTML'.

4. Lalu pada editor HTML, carilah kode berikut:
      
        <b:includable id='post' var='post'>...</b:includable>

5. Klik tanda panah  yang ada di sebelah kode, dan carilah kode berikut:

       <data:post.body/>

6.  Setelah kode ditemukan, ketikan kode berikut ini:

 <div itemscope='' itemtype='http://data-vocabulary.org/Review-aggregate'>
Time Published : <span itemprop='datePublished'><

data:post.timestamp/></span> WIB. <br/>
Rating : <span itemprop='rating' itemscope='' itemtype='http://data-vocabulary.org/Rating'><span itemprop='average'>7</span>/<span itemprop='best'>10</span></span>. </div><br/>
      <div style='clear: both;'/> <!-- clear for photos floats -->
    </div>

7. Simpan, dan microdata telah selesai dibuat. Untuk mengeceknya bisa kalian lihat pada blog kalian.

Sumber Referensi:
https://www.youtube.com/watch?v=DsFv6iuP3bo
https://schema.org/

Time Published : 21.32 WIB.
Rating : 7/10.

Mengenal microdata: Syarat dan ketentuan penggunaan microdata

Di post sebelumnya saya telah menjelaskan definisi dari microdata. Pada post kali ini saya akan menjelaskan tentang syarat dan ketentuan apa saja yang diperlukan dalam penggunaan microdata.

Seperti yang telah dibahas pada post sebelumnya, microdata adalah sebuah tools pada HTML yang memudahkan pencarian suatu data secara real-time, akurat dan lengkap. Sebelum menggunakan microdata, ada syarat dan ketentuan yang diperlukan dalam menggunakan microdata yaitu:

1. Harus ada setidaknya dua atau lebih kosakata yang berbeda. Pengembang web dapat merancang sebuah kosakata kustom atau kosakata penggunaan yang tersedia di web.koleksi umumnya terdapat di dua situs yaitu http://data-vocabulary.org (utama) dan Schema.org.Kosakata microdata pada google akan memudahkan hasil pencarian.

2.Menentukan sumber kosakata microdata(misal schema.org).

3. Setiap item data harus dibungkus dengan atribut itemscope.

4. Sebuah itemscope dapat didefinisikan namespace dengan atribut itemtype


5. Sebuah itemscope juga dapat didefinisikan URI sebagai ID item datanya dengan atribut itemid.

6.  Selanjutnya untuk mendeskripsikan setiap properti data item, gunakan atribut itemprop.

Sumber Refrensi:
http://schema.org/docs/gs.html#microdata_how
http://trisnanugrohosite.blogspot.com/2012/12/microdatahtml5.html
https://budsus.wordpress.com/2013/05/08/mengenal-microdata/

Time Published : 21.31 WIB.
Rating : 7/10.

Mengenal Microdata: Apa itu microdata?

Sebelum mengenal microdata lebih dalam, ada baiknya kita tahu dulu definisi microdata yang sebenarnya. Microdata sendiri adalah sebuah tools berisi script yang  dgunakan dalam HTML yang berfungsi agar sebuah website/search engine dapat menghasilkan pencarian data yang lengkap dan akurat serta dilakukan secara real-time.

Microdata sendiri sudah digunakan oleh banyak developer-developer website terkenal seperti Google, Bing, Yahoo, IMDB dan sebagainya. Maka tak heran jika website-website tersebut banyak digunakan orang untuk melakukan pencarian suatu data.

Buat yang masih bingung bagaimana microdata itu sebenarnya, bisa lihat screenshoot dibawah ini

Sumber Referensi:
http://en.wikipedia.org/wiki/Microdata_%28HTML%29

Time Published : 21.28 WIB.
Rating : 7/10.

Contoh soal graf(Tugas matematika informatika kelompok 2)

1.      Diberikan gambar sebuah graf seperti di bawah ini.

	(a)      Tunjukkan dengan ketidaksamaan Euler bahwa graf tersebut tidak planar.                                                    (5)
	(b)      Tunjukkan dengan Teorema Kuratowski bahwa graf tersebut tidak planar.                                                  (10)

      Jawab :

(a). Dengan ketidaksamaan euler

jika menggunakan rumus ketidaksamaa euler e ≤ 3n – 6 maka akan terlihat bahwa graf memenuhi ketidaksamaan tersebut (padahal graf tidak planar)

e ≤ 3n – 6

15 ≤ 3 * 8 – 6

15 ≤ 24 – 6

15 ≤ 18

untuk menunjukkan bahwa graf tidak planar kita membuat asumsi baru bahwa setiap daerah pada graf planar dibatasi oleh paling sedikit 4 buah sisi . Dengan demikian total banyaknya sisi lebih besar atau sama dengan 4f. Tetapi karena suatu sisi berada pada batas paling banyak 2 wilayah maka total banyaknya sisi lebih kecil atau sama dengan 2e. Jadi :

2e ≤ 4f

dengan rumus euler menjadi ketidaksamaan

e ≤ 2n – 4

15 ≤ 2 * 8 – 4

15 ≤ 16 – 4

15 ≤ 12               terbukti

           

            (b). Dengan teorema kuratowski

                 dapat dibuktikan bahwa graf tersebut mengandung upagraf yang homeomorfik dengan

                        graf K_3,3 atau K₅.

                       

G

G1 adalah upagraf dari G

G2 yang isomorfik dengan G1

G2 homeomorfik dengan K5 (dengan membuang simpul A dan C yang berderajat 2)

2.      Dept. IF mempunyai 6 kelompok kerja yang setiap bulannya masing-masing selalu mengadakan rapat satu kali. Keenam kelompok kerja dengan masing-masing anggotanya adalah: K₁ = {Amir, Budi, Yanti}, K₂ = {Budi, Hasan, Tommy}, K3 = {Amir, Tommy, Yanti}, K₄ = {Hasan, Tommy, Yanti}, K₅ = {Amir, Budi}, K₆ = {Budi, Tommy, Yanti}.

Berapa banyak waktu rapat berbeda yang harus direncanakan sehingga tidak ada anggota kelompok kerja yang dijadwalkan rapat pada waktu yang sama. Gambarkan graf yang merepresentasikan persoalan ini lalu (sisi menyatakan apa, simpul menyatakan apa) tentukan jumlah waktu rapat ini.  (20)

Jawab :

Simpul          : menyatakan kelompok

Sisi                : menyatakan adanya anggota kelompok yang sama

Jika ada sisi yang menghubungkan 2 kelompok berarti kelompok tersebut tidak boleh rapat pada waktu yang sama.

Dibawah dapat dilihat gambar graf yang terbentuk. Untuk mencari jumlah minimum waktu rapat yang harus disediakan kita dapat menggunakan cara yang sama seperti mencari bilangan kromatis dari graf tersebut. Setiap warna yang berbeda mewakili satu waktu rapat yang dibutuhkan.

Bilangan kromatis graf tersebut adalah 5. maka waktu rapat yang harus disediakan adalah 5.

                  1 waktu untuk K1

                  1 waktu untuk K2

                  1 waktu untuk K3

                  1 waktu untuk K4 dan K5

1        waktu untuk K6

 

3. Disebuah pulau terdapat 10 kota, dimana kota-kota tersebut dihubungkan dengan ruas-ruas jalan. Ada dua kota yang terhubung. Ada juga yang tidak. Suatu rute yang dimulai dari suatu kota, mengunjungi tepat 8 dari 9 kota lainnya masing-masing sekali dan kembali ke kota awal dinamakan rute wisata. Tentukan ruas jalan minimal yang perlu untuk dibuat, sehingga apabila diberikan sembarang kota di pulau tersebut ada rute wisata yang tidak melewati kota tersebut.

Jawab:

graph sebuah pulau dengan 10 kota

 

Rute  wisata di mulai dari kota 1 melewati 8 kota lainya. Kecuali kota 7. Ruas jalan yang di butuhkan ada 9 ruas jalan. Antara lain:

R1  : 1-2               R4       : 4-5              R7       : 8-9

R2 : 2-3              R5       : 5-6              R8       : 9-0

R3 : 3-4              R6       : 6-8              R9       : 0-1

4. Apakah graf pada gambar di bawah mempunyai sirkuit Euler? Jelaskan! Bila jawaban saudara “Ya”, maka berikan sirkuit Euler tersebut. Lalu, tentukan dua lingkaran Hamilton berbeda pada Geraf B di bawah ini!

           

                         A                                                                     B

Jawab:

Untuk mengetahui apakah graf A di atas memiliki sirkuit Euler, kita dapat menggunakan suatu teorema yang menyatakan “Jika pseudograf G terhubung dan derajat setiap titiknya  mempunyai derajat genap, maka G mempunyai sebuah sirkuit Euler” Untuk itu kita periksa bahwa A terhubung dan derajat setiap titiknya genap. Pertama kita beri label setiap titik dan sisi pada graf A sebagai berikut:

     

                                                      A

Graf A terhubung karena terdapat sebuah lintasan dari titik x dan y jika diketahui sembarang titik x dan y. Dan jika kita periksa sebagai berikut:

a ke b lintasannya (a, e1, b) ; a ke c lintasannya (a, e1, b, e2, c) ;  a ke d lintasannya (a, e12,d) ; a ke e lintasannya (a, e11, e) ; a ke f  lintasannya (a, e11, e, e10, f) ; b ke c lintasannya (b, e2, c) ; b ke d lintasannya (b, e4, d) ; b ke e lintasannya (b, e4, d, e8,e) ; b ke f lintasannya (b, e6, f) ; c ke lintasannya (c, e7, f, e9, d) ; c ke e lintasannya (c, e5, e) ; c ke f  lintasannya (c, e7, f) ; d ke e lintasannya (d, e8, e) ; d ke f lintasannya (d, e9, f) ; e ke f lintasannya (e, e10, f) ; sehingga dengan demikian  A terhubung.

d(a) = d(b) = d(c) = d(d) = d(e) = d(f) = 4 ini artinya setiap setiap titik pada graf A berderajat genap.

Karena derajat setiap titik adalah genap, menurut teorema tersebut di atas maka A mempunyai sebuah sirkuit Euler. 

Jadi graf A di atas mempunyai  Sirkuit Euler-nya, dan sirkuit Euler-nya yaitu:

                        (c, a, b, f, c, e, a, d, e, f, d, b, c)

Untuk menunjukan lingkaran Hamilton dalam sebuah graf B maka kita beri label terlebih dahulu setiap titik pada graf B seperti yang tampak di bawah ini:

                                                      B

Berikut ini dua lingkaran Hamilton berbeda pada graf B :

(l, h, i, d, c, b, a, j, k, g, f, e, l)

dan

(i, h, g, f, e, l, b, a, j, k, c, d, i)

5. Periksalah apakah kedua graf di bawah ini planar. Berikan alasan

(A)                                                                (B)

Jawab:

Untuk memeriksa graf A planar atau tidak planar maka kita beri label terlebih dahulu setiap titik pada graf A seperti yang tampak di bawah ini:

              

                                                      (A)

Dalam pemeriksaan apakah graf A planar atau tidak planar, dapat menggunakan Teorema Kuratowski yang menyatakan, “Graf G merupakan planar jika dan hanya jika G tidak mengandung suatu graf-K sebagai subgraf dari G”. Dalam hal ini sebuah graf-K adalah graf yang didapat dari K₅ atau K_3,3 dengan melakukan subdivisi pada sisinya. Artinya dalam persoalan pemeriksaan apakah graf A planar atau tidak planar kita akan mencoba menemukan  K₅ atau K_3,3 pada graf A..

Pertama kali kita ingat bahwa titik a, c, d, e dan  f pada graf A yang telah dilabeli pada gambar di atas, masing – masing mempunyai derajat 4. Untuk itu kita coba menemukan K₅ dalam graf A, karena dalam K₅ setiap titik mempunyai derajat 4, sehingga kita akan melakukannya sebagai berikut:

Graf A kita dapat membentuknya seperti tampak dibawah ini:

                

K₅ setiap titik mempunyai derajat 4, sehingga kita dapat menghapus sisi (d, h) dan (g, h) agar semua sisi mempunyai derajat 4, tampak pada gambar dibawah ini:

Hapus sisi (d, h) dan (g, h)

                

	Reduksi Seri

 

   

Gambar 5.1.

                           K₅

Selanjutnya kita dapat melakukan reduksi seri (Definisi: Jika sebuah graf G mempunyai sebuah sisi v berderajat 2 dan sisi (v, v₁) dan (v, v₂) dengan v₁ ¹ v₂ kita katakana bahwa rusuk  Reduksi seri   (v, v₁) dan (v, v₂) berada dalam seri. Reduksi seri terdiri dari penghapusan sisi v graf G dan menggantikan sisi-sisi (v, v₁) dan (v, v₂) dengan sisi (v₁, v₂). Graf yang dihasilkan G’ dikatakan diperoleh dari G dengan sebuah reduksi seri. Berdasarkan konvensi, G dikatakan dapat diperoleh dari diri sendiri dengan sebuah reduksi seri) dan graf yang dihasilkan akan mempunyai sepuluh sisi dan karena K₅ mempunyai sepuluh sisi, pendekatan ini kelihatan dapat menjanjikan. Dengan coba-coba, akhirnya kita lihat bahwa jika kita kurangi sisi (d, h) dan (g, h) dan kita lakukan reduksi seri, kita peroleh sebuah salinan dari K₅ seperti tampak pada Gambar 5.1. di atas.

Jadi, graf A pada soal 5. ini tidak planar, karena graf tersebut mengandung sebuah subgraf yang homeomorfik pada K₅.  

Untuk memeriksa graf B planar atau tidak planar maka kita beri label terlebih dahulu setiap titik pada graf B seperti yang tampak di bawah ini:

                     

                                                         (B)

Dalam pemeriksaan apakah graf B planar atau tidak planar, dapat menggunakan sama halnya seperti apa yang dilakukan pada graf A tadi di atas menggunakan  Teorema Kuratowski. Artinya dalam persoalan pemeriksaan apakah graf B planar atau tidak planar kita akan mencoba menemukan  K₅ atau K_3,3 pada graf B.

Pertama kali kita ingat bahwa titik a, b, d, c dan  d pada graf B yang telah dilabeli pada gambar di atas, masing – masing mempunyai derajat 4. Untuk itu kita coba menemukan K_3,3 dalam graf B, karena dalam K_3,3 setiap titik mempunyai derajat 3, sehingga kita akan melakukannya sebagai berikut:

Graf B kita dapat membentuknya seperti tampak dibawah ini:

                 

                                                    (B)

K_3,3 setiap titik mempunyai derajat 3, sehingga kita dapat menghapus sisi (c, h), (e, h) dan (i, h) agar semua sisi mempunyai derajat 4, tampak pada gambar dibawah ini:

Hapus sisi (c, h), (e, h) dan (i, h)

                                  

 

Reduksi Seri

          

Gambar 5.2.

                                                                   K_3,3

Selanjutnya kita dapat melakukan reduksi seri sehingga graf yang dihasilkan akan mempunyai sembilan sisi dan karena K_3,3 mempunyai sembilan sisi, pendekatan ini kelihatan dapat menjanjikan. Dengan coba-coba, akhirnya kita lihat bahwa jika kita kurangi sisi (c, h), (e, h) dan (i, h) dan kita lakukan reduksi seri, kita peroleh sebuah salinan dari K_3,3 seperti tampak pada Gambar 5.2. di atas.

Jadi, graf B pada soal 5. ini tidak planar, karena graf tersebut mengandung sebuah subgraf yang homeomorfik pada K_3,3.   

1.      Diberikan gambar sebuah graf seperti di bawah ini.

	(a)      Tunjukkan dengan ketidaksamaan Euler bahwa graf tersebut tidak planar.                                                    (5)
	(b)      Tunjukkan dengan Teorema Kuratowski bahwa graf tersebut tidak planar.                                                  (10)

      Jawab :

(a). Dengan ketidaksamaan euler

jika menggunakan rumus ketidaksamaa euler e ≤ 3n – 6 maka akan terlihat bahwa graf memenuhi ketidaksamaan tersebut (padahal graf tidak planar)

e ≤ 3n – 6

15 ≤ 3 * 8 – 6

15 ≤ 24 – 6

15 ≤ 18

untuk menunjukkan bahwa graf tidak planar kita membuat asumsi baru bahwa setiap daerah pada graf planar dibatasi oleh paling sedikit 4 buah sisi . Dengan demikian total banyaknya sisi lebih besar atau sama dengan 4f. Tetapi karena suatu sisi berada pada batas paling banyak 2 wilayah maka total banyaknya sisi lebih kecil atau sama dengan 2e. Jadi :

2e ≤ 4f

dengan rumus euler menjadi ketidaksamaan

e ≤ 2n – 4

15 ≤ 2 * 8 – 4

15 ≤ 16 – 4

15 ≤ 12               terbukti

           

            (b). Dengan teorema kuratowski

                 dapat dibuktikan bahwa graf tersebut mengandung upagraf yang homeomorfik dengan

                        graf K_3,3 atau K₅.

                       

G

G1 adalah upagraf dari G

G2 yang isomorfik dengan G1

G2 homeomorfik dengan K5 (dengan membuang simpul A dan C yang berderajat 2)

2.      Dept. IF mempunyai 6 kelompok kerja yang setiap bulannya masing-masing selalu mengadakan rapat satu kali. Keenam kelompok kerja dengan masing-masing anggotanya adalah: K₁ = {Amir, Budi, Yanti}, K₂ = {Budi, Hasan, Tommy}, K3 = {Amir, Tommy, Yanti}, K₄ = {Hasan, Tommy, Yanti}, K₅ = {Amir, Budi}, K₆ = {Budi, Tommy, Yanti}.

Berapa banyak waktu rapat berbeda yang harus direncanakan sehingga tidak ada anggota kelompok kerja yang dijadwalkan rapat pada waktu yang sama. Gambarkan graf yang merepresentasikan persoalan ini lalu (sisi menyatakan apa, simpul menyatakan apa) tentukan jumlah waktu rapat ini.  (20)

Jawab :

Simpul          : menyatakan kelompok

Sisi                : menyatakan adanya anggota kelompok yang sama

Jika ada sisi yang menghubungkan 2 kelompok berarti kelompok tersebut tidak boleh rapat pada waktu yang sama.

Dibawah dapat dilihat gambar graf yang terbentuk. Untuk mencari jumlah minimum waktu rapat yang harus disediakan kita dapat menggunakan cara yang sama seperti mencari bilangan kromatis dari graf tersebut. Setiap warna yang berbeda mewakili satu waktu rapat yang dibutuhkan.

Bilangan kromatis graf tersebut adalah 5. maka waktu rapat yang harus disediakan adalah 5.

                  1 waktu untuk K1

                  1 waktu untuk K2

                  1 waktu untuk K3

                  1 waktu untuk K4 dan K5

1        waktu untuk K6

 

3. Disebuah pulau terdapat 10 kota, dimana kota-kota tersebut dihubungkan dengan ruas-ruas jalan. Ada dua kota yang terhubung. Ada juga yang tidak. Suatu rute yang dimulai dari suatu kota, mengunjungi tepat 8 dari 9 kota lainnya masing-masing sekali dan kembali ke kota awal dinamakan rute wisata. Tentukan ruas jalan minimal yang perlu untuk dibuat, sehingga apabila diberikan sembarang kota di pulau tersebut ada rute wisata yang tidak melewati kota tersebut.

Jawab:

graph sebuah pulau dengan 10 kota

 

Rute  wisata di mulai dari kota 1 melewati 8 kota lainya. Kecuali kota 7. Ruas jalan yang di butuhkan ada 9 ruas jalan. Antara lain:

R1  : 1-2               R4       : 4-5              R7       : 8-9

R2 : 2-3              R5       : 5-6              R8       : 9-0

R3 : 3-4              R6       : 6-8              R9       : 0-1

4. Apakah graf pada gambar di bawah mempunyai sirkuit Euler? Jelaskan! Bila jawaban saudara “Ya”, maka berikan sirkuit Euler tersebut. Lalu, tentukan dua lingkaran Hamilton berbeda pada Geraf B di bawah ini!

           

                         A                                                                     B

Jawab:

Untuk mengetahui apakah graf A di atas memiliki sirkuit Euler, kita dapat menggunakan suatu teorema yang menyatakan “Jika pseudograf G terhubung dan derajat setiap titiknya  mempunyai derajat genap, maka G mempunyai sebuah sirkuit Euler” Untuk itu kita periksa bahwa A terhubung dan derajat setiap titiknya genap. Pertama kita beri label setiap titik dan sisi pada graf A sebagai berikut:

     

                                                      A

Graf A terhubung karena terdapat sebuah lintasan dari titik x dan y jika diketahui sembarang titik x dan y. Dan jika kita periksa sebagai berikut:

a ke b lintasannya (a, e1, b) ; a ke c lintasannya (a, e1, b, e2, c) ;  a ke d lintasannya (a, e12,d) ; a ke e lintasannya (a, e11, e) ; a ke f  lintasannya (a, e11, e, e10, f) ; b ke c lintasannya (b, e2, c) ; b ke d lintasannya (b, e4, d) ; b ke e lintasannya (b, e4, d, e8,e) ; b ke f lintasannya (b, e6, f) ; c ke lintasannya (c, e7, f, e9, d) ; c ke e lintasannya (c, e5, e) ; c ke f  lintasannya (c, e7, f) ; d ke e lintasannya (d, e8, e) ; d ke f lintasannya (d, e9, f) ; e ke f lintasannya (e, e10, f) ; sehingga dengan demikian  A terhubung.

d(a) = d(b) = d(c) = d(d) = d(e) = d(f) = 4 ini artinya setiap setiap titik pada graf A berderajat genap.

Karena derajat setiap titik adalah genap, menurut teorema tersebut di atas maka A mempunyai sebuah sirkuit Euler. 

Jadi graf A di atas mempunyai  Sirkuit Euler-nya, dan sirkuit Euler-nya yaitu:

                        (c, a, b, f, c, e, a, d, e, f, d, b, c)

Untuk menunjukan lingkaran Hamilton dalam sebuah graf B maka kita beri label terlebih dahulu setiap titik pada graf B seperti yang tampak di bawah ini:

                                                      B

Berikut ini dua lingkaran Hamilton berbeda pada graf B :

(l, h, i, d, c, b, a, j, k, g, f, e, l)

dan

(i, h, g, f, e, l, b, a, j, k, c, d, i)

5. Periksalah apakah kedua graf di bawah ini planar. Berikan alasan

(A)                                                                (B)

Jawab:

Untuk memeriksa graf A planar atau tidak planar maka kita beri label terlebih dahulu setiap titik pada graf A seperti yang tampak di bawah ini:

              

                                                      (A)

Dalam pemeriksaan apakah graf A planar atau tidak planar, dapat menggunakan Teorema Kuratowski yang menyatakan, “Graf G merupakan planar jika dan hanya jika G tidak mengandung suatu graf-K sebagai subgraf dari G”. Dalam hal ini sebuah graf-K adalah graf yang didapat dari K₅ atau K_3,3 dengan melakukan subdivisi pada sisinya. Artinya dalam persoalan pemeriksaan apakah graf A planar atau tidak planar kita akan mencoba menemukan  K₅ atau K_3,3 pada graf A..

Pertama kali kita ingat bahwa titik a, c, d, e dan  f pada graf A yang telah dilabeli pada gambar di atas, masing – masing mempunyai derajat 4. Untuk itu kita coba menemukan K₅ dalam graf A, karena dalam K₅ setiap titik mempunyai derajat 4, sehingga kita akan melakukannya sebagai berikut:

Graf A kita dapat membentuknya seperti tampak dibawah ini:

                

K₅ setiap titik mempunyai derajat 4, sehingga kita dapat menghapus sisi (d, h) dan (g, h) agar semua sisi mempunyai derajat 4, tampak pada gambar dibawah ini:

Hapus sisi (d, h) dan (g, h)

                

	Reduksi Seri

 

   

Gambar 5.1.

                           K₅

Selanjutnya kita dapat melakukan reduksi seri (Definisi: Jika sebuah graf G mempunyai sebuah sisi v berderajat 2 dan sisi (v, v₁) dan (v, v₂) dengan v₁ ¹ v₂ kita katakana bahwa rusuk  Reduksi seri   (v, v₁) dan (v, v₂) berada dalam seri. Reduksi seri terdiri dari penghapusan sisi v graf G dan menggantikan sisi-sisi (v, v₁) dan (v, v₂) dengan sisi (v₁, v₂). Graf yang dihasilkan G’ dikatakan diperoleh dari G dengan sebuah reduksi seri. Berdasarkan konvensi, G dikatakan dapat diperoleh dari diri sendiri dengan sebuah reduksi seri) dan graf yang dihasilkan akan mempunyai sepuluh sisi dan karena K₅ mempunyai sepuluh sisi, pendekatan ini kelihatan dapat menjanjikan. Dengan coba-coba, akhirnya kita lihat bahwa jika kita kurangi sisi (d, h) dan (g, h) dan kita lakukan reduksi seri, kita peroleh sebuah salinan dari K₅ seperti tampak pada Gambar 5.1. di atas.

Jadi, graf A pada soal 5. ini tidak planar, karena graf tersebut mengandung sebuah subgraf yang homeomorfik pada K₅.  

Untuk memeriksa graf B planar atau tidak planar maka kita beri label terlebih dahulu setiap titik pada graf B seperti yang tampak di bawah ini:

                     

                                                         (B)

Dalam pemeriksaan apakah graf B planar atau tidak planar, dapat menggunakan sama halnya seperti apa yang dilakukan pada graf A tadi di atas menggunakan  Teorema Kuratowski. Artinya dalam persoalan pemeriksaan apakah graf B planar atau tidak planar kita akan mencoba menemukan  K₅ atau K_3,3 pada graf B.

Pertama kali kita ingat bahwa titik a, b, d, c dan  d pada graf B yang telah dilabeli pada gambar di atas, masing – masing mempunyai derajat 4. Untuk itu kita coba menemukan K_3,3 dalam graf B, karena dalam K_3,3 setiap titik mempunyai derajat 3, sehingga kita akan melakukannya sebagai berikut:

Graf B kita dapat membentuknya seperti tampak dibawah ini:

                 

                                                    (B)

K_3,3 setiap titik mempunyai derajat 3, sehingga kita dapat menghapus sisi (c, h), (e, h) dan (i, h) agar semua sisi mempunyai derajat 4, tampak pada gambar dibawah ini:

Hapus sisi (c, h), (e, h) dan (i, h)

                                  

 

Reduksi Seri

          

Gambar 5.2.

                                                                   K_3,3

Selanjutnya kita dapat melakukan reduksi seri sehingga graf yang dihasilkan akan mempunyai sembilan sisi dan karena K_3,3 mempunyai sembilan sisi, pendekatan ini kelihatan dapat menjanjikan. Dengan coba-coba, akhirnya kita lihat bahwa jika kita kurangi sisi (c, h), (e, h) dan (i, h) dan kita lakukan reduksi seri, kita peroleh sebuah salinan dari K_3,3 seperti tampak pada Gambar 5.2. di atas.

Jadi, graf B pada soal 5. ini tidak planar, karena graf tersebut mengandung sebuah subgraf yang homeomorfik pada K_3,3.   

1.      Diberikan gambar sebuah graf seperti di bawah ini.

	(a)      Tunjukkan dengan ketidaksamaan Euler bahwa graf tersebut tidak planar.                                                    (5)
	(b)      Tunjukkan dengan Teorema Kuratowski bahwa graf tersebut tidak planar.                                                  (10)

      Jawab :

(a). Dengan ketidaksamaan euler

jika menggunakan rumus ketidaksamaa euler e ≤ 3n – 6 maka akan terlihat bahwa graf memenuhi ketidaksamaan tersebut (padahal graf tidak planar)

e ≤ 3n – 6

15 ≤ 3 * 8 – 6

15 ≤ 24 – 6

15 ≤ 18

untuk menunjukkan bahwa graf tidak planar kita membuat asumsi baru bahwa setiap daerah pada graf planar dibatasi oleh paling sedikit 4 buah sisi . Dengan demikian total banyaknya sisi lebih besar atau sama dengan 4f. Tetapi karena suatu sisi berada pada batas paling banyak 2 wilayah maka total banyaknya sisi lebih kecil atau sama dengan 2e. Jadi :

2e ≤ 4f

dengan rumus euler menjadi ketidaksamaan

e ≤ 2n – 4

15 ≤ 2 * 8 – 4

15 ≤ 16 – 4

15 ≤ 12               terbukti

           

            (b). Dengan teorema kuratowski

                 dapat dibuktikan bahwa graf tersebut mengandung upagraf yang homeomorfik dengan

                        graf K_3,3 atau K₅.

                       

G

G1 adalah upagraf dari G

G2 yang isomorfik dengan G1

G2 homeomorfik dengan K5 (dengan membuang simpul A dan C yang berderajat 2)

2.      Dept. IF mempunyai 6 kelompok kerja yang setiap bulannya masing-masing selalu mengadakan rapat satu kali. Keenam kelompok kerja dengan masing-masing anggotanya adalah: K₁ = {Amir, Budi, Yanti}, K₂ = {Budi, Hasan, Tommy}, K3 = {Amir, Tommy, Yanti}, K₄ = {Hasan, Tommy, Yanti}, K₅ = {Amir, Budi}, K₆ = {Budi, Tommy, Yanti}.

Berapa banyak waktu rapat berbeda yang harus direncanakan sehingga tidak ada anggota kelompok kerja yang dijadwalkan rapat pada waktu yang sama. Gambarkan graf yang merepresentasikan persoalan ini lalu (sisi menyatakan apa, simpul menyatakan apa) tentukan jumlah waktu rapat ini.  (20)

Jawab :

Simpul          : menyatakan kelompok

Sisi                : menyatakan adanya anggota kelompok yang sama

Jika ada sisi yang menghubungkan 2 kelompok berarti kelompok tersebut tidak boleh rapat pada waktu yang sama.

Dibawah dapat dilihat gambar graf yang terbentuk. Untuk mencari jumlah minimum waktu rapat yang harus disediakan kita dapat menggunakan cara yang sama seperti mencari bilangan kromatis dari graf tersebut. Setiap warna yang berbeda mewakili satu waktu rapat yang dibutuhkan.

Bilangan kromatis graf tersebut adalah 5. maka waktu rapat yang harus disediakan adalah 5.

                  1 waktu untuk K1

                  1 waktu untuk K2

                  1 waktu untuk K3

                  1 waktu untuk K4 dan K5

1        waktu untuk K6

 

3. Disebuah pulau terdapat 10 kota, dimana kota-kota tersebut dihubungkan dengan ruas-ruas jalan. Ada dua kota yang terhubung. Ada juga yang tidak. Suatu rute yang dimulai dari suatu kota, mengunjungi tepat 8 dari 9 kota lainnya masing-masing sekali dan kembali ke kota awal dinamakan rute wisata. Tentukan ruas jalan minimal yang perlu untuk dibuat, sehingga apabila diberikan sembarang kota di pulau tersebut ada rute wisata yang tidak melewati kota tersebut.

Jawab:

graph sebuah pulau dengan 10 kota

 

Rute  wisata di mulai dari kota 1 melewati 8 kota lainya. Kecuali kota 7. Ruas jalan yang di butuhkan ada 9 ruas jalan. Antara lain:

R1  : 1-2               R4       : 4-5              R7       : 8-9

R2 : 2-3              R5       : 5-6              R8       : 9-0

R3 : 3-4              R6       : 6-8              R9       : 0-1

4. Apakah graf pada gambar di bawah mempunyai sirkuit Euler? Jelaskan! Bila jawaban saudara “Ya”, maka berikan sirkuit Euler tersebut. Lalu, tentukan dua lingkaran Hamilton berbeda pada Geraf B di bawah ini!

           

                         A                                                                     B

Jawab:

Untuk mengetahui apakah graf A di atas memiliki sirkuit Euler, kita dapat menggunakan suatu teorema yang menyatakan “Jika pseudograf G terhubung dan derajat setiap titiknya  mempunyai derajat genap, maka G mempunyai sebuah sirkuit Euler” Untuk itu kita periksa bahwa A terhubung dan derajat setiap titiknya genap. Pertama kita beri label setiap titik dan sisi pada graf A sebagai berikut:

     

                                                      A

Graf A terhubung karena terdapat sebuah lintasan dari titik x dan y jika diketahui sembarang titik x dan y. Dan jika kita periksa sebagai berikut:

a ke b lintasannya (a, e1, b) ; a ke c lintasannya (a, e1, b, e2, c) ;  a ke d lintasannya (a, e12,d) ; a ke e lintasannya (a, e11, e) ; a ke f  lintasannya (a, e11, e, e10, f) ; b ke c lintasannya (b, e2, c) ; b ke d lintasannya (b, e4, d) ; b ke e lintasannya (b, e4, d, e8,e) ; b ke f lintasannya (b, e6, f) ; c ke lintasannya (c, e7, f, e9, d) ; c ke e lintasannya (c, e5, e) ; c ke f  lintasannya (c, e7, f) ; d ke e lintasannya (d, e8, e) ; d ke f lintasannya (d, e9, f) ; e ke f lintasannya (e, e10, f) ; sehingga dengan demikian  A terhubung.

d(a) = d(b) = d(c) = d(d) = d(e) = d(f) = 4 ini artinya setiap setiap titik pada graf A berderajat genap.

Karena derajat setiap titik adalah genap, menurut teorema tersebut di atas maka A mempunyai sebuah sirkuit Euler. 

Jadi graf A di atas mempunyai  Sirkuit Euler-nya, dan sirkuit Euler-nya yaitu:

                        (c, a, b, f, c, e, a, d, e, f, d, b, c)

Untuk menunjukan lingkaran Hamilton dalam sebuah graf B maka kita beri label terlebih dahulu setiap titik pada graf B seperti yang tampak di bawah ini:

                                                      B

Berikut ini dua lingkaran Hamilton berbeda pada graf B :

(l, h, i, d, c, b, a, j, k, g, f, e, l)

dan

(i, h, g, f, e, l, b, a, j, k, c, d, i)

5. Periksalah apakah kedua graf di bawah ini planar. Berikan alasan

(A)                                                                (B)

Jawab:

Untuk memeriksa graf A planar atau tidak planar maka kita beri label terlebih dahulu setiap titik pada graf A seperti yang tampak di bawah ini:

              

                                                      (A)

Dalam pemeriksaan apakah graf A planar atau tidak planar, dapat menggunakan Teorema Kuratowski yang menyatakan, “Graf G merupakan planar jika dan hanya jika G tidak mengandung suatu graf-K sebagai subgraf dari G”. Dalam hal ini sebuah graf-K adalah graf yang didapat dari K₅ atau K_3,3 dengan melakukan subdivisi pada sisinya. Artinya dalam persoalan pemeriksaan apakah graf A planar atau tidak planar kita akan mencoba menemukan  K₅ atau K_3,3 pada graf A..

Pertama kali kita ingat bahwa titik a, c, d, e dan  f pada graf A yang telah dilabeli pada gambar di atas, masing – masing mempunyai derajat 4. Untuk itu kita coba menemukan K₅ dalam graf A, karena dalam K₅ setiap titik mempunyai derajat 4, sehingga kita akan melakukannya sebagai berikut:

Graf A kita dapat membentuknya seperti tampak dibawah ini:

                

K₅ setiap titik mempunyai derajat 4, sehingga kita dapat menghapus sisi (d, h) dan (g, h) agar semua sisi mempunyai derajat 4, tampak pada gambar dibawah ini:

Hapus sisi (d, h) dan (g, h)

                

	Reduksi Seri

 

   

Gambar 5.1.

                           K₅

Selanjutnya kita dapat melakukan reduksi seri (Definisi: Jika sebuah graf G mempunyai sebuah sisi v berderajat 2 dan sisi (v, v₁) dan (v, v₂) dengan v₁ ¹ v₂ kita katakana bahwa rusuk  Reduksi seri   (v, v₁) dan (v, v₂) berada dalam seri. Reduksi seri terdiri dari penghapusan sisi v graf G dan menggantikan sisi-sisi (v, v₁) dan (v, v₂) dengan sisi (v₁, v₂). Graf yang dihasilkan G’ dikatakan diperoleh dari G dengan sebuah reduksi seri. Berdasarkan konvensi, G dikatakan dapat diperoleh dari diri sendiri dengan sebuah reduksi seri) dan graf yang dihasilkan akan mempunyai sepuluh sisi dan karena K₅ mempunyai sepuluh sisi, pendekatan ini kelihatan dapat menjanjikan. Dengan coba-coba, akhirnya kita lihat bahwa jika kita kurangi sisi (d, h) dan (g, h) dan kita lakukan reduksi seri, kita peroleh sebuah salinan dari K₅ seperti tampak pada Gambar 5.1. di atas.

Jadi, graf A pada soal 5. ini tidak planar, karena graf tersebut mengandung sebuah subgraf yang homeomorfik pada K₅.  

Untuk memeriksa graf B planar atau tidak planar maka kita beri label terlebih dahulu setiap titik pada graf B seperti yang tampak di bawah ini:

                     

                                                         (B)

Dalam pemeriksaan apakah graf B planar atau tidak planar, dapat menggunakan sama halnya seperti apa yang dilakukan pada graf A tadi di atas menggunakan  Teorema Kuratowski. Artinya dalam persoalan pemeriksaan apakah graf B planar atau tidak planar kita akan mencoba menemukan  K₅ atau K_3,3 pada graf B.

Pertama kali kita ingat bahwa titik a, b, d, c dan  d pada graf B yang telah dilabeli pada gambar di atas, masing – masing mempunyai derajat 4. Untuk itu kita coba menemukan K_3,3 dalam graf B, karena dalam K_3,3 setiap titik mempunyai derajat 3, sehingga kita akan melakukannya sebagai berikut:

Graf B kita dapat membentuknya seperti tampak dibawah ini:

                 

                                                    (B)

K_3,3 setiap titik mempunyai derajat 3, sehingga kita dapat menghapus sisi (c, h), (e, h) dan (i, h) agar semua sisi mempunyai derajat 4, tampak pada gambar dibawah ini:

Hapus sisi (c, h), (e, h) dan (i, h)

                                  

 

Reduksi Seri

          

Gambar 5.2.

                                                                   K_3,3

Selanjutnya kita dapat melakukan reduksi seri sehingga graf yang dihasilkan akan mempunyai sembilan sisi dan karena K_3,3 mempunyai sembilan sisi, pendekatan ini kelihatan dapat menjanjikan. Dengan coba-coba, akhirnya kita lihat bahwa jika kita kurangi sisi (c, h), (e, h) dan (i, h) dan kita lakukan reduksi seri, kita peroleh sebuah salinan dari K_3,3 seperti tampak pada Gambar 5.2. di atas.

Jadi, graf B pada soal 5. ini tidak planar, karena graf tersebut mengandung sebuah subgraf yang homeomorfik pada K_3,3.   

1.      Diberikan gambar sebuah graf seperti di bawah ini.

	(a)      Tunjukkan dengan ketidaksamaan Euler bahwa graf tersebut tidak planar.                                                    (5)
	(b)      Tunjukkan dengan Teorema Kuratowski bahwa graf tersebut tidak planar.                                                  (10)

      Jawab :

(a). Dengan ketidaksamaan euler

jika menggunakan rumus ketidaksamaa euler e ≤ 3n – 6 maka akan terlihat bahwa graf memenuhi ketidaksamaan tersebut (padahal graf tidak planar)

e ≤ 3n – 6

15 ≤ 3 * 8 – 6

15 ≤ 24 – 6

15 ≤ 18

untuk menunjukkan bahwa graf tidak planar kita membuat asumsi baru bahwa setiap daerah pada graf planar dibatasi oleh paling sedikit 4 buah sisi . Dengan demikian total banyaknya sisi lebih besar atau sama dengan 4f. Tetapi karena suatu sisi berada pada batas paling banyak 2 wilayah maka total banyaknya sisi lebih kecil atau sama dengan 2e. Jadi :

2e ≤ 4f

dengan rumus euler menjadi ketidaksamaan

e ≤ 2n – 4

15 ≤ 2 * 8 – 4

15 ≤ 16 – 4

15 ≤ 12               terbukti

           

            (b). Dengan teorema kuratowski

                 dapat dibuktikan bahwa graf tersebut mengandung upagraf yang homeomorfik dengan

                        graf K_3,3 atau K₅.

                       

G

G1 adalah upagraf dari G

G2 yang isomorfik dengan G1

G2 homeomorfik dengan K5 (dengan membuang simpul A dan C yang berderajat 2)

2.      Dept. IF mempunyai 6 kelompok kerja yang setiap bulannya masing-masing selalu mengadakan rapat satu kali. Keenam kelompok kerja dengan masing-masing anggotanya adalah: K₁ = {Amir, Budi, Yanti}, K₂ = {Budi, Hasan, Tommy}, K3 = {Amir, Tommy, Yanti}, K₄ = {Hasan, Tommy, Yanti}, K₅ = {Amir, Budi}, K₆ = {Budi, Tommy, Yanti}.

Berapa banyak waktu rapat berbeda yang harus direncanakan sehingga tidak ada anggota kelompok kerja yang dijadwalkan rapat pada waktu yang sama. Gambarkan graf yang merepresentasikan persoalan ini lalu (sisi menyatakan apa, simpul menyatakan apa) tentukan jumlah waktu rapat ini.  (20)

Jawab :

Simpul          : menyatakan kelompok

Sisi                : menyatakan adanya anggota kelompok yang sama

Jika ada sisi yang menghubungkan 2 kelompok berarti kelompok tersebut tidak boleh rapat pada waktu yang sama.

Dibawah dapat dilihat gambar graf yang terbentuk. Untuk mencari jumlah minimum waktu rapat yang harus disediakan kita dapat menggunakan cara yang sama seperti mencari bilangan kromatis dari graf tersebut. Setiap warna yang berbeda mewakili satu waktu rapat yang dibutuhkan.

Bilangan kromatis graf tersebut adalah 5. maka waktu rapat yang harus disediakan adalah 5.

                  1 waktu untuk K1

                  1 waktu untuk K2

                  1 waktu untuk K3

                  1 waktu untuk K4 dan K5

1        waktu untuk K6

 

3. Disebuah pulau terdapat 10 kota, dimana kota-kota tersebut dihubungkan dengan ruas-ruas jalan. Ada dua kota yang terhubung. Ada juga yang tidak. Suatu rute yang dimulai dari suatu kota, mengunjungi tepat 8 dari 9 kota lainnya masing-masing sekali dan kembali ke kota awal dinamakan rute wisata. Tentukan ruas jalan minimal yang perlu untuk dibuat, sehingga apabila diberikan sembarang kota di pulau tersebut ada rute wisata yang tidak melewati kota tersebut.

Jawab:

graph sebuah pulau dengan 10 kota

 

Rute  wisata di mulai dari kota 1 melewati 8 kota lainya. Kecuali kota 7. Ruas jalan yang di butuhkan ada 9 ruas jalan. Antara lain:

R1  : 1-2               R4       : 4-5              R7       : 8-9

R2 : 2-3              R5       : 5-6              R8       : 9-0

R3 : 3-4              R6       : 6-8              R9       : 0-1

4. Apakah graf pada gambar di bawah mempunyai sirkuit Euler? Jelaskan! Bila jawaban saudara “Ya”, maka berikan sirkuit Euler tersebut. Lalu, tentukan dua lingkaran Hamilton berbeda pada Geraf B di bawah ini!

           

                         A                                                                     B

Jawab:

Untuk mengetahui apakah graf A di atas memiliki sirkuit Euler, kita dapat menggunakan suatu teorema yang menyatakan “Jika pseudograf G terhubung dan derajat setiap titiknya  mempunyai derajat genap, maka G mempunyai sebuah sirkuit Euler” Untuk itu kita periksa bahwa A terhubung dan derajat setiap titiknya genap. Pertama kita beri label setiap titik dan sisi pada graf A sebagai berikut:

     

                                                      A

Graf A terhubung karena terdapat sebuah lintasan dari titik x dan y jika diketahui sembarang titik x dan y. Dan jika kita periksa sebagai berikut:

a ke b lintasannya (a, e1, b) ; a ke c lintasannya (a, e1, b, e2, c) ;  a ke d lintasannya (a, e12,d) ; a ke e lintasannya (a, e11, e) ; a ke f  lintasannya (a, e11, e, e10, f) ; b ke c lintasannya (b, e2, c) ; b ke d lintasannya (b, e4, d) ; b ke e lintasannya (b, e4, d, e8,e) ; b ke f lintasannya (b, e6, f) ; c ke lintasannya (c, e7, f, e9, d) ; c ke e lintasannya (c, e5, e) ; c ke f  lintasannya (c, e7, f) ; d ke e lintasannya (d, e8, e) ; d ke f lintasannya (d, e9, f) ; e ke f lintasannya (e, e10, f) ; sehingga dengan demikian  A terhubung.

d(a) = d(b) = d(c) = d(d) = d(e) = d(f) = 4 ini artinya setiap setiap titik pada graf A berderajat genap.

Karena derajat setiap titik adalah genap, menurut teorema tersebut di atas maka A mempunyai sebuah sirkuit Euler. 

Jadi graf A di atas mempunyai  Sirkuit Euler-nya, dan sirkuit Euler-nya yaitu:

                        (c, a, b, f, c, e, a, d, e, f, d, b, c)

Untuk menunjukan lingkaran Hamilton dalam sebuah graf B maka kita beri label terlebih dahulu setiap titik pada graf B seperti yang tampak di bawah ini:

                                                      B

Berikut ini dua lingkaran Hamilton berbeda pada graf B :

(l, h, i, d, c, b, a, j, k, g, f, e, l)

dan

(i, h, g, f, e, l, b, a, j, k, c, d, i)

5. Periksalah apakah kedua graf di bawah ini planar. Berikan alasan

(A)                                                                (B)

Jawab:

Untuk memeriksa graf A planar atau tidak planar maka kita beri label terlebih dahulu setiap titik pada graf A seperti yang tampak di bawah ini:

              

                                                      (A)

Dalam pemeriksaan apakah graf A planar atau tidak planar, dapat menggunakan Teorema Kuratowski yang menyatakan, “Graf G merupakan planar jika dan hanya jika G tidak mengandung suatu graf-K sebagai subgraf dari G”. Dalam hal ini sebuah graf-K adalah graf yang didapat dari K₅ atau K_3,3 dengan melakukan subdivisi pada sisinya. Artinya dalam persoalan pemeriksaan apakah graf A planar atau tidak planar kita akan mencoba menemukan  K₅ atau K_3,3 pada graf A..

Pertama kali kita ingat bahwa titik a, c, d, e dan  f pada graf A yang telah dilabeli pada gambar di atas, masing – masing mempunyai derajat 4. Untuk itu kita coba menemukan K₅ dalam graf A, karena dalam K₅ setiap titik mempunyai derajat 4, sehingga kita akan melakukannya sebagai berikut:

Graf A kita dapat membentuknya seperti tampak dibawah ini:

                

K₅ setiap titik mempunyai derajat 4, sehingga kita dapat menghapus sisi (d, h) dan (g, h) agar semua sisi mempunyai derajat 4, tampak pada gambar dibawah ini:

Hapus sisi (d, h) dan (g, h)

                

	Reduksi Seri

 

   

Gambar 5.1.

                           K₅

Selanjutnya kita dapat melakukan reduksi seri (Definisi: Jika sebuah graf G mempunyai sebuah sisi v berderajat 2 dan sisi (v, v₁) dan (v, v₂) dengan v₁ ¹ v₂ kita katakana bahwa rusuk  Reduksi seri   (v, v₁) dan (v, v₂) berada dalam seri. Reduksi seri terdiri dari penghapusan sisi v graf G dan menggantikan sisi-sisi (v, v₁) dan (v, v₂) dengan sisi (v₁, v₂). Graf yang dihasilkan G’ dikatakan diperoleh dari G dengan sebuah reduksi seri. Berdasarkan konvensi, G dikatakan dapat diperoleh dari diri sendiri dengan sebuah reduksi seri) dan graf yang dihasilkan akan mempunyai sepuluh sisi dan karena K₅ mempunyai sepuluh sisi, pendekatan ini kelihatan dapat menjanjikan. Dengan coba-coba, akhirnya kita lihat bahwa jika kita kurangi sisi (d, h) dan (g, h) dan kita lakukan reduksi seri, kita peroleh sebuah salinan dari K₅ seperti tampak pada Gambar 5.1. di atas.

Jadi, graf A pada soal 5. ini tidak planar, karena graf tersebut mengandung sebuah subgraf yang homeomorfik pada K₅.  

Untuk memeriksa graf B planar atau tidak planar maka kita beri label terlebih dahulu setiap titik pada graf B seperti yang tampak di bawah ini:

                     

                                                         (B)

Dalam pemeriksaan apakah graf B planar atau tidak planar, dapat menggunakan sama halnya seperti apa yang dilakukan pada graf A tadi di atas menggunakan  Teorema Kuratowski. Artinya dalam persoalan pemeriksaan apakah graf B planar atau tidak planar kita akan mencoba menemukan  K₅ atau K_3,3 pada graf B.

Pertama kali kita ingat bahwa titik a, b, d, c dan  d pada graf B yang telah dilabeli pada gambar di atas, masing – masing mempunyai derajat 4. Untuk itu kita coba menemukan K_3,3 dalam graf B, karena dalam K_3,3 setiap titik mempunyai derajat 3, sehingga kita akan melakukannya sebagai berikut:

Graf B kita dapat membentuknya seperti tampak dibawah ini:

                 

                                                    (B)

K_3,3 setiap titik mempunyai derajat 3, sehingga kita dapat menghapus sisi (c, h), (e, h) dan (i, h) agar semua sisi mempunyai derajat 4, tampak pada gambar dibawah ini:

Hapus sisi (c, h), (e, h) dan (i, h)

                                  

 

Reduksi Seri

          

Gambar 5.2.

                                                                   K_3,3

Selanjutnya kita dapat melakukan reduksi seri sehingga graf yang dihasilkan akan mempunyai sembilan sisi dan karena K_3,3 mempunyai sembilan sisi, pendekatan ini kelihatan dapat menjanjikan. Dengan coba-coba, akhirnya kita lihat bahwa jika kita kurangi sisi (c, h), (e, h) dan (i, h) dan kita lakukan reduksi seri, kita peroleh sebuah salinan dari K_3,3 seperti tampak pada Gambar 5.2. di atas.

Jadi, graf B pada soal 5. ini tidak planar, karena graf tersebut mengandung sebuah subgraf yang homeomorfik pada K_3,3.   

Time Published : 06.49 WIB.
Rating : 7/10.