KELOMPOK 11. DANY FAIRUZ F

11-90

2. RIZAL ILHAFAH13-02

3. SAVIRA OKTARI13-03

4. YOFANDA PUTRA P13-05

SIRKUIT EULERIAN

Rangkaian Sebuah jalan pada graf yang bersifat tidak ada sisi yang terulang

(semua sisinya berbeda).

Lintasan Sebuah rangkaian pada graf yang bersifat tidak ada titik yang

berulang.

Dengan kata lain, lintasan sebuah jalan pada graf dengan sifat tidak ada sisi

dan titik yang berulang.

Sirkuit Sebuah rangkaian yang tertutup (diakhiri dengan titik yang sama)

DEFINISI

Lintasan Eulerian ialah lintasan yang melalui masing-masing sisi di dalam graf

tepat satu kali.

LINTASAN EULERIAN

Lintasan Euler pada graf (a) : 3, 1, 2, 3, 4, 1

Lintasan Euler pada graf (b) : 1, 2, 4, 6, 2, 3, 6, 5, 1,

3

LINTASAN EULERIAN

Sirkuit Eulerian ialah sirkuit yang mengandung semua sisi pada graf.dimana lintasan euler kembali kesimpul awal, sehingga membentuk lintasan tertutup (sirkuit)

SIRKUIT EULERIAN

Suatu graf G merupakan graf Euler (memiliki sirkuit Euler) setiap titik pada graf tersebut berderajat genap.

Graf terhubung G merupakan graf semi Euler (memiliki lintasan Euler) di dalam graf tersebut terdapat dua titik berderajat ganjil.

Suatu graf terhubung berarah G merupakan graf Euler (memiliki sirkuit Euler) setiap titik pada graf tersebut memiliki derajat masuk dan derajat keluar yang sama.

Suatu graf terhubung berarah G merupakan graf semi Euler (memiliki lintasan Euler) jika G terhubung setiap simpul pada graf tersebut memiliki derajat masuk dan derajat keluar yang sama, kecuali dua titik yaitu titik pertama memiliki derajat keluar satu lebih besar daripada derajat masuk dan titik yang terakhir memiliki derajat masuk satu lebih besar dari pada derajat keluar.

SIFAT LINTASAN & SIRKUIT

EULERIAN

Graf yang mempunyai sirkuit Eulerian disebut graf Eulerian (Eulerian

graph).

Graf yang mempunyai lintasan Euler dinamakan juga graf semi-Euler

(semi-Eulerian graph).

GRAF EULERIAN

Teorema 1

Graf tidak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan

memiliki dua buah simpul berderajat ganjil atau tidak ada simpul berderajat

ganjil sama sekali.

Teorema

(a) dua simpul berderajat 3 (simpul 3,1) (b) dua simpul berderajat 3 (simpul 1,5)

(a) dua simpul berderajat 3 (simpul 3,1)

(b) dua simpul berderajat 3 (simpul 1,5)

Teorema 2

Graf tidak berarah G adalah graf Euler (memiliki sirkuit Euler) jika dan hanya jika

setiap simpul berderajat genap.

Catatan :

Bahwa graf yang memiliki sirkuit Euler pasti mempunyai lintasan Euler, tetapi

tidak sebaliknya

(c) simpul berderajat 2 (simpul 1,4)

dan simpul berderajat 4 (simpul

2,3,5,6,7)

(d) semua simpul berderajat 4

Teorema 3

Graf berarah G memiliki sirkuit Euler jika dan hanya jika G terhubung dan setiap

simpul memiliki derajat masuk dan derajat keluar sama.

(a) Graf berarah Euler (a, g, c, b, g, e, d, f, a)

Derajat masuk = derajat keluar = derajat 2

(a)

G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul

memiliki derajat-masuk dan derajat-keluar sama kecuali dua simpul, yang

pertama memiliki derajat-keluar satu lebih besar derajatmasuk, dan yang kedua

memiliki derajat-masuk satu lebih besar dari derajat-keluar.

(a) Graf berarah Euler (a, g, c, b, g, e, d, f, a)

(b) Graf berarah semi-Euler (d, a, b, d, c, b)

Graf yang mempunyai sirkuit Euler harus memenuhi :1. Graf tersebut harus terhubung.2. Semua simpul pada graf berderajat genap.

Graf yang mempunyai lintasan Euler harus memenuhi :1. Graf tersebut harus terhubung.2. Graf memiliki tepat 2 buah simpul berderajat ganjil.

f

e d

c

b

g

a

ba

cd

SOME APPLICATIONS OF EULERIAN GRAPHS

ABDUL SAMAD ISMAIL , ROSLAN HASNI AND K. G. SUBRAMANIAN

SCHOOL OF MATHEMATICAL SCIENCES,UNIVERSITI SAINS MALAYSIA,11800

PENANG,MALAYSIA

PAPER

