PENERAPAN TEKNIK RAINBOW CONNECTION DALAM PENGEMBANGAN DELIVERY DESIGN SYSTEM YANG AMAN PADA JARINGAN TRANSPORTASI DAN KOMUNIKASI (The Application of Rainbow Connection Technique in Developing a Secured Delivery Design System of Transportation and Communication Network)

Abstract

In graph theory perspective, the communication and transport networks can be represented as a graph where each element is described as a point and the connection between the two elements is described as an edge. There are a lot of problem that can be modelled as a graph such as communication network, transportation delivery system design. One of graph study which can be used to solve those problems is a Rainbow Connection. Let c be a coloring c : E(G) →{1, 2, . . . , k}, 𝑘𝜖𝑁, of a nontrivial, finite, simple and undirected connected graph G=(V,E). A rainbow is an edge colored graph in which to edges on the path have different colors. An edge colored graph G is rainbow connected if there exists a rainbow u - v path for every two vertices u and v of G. The smallest number of k colors required to edge color the graph such that the graph is rainbow connected is called a rainbow connection number of a graph G, denoted by rc(G). To determine the rainbow connection number for any graph is considered to be a hard problem. Suppose we are given an edge coloring of the graph. How are we convinced whether the colored graph is rainbow connected. Clearly, if the number of colors is constant then this problem becomes easy. However, if it has an unbounded number of colors, the problem becomes NP-Complete. In this paper, we determine the exact values of rainbow connection number of some special graphs and its operations. The result shows that all exact values of rc(G) studied in this paper attain a lower bound of the rainbow connectivity.