Lewati ke konten utama
Gambar logo

Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Oscar Levin

Pratinjau cetak

Ukuran kertas

Lembar Kerja Aktivitas Pratinjau

Graf mana saja di bawah ini yang memiliki jejak Euler? Graf mana saja yang memiliki sirkuit Euler?
🔗
Sebuah pohon dengan 7 simpul dan 6 sisi. Simpul bawah berderajat 2 dan terhubung ke dua simpul tengah yang masing-masing berderajat 3 serta masing-masing terhubung ke dua daun.
Sebuah graf yang terdiri atas 6 simpul dan 10 sisi
Sebuah graf dengan 7 simpul dan 9 sisi
\begin{equation*} G_1 \end{equation*}
🔗
\begin{equation*} G_2 \end{equation*}
🔗
\begin{equation*} G_3 \end{equation*}
🔗
Sebuah graf dengan enam simpul. Empat simpul membentuk persegi, satu simpul lain berada di tengah persegi, dan simpul terakhir berada di tengah, di atas persegi. Sisi-sisi membentuk batas persegi dan menghubungkan setiap sudut dengan simpul pusat. Kedua simpul atas pada persegi bertetangga dengan simpul di atas persegi.
Sebuah graf dengan tujuh simpul. Empat simpul membentuk sudut-sudut persegi; tiga simpul lainnya berada pada baris tengah, yaitu satu di kiri, satu di pusat, dan satu di kanan persegi. Sisi-sisi membentuk batas persegi. Setiap simpul pada persegi bertetangga dengan dua simpul pada baris tengah yang paling dekat dengannya.
Sebuah graf dengan 8 simpul dan 12 sisi yang merepresentasikan kubus.
\begin{equation*} G_4 \end{equation*}
🔗
\begin{equation*} G_5 \end{equation*}
🔗
\begin{equation*} G_6 \end{equation*}
🔗
1.
\(G_1\) memiliki
. \(G_2\) memiliki
. \(G_3\) memiliki
🔗
\(G_4\) memiliki
. \(G_5\) memiliki
. \(G_6\) memiliki
🔗
🔗
2.
Tuliskan barisan derajat graf-graf di atas.
🔗
\(G_1\text{:}\)
🔗
\(G_2\text{:}\)
🔗
\(G_3\text{:}\)
🔗
\(G_4\text{:}\)
🔗
\(G_5\text{:}\)
🔗
\(G_6\text{:}\)
🔗
Apa kemungkinan hubungan antara barisan derajat dan keberadaan jejak atau sirkuit Euler?
🔗
🔗
3.
Salah satu cara menuliskan jejak atau sirkuit Euler adalah mencantumkan sisi-sisinya secara berurutan. Setiap sisi berupa pasangan simpul, dan untuk menunjukkan arah kita melintasi sisi tersebut, kita dapat menuliskannya sebagai pasangan terurut alih-alih sebagai himpunan. Sebagai contoh, perhatikan graf berikut:
🔗
Lintasan dengan 4 simpul berlabel a, b, c, d yang terhubung dalam urutan tersebut oleh tiga sisi.
Terdapat dua jejak Euler yang dapat kita tuliskan:
🔗
\begin{equation*} (a,b), (b,c), (c,d) \qquad \text{atau} \qquad (d,c), (c,b), (b,a) \text{.} \end{equation*}
🔗
(a)
Tuliskan sebuah jejak Euler untuk graf di bawah ini.
🔗
Sebuah graf dengan 6 simpul berlabel a hingga f. Simpul a dan f berderajat satu dan masing-masing digambar di ujung kiri dan kanan. Simpul-simpul lainnya membentuk belah ketupat. Sisi-sisinya adalah (a,b), (b,c), (b,e), (b,d), (c,e), (d,e), dan (e,f).
Untuk setiap simpul, tuliskan derajatnya dan berapa kali simpul tersebut muncul dalam daftar sisi Anda.
🔗
simpul derajat banyak kemunculan
\(a\)
\(b\)
\(c\)
\(d\)
\(e\)
\(f\)
🔗
(b)
Misalkan Anda memiliki graf dengan barisan derajat \((4,2,2,2,2)\) yang mempunyai jejak Euler. Berapa kali nama simpul berderajat 4 akan muncul dalam daftar sisi Anda?
🔗
🔗
(c)
Misalkan Anda memiliki graf dengan jejak Euler yang ditulis sebagai daftar sisi. Apa yang dapat Anda simpulkan tentang simpul yang muncul tepat 3 kali dalam daftar tersebut? Pilih semua pernyataan yang mungkin benar.
🔗
  • Simpul tersebut dapat muncul pada awal dan akhir jejak Euler.
    🔗
    🔗
  • Simpul tersebut dapat muncul pada awal atau akhir jejak Euler, tetapi tidak keduanya.
    🔗
    🔗
  • Simpul tersebut hanya dapat muncul di tengah jejak Euler.
    🔗
    🔗
  • Simpul tersebut sama sekali tidak dapat muncul dalam jejak Euler.
    🔗
    🔗
  • Harus ada simpul berderajat ganjil lain yang juga muncul pada awal atau akhir jejak Euler.
    🔗
    🔗
🔗
🔗
🔗
🔗
SblmTopLnjt
Umpan Balik