Introducing 

Prezi AI.

Your new presentation assistant.

Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.

Loading…
Transcript

Derajat Vertex

Derajat keluar (out-degree) dari titik v adalah banyak garis yang keluar dari v yang dinotasikan outdeg v.

Derajat masuk (in degree) dari titik v adalah banyak busur masuk yang masuk ke titik v yang dinotasikan indeg v

Closed walk pada digraph adalah urutan busur (arcs) dari bentuk

uv, vw, wx, ..., yz, zu

yang dimulai dan berakhir pada vertex yang sama.

Closed Trail adalah closed walk yang semua busurnya (arcs) berbeda.

Cycle adalah closed walk yang semua vertex tengahnya berbeda.

  • Sebuah graph terhubung adalah euler jika terdiri dari sebuah closed trail yang memasukkan setiap busur (arc). Trail yang seperti itu disebut Eulerian Trail.
  • Sebuah graph terhubung adalah Hamilton jika terdiri dari sebuah cycle yang mmasukkan setiap vertex, cycle yang seperti itu disebut Hamilton Cycle.

Lintasan dan Sikel

  • Sebuah digraph terhububung jika graph pokoknya terhubung dan tidak terhubung jika sebaliknya.
  • Sebuah graph terhubung kuat jika ada path antara tiap-tiap pasangan vertex

Derajat Vertex, Lintasan Sikel, Digraph Euler dan Hamilton

Barisan derajat keluar (out-degree sequence) dari digraph D adalah barisan yang diperoleh dengan mendaftar derajat keluar dari D dalam urutan meningkat dan perulangan jika diperlukan.

Barisan derajat masuk (in-degree sequence) dari digraph D adalah barisan yang diperoleh dengan mendaftar derajat masuk dari D dalam urutan meningkat dan perulangan jika diperlukan.

Soal

BUKTI

Diketahui G digraph terhubung

Misalkan G digraph yang setiap vertexnya memiliki derajat masuk dan derajat keluar yang sama berarti setiap vertex berderajat genap. Berdasarkan teorema 3.2 maka G Euler.

Jika digraph terhubung adalah Euler maka setiap titik memiliki derajat masuk dan derajat keluar yang sama

Jika setiap vertex pada digraph terhubung memiliki derajat masuk dan derajat keluar yang sama maka digraph tersebut Euler

Diketahui G adalah digraf terhubung.

Misalkan G adalah digraf euler, maka terdapat trail euler. Ketika trail melewati suatu vertex berarti trail tersebut melalui 2 busur yaitu busur masuk dan busur keluar. Karena G merupakan graf Euler maka setiap busur hanya boleh dilalui sekali, sehingga setiap vertex memiliki derajat masuk dan derajat keluar yang sama.

TEOREMA 4.2

BUKTI

Sebuah graph terhubung adalah Euler jika dan hanya jika untuk tiap-tiap vertex derajat masuk sama dengan derajat keluar

Pada sebarang digraph, tiap busur (arcs) memiliki 2 akhir sehingga mengkontribusikan 1 untuk derajat keluar dan 1 untuk derajat masuk. Akibatnya jumlah derajat masuk dan jumlah derajat keluar sama dengan jumlah busur (arcs)

Teorema 4.1 : Handshaking Dilemma

“Dalam sebarang digraph, jumlah semua derajat keluar = jumlah semua derajat masuk = banyak busur”

TEOREMA 4.3

Sebuah digraph Euler dapat dipecah menjadi cycles dengan tidak ada 2 cycles yang memuat busur (arcs) yang sama

BUKTI

Digraph Euler dan Hamilton

NAMA ANGGOTA

ANANDA SYAHRIYA R.

MITA AKBAR S.

MUHAMAD NOR

WENNY FAIZZATUNNISA

Barisan derajat keluar : (0,2,2,3,3)

Barisan Derajat Masuk : (1,2,2,2,3)

  • suatu walk of length k pada digraph adalah urutan dari k busur (arcs) dari bentuk

uv, vw, wx, ..., yz

walk ini dinotasikan dengan uvwx...yz , dan disebut sebagai perjalanan (walk) antara u dan z.

  • Trail adalah walk yang semua busurnya (arcs) berbeda, tetapi vertexnya boleh sama.
  • Path adalah walk yang semua busur (arcs) dan semua vertex berbeda.

Pada digraph disamping closed walk uvwyvzu adalah closed trail yang bukan cycle, karena titik v terjadi 2 kali. Sedangkan closed trail zz,wxw, vwxyv dan uvwxyzu adalah cycle.

  • Digraph (a) euler- Eulerian trail: a b c d e f b g c e g f a dan Hamilton- sebuah Hamiltonian cycle : a b c d e g f a;
  • Digraph (b) euler- Eulerian trail: b c g f e g b tapi bukan Hamilton
  • Digraph (c) bukan euler dan Hamilton- sebuah Hamiltonian cycle : b c d e g f b;
  • Digraph (d) bukan euler dan bukan Hamilton

indeg v1 = 1

indeg v2 = 2

indeg v3 = 2

indeg v4 = 2

indeg v5 = 3

outdeg v1 = 2

outdeg v2 = 3

outdeg v3 = 3

outdeg v4 = 2

outdeg v5 = 0

  • Graph (a) tidak terhubung karena graph pokoknya tidak terhubung
  • Graph (b) terhubung tidak kuat
  • Graph (c) terhubung dengan kuat ada path yang menggabungkan semua pasangan titik.

Pada diagram berikut, walk vwxyvwyzzu adalah walk of lenght 9 dari vertex v ke u yang mengandung busur (arc) vw dua kali dan vertex v, w, y, dan z dua kali. walk uvwyvz adalah suatu trail yang bukan path, karena vertex v terjadi dua kali. Sedangkan walk vwxyz tidak terjadi pengulangan vertex, dan karena itu disebut path.

Learn more about creating dynamic, engaging presentations with Prezi