Lintasan Dan Sirkuit Euler

Dfinisi 6.44

Misalkan G = (V,E) adalah sebuah graf. Sebuah sirkuit yang memuat semua sisi dan titik sudut disebut sirkuit euler. Jika kondisi ini terpenuhi, dikatakan bahwa graf G tersebut memiliki sirkuit euler.

Jika kita melihat kembali pada masalah jembatan Konigsberg, kita melihat bahwa kita sebenarnya berusaha memutuskan apakah graf tersebut memiliki sirkuit euler atau tidak. Untuk membantu memecahkan permasalahan ini, kita memerlukan beberapa teorema yang sesuai. Teorema-teorema berikut juga benar untuk multigraf dan pseudograf, kecuali pseudograf yang hanya memiliki satu titik sudut.

Teorema 6.45

Sebuah graf dengan lebih dari satu titik sudut memiliki sirkuit euler jika dan hanya jika graf ini terhubung dan setiap titik sudut memiliki derajat genap.

Bukti:

Misalkan sebuah graf G memiliki sirkuit euler. Graf ini terhubung karena setiap titik sudutnya terletak pada sirkuit. Untuk sembarang titik sudut v pada G, setiap kali sirkuit euler melalui v, maka G akan menyumbangkan 2 degree untuk v, akibatnya v memiliki degree genap.

Sebaliknya, kita akan menunjukkan bahwa setiap graf terhubung yang memiliki degree genap adalah sirkit euler. Kita akan membuktikan teorema ini menggunakan induksi terhadap banyak dari titik sudut.karena teorema ini benar untuk n≤3, kita akan memulai induksi untuk n=3. Asumsika bahwa setiap graf terhubng memiliki titik sudut dengan degree genap dan titik sudut kurang dari k memiliki sirkuit euler. Misalkan G adalah graf terhubung yang memiliki k vertex, dimana setiap verteksnya berdegree genap. Asumsikan v1 dan v2 adalah vertex dari G. karena G terhubung, maka terdapat lintasan dari v1 ke v2. Karena v2 memiliki degree genap maka terdapat edge yang tidak terpakai yang bias digunakan untuk melanjutkan lintasan. Karena graf ini berhingga, akibatnya lintasan tersebut harus kembali lagi ke v1 sehingga terbentuklah sirkuit euler yang kita sebut C1, dimana Ci1 adalah sirkuit euler dari G. Jadi kita telah membuktikan bahwa C1 adalah sirkuit euler dari G, jika tidak kita misalkan G’ adalah subgraf dari G yang terbentuk dengan menghilangkan semua edge dari C1. Karena C1 memuat edge yang saling insiden dengan vertex lain yang banyaknya genap. Maka setiap vertex pada G’ juga memiliki degree genap.

Misalkan e adalah edge dari G’ dan Ge adalah component dari G’ yang memuat e. karena G’ memiliki vertex yang krang dari k dan setiap vertex dari dari G’ memiliki degree genap, maka G’ memiliki sirkuit euler yang kita sebut C2. Selanjutnya C1 dan C2 memiliki vertex yang sama, kita sebut a.

Contoh 6.46

Contoh 6.47

Definisi 6.48

Misalkan G = (v,E) adalah sebuah graf. Sebuah lintasan yang memuat setiap edge pada G tepat satu kali disebut lintasan euler. Jika kondisi ini terpenuhi, maka graf G memiliki lintasan euler.

Teorema 6.49

Sebuah graf ( multigraf atau pseudograf) memiliki sebuah lintasan euler jika dan hanya jika terhbung dan tepat dua vertexnya memiliki degree ganjil.

Contoh 6.50

Contoh 6.51

Definisi 6.52

Misalkan G = (V,E) adalah graf berarah. Sebuah sirkit berarah adalah sebuah lintasan berarah dengan panjang lebih besar dari 0 dan dimlai dari sebuah vertex kembali ke vertex tersebut tanpa ada edge yang dilalui lebih dari satu kali.

Definisi 6.53

Misalkan G = (V,E) adalah sebuah graf berarah. Sebuah sirkuit yang memuat semua edge dan vertex dari G disebut sirkuit euler.jika kondisi ini terpenuhi, dikatakan bahwa graf berarah G memiliki sirkit euler.

Teorema 6.54

Sebuah graf berarah memiliki sebuah sirkuit euler jika dan hanya jika dia terhubung dan dimana degree keluar dan degree masuk dari setiap vertex sama.

POHON (TREE)

Pohon adalah graph yang tidak memiliki cycles. Pohon memiliki banyak kegunaan pada bidang

numerik termasuk matematika dan ilmu komputer. Contohnya, pohon ini sering digunakan

sebagai alat penghitung dan penyimpan data untuk ketepatan pemilihan atau untuk pencarian

data. Kegunaan yang lainnya akan dijelaskan di bagian berikutnya.

