Rank minimum dari graf G pada field Z_2

INDONESIA:

Rank minimum dari suatu graf pada field Z_2 adalah rank terkecil dari matriks simetri dengan unsur-unsur pada field Z_2 dari suatu graf dimana elemen ke-ij adalah satu jika titik i terhubung dengan titik j dan nol jika titik i tidak terhubung dengan titik j, sedangkan jika i = j maka nilainya diabaikan dengan memuat unsur-unsur pada field Z_2 yaitu {0,1}. Rank minimum dari suatu graf pada field Z_2 dinotasikan dengan mr(S_G^(Z_2)). Penentuan rank minimum dari suatu graf dengan mencari matriks adjacency, kemudian dikembangkan menjadi beberapa matriks simetri dengan unsur-unsur pada field Z_2 serta dicari rank minimum dengan operasi baris tereduksi dengan bantuan program Matlab. Pada skripsi ini akan dikaji rank minimum dari matriks simetri dengan unsur-unsur pada pada field Z_2 dari graf path (P_n), graf komplit (K_n), graf star (S_n), dan graf sikel (C_n), kemudian hasil yang diperoleh adalah
a. Teorema: Rank minimum dari graf path (P_n) pada field Z_2 adalah mr(S_(P_n)^(Z_2))=n-1 dengan n ≥ 2 dan n ∈ N.
b. Teorema: Rank minimum dari graf komplit (K_n) pada field Z_2 adalah mr(S_(K_n)^(Z_2))=1 dengan n ≥ 2 dan n ∈ N.
c. Teorema: Rank minimum dari graf star (S_n) pada field Z_2 adalah mr(S_(S_n)^(Z_2))=2 dengan n ≥ 3 dan n ∈ N.
d. Konjektur: Rank minimum dari graf sikel (C_n) pada field Z_2 adalah mr(S_(C_n)^(Z_2))=n-2 dengan n ≥ 3 dan n ∈ N, dan n genap.

ENGLISH:

The minimum rank of a graph on field Z_2 is the smallest rank of the symmetric matrices with the element in the field Z_2 of a graph in which the element ij entry is one if edge i connected with edge j and zero if edge i is not connected with the edge j, while if i = j is ignored by loading the elements in the field Z_2 {0,1}. The minimum rank of a graph on field Z_2 is denoted by mr(S_G^(Z_2)). Determination of the minimum rank of a graph by finding adjacency matrices, then it is developed into a symmetric matrices with the elements in the field Z_2 and looked for the minimum rank with reduced row echelon and with the help of Matlab programe. This thesis will be reviewed the minimum rank of symmetric matrices with the elements in the field Z_2 of a path graph (P_n), complete graph (K_n), star graph (S_n), and cycle graph (C_n), then the results obtained are
a. Theorem: The minimum rank of a path graph (P_n) on the field Z_2 is mr(S_(P_n)^(Z_2))=n-1 with n ≥ 2 and n ∈ N.
b. Theorem: The minimum rank of a complete graph (K_n) on the field Z_2 is mr(S_(K_n)^(Z_2))=1 with n ≥ 2 and n ∈ N.
c. Theorem: The minimum rank of a star graph (S_n) on the field Z_2 is mr(S_(S_n)^(Z_2))=2 with n ≥ 3 and n ∈ N.
d. Conjecture: The minimum rank of a cycle graph (C_n) on the field Z_2 is mr(S_(C_n)^(Z_2))=n-2 with n ≥ 3, n ∈ N, and n even.