Tugas mandiri 4 - Matematika diskrit kampus milenial ITBI Medan

Nama : Rika aulia

Kelas : pagi

Jurusan : sistem informasi akuntansi S1

JAWABAN

A.1.Perhatikan graf G berikut

Berdasarkan graf di atas, carilah:

1. Sebuah jalan tertutup dengan panjang $9$;
2. Sebuah trail terbuka dengan panjang $9$;
3. Sebuah trail tertutup dengan panjang $7$;
4. Sebuah lintasan (path) dari simpul $a$ ke $n$;
5. Panjang sikel terpanjang dalam $G$;
6. Panjang lintasan (path) terpanjang dalam $G$;
7. Lilitan (girth) dalam $G$;
8. Sebuah graf bagian bukan rentang.

Pembahasan

Jawaban a)
Contoh jalan tertutup dengan panjang $9$ adalah jalan dengan barisan titik $icdemldkci$.
Jawaban b)
Contoh trail terbuka dengan panjang $9$ adalah jalan dengan barisan titik $agbhjickde$.
Jawaban c)
Contoh trail tertutup dengan panjang $7$ adalah jalan dengan barisan titik $cdemldkc$.
(Jawaban d)
Contoh lintasan (path) dari $a$ ke $n$ adalah jalan dengan barisan titik $agbicden$.
Jawaban e)
Panjang sikel terpanjang dalam $G$ adalah $4$. Salah satu sikel yang panjangnya demikian adalah jalan dengan barisan titik $gbijg$.
Jawaban f)
Panjang lintasan (path) terpanjang dalam $G$ adalah 12.Salah satu lintasan yang panjangnya demikian adalah jalan dengan barisan titik $agbhjickdlmen$.
Jawaban g)
Lilitan (girth) adalah panjang sikel terpendek dalam suatu graf. Lilitan pada graf $G$ di atas adalah $3$ (contoh: jalan $ick$).
Jawaban h)
Graf bagian bukan rentang adalah graf bagian yang tidak memuat seluruh titik pada graf induknya. Contohnya sebagai berikut di mana Titik selain e,f,m,n dihapus

2.Misalkan G

 adalah suatu graf yang dipresentasikan seperti gambar berikut.

Nyatakanlah matriks keterhubungan langsung dan matriks keterkaitan dari graf di atas.

Misalkan A(G)menyatakan matriks keterhubungan langsung (adjacency matrix) dari graf G, maka A(G)

 dapat dinyatakan sebagai berikut.

(aij menyatakan banyaknya sisi yang menghubungkan titik i dan titik j, misalnya a24 berarti banyak sisi yang menghubungkan

titik 2 dan 4, yaitu ada 2 sisi)Selanjutnya, misalkan I(G) menyatakan matriks keterkaitan (incidency matrix) dari graf G, maka I(G) dapat dinyatakan sebagai berikut.

Catatan: 

aij menyatakan banyaknya keterkaitan titik 

i pada sisi j. Misalkan a43bernilai 1 menyatakan ada 1 sisi, yaitu sisi 3, yang terkait dengan titik 4.3.Tentukan χ(G1), χ(G2), λ(G1), dan λ(G2)dari graf-graf yang direpresentasikan sebagai berikut.

Pembahasan

Sama seperti soal sebelumnya,

λ(G1)=1λ(G2)=2 (hilangkan 2 sisi yang mengait titik di bagian ujung)χ(G1)=1χ(G2)=2 (hilangkan 2 titik dengan sisi yang mengait titik

ujung).

B.1) R = {(A, B)} = {(1,2), (1,3), (-1,5), (0,2)}

2) R = {(M, N)} = {(10,2), (11,3), (12,2), (13,3), (13,2), (14,0)}

3) R = {(X, Y)} = {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)}