UI - Skripsi Membership :: Kembali

UI - Skripsi Membership :: Kembali

Karakteristik matriks adjacency dalam penentuan line digraph = Characterization of an adjacency matrix in determining line digraph

Ahmad Fikri; (Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia, 2013)

 Abstrak

Misalkan 𝐷=𝐷(𝑉,𝐴) adalah graf berarah dengan |𝑉| simpul dan |𝐴| busur berarah. Line digraph 𝐷′=𝐷′(𝑉′,𝐴′) dari 𝐷 merupakan graf berarah dengan himpunan simpul 𝑉′=𝐴 dan untuk dua simpul 𝑥,𝑦 di 𝐷′, 𝑥 bertetangga ke 𝑦 jika dan hanya jika pada 𝐷 ujung busur berarah 𝑥 merupakan asal dari busur berarah 𝑦. Tidak semua graf berarah merupakan line digraph dari suatu graf berarah. Aigner (1967) memberikan teorema tentang syarat perlu dan cukup agar suatu graf berarah merupakan line digraph dari suatu graf berarah. Pada skripsi ini dibahas karakteristik matriks adjacency suatu graf berarah supaya merupakan line digraph. Karakteristik yang diperoleh dari pengembangan teorema Aigner ini dapat digunakan untuk mengkonstruksi graf asal dari suatu line digraph. Di sini juga dibahas keterkaitan antara matriks adjacency line digraph dengan matriks incidence graf asal.

Let 𝐷=𝐷(𝑉,𝐴) be a directed graph with |𝑉| vertices and |𝐴| arcs. Line digraph 𝐷′=𝐷′(𝑉′,𝐴′) of 𝐷 is a directed graph with vertex set 𝑉′=𝐴 and for two vertices 𝑥,𝑦 in 𝐷′, 𝑥 adjacent to 𝑦 if and only if on 𝐷 the tail of arc 𝑥 is the origin of arc 𝑦. Not every directed graph is a line digraph of a directed graph. Aigner (1967) gave a theorem about necessary and sufficient condition for a directed graph to be a line digraph of a directed graph. This research gives the adjacency matrix’s characteristic of a directed graph to be a line digraph of a directed graph. This characteristic is developed based on Aigner’s theorem and the characteristic can be used to construct the origin graph of a line digraph. This research also gives a connection between adjacency matrix of a line digraph with incidence matrix of the original graph.

 File Digital: 1

Shelf
 S53593-Ahmad Fikri.pdf :: Unduh

LOGIN required

 Metadata

Jenis Koleksi : UI - Skripsi Membership
No. Panggil : S53593
Entri utama-Nama orang :
Program Studi :
Subjek :
Penerbitan : Depok: Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia, 2013
Bahasa : ind
Sumber Pengatalogan :
Tipe Konten :
Tipe Media :
Tipe Carrier :
Deskripsi Fisik : xii, 60 hlm. : il., ; 28 cm
Naskah Ringkas :
Lembaga Pemilik : Universitas Indonesia
Lokasi : Perpustakaan UI, Lantai 3
  • Ketersediaan
  • Ulasan
  • Sampul
No. Panggil No. Barkod Ketersediaan
S53593 14-22-88081138 TERSEDIA
Ulasan:
Tidak ada ulasan pada koleksi ini: 20368468
Cover