Perpustakaan Digital ITB

Analisis sistem persamaan linear dalam konteks struktur bangunan dan jembatan merupakan permasalahan yang sering dihadapi dalam bidang teknik sipil. Kompleksitas penyelesaian sistem persamaan linear berskala besar menuntut pendekatan yang lebih efisien untuk mengurangi beban komputasi. Harper dalam (Harper, 1966) mengusulkan pendekatan melalui optimasi kombinatorial yang dikaitkan dengan Teori Graf, di mana struktur matriks koefisien direpresentasikan sebagai graf dan penyelesaian optimal dicapai melalui minimisasi bandwidth graf tersebut. Konsep bandwidth graf menjadi krusial dalam mereduksi kompleksitas komputasi, khususnya untuk graf dengan struktur simetri tinggi seperti graf sirkulan. Misalkan G = (V,E) suatu graf sederhana dan terhubung. Nilai bandwidth dari suatu pelabelan bijeksi f : V (G) ? {1, 2, . . . ,n} adalah Bf (G) := maks{|f(u)? f(v)| | (u, v) ? V (G)}. Nilai bandwidth dari graf G didefinisikan sebagai B(G) := {min Bf (G) | f pelabelan bandwidth}. Untuk sebarang dua bilangan bulat positif n dan k, graf sirkulan Cn(a1, a2, . . . ,ak) adalah suatu graf dengan V = {v0, v1, ..., vn?1} dan E(= {vivj | j ? i + az(mod n), 1 ? z ? k}. Graf sirkulan merupakan graf transitif titik. Pada penelitian ini, nilai bandwidth dari graf sirkulan Cn(a1, a2, . . . ,ak) akan ditentukan, khususnya untuk Cn(1, 4), Cn(1, 2, 4), Cn(1, 3, 4), Cn(1, 2, 3, 4) dengan n ? 25. Ditunjukkan bahwa keempat graf sirkulan tersebut memiliki nilai bandwidth sama dengan 8 untuk n ? 25. Selain itu, diberikan hasil dari nilai bandwidth untuk graf sirkulan yang lebih umum.