Analisis batas jumlah kartu hilang dalam rekonstruksi barisan derajat Graf dari Deck Parsial

Sari, Luki Valentina (2026) Analisis batas jumlah kartu hilang dalam rekonstruksi barisan derajat Graf dari Deck Parsial. Sarjana thesis, UIN Sunan Gunung Djati Bandung.

Preview	Text (COVER) 1_cover.pdf Download (216kB) | Preview
Preview	Text (ABSTRAK) 2_abstrak.pdf Download (348kB) | Preview
Preview	Text (SK BEBAS PLAGIARISME) 3_skbebasplagiarism.pdf Download (228kB) | Preview
Preview	Text (DAFTAR ISI) 4_daftarisi.pdf Download (265kB) | Preview
Preview	Text (BAB I) 5_bab1.pdf Download (311kB) | Preview
	Text (BAB II) 6_bab2.pdf Restricted to Registered users only Download (726kB) | Request a copy
	Text (BAB III) 7_bab3.pdf Restricted to Registered users only Download (797kB) | Request a copy
	Text (BAB IV) 8_bab4.pdf Restricted to Registered users only Download (296kB) | Request a copy
	Text (DAFTAR PUSTAKA) 9_daftarpustaka.pdf Restricted to Registered users only Download (201kB) | Request a copy
	Text (LAMPIRAN) 10_lampiran.pdf Restricted to Repository staff only Download (220kB) | Request a copy

Abstract

INDONESIA : Penelitian ini membahas rekonstruksi barisan derajat graf dari deck parsial, yaitu deck yang kehilangan sejumlah kartu akibat penghapusan titik pada graf asal. Hilangnya kartu menyebabkan informasi mengenai graf asal menjadi tidak lengkap sehingga diperlukan analisis untuk menentukan jumlah kartu yang masih dapat hilang dengan tetap memungkinkan barisan derajat direkonstruksi. Penelitian ini bertujuan menganalisis batas jumlah kartu yang hilang dalam rekonstruksi barisan derajat graf dari deck parsial. Metode yang digunakan adalah studi literatur dan analisis teoritis terhadap konsep teori graf, barisan derajat, rekonstruksi graf, dan deck parsial. Hasil analisis menunjukkan bahwa barisan derajat masih dapat direkonstruksi ketika paling banyak satu kartu hilang. Selain itu, untuk graf dengan titik dan derajat rata-rata yang dibatasi oleh d , diperoleh batas jumlah kartu hilang sebesar k\ \leq \ \frac{n}{{10}^{4}d^{3}}, dengan penerapan batas tersebut pada graf pohon sebagai ilustrasi, serta dengan d=2, menghasilkan k\ \leq \ \frac{n}{80000}. Hasil perhitungan menunjukkan bahwa semakin besar orde graf, semakin besar jumlah kartu yang secara teoritis masih dapat hilang dengan jaminan rekonstruksi, sedangkan semakin besar batas atas derajat rata-rata, semakin kecil jumlah kartu yang dapat hilang. Dengan demikian, jumlah kartu yang dapat hilang dengan jaminan rekonstruksi bergantung pada orde dan karakteristik derajat rata-rata graf, serta batas yang diperoleh merupakan batas jaminan teoritis, bukan batas maksimum yang pasti berlaku pada setiap graf. ENGLISH : This study investigates the reconstruction of graph degree sequences from a partial deck, which is a deck in which some cards are missing due to vertex deletion from the original graph. The loss of cards causes incomplete information about the original graph, necessitating an analysis to determine the number of cards that can be missing while still allowing the degree sequence to be reconstructed. This study aims to analyze the bound on the number of missing cards in the reconstruction of graph degree sequences from a partial deck. The method used is a literature study and theoretical analysis of concepts related to graph theory, degree sequences, graph reconstruction, and partial decks. The analysis shows that the degree sequence can still be reconstructed when at most one card is missing. Furthermore, for a graph with vertices and average degree bounded above by d , the bound on the number of missing cards is given by k\ \leq \ \frac{n}{{10}^{4}d^{3}}, applying this bound to a tree graph as an illustration, with d=2, gives \mathrm{k}\ \leq \ \frac{\mathrm{n}}{80000}. The results show that as the order of the graph increases, the number of cards that can theoretically be missing while reconstruction is guaranteed also increases, whereas a larger upper bound on the average degree results in a smaller number of cards that can be missing. Thus, the number of missing cards for which reconstruction is guaranteed depends on the order and average-degree characteristics of the graph, and the resulting bound represents a theoretical guaranteed bound rather than a maximum bound that necessarily applies to every graph.

Actions (login required)

View Item