Badri, Alifiah Yulisda (2018) Kajian Dimensi Metrik Ketetanggaan dan Dimensi Metrik Ketetanggaan Lokal pada Graf Matahari dan Graf Buku Bertumpuk. Masters thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
06111650010010-Master_Thesis.pdf - Accepted Version Download (19MB) | Preview |
Abstract
Graf G didefinisikan sebagai himpunan berhingga tak kosong dari objek yang disebut simpul dan himpunan (yang mungkin kosong) yang elemennya merupakan pasangan tak terurut dari dua simpul berbeda dari graf G yang disebut sisi. Salah satu topik yang menjadi kajian dalam teori graf adalah dimensi metrik, aplikasi penerapan dalam dimensi metrik salah satunya adalah pada sistem pergerakkan robot pada suatu lintasan. Robot bergerak dari satu simpul ke simpul lainnya pada bidang dengan meminimalkan kesalahan yang terjadi dalam menerjemahkan petunjuk (kode) yang didapatkan dari simpul- simpul tersebut. Untuk bergerak robot harus memberikan petunjuk (kode) yang berbeda. Agar robot bergerak secara efisien, maka robot harus cepat untuk menerjemahkan kode simpul-simpul yang dilaluinya. sehingga simpul tersebut mempunyai jarak seminimal mungkin. Namun jika robot harus
bergerak dengan simpul-simpul pada bidang yang sangat besar,sehingga robot tidak dapat mendeteksi karena jarak yang terlalu jauh. Dalam kasus ini, robot dapat menentukan posisinya dengan memanfaatkan simpul-simpul berdasarkan ketetanggaan. Permasalahannya adalah menemukan kardinalitas minimal dari simpul-simpul lokasi yang dibutuhkan, dan dimana harus diletakkan, sehingga
robot dapat menentukan lokasinya. Solusi dari permasalahan ini adalah dimensi metrik ketetanggaan dan basis metrik ketetanggaan.
Dimensi metrik ketetanggaan yaitu setiap simpul pada graf tidak boleh memiliki representasi yang sama, sedangkan untuk dimensi metrik ketetanggaan lokal setiap simpul pada graf boleh memiliki representasi ketetanggaan yang sama dengan syarat simpul-simpul tersebut. Untuk mendapatkan nilai dimensi metrik ketetanggaan dan dimensi metrik ketetanggaan lokal pada graf Matahari dan graf Buku bertumpuk digunakan metode konstruksi dengan memperhatikan representasi masing-masing simpul yang bertetangga pada graf tersebut, sehingga diperoleh dimensi metrik ketetanggaan graf Matahari 〖dim〗_A (M_(n,m) )=nm-1 dan dimensi metrik ketetanggaan graf Buku Bertumpuk 〖dim〗_A (B_(n,m))= n(m/2) +m/2 -1, jika m genap dan 〖dim〗_A (B_(n,m))= n(m+1/2)+(m+1/2)-1, jika m gasal. Untuk dimensi metrik ketetanggaan lokal graf Matahari 〖dim〗_A,l (M_(n,m))= 2, jika n = 3,m ≥ 1, 〖dim〗_A,l (M_(n,m))= n/3, jika n > 3,m ≥ 1, dan dimensi metrik ketetanggaan lokal graf Buku Bertumpuk 〖dim〗_A,l (B_(n,m))= m/2. ================= The G graph is defined as a finite non-empty set of objects called nodes and sets whose elements are un ordered pairs of two distinct vertices of G graph called sides. One of the topics to be studied in graph theory is the metric dimension. One application in the metric dimension is the robot navigation system on a path. Robot moves from one vertex to another vertex in the field by
minimizing the errors that occur in translating the instructions (code) obtained from the vertices of that location. To move the robot must give different instructions (code). In order for the robot to move efficiently, the robot must be fast to translate the code of the nodes it passes, so that the location vertex
has a minimum distance. However, if the robot must move with the vertex location on a very large field, so the robot can not detect because the distance is too far. In this case, the robot can determine its position by utilizing location vertices based on adjacency. The problem is to find the minimum cardinality of the required location vertex, and where to put, so that the robot can determine its location. The solution to this problem is adjacency metric dimension and adjacency metric dimension bases.
Adjacency metric dimension is that each vertex in a graph can not have the same representation, whereas for the local adjacency metric dimension, each vertex in the graph may have the same adjacency representation as the terms of the vertices. Adjacency metric dimension and local adjacency metric dimension of values in the graph of the Sun and the stacked Book graph is used the construction method by considering the representation of
each adjacent vertex of the graph. Adjacency metric dimension of Sun Graph 〖dim〗_A (M_(n,m) )=nm-1 and adjacency metric dimension of Stacked Book Graph is 〖dim〗_A (B_(n,m))= n(m/2) +m/2 -1, if m even and 〖dim〗_A (B_(n,m))= n(m+1/2)+(m+1/2)-1, if m odd. For local adjacency metric dimension of Sun Graph〖dim〗_A,l (M_(n,m))= 2, if n = 3,m ≥ 1, 〖dim〗_A,l (M_(n,m))= n/3, if n > 3,m ≥ 1, and local adjacency metric dimension of Stacked Book Graph 〖dim〗_A,l (B_(n,m))= m/2.
| Item Type: | Thesis (Masters) |
|---|---|
| Additional Information: | RTMa 516.37 Bad k |
| Uncontrolled Keywords: | Graf Matahari; Graf Buku Bertumpuk; Dimensi Metrik Ketetanggaan dan Dimensi Metrik Ketetanggaan Lokal; Sun Graph; Stacked Book Graph; adjacency metric dimension and Local adjacency metric dimension |
| Subjects: | Q Science > QA Mathematics > QA166 Graph theory Q Science > QA Mathematics > QA184 Algebra, Linear Q Science > QA Mathematics > QA611.28 Metric spaces |
| Divisions: | Faculty of Mathematics, Computation, and Data Science > Mathematics > 44101-(S2) Master Thesis |
| Depositing User: | Alifiah Yulisda Badri |
| Date Deposited: | 19 Apr 2018 04:21 |
| Last Modified: | 11 Sep 2020 06:41 |
| URI: | http://repository.its.ac.id/id/eprint/50960 |
Actions (login required)
 |
View Item |