President

AcademicVice President

AdministrativeVice President

Gambar 3.1 merupakan pohon.

Gambar 3.2 bukan pohon karena mengandung cycle.

Gambar 3.3 bukan pohon, karena setiap komponennya adalah pohon maka disebut

sebagai forest.

Silsilah keluarga adalah salah satu bentuk pohon. Jika kita memulai dari orang tertentu, lalu buat

rusuk di antara orang tua dan setiap anak-anak mereka, maka terbentuklah pohon. Kemudian,

jika masing-masing anak menikah, maka akan ada sepupu. Namun, pembuatan silsilah keluarga

ini perlu diperhatikan, karena jika terdapat pernikahan antar sepupu, dapat membentuk cycle.

Contoh lain pohon adalah susunan organisasi. Contohnya pada gambar susunan organisasi

universitas pada gambar 3.4.

v7 v8

v6v5v4v3

v1 v2

v0

Sebuah directed tree T adalah sebuah loop-free directed graph, yang mendasari sebuah

graph adalah pohon, sehingga jika a dan b adalah verteks di T, maka terdapat lintasan tunggal

dari a ke b. Dengan demikian, misalkan E adalah himpunan dua edges untuk pohon, maka relasi

untuk pohon tersebut memiliki sifat: jika (a, b) E maka (b, a) E. Relasi ini disebut

asimetris.

Titik-titik yang memiliki derajat 1 dinamakan daun. Verteks yang lainnya dinamakan

internal vertices. Verteks v3, v4, v5, v6, dan v7 adalah leaves.

Teorema 6.37

Gambar 3.5

Gambar 3.4

v8

v6

v5v4

v7

v3v2

v1

v0

Untuk sembarang titik a dan b dari sebuah pohon T, terdapat lintasan tunggal dari a ke b.

Bukti

Untuk membuktikan teorema ini, kita andaikan lintasan dari a ke b tidak tunggal untuk titik a

dan b dari T dan perlihatkan bahwa T bukan pohon. Jika kita misalkan ada dua lintasan berbeda

v0v1v2...vn, dengan panjang n dan , dengan panjang m, dimana a = v0 dan b = vn = .

Pasti terdapat titik pertama di setiap lintasan dimana vi dan pasti terdapat sebuah titik yang

sama lagi, katakanlah dimana vj = vk. Maka vi - l vi vi + l vi+2... vj - l - 2 vi – l adalah cycle

maka T bukan pohon.

Dengan teorema tersebut, kita bisa lihat kebalikan dari teorema di atas yang juga benar. Karena

itu, kita sebaiknya mendefinisikan pohon adalah graph yang terdapat lintasan tunggal pada

sembarang dua titik

Theorema 6.38

Jika untuk sembarang dua titik di dalam graph G, terdapat sebuah lintasan tunggal dari a ke b,

maka G adalah pohon.

Bukti

Misalkan G bukan pohon. Maka G juga tidak terhubung atau memiliki cycle. Jika G tidak

terhubung, maka terdapat verteks a, b G yang tidak memiliki lintasan dari a ke b. Oleh karena

itu, tentu saja tidak ada lintasan tunggal. Jika G memiliki cycle v0v1v2v3v4...vk-1vk, maka v2v3...vk-

1vkv0 dan v1v2 v0 adalah kedua lintasan dari v2 ke v0. Misalkan a = v2 dan b = v0, kita telah

menemukan verteks a dan b yang tidak memiliki lintasan tunggal diantara mereka.

Misalkan kita menganggap sebuah pohon sebagai objek fisik yang fleksibel pada

titiknyanya dan tahan titik pohon tersebut sehingga sisa titik-titik yang menggantung di

bawahnya. Contohnya lihat pada gambar di bawah ini.

Gambar 3.6

''2

'10 ... mvvvv '

mv

'iv

'kv '

kv 'kv '

iv

v0 v1

v2

v3

v4

v5

v6

v7

v8v0 v1

v2

v3

v4

v5

v6

v7

v8

Jika kita tahan titik v3 pohon ini, kita memiliki pohon seperti yang disajikan pada Gambar 3.7.

Jika kita tahan titik v4 pohon ini, maka akan terbentuk pohon seperti yang terlihat pada Gambar

3.8.

Titik pada bagian atas pohon tersebut disebut akar(root) dari pohon. Apabila akar dari pohon

memang telah ditentukan, maka pohon tersebut dikatakan sebagai pohon berakar.

Pohon berakar T bisa berubah menjadi pohon berarah T yang dikenal dengan sebutan pohon

berakar berarah T seperti pada gambar dibawah ini.

Beberapa Istilah Pada Pohon

Level dari titik v adalah panjang lintasan tunggal dari akar ke v

Tinggi pohon adalah panjang lintasan terpanjang dari akar pohon ke daun

