PEWARNAAN SISI UNIQUE-MAXIMUM PADA GRAF BIDANG TERHADAP FACE

Abstract

ABSTRACT

Plane graphs is planar graphs depicted with non-intersecting sides. In the plane graph there is a face that is a region or area that is surrounded by the edge connected. In the graph there are several kinds of Colouring. A unique-maximum k-edge-colouring with respect to faces of a 2-edge-connected plane graph G is an edge-colouring with colours 1, . . . , k so that, for each face α of G, the maximum colour occurs exactly once on the edges of α. It is said that an edge colouring of a plane graph G is facially proper if no two face-adjacent edges of G receive the same colour .The purpose of this research is to determine the minimum color such that G has k-edge unique-maximum of plane graph and Determines the minimum color such that G has k-edge FPUM (Facially Proper Unique-Maximum) of the Plane Graph. The research was done by to determine the minimum color such that G has k-edge unique-maximum of plane graph and Determines the minimum color such that G has k-edge FPUM (Facially Proper Unique-Maximum) of the Plane Graph. The results of this study, namely (1) The set of edges on the Dual Graph corresponds to the set of edges on Plane Graph. (2) Minimum color on k-edge UM (Unique-Maximum) is 3. (3) Every 2-edge-connected plane graph G has a facially proper 4-edge-colouring.. (4) Minimum color on k-edge FPUM (Facially Proper Unique-Maximum) is 6

Keywords : Plane Graphs, Face, Edge Colouring, Unique-Maximum Edge Colouring, Facially Proper.

ABSTRAK

Graf bidang merupakan Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan. Pada graf bidang terdapat face yaitu suatu wilayah atau area yang dikeliling oleh sisi yang saling terhubung. Pada graf terdapat beberapa macam pewarnaan. Sebuah pewarnaan sisi unique-maximum terhadap face, dari dua sisi yang terhubung pada sebuah graf bidang G adalah pewarnaan sisi dengan warna 1, . . . , k sehingga untuk setiap face α dari G maksimum warna yang terjadi adalah tepat satu kali pada sisi α. Dikatakan sebuah pewarnaan sisi pada graf bidang G adalah facially proper apabila tidak ada 2 sisi face yang bersinggungan pada G menerima warna yang sama. Tujuan dari penelitian ini adalah Menentukan minimum warna sedemikian sehingga G mempunyai k-sisi unique-maximum dari graf bidang dan Menentukan minimum warna sedemikian sehingga G mempunyai k-sisi FPUM (Facially Proper Unique-Maximum) dari graf bidang. Penelitian ini dilakukan dengan cara menentukan minimum warna sedemikian sehingga  mempunyai k-sisi unique-maximum dari graf bidang serta menentukan minimum warna sedemikian sehingga  mempunyai k-sisi FPUM (Facially Proper Unique-Maximum) dari graf bidang. Hasil dari penelitian ini, yaitu (1) Himpunan sisi pada Graf Dual bersesuaian dengan himpunan sisi pada Graf Bidang. (2) Minimum warna pada pewarnaan sisi-k UM (Unique-Maximum)  adalah 3. (3) Setiap Graf bidang  terhubung Sisi-2 mempunyai facially proper pewarnaan sisi 4. (4) Minimum warna pada pewarnaan sisi-k FPUM (Facially Proper Unique-Maximum)  adalah 6

Kata Kunci : Graf Bidang, Face , pewarnaan sisi, Pewarnaan sisi Unique-Maximum, facially proper.