ABSTRAKMatematikawan jenius Swiss Leonhard Euler yang merupakan contributor produktif untuk beberapa bidang Matematika dianggap sebagai penemu konsep grafik. Grafik telah terbukti sangat berguna dalam pemodelan berbagai situasi kehidupan nyata ysng diterapkan di banyak disiplin ilmu.

PENDAHULUANPada artikel ini kita membahas pengertian dari grafik, graf Euler dan masalah aplikasi tertentu yang melibatkan grafik Euler, mulai dari masalah Konigsberg tujuh jembatan untuk masalah saat fragmen DNA perakitan, untuk menarik perhatian para peneliti muda belum tahu di wilayah studi ini. Kami juga membawa keluar beberapa koneksi sirkuit Euler dengan desain lantai tertentu, yang dikenal sebagai "kolam".

KENALAN MASALAH DAN GRAFIK Teorema handshaking : Pada grafik apapun, jumlah dari derajat simpul

adalah dua kali jumlah sisi.

CONTOH

Masing-masing derajat v, w, x, y pada gambar 3 adalah 1, 2, 3, 2 Jika kita menambahkan semua gelar ini kami telah penjumlahan = 2 + 1 + 2 + 3 + 2 = 10 Jumlah ini dua kali jumlah sisi, yaitu 5.

GRAF EULER

Bagaimana caranya kita melewati semua garis dari awal 1 titik sampai berhenti pada titik yang sama, dan melewati tepat 1 garis,manakah yang bisa ? , gambar 5a atau 5b ? Jawabannya adalah 5a,karena gambar 5a adalah euler dan gambar 5b bukan merupakan sirkuit euler

Misalnya dalam grafik pada Gambar 6, (a, b) (b, c) (c, b) (b, c) (c, d) adalah jalan dan (a, b) (b, c) (c, b) (b, c) (c, a) adalah sebuah sirkuit.

Sebuah jalur Euler dalam grafik adalah jalan yang menggunakan semua sisi grafik tetapi menggunakan masing-masing sisi tepat satu kali. Sebuah sirkuit Euler adalah sirkuit yang memiliki properti yang sama. Perhatikan bahwa di jalur Euler atau sirkuit Euler, simpul dapat dikunjungi lebih dari sekali tapi tidak pada sisi ! Sebuah sirkuit Euler dimulai dan berakhir pada simpul yang sama. Sebuah grafik yang memiliki Sirkuit Euler dikenal sebagai graf Euler. Misalnya dalam grafik pada Gambar 6, (a, b) (b, c) (c, e) (e, d) (d, c) (c, a) adalah sebuah sirkuit Euler dan karenanya grafik pada Gambar 6 merupakan Graf Euler.

MASALAH SEVEN BRIDGES

A

B

C

D

Masalah jembatan Königsberg

Apakah mungkin melalui ketujuh buah jembatan itu masing-masing tepat satu kali, dan kembali lagi ke tempat semula ?

Jawaban yang dikemukakan oleh Euler adalah :Orang tidak mungkin melalui ketujuh jembatan itu masing-masing satu kali dan kembali lagi ke tempat asal keberangkatan jika derajat setiap simpul tidak seluruhnya genap.

A

B

C

D

(3)

(3)

(5) (3)

Persoalan tukang pos Cina

Seorang tukang pos akan mengantar surat ke alamat-alamat sepanjang jalan di suatu daerah. Bagaimana ia merencanakan rute perjalanannya supaya ia melewati setiap jalan tepat sekali dan kembali lagi ke tempat awal keberangkatan

Mei Gan berasal dari China 1962 mengemukakan persoalan tukang pos Cina

Persoalan tukang pos cina tidak lain menentukan sirkuit Euler 1

2 3

4

76

PRAKITAN FRAGMEN DNASekuens yang dihasilkan dari lintasan Euler merupakan sekuens DNA target yang memiliki kemungkinan cocok dengan DNA yang sedang diteliti. Adapun lintasan Euler dari graf berarah di atas ditunjukkan pada gambar berikut

Dari lintasa Euler di atas, maka sekuens DNA target yang mungkin adalah ATGGCGTGCA dan ATGCGTGGCA.

Desain Lantai dan graf

Kambi kolam tunggal pada gambar 9 merupakan grafik Euler dengan gambar mulai dan berakhir di titik yang sama dan melewati setiap tepi grafik hanya sekali. Dalam Gambar 10, kolam Kambi Gambar 9 ditampilkan sebagai graph dengan simpul (ditandai dengan titik tebal kecil) dan tepi dan grafik ini Euler sebagai setiap simpul adalah berderajat 4.Perhatikan bahwa grafik Kambi kolam (dengan lebih dari satu Kambi) pada Gambar 11 juga akan menjadi Euler tetapi gambar kolam dengan cara itu akan selesai oleh praktisi kolam tidak akan menimbulkan sirkuit Euler.

Desain Lantai dan graf

Pada sebaliknya dalam kasus Kambi kolam tunggal itu menarik untuk dicatat, bahwa gambar kolam akan memberikan penelusuran sebuah sirkuit Euler pada grafik yang sesuai.

SEMOGA BERMANFAAT

THX GAN