Text

Graf Representasi-Kata

---

ABSTRAK

Graf G=(V,E) adalah representasi-kata jika terdapat sebuah kata W atas alfabet V sedemikian sehingga untuk setiap pasangan huruf yang berbeda X dan Y, (X,Y)∈E jika dan hanya jika kemunculan huruf-hurufnya bersifat selang-seling (alternate) di W. Suatu pasangan huruf X dan Y dikatakan selang-seling (alternate) di W jika dan hanya jika X dan Y selang-seling (alternate) di w_(X∪Y). Pada tugas akhir ini dikaji graf orientasi dan graf representasi-kata, bahwa graf adalah representasi-kata jika dan hanya jika graf tersebut mempunyai orientasi semi-transitif. Dikaji juga bahwa jumlah representasi-kata pada n titik dari suatu graf adalah n/2. Pada bagian akhir dalam tugas akhir ini dibahas bahwa semua graf pewarnaan-3 merupakan graf representasi-kata, termasuk graf outerplanar, graf subdivisi, dan graf prisma.
Kata kunci: Representasi-Kata, Orientasi Semi-Transitif, Jumlah Representasi, Graf Pewarnaan-3

ABSTRACT

A graph G=(V,E) is a word-representable graph if there exists a word W over the alphabet V such that for each pair of distinct letters X and Y, (X,Y)∈E if and only if the occurences of the letters alternate in W. Each pair of letters X and Y are alternate in W if and only if X and Y alternate in w_(X∪Y). This paper studies about orientation graphs and word-representable graphs, a graph is word-representable if and only if it admits a semi-transitive orientation. We also study about representation number on word-representable graph on n vertices is at most 2n. The last part of this paper is about all 3-colorable graphs are word-representable graphs, includes outerplanar graphs, subdivision graphs, and prisms.
Keywords: Word-Representable, Semi-Transitive Orientation, Representation Number, 3-Colorable Graphs.

---

Ketersediaan

2158A19I

2158 A 19-i

Perpustakaan FSM Undip (Referensi)

Tersedia

Informasi Detail

Judul Seri

MATEMATIKA

No. Panggil

2158 A 19-i

Penerbit

: ., 2019

Deskripsi Fisik

-

Bahasa

Indonesia

ISBN/ISSN

-

Klasifikasi

005.1068

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

-

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Alif Nurjanah

Versi lain/terkait

Lampiran Berkas

Komentar

---

Anda harus masuk sebelum memberikan komentar