MODUL 4 Materi Kuliah New_S1
KULIAH 7 , 8 TEOREMA : Jika dari vertex V1 ke vertex V2 dari graph G dengan n vertex terdapat suatu lintasan, maka ada lintasan yang panjangnya tidak lebih dari n – 1. Bukti : Misalnya p = (V1…, Vi, …, V2) adalah lintasan dari vertex V1 ke V2 yang panjangnya k, maka akan terdapat ( k + 1) vertex yang dilalui lintasan tersebut. Misalkan k > n – 1, ini berarti bahwa akan ada vertex Vj yang muncul lebih dari satu kali pada lintasan tersebut, jadi lintasannya adalah ( V1, …, Vi, …, Vj, …, V2). Dengan menghapus sisi-sisi pada lintasan dari Vj kembali ke Vj, maka panjang lintasan dari V1 ke V2 akan berkurang menjadi k1. Bila k1 > n – 1, maka proses di atas dapat diulang sekian kali sampai panjang lintasan yang tinggal adalah tidak lebih dari n – 1. Teorema : Jika suatu graph mempunyai tepat dua vertex berdegree ganjil maka pasti ada lintasan yang menghubungi kedua vertex tersebut. Bukti : Misalnya semua vertex dari graph G berdegree genap, kecuali vertex V1 dan V2 berdegree ganjil. Berdasarkan teorema sebelumnya yang mengatakan bahwa banyaknya vertex berdegree ganjil di dalam suatu graph adalah genap, maka V1 dan V2 termasuk dalam suatu komponen dari G, (sebab bila V1 termasuk dalam komponen G1 dan V2 termasuk komponen G2, akan mengakibatkan bahwa graph G1 mempunyai satu vertex berdegree ganjil), sedangkan setiap komponen adalah terhubung, maka ada lintasan dari V1 ke V2. Teorema : Suatu graph G = ( V, E ) adalah tidak terhubung jika dan hanya jika V dapat dipecah menjadi dua himpunan tidak kosong V1 dan V2 yang saling asing sehingga menghubungi vertex di V1 dan vertex di V2. Bukti :
e
Misalnya ada V1 dan V2 saling asing sehingga V = V1 U V2 dan tidak
e
di E
sehingga e menghubungi vertex di V1 dan vertex di V2. Ambil sembarang vertex A di V1 dan vertex B di V2, maka antara A dan B tidak akan ada lintasan. Jadi G tidak terhubung. Sebaliknya, jika G tidak terhubung. Ambil vertex A di G. Misalnya V1 adalah himpunan semua vertex di G yang dapat dihubungkan sebuah lintasan dengan vertex A tadi. Ambil V = V – 1, maka V2 tidak kosong dan tidak ada e di E sehingga
e
menghubungi
vertex di G2.
– Penyatuan (Fusion) Sepasang vertex A dan B dalam suatu graph dikatakan disatukan jika dua vertex tersebut tersebut diganti dengan satu vertex baru sehingga setiap sisi yang bertitik ujung A atau B kedua-duanya akan bertitik ujung vertex baru. Contoh : E
e1
E
e2
e1 e3
e2 A
B
(AB) e3
e4
F e4
C
e5
e5
e6
C e7
D
e7
e6
D (b)
(a)
Contoh – 30
Contoh– 30 (b) adalah graph yang diperoleh dari graph contoh – 30 (a) dengan menyatukan vertex A dan vertex B. Algoritma menentukan keterhubungan suatu graph. Step utama adalah penyatuan dua vertex yang dihubungkan oleh suatu sisi. Mula- mula ambil suatu vertex, lalu satukan semua vertex- vertex yang adjacent dengan vertex tadi.Lalu ambil vertex hasil penyatuan tadi dan satukan lagi dengan dengan vertexvertex lain yang dapat disatukan.Dalam hal ini, graph yang bersangkutan hanya mempunyai satu komponen atau graph ini terhubung. Jika masih ada vertex yang tinggal,
lakukan lagi proses seperti di atas, proses kedua kali ini menentukan komponen kedua dari graph tersebut dan seterusnya. Dengan demikian dapat ditentukan komponenkomponen dari suatu graph. Pada adjacent matrix penyatuan vertex d ke vertex I berarti melakukan operasi OR terhadap baris j dan beris i , dan terhadap kolom j dan kolom i , dengan ketentuan bahwa : 1 + 0 = 0 + 1 = 1 + 1 =1 dan 0 + 0 = 0 lalu baris j dan kolom j dihapus atau diabaikan. Algoritma di atas dapat dinyatakan dengan flow chart berikut : Intialize : Subgraph g Komponen ke c
G 1
Ambil vertex vi di g
Satukan semua vertex yang adjacent dengan vi ke vi
banyaknya vertex yang tidak adjacent dengan v1 tetap ?
N
Y Hapus vi dan semua vertex adjacent dengan vi, sisanya sebut g
Y G
c+1
apakah ada vertex di g ?
N cetak setiap komponen
Stop
– Contoh : Tentukan komponen-komponen dari suatu graph G dengan n = 17 vertex jika diketahui adjacent matrixnya sebagai berikut :
A=
1
1
1 2
1
2
3
4
5
6
7
8
9
0
1
1 0 2 1 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 1 12 0
1 0 1 0 0 0 0 0 0 0 1 0
0 1 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 1 0 1 1 0 1
0 0 0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 1 1 1 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0
1
1
0
2
1
3
4
5
6
7
8
9
0 0 0 0 0 0 0 1 1 0 0 0
A1 =
1 3 4 5 6 7 8 9 10 12
1 1 0 0 0 0 0 0 0 0
1 1 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 1 0 1 1 1
0 0 0 0 0 1 1 0 0 1
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 1 1 0 0
Ambil vertex 1 vertex, periksa baris 1, a12 = a11 = 1, berarti vertex 2 dan 11 adjacent dengan vertex 1, maka kerjakan operasi OR terhadap baris 2, 11, dan 1, dpl. Satukan vertex-vertex 2, 11 dengan vertex 1 dan namakan vertex baru vertex 1.
Sebelum
disatukan, banyak vertex yang tidak adjcent dengan vertex 1 ada 9 vertex. Setelah disatukan adjacent matrixnya menjadi matrix A1. Dari matrix A1, periksa baris 1 lagi, a15 = 1, banyaknya vertex yang tidak adjacent dengan vertex 1 ada 7 vertex, jadi tidak sama dengan sebelum disatukan. Maka kerjakan pernyataan vertex lagi, yaitu lakukan operasi OR terhadap baris 5 dan 1, kolom 5 dan kolom 1, akan didapat matrix A3. Dari matrix A3, periksa baris 1 lagi, banyaknya vertex yang tidak adjacent dengan vertex 1 ada 7 vertex, jadi tetap sama dengan sebelum pertanyaan vertex,ini berarti sudah tidak ada lagi vertex yang dapat disatukan. Dengan demikian terbentuklah komponen : G = ( V1, E1 ) dengan V1 = { 1, 2, 11, 3, 5 } Pada matrix A3, periksa baris berikutnya, yaitu baris 4, ternyata tidak ada elemen yang sama dengan 1, berarti semua vertex tidak adjacent dengan vertex 4, didapat komponen kedua : G2 = ( V2, E2 ). Dengan V2 = { 4 }. Kemudian lanjutkan ke baris berikutnya lagi, yaitu baris 6, e6, 10 = 1, dan banyaknya vertex yang tidak adjacent dengan vertex 6 ada 6 buah, lalu kerjakan operasi OR terhadap baris 10 dan 6, dan kolom 10 dan kolom 6, akan diperoleh matrix A4.
1
A2 =
A3 =
1 4 5 6 7 8 9 10 12
1 4 6 7 8 9 10 12
1 0 1 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0
5 1 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 1 0
7
8
0 0 0 0 0 1 1 1 0
0 0 0 0 1 0 1 1 1
9
1
1
0
2
0 0 0 1 1 1 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0 1
1
1
1
4
6
7
8
9
0
0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 1 1 0
0 0 0 1 0 1 1 1
0 0 0 1 1 0 0 1
0 0 1 1 1 0 0 0
0 0 0 0 1 1 0 0
1 1 4 6 A4 = 7 8 9 12
4
1 0 0 0 0 0 0
0 0 0 0 0 0 0
6
7
8
9
12
0 0 1 1 1 0 0
0 0 1 0 1 1 0
0 0 1 1 0 1 1
0 0 0 1 1 0 1
0 0 0 0 1 1 0
Dari matrix A4, periksa baris, a67 = a68 = 1, banyaknya vertex 6 ada 4 buah, tidak sama dengan sebelum pernyataan vertex, jadi dilakukan lagi operasi OR terhadap baris 7, 8 dan 6, akan diperoleh matrix A5.
1
A5 =
1 4 6 9 12
1 0 0 0 0
4 0 0 0 0 0
6
9
12
0 0 1 1 1
0 0 1 0 1
0 0 1 1 1
Dari matrix A5, selidiki baris, 6 = a6,6, a6,7, a6,12 = 1, banyaknya vertex yang tidak adjacent dengan vertex 6 ada 2, berkurang dari sebelum pernyataan vertex, jadi lakukan operasi OR terhadap baris 9, 12 dan 6 kolom 9, 12, dan 6, diperoleh oleh matrix A6.
A6 =
1
4
6
1 1 4 0 6 0
0
0 0 1
0 0
Pada matrix A6 banyaknya vertex yang tidak adjacent dengan vertex 6 ada 2 buah, tetap banyaknya. Jadi proses pernyatuan vertex telah selesai dan terbentuk komponen ke 3 : G3 = ( V3, E3 ) dengan V3 = { 6,10, 7,8 9, 12 }. Algoritma menentukan suatu lintasan dari vertex vp ke vertex ke vertex vq dari suatu graph berarah G = ( V, E ) berdasarkan adjacent matrixnya.
Step 1 : tentukan subset T dan subset P dari V. Dimana T mengandung vertex-vertex yang dapat dicapai dari vp dengan suatu lintasan dan P mengandung initial vertex dari edgeedge yang mempunyai terminal certex di T. Pada awal, ambil T = { Vp } dan P = { 0 }. Step 2 : Cek elemen-elemen pada setiap baris ke 1 dari adjacent matrixnya, bila di j tidak nol ( j = 1, 2, 3, …, n), maka vertex vj dimasukkan ke T dan vi dimasukkan ke P. Pengecekan ini dimulai dengan baris ke 1 dan diulangi terus sampai beris ke n, jika vertex vq termasuk di T, berarti ada lintasan dari vp ke vq, banyaknya vq di T mencerminkan banyaknya lintasan dari vp ke vq atau vq tidak termasuk T, dalam hal ini berarti tidak ada lintasan dari vp ke vq. Step 3 : jika vq termasuk di T, teruskan ke step 4, jika tidak, stop. Step 4 : Mulai dari vq di T cari vi di P yang korespondensi dengan vq, kemudian cari vi di T dan vj di P yang korenspondeni dengan vi, proses ini diteruskan sampai ketemu vp di P. Dengan demikian akan didapat lintasan dari vp ke vq. Step 4 ini diulang sekian kali, tergantung dari banyaknya vq di T. Contoh : Graph G = ( V, E ) dengan V = { v1, v2, v3, v4, v5, v6, v7 }. V1
V2
V5
V3
V6
Dan adjacent matrix dari G adalah :
V1 V 2 V 3 V 4 V 5 V 6 V 7
V4
V7
V 1 0 V 2 0 V 3 0 A = V 4 0 V 5 1 V 6 0 V 7 0
1 0 0
0 1 0
0 1 0
0 0 0
0 0 1
0 0 0
0 0 0
0 0 0
0 0 1
0 0 0
0
0
0
0
0
0 0 1 0 0 0 0
Contoh– 31 1. Misalnya ingin dicari litasan dari v5 ke v4 di graph G pada contoh –31. Step 1 : T = { V5 }, P = { 0 }. Step 2 : Cek baris ke 1, elemen a12 = 1 maka v2 dimasukkan ke T, dan v1 dimasukkan ke P, jadi T = { v5, v2 }, P = { 0, v1 } V4 belum ada di t, ulangi step 2 untuk baris ke 2. Step 2 : Cek baris ke 2 elemen a23 = 1 maka v3 dimasukkan ke T dan v2 dimasukkan ke P, jadi T = { v5, v2, v3 }, P = { 0, v1, v2 }. V4 belum termasuk di T, jika diinginkan hanya satu lintasan, lanjutkan ke step 3.jika diinginkan semua lintasan yang ada, ulangi step 2 untuk baris ke 4, 6, dan 7. Step 2 : Cek baris ke 4, semua elemen nol, maka ulangi step 2 untuk baris ke 5. Step 2 : Cek baris ke 5 elemen a51 = 1 maka vertex v1 dimasukkan ke T dan v5 dimasukkan ke P, jadi T = { v5, v2, v3, v4, v6, v7, v1 }, P = { 0, v1, v2, v3, v3, v3, v5 }. Step 2 : Cek baris ke 6 elemen a65 = 1 maka vertex v5 dimasukkan ke T dan v6 dimasukkan ke P, jadi T = { v5, v2, v3, v4, v6, v7, v1, v5 }, dan P = { 0, v1, v2, v3, v3, v3, v5, v6 }. Step 2 : Cek baris ke 7 elemen a74 = 1 maka vertex v4 dimasukkan ke T dan v7 dimasukkan ke P, jadi T = { v5, v2, v3, v4, v6, v7, v1, v5, v4 }, dan
P = { 0, v1, v2, v3, v3, v3, v5, v6, v7 }. Step 3 : Karena di T ada vertex v4, maka lintasan dari v5 ke v4 ada, lanjutkan ke step 4. Step 4
: Untuk v4 di T, vertex di P yang sesuai adalah v7, untuk v7 di T, vertex di P yang sesuai adalah v3, untuk v3 di T, vertex di P yang sesuai adalah v2, untuk v2 di T, vertex di P yang sesuai adalah v1, untuk v1 di T, vertex di P yang sesuai adalah v5.
Jadi solusi yang kedua adalah ; v5 – v1 – v2 – v3 – v7 – v4. Di T terdapat dua v4, maka lanjutkan step 4 sekali lagi : Step 4
: Untuk v4 di T, vertex di P yang sesuai adalah v3, untuk v3 di T, vertex di P yang sesuai adalah v3, untuk v2 di T, vertex di P yang sesuai adalah v1, untuk v1 di T, vertex di P yang sesuai adalah v5.
Jadi solusi yang kedua adalah ; v5 – v1 – v2 – v3 – v4.
– Lintasan terpendek : Misalnya graph G = ( V, W ) adalah suatu graph berbobot. Timbul masalah mencari lintasan terdekat antara dua vertex tertentu. Algoritma untuk mencari lintasan terdekat dapat manggunakan matrix jarak yang didefinisikan sebagai berikut : Suatu graph berbobot G yang terdiri dari n vertex dapat dinyatakan oleh matrix jarak D = (dij) dimana Dij = bobot dari sisi yang dihubungkan vertex vi dan vj, jadi dij >= 0. dij = 0 dij = ~ (99999999), jika tidak sisi yang menghubungkan vertex vi dan vj.
Contoh : Matrix D untuk graph berbobot.
2
V1
8 V4
7
2
V2
2 V7
V5 3
10
4 4
1
7 3
V3
V6
Adalah :
V1 V 2 V 3 V 4 V 5 V 6 V 7
D=
V V V V V V V
1 2 3 4 5 6 7
0 7 3 2 ~ ~ ~
~ 0 ~ ~ ~ ~ ~
~ 1 0 ~ ~ ~ ~
8 ~ ~ 0 ~ 10 2
2 ~ 4 1 0 4 ~
~ ~ 3 ~ ~ 0 ~
~ ~ ~ ~ 2 7 0
Contoh – 32
Algoritma : Jarak terdekat dari vertex ke vertex vt. Algoritma ini memberi setiap vertex dua macam label, yang satu label sementara yang satu lagi label tetap.Pada awal vertex s diberi label tetap 0 dan label sementara ~ untuk n – 1 vertex lainnya. Lalu lakukan iterasi yang memberikan label tetap kepada vertex lainnya berdasarkan aturan sebagai berikut : 1. Misalnya vi adalah vertex terakhir yang baru diberi label tetap. Setiap vertex vj yang belum diberi label tetap mendapat label sementara baru sebesar. Min [ label lama vj, di j + label lama di vj ]. 2. Pada setiap iterasi cari label sementara terkecil, maka label ini akan menjadi label tetap untuk vertex yang bersangkutan. Bila ada dua label terkecil yang sama, ini akan berarti ada dua lintasan terdekat.
Step 1 dan 2 diulang sampai vertex vt mendapat label tetap. Label tetap dari vertex vt inilah yang menunjukkan jarak terdekat dari vs ke vt. Algoritma di atas dapat pula digambarkan dalam bagan arus berikut :
Read D, n, s, t Label ~ Label (s) 0 Vect 0 1 s Vect (s) 1
j m
1
~
NO z
VECT (J) = 1 ?
dij + 1 LABEL (i)
YES NO j
j+ 1
j= n?
Z < LABEL (J) ?
NO YES
YES j i
j+ 1 p LABEL (j)
z
P= L ? NO
LABEL (J) > m ?
YES YES
NO CETAK LABEL ( t )
m p
LABEL (J) j
STOP
Misalnya ingin dicari jarak dari vertex v2 ke vertex v dari graph berbobot pada contoh – 32. Mulai dari vertex v2 diberi label 0, vertex lainnya diberi label ~, maka dengan mengikuti bagan arus di atas akan dperoleh urutan pemberian label sebgai berikut :
V 1
V 2
V 3
V 4
V 5
V 6
V 7
~, 0,0 7,0,0 7,0,0 4,0,0 4,0,0 4,1,1 4,1,0 4,1,0
0,1,1 0,1,0 0,1,0 0,1,0 0,1,0 0,1,0 0,1,0 0,1,0
~, 0,0 1,0,0 1,1,1 1,1,0 1,1,0 1,1,0 1,1,0 1,1,0
~, 0,0 ~, 0,0 ~, 0,0 ~, 0,0 14, 0,0 14, 0,0 12, 0,0 12, 0,0
~, 0,0 ~, 0,0 ~, 0,0 5, 0,0 5, 0,0 5, 0,0 5, 0,0 5, 1,1
~, 0,0 ~, 0,0 ~, 0,0 4, 0,0 4, 1,1 4, 1,0 4, 1,0 4, 1,0
~, 0,0 ~, 0,0 ~, 0,0 ~, 0,0 11, 0, 0 11, 0, 0 11, 0, 0 11, 0, 0
4,1,0 4,1,0
0,1,0 0,1,0
1,1,0 1,1,0
12, 0,0 12, 0,0
5, 1,0 5, 1,0
4, 1,0 4, 1,0
11, 0, 0 7,1,1
Arti tiga bilangan untuk setiap vertex di atas adalah Bilangan pertama adalah label baru untuk vertex ybs. Label ini adalah label tetap bila bilangan ketiga adalah 1, dan label ini adalah label sementara bila bilangan kedua adalah 0.bilangan ketiga menunjukkan vertex ybs. baru diberi label tetap bila bilangan ketiga adalah 1. Dari atas tidak hanya diperoleh jarak terdekat dan lintasan terdekat dari v2 ke v7, juga dapat pula disimpulkan bahwa jarak terdekat – dari v2 ke v1 adalah 4, dengan lintasan ( v2, v3, v1 ) – dari v2 ke v3 adalah 1, dengan lintasan ( v2, v1 ) – dari v2 ke v5 adalah 5, dengan lintasan ( v2, v3, v5 ) – dari v2 ke v6 adalah 4, dengan lintasan ( v2, v3, v6 ) – dari v2 ke v7 adalah 7, dengan lintasan ( v2, v3, v6, v7 )
Materi Kuliah New_S1
KULIAH 8 (sambungan) – LINTASAN EULER dalam suatu graph tak terarah adalah lintasan yang melalui setiap sisi tetap satu kali dalam graph tersebut. – Sirkuit Euler dalam suatu graph tak terarah adalah sirkuit yang melalui tetap satu kali dalam graph tersebut. Contoh : Persoalan jembatan konigsberg
.
Contoh –32a Contoh –32b
Contoh –32a, menggambarkan dua pulau C dan D ( yang terbentuk oleh sungai A dan B oleh 7 jembatan ). Timbul persoalan apakah seseorang dapat melintasi ketujuh jembatan tersebut masingmasing tepat satu kali jika berangkat dari salah satu daratan A, B, C atau D dan kembali ke daratan semula. Contoh 33b adalah graph G yang menyatakan hal yang digambarkan pada contoh 33a. Vertex-vertexnya menyatakan daratan A, B, C dan D, sisinya menyatakan jembatanjembatan yang menghubungkannya. Dengan menyatakan jembatan konigsberg dengan graph G maka persoalan di atas dapat diterjemahkan menajadi : apakah ada sebuah lintasan Euler di graph G ? Untuk menjawab persoalan di atas dibutuhkan teorema di bawah ini : TEOREMA : Graph tak terarah G mempunyai lintasan Euler
graph tersebut terhubung dan
tidak memiliki vertex dengan derajat ganjil. Bukti : Misalnya G mempunyai lintasan Euler, berarti setiap 2 vertex dari G selalu ada lintasan yang menghubungkannya, ini berarti bahwa G terhubung. Pada lintasan Euler, bila lintasan melalui suatu vertex maka selalu ada 2 sisi yang dilalui dan belum pernah dilalui sebelumnya dengan perkecualian pada vertex awal dan vertex akhir, ini berarti bahwa setiap vertex berderajat genap kecuali 2 vertex ( vertex awal dan vertex akhir lintasan Euler tersebut ) berjarak ganjil. Bila vertex awal lintasan = vertexakhir lintasan, ini berarti bahwa tidak ada vertex berderajat ganjl.
Graph G terhubung, berarti setiap 2 vertex selalu ada lintasan. Buat sebuah lintasan P mulai dari vertex sembarang bila G tak memiliki vertex berderajat ganjil atau mulai dari vertex berderajat ganjil bila ada, sedemikian rupa sehingga tidak ada sisi yang ditelusuri lebih dari 1 kali.Selama lintasan P masuk ke vertex derajat genap, lintasan P pasti dapat keluar ke sisi yang belum pernah ditelusuri. Dalam hal G tak memiliki vertex berderajat ganjil, lintasan tersebut akan kembali ke vertex awal, lintasan tersebut akan menjadi sirkuit Euler. Ada dua kemungkinan yang terjadi, pertama lintasan P melalui semua sis graph G, berarti P adalah lintasan Euler. Kedua, masih ada sisi yang belum ditelusuri oleh lintasan P. Jika belum semua sisi belum ditelusuri hilangkan sisi yang sudah dilalui lintasan P, akan diperoleh graph bagian G yang terbentuk dari sisa sisi-sisi. Semua vertex di G berderajat genap dan graph bagian G’ pasti menyinggung lintasan P dibeberapa vertex karena graph G terhubung. Buat lagi lintasan P’ seperti tadi di sub graph G’ mulai dari salah satu vertex singgung P, di sini vertex awal lintasan P akan sama dengan vertex akhir lintasan P’ yaitu vertex V, karena semua vertex berderajat genap. Gabungkan dengan lintasan P dan lintasan P’ melalui vertex v. bila masih ada sisi yang tertinggal, maka hasil gabungan lintasanlintasan yang diperoleh adalah lintasan Euler. Contoh :
E
E
j
k
F c
D
b
e C
A a
C
F
D
b
e
d B
Contoh – 34a
k
j
B
Contoh – 34b
Pada contoh –34a dapat dibuat lintasan P1 = ( a, d, m, g, j, h ). Belum semua sisi ditelusuri oleh P1, maka terjadi subgraph G1 pada contoh –34b. Subgraph G1 di vertex B, P dan D. Setiap vertex di G1 berderajat genap. Buat lintasan P2 dimulai dari salah satu B,
D, F, misalnya dimulai dari B, P2 = (i, e, k, f, b, j, c). Dengan demikian semua sisi di G telah masuk P1 atau P2.Lintasan Eulernya adalah P hasil gabungan P1 dan P2. P1 dan P2 digabung melalui vertex singgung yang dipakai untuk melalui P2 yaitu B, jadi P = (a, e, k, f, b, d, m, m, g, i, h ).
AKIBAT : Graph tidak terarah mempunyai
graph tersebut terhubung dan semua vertex berderajat
genap
Contoh :
A
B j
C
i
B
e
C e
h
g
k
c
h
D
g
k
E
f
m
b
m
F
b
a
E
f a
D
c
F Contoh – 35a
Contoh – 35b
Graph G pada contoh –35a setiap vertexnya berderajat genap, maka G mempunyai sirkuit Euler, yang dapat dibentuk sebagai berikut : Ambil lintasan tertutup ( sirkuit ) S1 = ( j, d, h, g, f ) dimulai dari vertex sembarang A, tidak semua sisi dari G masuk sirkuit S1. Subgraph G1 bersinggungan dengan sirkuit S1 di vertex B, C, D, dan E. Bentuk lagi sirkuit S2 mulai dari misalnya B, S2 = ( e, a, b, c, m, k ). Sekarang semua sisi telah tertelusuri tepat satu kali, sirkuit Eulernya adalah S = ( j, e, a, b, c, m, k, d, i, h, g, f ) Pada contoh –34a mempunyai lintasan Euler tapi tidak mempunyai sirkuit Euler, sedangkan pada contoh –35a mempunyai lintasan Euler juga sirkuit Euler.
Kembali kepada persoalan jembatan Konigeberg, graph G pada contoh –33b mempunyai 3 vertex berderajat 3 dan 1 berderajat 5, jadi menurut teorema di atas, graph G tidak mungkin mempunyai 1 lintasan Euler atau sirkuit Euler. Perluasan pada Graph berarah : TEOREMA : a. Graph berarah G mempunyai sirkuit Euler 1. G terhubung 2. din ( v ) = dout ( v ) untuk setiap vertex dari G. b.Graph berarah G mempunyai lintasan Euler 1. G terhubung 2. din ( v ) = dout ( v ) untuk setiap vertex di G kecuali mungkin dua vertex yaitu vertex awal v dan vertex akhir v2. Dalam hal ini berlaku : din ( v1 ) = dout ( v1 ) + 1 din ( v2 ) = dout ( v2 ) + 1
