Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas konsep matriks kehadiran dalam Teori Graf, yang merupakan bentuk matriks yang menyatakan hubungan antara simpul dan busur dalam graf. Matriks kehadiran tidak selalu berbentuk persegi, melainkan tergantung pada jumlah simpul dan busur dalam graf. Setiap baris mewakili simpul dan setiap kolom mewakili busur, dengan elemen 1 menunjukkan hubungan antara simpul dan busur tersebut. Pada kasus pseudograph dengan loop dan busur ganda, penggambaran dalam matriks kehadiran juga berbeda. Dengan cara ini, matriks kehadiran memberikan representasi yang jelas tentang hubungan antara simpul dan busur dalam sebuah graf.

Bentuk matriks yang merepresentasikan graf itu juga ada beberapa,

tadi kita sudah bahas tentang matriks ketetanggaan.

Ada lagi matriks lain yang kita sebut sebagai matriks kehadiran,

dia menyatakan hubungan antara simpul dan busur,

kalau tadi kan simpul dengan simpul, kalau ini simpul dan busur.

Jadi kalau matriks ketetanggaan bentuknya adalah persegi

dan dia adalah simetri kalau untuk graf sederhana yang tak berarah,

tapi kalau matriks kehadiran itu dia bentuknya tidak selalu persegi,

tapi dia bujur sangkar tergantung pada banyaknya simpul dan banyaknya busur.

Jadi di sini barisnya itu mewakili simpul, kolomnya mewakili busur,

jadi di dalam graf ini contohnya kita punya 5 simpul dan 6 busur.

Nanti kita lihat busur E1 di sini itu membuat 2 simpul bertetangga yang mana,

Kita lihat di gambar E1 itu menghubungkan antara V1 dengan V4,

jadi di baris V1 dengan V4 kita tulis 1, yang lainnya 0.

Kemudian kita lihat lagi E2, E2 di grafnya itu dia menghubungkan siapa?

Di sini menghubungkan V1 dan V5, berarti kita taruh 1 di V1 dan 1 di V5, di baris 1 dengan 5.

Dengan cara yang sama kita nanti akan dapat untuk representasi yang E3, E4, E5, E6,

jadi kita lihat setiap kolomnya di sini hanya ada 2 elemen 1,

kalau barisnya itu nanti kalau dijumlahkan akan memperlihatkan derajatnya dia berapa,

karena untuk V1 busur mana saja yang menghubungkan si V1 dengan simpul yang lain,

kalau V2 itu ada 3 lewat E3, lewat E4, sama lewat E6, jadi nanti derajatnya 3.

Kalau untuk pseudograph yang ada loopnya tadi dan juga ada busur ganda,

dalam kasus ini dia yang tidak berarah, jadi kita bisa lihat juga khusus bedanya kan yang loop,

di sini E1 nya itu loop berarti dia akan menunjukkan 1 ke 1,

sehingga dia cuma dituliskan 1 di baris itu tidak ada pasangan yang lain.

Kalau di sini E2, E2 itu menghubungkan V1 ke V2, jadi seperti biasa V1 V2,

E3 juga V1 V2, jadi ada 2 kolom yang sama tapi caranya itu sama dengan yang lain.