GRAPH GRABBING GAME PADA GRAF LINTASAN P_n DENGAN n GANJIL

Abstract

Diberikan graf terhubung G dengan setiap simpul v dari graf G memiliki bobot berupa bilangan bulat tak negatif, yaitu w(v). Dalam permainan Graf Grabbing Game, terdapat dua pemain, yaitu Alice dan Bob, dimana Alice adalah pemain pertama. Permainan dilakukan dengan cara setiap pemain secara bergantian mengambil satu simpul dalam graf G dengan ketentuan bahwa simpul yang diambil bukan merupakan cut vertex, artinya, setelah simpul v diambil, graph G – v, tetap merupakan graf terhubung. Pemenang permainan adalah pemain yang memiliki jumlah bobot terbanyak setelah semua simpul diambil. Dalam literatur, Alice selalu memenangkan permainan untuk graf lintasan , dengan genap, tetapi tidak selalu menang untuk n ganjil. Artikelinimembahaskriteria yang harus dipenuhi untuk pelabelan graf lintasan dengan ganjil yang memberikan kepastian kemenangan kepada Alice. Penelitian ini merupakan penelitian pustaka. Hasil penelitian ini adalah Alice akan memenangkan graph grabbing game untuk graf lintasan dengan ganjil jika terdapat simpul ujung dengan

Kata Kunci: graph grabbing game, graf lintasan, graf terbobot