Latihan 11.

Kita sering mendefinisikan konsep-konsep teori graf menggunakan teori himpunan. Sebagai contoh, untuk graf \(G = (V, E)\) dan simpul \(v \in V\text{,}\) kita mendefinisikan
\begin{equation*} N(v) = \{u \in V \st \{v,u\} \in E\}\text{.} \end{equation*}
Kita mendefinisikan \(N[v] = N(v) \cup \{v\}\text{.}\) Tujuan soal ini adalah memahami makna semua definisi tersebut.
  1. Misalkan \(G\) adalah graf dengan himpunan simpul \(V\) dan himpunan sisi \(E\) yang diberikan oleh
    \begin{equation*} V = \{a,b,c,d,e,f\},~~E = \{\{a,b\}, \{a,e\},\{b, c\}, \{b,e\}, \{c,d\}, \{c, f\}, \{d, f\}, \{e,f\}\}\text{.} \end{equation*}
    Tentukan \(N(a)\text{,}\) \(N[a]\text{,}\) \(N(c)\text{,}\) dan \(N[c]\text{.}\)
  2. Berapakah nilai terbesar dan terkecil yang mungkin bagi \(|N(v)|\) dan \(|N[v]|\) (ukuran himpunan-himpunan tersebut) untuk graf pada bagian (a)? Jelaskan.
  3. Berikan contoh graf \(G = (V, E)\) (kemungkinan berbeda dari graf di atas) yang memenuhi \(N[v] = V\) untuk suatu simpul \(v \in V\text{.}\) Adakah graf yang memenuhi \(N[v] = V\) untuk setiap \(v \in V\text{?}\) Jelaskan.
  4. Berikan contoh graf \(G = (V,E)\) yang memenuhi \(N(v) = \emptyset\) untuk suatu \(v \in V\text{.}\) Adakah contoh graf semacam itu yang juga memenuhi \(N[u] = V\) untuk suatu simpul lain \(u \in V\text{?}\) Jelaskan.
  5. Jelaskan dengan kata-kata makna umum \(N(v)\) dan \(N[v]\text{.}\)
Petunjuk.
Anda seharusnya dapat menyimpulkan semuanya langsung dari definisi. Namun, mungkin akan membantu jika diketahui bahwa \(N\) melambangkan lingkungan.
dalam konteks