Graf berarah adalah pasangan terurut dari 𝑉 dan 𝐴 dengan 𝑉 merupakan himpunan tak kosong hingga berisi simpul dan 𝐴 merupakan himpunan berisi pasangan terurut simpul yang disebut busur berarah. Suatu graf berarah disebut graf DNA jika graf tersebut dapat dilabel dengan pelabelan-(4,𝑘) yang memiliki tiga sifat, yaitu tiap tupel pada label simpul merupakan elemen dari {1,2,3,4}, tiap simpul memiliki label yang berbeda, dan busur berarah (𝑢,𝑣)∈𝐴 jika dan hanya jika 𝑙𝑖(𝑢)=𝑙𝑖−1(𝑣),𝑖=2,?,𝑘. Untuk memudahkan konstruksi pelabelan-(𝛼,𝑘), digunakan pelabelan quasi-(𝛼,𝑘) yang memiliki definisi yang mirip dengan pelabelan-(𝛼,𝑘) tetapi untuk sifat ketiga hanya berlaku satu arah, yaitu busur berarah (𝑢,𝑣)∈𝐴. Pada skripsi ini ditunjukkan bahwa graf lingkaran berarah dengan satu tali busur sembarang memiliki pelabelan quasi-(4,𝑘), line digraph dari graf lingkaran berarah dengan satu tali busur sembarang memiliki pelabelan-(4,𝑘+1), dan line digraph tersebut merupakan graf DNA.
A directed graph consists of a non empty finite set 𝑉 of vertices and a set 𝐸 of ordered pairs of distinct vertices. A directed graph is a DNA graph if it can be labeled by (4,𝑘)-labeling which has three properties, that are, every tuple in label of each vertex is element of {1,2,3,4}, all labels are different, and (𝑢,𝑣)∈𝐴 if and only if 𝑙𝑖(𝑢)=𝑙𝑖−1(𝑣),𝑖=2,?,𝑘. Constructing (𝛼,𝑘)-labeling can be done by using (𝛼,𝑘)-quasi labeling that has the same definition with (𝛼,𝑘)-labeling except for the third property that is, if (𝑢,𝑣)∈𝐴 then 𝑙𝑖(𝑢)=𝑙𝑖−1(𝑣),𝑖=2,?,𝑘. In this skripsi, it is shown that directed cycle with one arbitrary chord can be labeled by a (4,𝑘)-quasi labeling and its line digraph can be labeled by a (4,𝑘+1)-labeling and it is a DNA graph. |
S56720-Putri Metasari Pangaribuan.pdf :: Unduh