Vertex Degree, Euler Trail Dan Euler Circuit
Vertex Degree, Euler Trail Dan Euler Circuit
Vertex Degree, Euler Trail Dan Euler Circuit
VERTEX DEGREE,
EULER TRAIL,
EULER CYRCUIT
Aulia Tu Zahra (2225220053)
Aura Noer Afrietha (2225220014)
Cherlyantika Agustina (2225220005)
Dina Rosdianti (2225220093)
ANGGOTA
Diyanah Fujiyati (2225220003)
Dewi Aulia (2225220019)
Farras Sahil Mumtaz (2225220089)
VERTEX DEGREE
Degree vertex pada suatu
Graf adalah banyaknya sisi
yang terkait dengan vertex
VERTEX
DEGREE Notasi nya dilambangkan
dengan deg (v)
Contoh Graph
apabila degree nya 1 disebut Perdent Vertex
2q = 2(8) =16
Pada graf disamping, vertex yang memiliki
derajat ganjil yaitu deg(a)=3 dan deg(h)=1
EULER
terdapat cyrcuit yang melintasi setiap
edge tepat 1 kali. jika ada open trail dari
Euler a ke b di G, dan trail ini melintasi di
TRAIL
Trail setiap edge di G tepat 1 kali. maka trail
tersebut disebut euler trail.
Trail :
dimana semua edge tidak boleh berulang,
tetapi boleh ada edge yang terlewat atau
tidak terlintasi
Euler trail :
dimana semua edge harus terjangkau, dan
tidak boleh ada edge yang terulang.
Contoh Graph
graph yang dapat dibuat euler graph yang tidak dapat dibuat euler
Kasus jembatan konigsberg
EULER
Circuit euler ialah circuit yang melewati masing-masing edge
tepat satu kali, vertex boleh di ulang akan terapi edge
CIRCUIT
tidak boleh di ulang, dan harus melewati semua edge yang
ada dalam graf tersebut
Graf yang mempunyai sirkuit euler disebut graf euler ( Eulerian graph ).
Graf yang mempunyai sirkuit euler harus memenuhi :
Graf tersebut harus terhubung.
Semua simpul pada graf berderajat genap.
Contoh Euler Circuit Graf disamping bisa dikatakan Euler
Circuit, karena dari vertex 1 ke 1 lagi
semua garis terlewati, tetapi tidak ada
edge yang dilewati 2 kali (bolak balik). Ini
Circuit Normal Euler Circuit sesuai dengan pengertian sebelumnya,
bahwa "Circuit euler ialah circuit yang
melewati masing-masing edge
tepat satu kali, vertex boleh di ulang
akan terapi edge
tidak boleh di ulang, dan harus melewati
semua edge yang
ada dalam graf tersebut"
Circuit normal pada Euler Circuit pada graf : 1 - Tapi, graf di sebelahnya
-> 2 --> 3 --> 4 --> 7 --> 3 --> merupakan Circuit biasa, karena
graf : 1 --> 2 --> 3 --> 4 -- 5 --> 7 --> 6 --> 5 --> 2 --> 6 - walaupun graf tersebut balik ke
> 7 --> 6 --> 1 -> 1 vertex awal, tetapi ada beberapa
edge yang tidak dilewati
Dengan menggunakan teorema euler, maka masalah Jembatan Konigsberg tidak
memiliki sirkuit euler karena simpul atau verteksnya berderajat ganjil.
deg (A) = 5
deg (B) = 3
deg (C) = 3
deg (D) = 3
Graf tidak berarah G adalah graf Euler
(memiliki sirkuit Euler) jika dan hanya jika
setiap simpul berderajat genap.
TEOREMA
memiliki derajat-masuk dan derajat-keluar
sama. Atau
id(v) = od(v)
untuk semua v anggota Vertex
Sesuai dengan teorema, maka graf di Sesuai dengan teorema, maka graf di atas
atas merupakan graf tak berarah euler merupakan graf berarah euler
dimana memiliki sirkuit euler (a,g,c,b,g,e,d,f,a) dimana memiliki sirkuit
(1,2,3,4,7,3,5,7,6,5,2,6,1) dan setiap euler dan setiap simpulnya memiliki derajat
simpulnya berderajat genap. masuk dan derajat keluar yang sama.
deg (1) = 2 id (a) = od (a) yaitu 1
deg (2) = 4 id (d) = od (d) yaitu 1
deg (3) = 4 id (g) = od (g) yaitu 2
Contoh Euler Circuit
Penyelesaian!
1) a-->b-->c-->g-->k-->j-->i-->h-->d-->a
2) b-->g-->j-->f-->i-->e-->d-->b
3) a-->b-->g-->j-->f-->i-->e-->d-->
b-->c-->g-->k-->j-->i-->h-->d-->a
4) b-->e-->f-->b
5) a-->b-->e-->f-->b-->g-->j-->f-->i-->e-->
d-->b-->c-->g-->k-->j-->i-->h-->d-->a
Jadi terdapat 5 cara euler circuit pada graf
tersebut
Elementary Math
THANK YOU
FOR LISTENING!