Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
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.
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.
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.
Sebuah graph terhubung adalah Euler jika dan hanya jika untuk tiap-tiap vertex derajat masuk sama dengan derajat keluar
“Dalam sebarang digraph, jumlah semua derajat keluar = jumlah semua derajat masuk = banyak busur”
Sebuah digraph Euler dapat dipecah menjadi cycles dengan tidak ada 2 cycles yang memuat busur (arcs) yang sama
Digraph Euler dan Hamilton
Barisan derajat keluar : (0,2,2,3,3)
Barisan Derajat Masuk : (1,2,2,2,3)
uv, vw, wx, ..., yz
walk ini dinotasikan dengan uvwx...yz , dan disebut sebagai perjalanan (walk) antara u dan z.
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.
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
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.