Rainbow connection number graf lintasan, graf tangga, dan hasil perkaliannya

INDONESIA:

Misalkan G adalah graf terhubung tak trivial. Didefinisikan pewarnaan sisi c∶E(G)→{1,2,…,k},k∈N adalah pewarnaan sedemikian sehingga setiap sisi bertetangga mungkin memiliki warna yang sama. Misalkan u,v∈V(G) dan P adalah lintasan dari u ke v. Suatu lintasan u-v P dikatakan rainbow path jika tidak terdapat dua sisi di P yang memiliki warna sama. Graf G bersifat rainbow connection jika terdapat satu rainbow path yang menghubungkan setiap dua titik berbeda di G. Jadi, pewarnaan sisi yang menyebabkan G bersifat rainbow connection disebut rainbow coloring dari graf G. Minimum banyaknya k warna yang diperlukan untuk mewarnai sisi G sehingga terdapat rainbow k-coloring disebut rainbow connection number dari G, ditulis rc(G).
Tujuan penelitian ini adalah mencari pola umum yang nantinya dijadikan suatu teorema dari rainbow connection number pada graf P_n, graf T_n, dan graf P_n×T_n. Hasil penelitian ini adalah:
rc(P_n )=n-1 untuk n≥2.
rc(T_n )=n untuk n≥2.
rc(P_n×T_n )=2n-1 untuk n≥2.

Untuk penelitian selanjutnya diharapkan dapat menemukan bermacam-macam teorema tentang rainbow connection number dari graf lainnya dan juga operasi lainnya.

ENGLISH:
Let G be a nontrivial connected graph and define a coloring
c:E(G)→{1,2,…,k},k∈N of the edges of G, where adjacent edges may have the same colored. Let u,v∈V(G) and P be the path from u to v. P is a rainbow path if no two edges of P are colored the same. The graph G is rainbow connected if G contains a rainbow path for every two vertices of G. Thus, the edge coloring that causes G is a rainbow connected is called rainbow coloring of G. The minimum k for which there exists a rainbow k-coloring of the edges of G is the rainbow connection number rc(G) of G.
The purpose of this research is to find a general formula which will be used as theorems of rainbow connection number of P_n, T_n, and P_n×T_n. The results from the research are:
rc(P_n )=n-1 for n≥2.
rc(T_n )=n for n≥2.
rc(P_n×T_n )=2n-1 for n≥2.

For further research the writer suggest to determine other theorems about rainbow connection number from the other graphs and the other operations.