Podcast
Questions and Answers
Dua graf dikatakan sama jika dan hanya jika mereka memiliki himpunan simpul dan busur yang identik.
Dua graf dikatakan sama jika dan hanya jika mereka memiliki himpunan simpul dan busur yang identik.
True (A)
Jika ada fungsi injektif dari himpunan simpul graf $G$ ke himpunan simpul graf $H$ yang mempertahankan ketetanggaan, maka $G$ dan $H$ adalah isomorfis.
Jika ada fungsi injektif dari himpunan simpul graf $G$ ke himpunan simpul graf $H$ yang mempertahankan ketetanggaan, maka $G$ dan $H$ adalah isomorfis.
True (A)
Jika graf $G$ dan $G'$ isomorfis, maka jumlah simpul di $G$ harus lebih besar dari jumlah simpul di $G'$.
Jika graf $G$ dan $G'$ isomorfis, maka jumlah simpul di $G$ harus lebih besar dari jumlah simpul di $G'$.
False (B)
Jika graf $G$ dan $G'$ isomorfis, urutan graf $G$ sama dengan urutan graf $G'$ .
Jika graf $G$ dan $G'$ isomorfis, urutan graf $G$ sama dengan urutan graf $G'$ .
Jika dua graf memiliki urutan dan ukuran yang sama, maka kedua graf tersebut pasti isomorfis.
Jika dua graf memiliki urutan dan ukuran yang sama, maka kedua graf tersebut pasti isomorfis.
Jika dua graf memiliki urutan derajat yang berbeda, mereka dapat menjadi isomorfis.
Jika dua graf memiliki urutan derajat yang berbeda, mereka dapat menjadi isomorfis.
Jika dua graf memiliki degree sequence yang sama, maka mereka pasti isomorfis.
Jika dua graf memiliki degree sequence yang sama, maka mereka pasti isomorfis.
Jika $G$ adalah graf bipartit dan $G'$ isomorfis dengan $G$, maka $G'$ juga merupakan graf bipartit.
Jika $G$ adalah graf bipartit dan $G'$ isomorfis dengan $G$, maka $G'$ juga merupakan graf bipartit.
Jika $G$ terhubung dan $G'$ isomorfis dengan $G$, maka $G'$ mungkin tidak terhubung.
Jika $G$ terhubung dan $G'$ isomorfis dengan $G$, maka $G'$ mungkin tidak terhubung.
Dalam memeriksa isomorfisma, hanya menghitung jumlah simpul dan busur yang diperlukan.
Dalam memeriksa isomorfisma, hanya menghitung jumlah simpul dan busur yang diperlukan.
Graf dengan lingkaran pendek selalu isomorfis dengan graf lain dengan lingkaran pendek.
Graf dengan lingkaran pendek selalu isomorfis dengan graf lain dengan lingkaran pendek.
Setiap dua graf berlabel dengan jumlah simpul yang sama selalu dapat dibuat menjadi isomorfik melalui pelabelan yang tepat dan rotasi.
Setiap dua graf berlabel dengan jumlah simpul yang sama selalu dapat dibuat menjadi isomorfik melalui pelabelan yang tepat dan rotasi.
Jika dua graf tidak berlabel dapat dilabeli sehingga graf tersebut identik, maka graf tersebut isomorfis.
Jika dua graf tidak berlabel dapat dilabeli sehingga graf tersebut identik, maka graf tersebut isomorfis.
Graf tidak berlabel memungkinkan jumlah graf yang mungkin lebih banyak dibandingkan dengan graf berlabel untuk jumlah simpul tertentu.
Graf tidak berlabel memungkinkan jumlah graf yang mungkin lebih banyak dibandingkan dengan graf berlabel untuk jumlah simpul tertentu.
Ada hanya satu graf terhubung tidak berlabel dengan 2 simpul.
Ada hanya satu graf terhubung tidak berlabel dengan 2 simpul.
Jika graf $G_1$ dan $G_2$ tidak isomorfik, maka komplemennya, $\overline{G_1}$ dan $\overline{G_2}$, juga tidak isomorfik.
Jika graf $G_1$ dan $G_2$ tidak isomorfik, maka komplemennya, $\overline{G_1}$ dan $\overline{G_2}$, juga tidak isomorfik.
Jika graf $G$ self-complementary, maka $G$ memiliki jumlah simpul yang sama dengan komplemennya.
Jika graf $G$ self-complementary, maka $G$ memiliki jumlah simpul yang sama dengan komplemennya.
Graf self-complementary dengan order $n$ harus memenuhi $n \equiv 0 \pmod{4}$ atau $n \equiv 3 \pmod{4}$.
Graf self-complementary dengan order $n$ harus memenuhi $n \equiv 0 \pmod{4}$ atau $n \equiv 3 \pmod{4}$.
Relasi isomorfisma pada himpunan semua graf hanya bersifat refleksif.
Relasi isomorfisma pada himpunan semua graf hanya bersifat refleksif.
Jika graf $G_1$ isomorfis dengan $G_2$ dan $G_2$ isomorfis dengan $G_3$, maka $G_1$ tidak dapat isomorfis dengan $G_3$.
Jika graf $G_1$ isomorfis dengan $G_2$ dan $G_2$ isomorfis dengan $G_3$, maka $G_1$ tidak dapat isomorfis dengan $G_3$.
Flashcards
Apa itu graf yang sama?
Apa itu graf yang sama?
Dua graf yang memiliki himpunan simpul dan busur yang sama.
Apa itu isomorfisma graf?
Apa itu isomorfisma graf?
Fungsi satu-satu antara simpul-simpul dua graf yang mempertahankan hubungan ketetanggaan.
Bagaimana jumlah simpul dan busur pada graf isomorfis?
Bagaimana jumlah simpul dan busur pada graf isomorfis?
Jika G dan G' isomorfis, maka jumlah simpul dan busur pada kedua graf harus sama.
Bagaimana derajat simpul pada graf isomorfis?
Bagaimana derajat simpul pada graf isomorfis?
Signup and view all the flashcards
Apa yang sama antara graf isomorfis?
Apa yang sama antara graf isomorfis?
Signup and view all the flashcards
Apa hubungan isomorfisma dengan degree sequence?
Apa hubungan isomorfisma dengan degree sequence?
Signup and view all the flashcards
Bagaimana sifat bipartit dan keterhubungan dipertahankan dalam isomorfisma?
Bagaimana sifat bipartit dan keterhubungan dipertahankan dalam isomorfisma?
Signup and view all the flashcards
Bagaimana cara memeriksa isomorfisma graf?
Bagaimana cara memeriksa isomorfisma graf?
Signup and view all the flashcards
Apa itu graf self-complementary?
Apa itu graf self-complementary?
Signup and view all the flashcards
Apa sifat isomorfisma sebagai relasi?
Apa sifat isomorfisma sebagai relasi?
Signup and view all the flashcards
Study Notes
Isomorfisma Graf
- Dua graf dianggap sama jika mereka memiliki himpunan simpul dan busur yang identik, dengan syarat G = H jika V(G) = V(H) dan E(G) = E(H).
- Dua graf G(V, E) dan G'(V', E') dikatakan isomorfis jika terdapat fungsi satu-satu f: V → V', sehingga untuk setiap u, v ∈ V, uv ∈ E ↔ f(u)f(v) ∈ E'.
- Fungsi f ini disebut sebagai isomorfisma.
- Jika G(V, E) dan G'(V', E') isomorfis, maka jumlah simpul di kedua graf tersebut sama, yaitu |V| = |V'|, dan jumlah busurnya juga sama, yaitu |E| = |E'|.
- Jika G(V, E) dan G'(V', E') isomorfis, maka derajat setiap simpul di G akan sama dengan derajat simpul yang sesuai di G'.
- Jika dua graf isomorfis, urutan (order), ukuran (size), dan derajat simpul-simpulnya sama.
- Jika dua graf isomorfis, maka degree sequence-nya juga sama.
- Teorema: Jika G dan G' isomorfis, maka G bipartit jika dan hanya jika G' bipartit, dan G terhubung jika dan hanya jika G' terhubung.
- Pemeriksaan isomorfisma melibatkan pengecekan jumlah simpul dan busur, urutan derajat (degree sequence), dan fitur khusus seperti lingkaran pendek pada graf.
Isomorfisma Graf Berlabel
- Dua graf berlabel G(V, E) dan G'(V', E') dengan fungsi pelabelan l:V→L dan l':V'→L dikatakan isomorfis jika memenuhi definisi graf isomorfis dan l(v) = l'(f(v)).
- Isomorfisma pada graf berlabel dengan struktur yang sama dapat terjadi karena rotasi atau refleksi.
Isomorfisma Graf Tidak Berlabel
- Dua graf tidak berlabel isomorfis jika keduanya dapat dilabel ulang sehingga menjadi graf yang identik.
Menghitung Graf (Counting Graphs)
- Menghitung jumlah graf berlabel dan tidak berlabel dengan jumlah simpul tertentu.
- Menghitung jumlah graf terhubung tidak berlabel dengan 1, 2, 3, 4, atau 5 simpul.
Isomorfisma dan Komplemen
- Teorema: Graf G₁ dan G₂ isomorfis jika dan hanya jika komplemennya, G₁ dan G₂, juga isomorfis.
- Graf G disebut self-complementary jika isomorfis dengan komplemennya sendiri (G ≈ G).
- Graf G dengan order n self-complementary memiliki ukuran G = n(n-1) / 4.
- n ≡ 0 (mod 4) atau n ≡ 1 (mod 4)
Isomorfisma Sebagai Relasi
- Isomorfisma adalah relasi ekivalen pada himpunan semua graf.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
