Boxicity pada graf lintasan (Pn), graf tangga (Ln), graf bintang (Sn), graf sikel (Cn), dan graf kipas (Fn)

Habibi, Azwar Riza (2012) Boxicity pada graf lintasan (Pn), graf tangga (Ln), graf bintang (Sn), graf sikel (Cn), dan graf kipas (Fn). Undergraduate thesis, Universitas Islam Negeri Maulana Malik Ibrahim.

[img] Text (Fulltext)
08610050.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (1MB)

Abstract

INDONESIA:

Boxicity dari graf G, dinotasikan sebagai kotak(G), adalah bilangan bulat positif terkecil k sehingga G dapat direpresentasikan sebagai irisan k-kotak. Skripsi ini membahas tentang boxicity pada graf lintasan (P_n ), graf tangga (L_n), graf bintang (S_n ), graf sikel ( C_n), dan graf kipas (F_n).

Langkah-langkah yang dilakukan dalam membahas penelitian ini adalah sebagai berikut: a). Menggambarkan graf lintasan (P_n ), graf tangga (L_n), graf bintang (S_n ), graf sikel ( C_n), dan graf kipas (F_n). b). Merubah gambar graf lintasan (P_n ), graf tangga (L_n), graf bintang (S_n ), graf sikel ( C_n), dan graf kipas (F_n) dalam bentuk bidang. c). Mencari irisan dari gambar bidang. d). Menyusun irisan bidang dalam bentuk dimensi. e). Menentukan pola irisan, pola dimensi pada graf lintasan (P_n ), graf tangga (L_n), graf bintang (S_n ), graf sikel ( C_n), dan graf kipas (F_n) yang di sajikan dalam bentuk tabel. f). Membuat sifat dan membuktikan sifat benar secara umum.

Berdasarkan hasil pembahasan dapat diperoleh boxicity sebagai berikut:
1. Graf Lintasan
Boxicity pada graf lintasan yaitu:
a). Kotak (P_n ) = 2, untuk 2 ≤ n ≤ 6 .
b). Kotak(P_n) ≥ 3, untuk n ≥ 7.
2. Graf Tangga
Boxicity pada graf tangga yaitu:
a). Kotak(L_n) = 2, untuk .n = 2 dan 3.
b). Kotak(L_n) ≥ 3 , untuk n ≥ 4.
3. Graf Bintang
Boxicity pada graf bintang yaitu:
a). Kotak(S_n) = 2, untuk n = 3,4, dan 5.
b). Kotak(S_n) ≥ 3 , untuk n≥ 6.
4. Graf Sikel
Boxicity pada graf sikel C_n adalah 2, untuk n≥ 3
5. Graf Kipas
Boxicity pada graf kipas yaitu:
a). Kotak(F_n) = 2, untuk n = 2 dan 3.
b). Kotak(F_n) , untuk n ≥ 4.

ENGLISH:

The Boxicity of a graph G, denoted as box(G), is minimum positive integer k such that G is respresentable as the intersection of k-boxes. The thesis works thought about Boxicity on path graf (P_n), ladder graf (L_n), star graf (S_n), cycle graf (C_n), and fan graf (F_n).

Steps that is done in work through this research is as follows: a). Figuring path graf (P_n), ladder graf (L_n), star graf (S_n), cycle graf (C_n), and fan graf (F_n). b). transforms draws path graf (P_n), ladder graf (L_n), star graf (S_n), cycle graf (C_n), and fan graf (F_n). in shaped area. c). Determining slice of area image. d). Arranging area slice in shaped dimensioning. e). Determining cut pattern, dimensioning on path graf (P_n), ladder graf (L_n), star graf (S_n), cycle graf (C_n), and fan graf (F_n). served in tabel. f). Making characteristic and proves characteristic true in generally.

Base result get boxicity as follows:
1. Path Graph
Boxicity on path graph is:
a). Box(P_n ) = 2, to 2 ≤ n ≤ 6.
b). Box(P_n) ≥ 3, to n ≥ 7.
2. Ladder Graph
Boxicity on ladder graph is:
a). Box(L_n) = 2, to n = 2 and 3.
b). Box(L_n) ≥ 3 , to n ≥ 4.
3. Star Graph
Boxicity on star graph is:
a). Box(S_n) = 2, for n = 3,4, and 5.
b). Box(S_n) ≥ 3 , to n≥ 6.
4. Cycle Graph
Boxicity on cycle graph C_n is 2, to n≥ 3
5. Fan Graph
Boxicity on fan graph is:
a). Box(F_n) = 2, to n = 2 and 3.
b). Box(F_n), to n ≥ 4.

Item Type: Thesis (Undergraduate)
Supervisor: Irawan, Wahyu Hengky and Barizi, Ahmad
Keywords: Graf; dimensi; Boxicity; Graph; Dimension; Boxicity
Departement: Fakultas Sains dan Teknologi > Jurusan Matematika
Depositing User: Nisfu Lailatul Maghfiroh
Date Deposited: 23 May 2017 01:43
Last Modified: 23 May 2017 01:43
URI: http://etheses.uin-malang.ac.id/id/eprint/6699

Actions (login required)

View Item View Item