Parentmerupakan titik yang dihubungkan dengan akar pohon yang telah ditentukan

sebelumnya oleh sebuah sisi berarah dimana arahnya dari titik tersebut ke akar pohon.

Child merupakan titik yang dihubungkan dengan akar pohon yang telah ditentukan

sebelumnya oleh sebuah sisi berarah dimana arahnya dari akar pohon ke titik tersebut

Siblings adalah sebuah titik dikatakan saudara dengan titik lainnya apabila titik-titik

tersebut memiliki parent yang sama

Ancestor dan descendant : apabila terdapat lintasan berarah dari titik u ke titik v

maka u disebut sebagai ancestor v dan v disebut sebagai descendant u

Pohon m-ary : disebut pohon m-ary (m-ary tree) apabila outdegree terbesar untuk

sembarang titik pada pohon tersebut adalah m

Gambar 3.7 Gambar 3.8

Pohon biner : disebut pohon m-ary (m-ary tree) apabila outdegree terbesar untuk

sembarang titik pada pohon tersebut adalah 2

Teorema 6.40

Jika pohon T memiliki e sisi dan v titik maka v = e +1

Bukti:

Dibuktikan dengan induksi matematika

Pernyataan diatas benar untuk v = 1, sebab jika v = 1 maka pohon tersebut tidak mempunyai sisi,

jadi e = 0, atau v = e + 1. Untuk n = 2, pohon tersebut hanya memiliki satu sisi, jadi e = 1 atau v

= e + 1 juga.

Andaikan pernyataan diatas benar untuk pohon dengan banyaknya titik kurang dari v. sekarang

misalkan T adalah suatu pohon dengan x titik dan y adalah suatu sisi dalam pohon T yang

menghubungkan vi dan vj. Pandang T-y karena teorema 6.37 maka tidak ada lagi lintasan yang

menghubungkan antara vi dan vj. Dengan demikian T akan terpisah menjadi dua komponen yang

juga berupa pohon. Katan T1 dan T2. Banyaknya titik pada T1 misalkan v’ dan banyaknya sisi

adalah e’, sehingga v’ < v dan berlaku v’ = e’+ 1 sedangkan banyaknya titik di T2 adalah v” dan

banyaknya sisi pada T2 adalah e”, sehingga v” < v dan berlaku v = e + 1

Selanjutnya v’ + v” = e’ + e” + 2 sedangkan v = v’ + v” dan e = e’+ e” +1 akibatnya v = e +1.

Jadi pernyataan diatas benar untuk setiap pohon.

Teorema 6.41

Jika sebuah graf G terhubung memiliki e sisi dan v titik dan v = e + 1 maka G adalah sebuah

pohon.

Bukti :

Misalkan G adalah sebuah graf terhubung dengan v titik dan e = v-1 sisi. Untuk membuktikan

bahwa G adalah sebuah pohon maka dibuktikan bahwa G tidak mempunyai sirkuit. Misalkan g

memiliki sirkuit elementer v1,v2,v3,…,vm. Pada sirkuit ini terdapat m titik dan m sisi ( m<v). jadi

masih sisa v-m titik. Karena G terhubung maka paling sedikit masih ada v-m sisi lagi diluar

sirkuit tersebut. Yang berarti bahwa G mempunyai m + (v-m) = v titik dan m + (v-m) = v sisi. Ini

bertentangan dengan pemisalan sebelumnya. Jadi G tidak mungkin memiliki sirkuit. Dengan

demikian G adalah sebuah pohon.

Definisi 6.42

Sebuah pohon T adalah pohon pembangun/rentang (spanning tree) untuk suatu graf G, apabila T

adalah sebuah subgrafdari G dan setiap titik pada G adalah juga titik pada T.

Teorema 6.43

Sebuah graf G disebut terhubung jika dan hanya jika G memuat pohon pembangun.

Bukti

Jika graf G memuat pohon pembangun, jelas G terhubung. Kita buktikan konvers pernyataan ini

dengan induksi pada |E (G )|. Jika G terhubung dan |E (G )|=0, maka G = K1 sehingga jelas G

memuat pohon pembangun

Asumsikan setiap graf terhubung dengan k sisi memuat pohon pembangun, akan ditunjuka

bahwa, jika G graf terhubung dengan k + 1 sisi, amka G memuat pohon pembangun.

Pandang sebuah graf terhubung dengan k+1 sisi. Jika G tidak memuat siklus, maka G sebuah

pohon pembangun. Jika G memuat siklus, dan misalkan e adalah sebuah sisi dari siklus di G,

maka graf G1 = G – e terhubung dengan k sisi, sehingga berdasarkan asumsi, G1 meuat pohon

pembangun, sebut saja T. T adalah pohon pembangun di G1. Jelas T adalah pohon pembangun di

G. jadi teorema terbukti.