Untuk sebarang bilangan bulat positif 𝑎≥2 dan 𝑛≥1 yang diberikan, dapat di-lakukan konstruksi graf de Bruijn yang didefinisikan sebagai graf berarah dengan banyaknya simpul 𝑎𝑛−1, panjang label simpulnya 𝑛−1, banyaknya busur berarah 𝑎𝑛, dan panjang label busurnya 𝑛. Karena setiap graf de Bruijn merupakan graf Euler maka dapat ditentukan sirkuit Euler dengan label minimal. Barisan de Bruijn yang dibangun oleh 𝑛 dinyatakan oleh Sirkuit Euler dengan label minimal. Graf de Bruijn tidak mudah dikonstruksi untuk 𝑛 yang berukuran besar, kesulitan selanjutnya dijumpai pada penentuan sirkuit Euler dengan label minimal. Oleh karena itu, pada tesis ini akan diberikan metode alternatif sebagai solusi konstruk-si barisan de Bruijn dengan menggunakan teorema Fredicksen dan Maiorana. Teo-rema ini menjamin keberadaan barisan de Bruijn untuk setiap 𝑛 yang diberikan dengan merangkai Lyndon word yang terurut secara Lexicographic. Hasil kajian ini memberikan kontribusi terhadap langkah-langkah untuk merangkai sebarang Lyndon word dari suatu alfabet 𝐴 dengan panjang 𝑛, sehingga diperoleh barisan de Bruijn yang dibangun oleh 𝑛. Sebagai akhir pembahasan akan diberikan kaitan antara graf de Bruijn dan barisan de Bruijn.
Given any integer 𝑎≥2 and 𝑛≥1, de Bruijn graph can be constructed. De Bruijn graph is a digraph with 𝑎𝑛−1 vertices, each has 𝑛−1 length label, and 𝑎𝑛 arc, each has 𝑛 length label. Since each of de Bruijn graph is an Eulerian graph, then we can find an Eulerian circuit with minimal label. De Bruijn sequence which is spanned by 𝑛 can be representated by Eulerian circuit with minimal la-bel. It is not easy to construct de Bruijn graph for 𝑛 large, it is implied difficulties to find Eulerian circuit with minimal label. In this ?thesis? will be presented alter-native method on how to construct de Bruijn sequence using Fredicksen and Mai-orana Theorem. This theorem guarantees the existence of de Bruijn sequence for any given 𝑛 using concatenation Lexicographic ordered of Lyndon word. The re-search result has contributed on construct step by step to obtain concatenation any Lyndon word of length 𝑛 of alphabet 𝐴, so we obtain de Bruijn sequence span by 𝑛. For conclusi, will be given correlations between de Bruijn graph and de Bruijn sequences. |
