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)
|
|
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. |
 S53593-Ahmad Fikri.pdf :: Unduh
|
| No. Panggil : | S53593 |
| Entri utama-Nama orang : | |
| Subjek : | |
| Penerbitan : | Depok: Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia, 2013 |
| Program Studi : |
| 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 |
| No. Panggil | No. Barkod | Ketersediaan |
|---|---|---|
| S53593 | 14-22-88081138 | TERSEDIA |
| Ulasan: |
| Tidak ada ulasan pada koleksi ini: 20368468 |
