INNOVATIVE: Journal Of Social Science Research Volume 4 Nomor 2 Tahun 2024 Page 3370-3381 E-ISSN 2807-4238 and P-ISSN 2807-4246
Website: https://j-innovative.org/index.php/Innovative
Penetuan Lokasi Strategis Menggunakan Pusat dan Pusat Berat untuk Pembangunan Sekolah Unggulan Di Wilayah Kabupaten Pasaman Barat
Yogi Wm Simarmata 1 ✉ , Mulyono 2
Universitas Negeri Medan Email: yogisimarmata29@gmail.com 1 ✉

## Abstrak
Penelitian  ini  bertujuan  menentukan  lokasi  strategis  untuk  pembangunan  sekolah  unggulan  di Kabupaten Pasaman Barat. Pemilihan lokasi yang tepat memiliki peran penting dalam meningkatkan akses dan kualitas pendidikan di suatu daerah. Metode yang digunakan pada penelitian ini yaitu pusat dan  pusat  berat.  Adapun  jenis  graf  yang  digunakan  untuk  konsep  pusat  berupa  graf  terhubung sedangkan untuk konsep pusat berat berupa pohon perentang minimum dari graf terhubung tersebut. Setelah membandingkan antara hasil dari kedua konsep tersebut diperoleh satu titik pada graf yang direpresentasikan  sebagai  lokasi  strategis.  Hasil  dari  penelitian  ini  menyatakan  bahwa  lokasi  yang dianggap sebagai lokasi strategis untuk pembangunan sekolah unggulan adalah Nagari Lingkuang Aua. Hal  ini  menunjukkan  bahwa  Nagari  Lingkuang  Aua  memiliki  karakteristik  yang  memenuhi  kriteria sebagai lokasi yang strategis untuk pendirian sekolah unggulan berdasarkan konsep pusat dan pusat berat.
Kata Kunci: Graf Terhubung, Kabupaten Pasaman Barat, Lokasi Strategis, Minimum Spanning Tree, Pusat,
Pusat Berat

## Abstract
This research aims to determine strategic locations for establishing a prestigious school in Pasaman Barat Regency. The selection of an appropriate location plays a crucial role in enhancing access to and the quality of education in a region. The method employed in this study involves the concepts of center and centroid. The type of graph used for the center concept is a connected graph, while for the centroid concept, it is a minimum spanning tree derived from the connected graph. After comparing the results between these two concepts, one point on the graph is obtained, represented as a strategic location. The findings of this research indicate that the identified strategic location for establishing a prestigious school is Nagari Lingkuang Aua. This demonstrates that Nagari Lingkuang Aua possesses characteristics that fulfill the criteria for a strategic location for establishing a prestigious school based on the concepts of center and centroid.
Keywords: Connected  Graph,  Pasaman  Barat  Regency,  Strategic  Location,  Minimum  Spanning  Tree, Center, Centroid

## PENDAHULUAN
Graf  pertama  kali  diperkenalkan  oleh  Leonhard  Euler  pada  tahun  1736  melalui tulisannya yang membahas terkait upaya pemecahan masalah jembatan Konigsberg yang sangat terkenal di Eropa (Rahayuningsih, 2018). Graf dapat berfungsi sebagai model dari suatu sistem yang berupa himpunan titik dan garis yang menghubungkan setiap titik yang berpasangan. Beraneka ragam permasalahan dalam kehidupan yang dapat diaplikasikan dengan teori graf. Salah satu permasalahan yang dapat diselesaikan dengan konsep graf yaitu penentuan lokasi strategis.
Berdasarkan  observasi,  menurut  Pemerintah  Kabupaten  Pasaman  Barat  bahwa Pasaman Barat saat ini masih kekurangan sarana sekolah yang unggul yang menyebabkan cukup banyak siswa siswi di Pasaman Barat setelah tamat dari tingkat sekolah dasar memilih melanjutkan pendidikan disekolah unggul yang berada diluar daerah Pasaman Barat. Oleh karena  itu pemerintah  Kabupaten Pasaman Barat saat ini menyusun  program unggulan, salah satunya yaitu Pasbar Cerdas. Hal ini juga tertuang didalam Rencana Pembangunan Jangka Menengah Daerah (RPJMD) Kabupaten Pasaman Barat Tahun 2021-2026. Program “Pasbar  Cerdas”  ditujukan  untuk  mempercepat  tercapainya  misi  pembangunan  daerah yaitu: membangun sumber daya manusia yang mampu, mandiri, dan memiliki daya saing baik di tingkat nasional maupun internasional. Adapun upaya pemerintah Kabupaten untuk mewujudkan  pelaksanan  program  tersebut  di  bidang  pembangunan  yaitu  mendirikan sekolah unggulan.
Dalam membangun Sekolah Unggulan milik Pemerintah Daerah Kabupaten Pasaman Barat  tentunya  dibutuhkan  sebuah  lokasi.  Menurut  Antu,  (2022)  pemilihan  lokasi
pembangunan  sekolah  harus  memperhatikan  aksesibilitas  yang  akan  ditempuh  peserta didik.  Hal  ini  juga  terdapat  di  dalam  Permendiknas  No.24  tahun  2007.  Aksesibilitas merupakan ukuran kemudahan untuk mencapai atau mengakses suatu lokasi atau fasilitas. Ukuran  keterjangkauan  atau  aksesibilitas  meliputi  kemudahan  waktu,  biaya,  dan  usaha dalam  melakukan  perpindahan  antar  tempat  atau  kawasan.  Dimana  aksesibilitas  yang dimaksud yaitu jarak tempuh, Semakin dekat jaraknya, semakin mudah bagi siswa untuk mencapai sekolah dengan waktu dan usaha yang lebih sedikit. Konsep dalam graf yang mempertimbangkan jarak antara lintasan yang satu dengan lintasan yang lain pada setiap dua titik dalam graf adalah konsep tentang pusat dan pusat berat suatu graf. Oleh karena itu, konsep pusat dan pusat berat dapat digunakan dalam penentuan lokasi strategis untuk pembangunan suatu fasilitas tertentu.
Adapun  jenis  graf  yang  digunakan  untuk  konsep  pusat  berupa  graf  terhubung sedangkan  untuk  konsep  pusat  berat  berupa  pohon  perentang  minimum  dari  graf terhubung tersebut. Penentuan lokasi strategis sebagai tempat untuk kepentingan umum pada suatu wilayah dilakukan dengan terlebih dahulu mengubah suatu peta menjadi graf dimana area  tertentu menjadi titik  graf dan hubungan dua area  menjadi sisi graf. Pusat suatu graf adalah titik yang paling representatif ditinjau dari segi jarak yakni jarak antara dua area, sedangkan pusat berat adalah titik paling representatif ditinjau dari segi ukuran percabangan  suatu titik yang dalam kenyataannya menyatakan  banyaknya jalan menuju suatu area (titik pusat). Setelah membandingkan antara kedua konsep tersebut diperoleh titik pada graf yang direpresentasikan sebagai lokasi strategis.

## METODE PENELITIAN
Pada penelitian ini, data yang digunakan yaitu peta Kabupaten Pasaman Barat, titik koordinat  setiap  kantor  wali  nagari,  jarak  antar  setiap  kantor  wali  nagari.  Teknik pengumpulan  data  yang  dilakukan  yaitu  dengan  melakukan  studi  kasus  di  Badan Perencanaan  Pembangunan,  Penelitian  dan  Pembangunan  Daerah  Kabupaten  Pasaman Barat.
Adapun prosedur yang akan dilakukan dalam penelitian ini adalah sebagai berikut:
1. Pengambilan data
2. Mengubah peta ke dalam graf
3. Mencari eksentrisitas suatu titik
4. Penentuan titik pusat graf
5. Membentuk pohon perentang minimum dari graf peta pasaman barat
6. Penentuan pusat berat graf

## 7. Menginterpretasi hasil dan membuat kesimpulan.

## HASIL DAN PEMBAHASAN
Kabupaten Pasaman Barat merupakan salah satu kabupaten yang terletak di Provinsi Sumatra  Barat  yang  memiliki  11  kecamatan  dan  19  nagari.  Berdasarkan  penelitian  di Bappelitbang Pasaman Barat,akan ditentukan nagari yang dianggap lokasi strategis untuk pengembangan  pembangunan  wilayah  di  bidang  pendidikan  yaitu  dengan  mendirikan sekolah  unggulan  milik  Pasaman  Barat.  Untuk  menentukan  lokasi  yang  strategis,  perlu dibentuk graf dari wilayah Kabupaten Pasaman Barat dengan menggunakan titik koordinat dari setiap kantor Wali Nagari. Peta Kabupaten Pasaman Barat dapat dilihat pada gambar 1.

## Gambar 1. Peta Kabupaten Pasaman Barat
Mempresentasikan Data ke dalam Graf
Beberapa asumsi yang digunakan dalam mempresentasikan peta wilayah Kabupaten Pasaman Barat ke graf:
1. Titik  pada  graf  menyatakan  kantor  wali  nagari  yang  berada  di  wilayah  Kabupaten Pasaman Barat
2. Sisi (garis) pada graf menyatakan jalan terpendek yang menghubungkan setiap nagari.
3. Setiap nagari memiliki pemukiman dengan kepadatan penduduk yang sama.
4. Semua warga memiliki kepentingan yang sama terhadap fasilitas umum.
Berdasarkan  asumsi-asumsi  tersebut  maka  diperoleh  titik-titik  pada  graf  sebagai berikut.
Titik a = Kantor Wali Nagari Air Bangih Titik b = Kantor Wali Nagari Desa Baru Titik c = Kantor Wali Nagari Batahan Titik d = Kantor Wali Nagari Parit Titik  e  =  Kantor  Wali  Nagari  Ujung Gading
Titik f = Kantor Wali Nagari Sungai Aua Titik  g  =  Kantor  Wali  Nagari  Muaro Kiawai Titik h = Kantor Wali Nagari Sasak Titik i = Kantor Wali Nagari Aia Gadang
Titik j = Kantor Wali Nagari Lingkuang Aua Titik k = Kantor Wali Nagari Sasak Titik l = Kantor Wali Nagari Kapa Titik m = Kantor Wali Nagari Sinuruik Titik n = Kantor Wali Nagari Talu Titik o = Kantor Wali Nagari Kajai Titik p = Kantor Wali Nagari Aua Kuniang Titik q = Kantor Wali Nagari Koto Baru Titik r = Kantor Wali Nagari Katiagan Titik s = Kantor Wali Nagari Kinali
Gambar 2. Graf Peta Kabupaten Pasaman Barat

## Menentukan Pusat Graf
Pusat merupakan himpunan dari titik sentral suatu graf, sedangkan titik sentral yaitu eksentrisitas 𝑒(𝑣)   =  𝑟(𝐺) . Di mana 𝑟(𝐺)   =  𝑚𝑖𝑛{𝑒(𝑣) ∶  𝑣  ∈  𝑉 (𝐺)}. Graf dari Kabupaten Pasaman Barat dinotasikan sebagai 𝐺 𝑃 . Menurut Hasmawati, (2020) dalam pencarian pusat suatu graf berhubungan dengan jarak dimana konsep jarak dalam teori graf yang dimaksud tidak terkait dengan panjang garis secara geometri tetapi berkaitan dengan banyaknya sisi pada lintasan terpendek yang menghubungkan dua buah titik. Hal utama yang perlu dicari dalam menentukan pusat suatu graf yaitu mencari eksentrisitas suatu titik. Dalam teori graf,
eksentrisitas merupakan ukuran jarak maksimum antara suatu simpul dalam graf dengan simpul-simpul lainnya.
Berikut ini penentuan eksentrisitas titik-titik pada graf 𝐺 𝑃 yaitu:
𝑒(𝑎)   = maks  { 𝑑(𝑎, 𝑏), 𝑑(𝑎, 𝑐), 𝑑(𝑎, 𝑑), 𝑑(𝑎, 𝑒), 𝑑(𝑎, 𝑓), 𝑑(𝑎, 𝑔), 𝑑(𝑎, ℎ),
𝑑(𝑎, 𝑖), 𝑑(𝑎, 𝑗), 𝑑(𝑎, 𝑘), 𝑑(𝑎, 𝑙), 𝑑(𝑎, 𝑚), 𝑑(𝑎, 𝑛), 𝑑(𝑎, 𝑜), 𝑑(𝑎, 𝑝), 𝑑(𝑎, 𝑞), 𝑑(𝑎, 𝑟), 𝑑(𝑎, 𝑠) } = maks {1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 5, 5, 4, 3, 4, 4, 5 ,5} = 5 𝑒(𝑏)   = maks  { 𝑑(𝑏, 𝑎), 𝑑(𝑏, 𝑐), 𝑑(𝑏, 𝑑), 𝑑(𝑏, 𝑒), 𝑑(𝑏, 𝑓), 𝑑(𝑏, 𝑔), 𝑑(𝑏, ℎ), 𝑑(𝑏, 𝑖), 𝑑(𝑏, 𝑗), 𝑑(𝑏, 𝑘), 𝑑(𝑏, 𝑙), 𝑑(𝑏, 𝑚), 𝑑(𝑏, 𝑛), 𝑑(𝑏, 𝑜), 𝑑(𝑏, 𝑝), 𝑑(𝑏, 𝑞), 𝑑(𝑏, 𝑟), 𝑑(𝑏, 𝑠) } = maks {1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 3, 3, 4, 4, 4, 4, 5, 5} = 5 𝑒(𝑐)   = maks  { 𝑑(𝑐, 𝑎), 𝑑(𝑐, 𝑏), 𝑑(𝑐, 𝑑), 𝑑(𝑐, 𝑒), 𝑑(𝑐, 𝑓), 𝑑(𝑐, 𝑔), 𝑑(𝑐, ℎ), 𝑑(𝑐, 𝑖), 𝑑(𝑐, 𝑗), 𝑑(𝑐, 𝑘), 𝑑(𝑐, 𝑙), 𝑑(𝑐, 𝑚), 𝑑(𝑐, 𝑛), 𝑑(𝑐, 𝑜), 𝑑(𝑐, 𝑝), 𝑑(𝑐, 𝑞), 𝑑(𝑐, 𝑟), 𝑑(𝑐, 𝑠) } = maks {1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 3, 3, 4, 4, 4, 4, 5, 5} = 5 𝑒(𝑑)   = maks  { 𝑑(𝑑, 𝑎), 𝑑(𝑑, 𝑏), 𝑑(𝑑, 𝑐), 𝑑(𝑑, 𝑒), 𝑑(𝑑, 𝑓), 𝑑(𝑑, 𝑔), 𝑑(𝑑, ℎ), 𝑑(𝑑, 𝑖), 𝑑(𝑑, 𝑗), 𝑑(𝑑, 𝑘), 𝑑(𝑑, 𝑙), 𝑑(𝑑, 𝑚), 𝑑(𝑑, 𝑛), 𝑑(𝑑, 𝑜), 𝑑(𝑑, 𝑝), 𝑑(𝑑, 𝑞), 𝑑(𝑑, 𝑟), 𝑑(𝑑, 𝑠) } = maks {1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 2, 3, 3, 3, 3, 4, 4} = 4 𝑒(𝑒)   = maks  { 𝑑(𝑒, 𝑎), 𝑑(𝑒, 𝑏), 𝑑(𝑒, 𝑐), 𝑑(𝑒, 𝑑), 𝑑(𝑒, 𝑓), 𝑑(𝑒, 𝑔), 𝑑(𝑒, ℎ), 𝑑(𝑒, 𝑖), 𝑑(𝑒, 𝑗), 𝑑(𝑒, 𝑘), 𝑑(𝑒, 𝑙), 𝑑(𝑒, 𝑚), 𝑑(𝑒, 𝑛), 𝑑(𝑒, 𝑜), 𝑑(𝑒, 𝑝), 𝑑(𝑒, 𝑞), 𝑑(𝑒, 𝑟), 𝑑(𝑒, 𝑠) } = maks {2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 3, 2, 3, 3, 3, 3, 4, 4} = 4 𝑒(𝑓)   = maks  { 𝑑(𝑓, 𝑎), 𝑑(𝑓, 𝑏), 𝑑(𝑓, 𝑐), 𝑑(𝑓, 𝑑), 𝑑(𝑓, 𝑒), 𝑑(𝑓, 𝑔), 𝑑(𝑓, ℎ), 𝑑(𝑓, 𝑖), 𝑑(𝑓, 𝑗), 𝑑(𝑓, 𝑘), 𝑑(𝑓, 𝑙), 𝑑(𝑓, 𝑚), 𝑑(𝑓, 𝑛), 𝑑(𝑓, 𝑜), 𝑑(𝑓, 𝑝), 𝑑(𝑓, 𝑞), 𝑑(𝑓, 𝑟), 𝑑(𝑓, 𝑠) } = maks {2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 3, 3} = 3 𝑒(𝑔)   = maks  { 𝑑(𝑔, 𝑎), 𝑑(𝑔, 𝑏), 𝑑(𝑔, 𝑐), 𝑑(𝑔, 𝑑), 𝑑(𝑔, 𝑒), 𝑑(𝑔, 𝑓), 𝑑(𝑔, ℎ), 𝑑(𝑔, 𝑖), 𝑑(𝑔, 𝑗), 𝑑(𝑔, 𝑘), 𝑑(𝑔, 𝑙), 𝑑(𝑔, 𝑚), 𝑑(𝑔, 𝑛), 𝑑(𝑔, 𝑜), 𝑑(𝑔, 𝑝), 𝑑(𝑔, 𝑞), 𝑑(𝑔, 𝑟), 𝑑(𝑔, 𝑠) } = maks {3, 3, 3, 2, 2, 1, 1, 2, 2, 2, 3, 1, 2, 2, 3, 4, 5, 5} = 5 𝑒(ℎ)   = maks  { 𝑑(ℎ, 𝑎), 𝑑(ℎ, 𝑏), 𝑑(ℎ, 𝑐), 𝑑(ℎ, 𝑑), 𝑑(ℎ, 𝑒), 𝑑(ℎ, 𝑓), 𝑑(ℎ, 𝑔), 𝑑(ℎ, 𝑖), 𝑑(ℎ, 𝑗), 𝑑(ℎ, 𝑘), 𝑑(ℎ, 𝑙), 𝑑(ℎ, 𝑚), 𝑑(ℎ, 𝑛), 𝑑(ℎ, 𝑜), 𝑑(ℎ, 𝑝), 𝑑(ℎ, 𝑞), 𝑑(ℎ, 𝑟), 𝑑(ℎ, 𝑠) } = maks {3, 3, 3, 2, 2, 1, 1, 1, 2, 2, 3, 1, 2, 2, 2, 3, 4, 4} = 4 𝑒(𝑖)   = maks  { 𝑑(𝑖, 𝑎), 𝑑(𝑖, 𝑏), 𝑑(𝑖, 𝑐), 𝑑(𝑖, 𝑑), 𝑑(𝑖, 𝑒), 𝑑(𝑖, 𝑓), 𝑑(𝑖, 𝑔),
𝑑(𝑖, ℎ), 𝑑(𝑖, 𝑗), 𝑑(𝑖, 𝑘), 𝑑(𝑖, 𝑙), 𝑑(𝑖, 𝑚), 𝑑(𝑖, 𝑛), 𝑑(𝑖, 𝑜),
𝑑(𝑖, 𝑝), 𝑑(𝑖, 𝑞), 𝑑(𝑖, 𝑟), 𝑑(𝑖, 𝑠) } = maks {3, 3, 3, 2, 2, 1, 2, 1, 2, 2, 2, 2, 3, 2, 1, 2, 3, 3}
= 3
𝑒(𝑗)   = maks  { 𝑑(𝑗, 𝑎), 𝑑(𝑗, 𝑏), 𝑑(𝑗, 𝑐), 𝑑(𝑗, 𝑑), 𝑑(𝑗, 𝑒), 𝑑(𝑗, 𝑓), 𝑑(𝑗, 𝑔), 𝑑(𝑗, ℎ), 𝑑(𝑗, 𝑖), 𝑑(𝑗, 𝑘), 𝑑(𝑗, 𝑙), 𝑑(𝑗, 𝑚), 𝑑(𝑗, 𝑛), 𝑑(𝑗, 𝑜),
𝑑(𝑗, 𝑝), 𝑑(𝑗, 𝑞), 𝑑(𝑗, 𝑟), 𝑑(𝑗, 𝑠) } = maks {3, 3, 3, 2, 2, 1, 2, 2, 1, 1, 1, 3, 3, 2, 1, 1, 2, 2} = 3 𝑒(𝑘)   = maks  { 𝑑(𝑘, 𝑎), 𝑑(𝑘, 𝑏), 𝑑(𝑘, 𝑐), 𝑑(𝑘, 𝑑), 𝑑(𝑘, 𝑒), 𝑑(𝑘, 𝑓), 𝑑(𝑘, 𝑔), 𝑑(𝑘, ℎ), 𝑑(𝑘, 𝑖), 𝑑(𝑘, 𝑗), 𝑑(𝑘, 𝑙), 𝑑(𝑘, 𝑚), 𝑑(𝑘, 𝑛), 𝑑(𝑘, 𝑜), 𝑑(𝑘, 𝑝), 𝑑(𝑘, 𝑞), 𝑑(𝑘, 𝑟), 𝑑(𝑘, 𝑠) } = maks {3, 3, 3, 2, 2, 1, 2, 2, 2, 1, 1, 2, 3, 3, 2, 1, 2, 2} = 3 𝑒(𝑙)   = maks  { 𝑑(𝑙, 𝑎), 𝑑(𝑙, 𝑏), 𝑑(𝑙, 𝑐), 𝑑(𝑙, 𝑑), 𝑑(𝑙, 𝑒), 𝑑(𝑙, 𝑓), 𝑑(𝑙, 𝑔), 𝑑(𝑙, ℎ), 𝑑(𝑙, 𝑖), 𝑑(𝑙, 𝑗), 𝑑(𝑙, 𝑘), 𝑑(𝑙, 𝑚), 𝑑(𝑙, 𝑛), 𝑑(𝑙, 𝑜) 𝑑(𝑙, 𝑝), 𝑑(𝑙, 𝑞), 𝑑(𝑙, 𝑟), 𝑑(𝑙, 𝑠) } = maks {4, 4, 4, 3, 3, 2, 3, 3, 2, 1, 1, 4, 4, 3, 2, 1, 2, 2} = 4 𝑒(𝑚)   = maks  { 𝑑(𝑚, 𝑎), 𝑑(𝑚, 𝑏), 𝑑(𝑚, 𝑐), 𝑑(𝑚, 𝑑), 𝑑(𝑚, 𝑒), 𝑑(𝑚, 𝑓), 𝑑(𝑚, 𝑔) 𝑑(𝑚, ℎ), 𝑑(𝑚, 𝑖), 𝑑(𝑚, 𝑗), 𝑑(𝑚, 𝑘), 𝑑(𝑚, 𝑙), 𝑑(𝑚, 𝑛), 𝑑(𝑚, 𝑜), 𝑑(𝑚, 𝑝), 𝑑(𝑚, 𝑞), 𝑑(𝑚, 𝑟), 𝑑(𝑚, 𝑠) } = maks {3, 3, 3, 2, 2, 1, 1, 1, 2, 2, 3, 2, 1, 1, 2, 3, 4, 4} = 4 𝑒(𝑛)   = maks  { 𝑑(𝑛, 𝑎), 𝑑(𝑛, 𝑏), 𝑑(𝑛, 𝑐), 𝑑(𝑛, 𝑑), 𝑑(𝑛, 𝑒), 𝑑(𝑛, 𝑓), 𝑑(𝑛, 𝑔) 𝑑(𝑛, ℎ), 𝑑(𝑛, 𝑖), 𝑑(𝑛, 𝑗), 𝑑(𝑛, 𝑘), 𝑑(𝑛, 𝑙), 𝑑(𝑛, 𝑚), 𝑑(𝑛, 𝑜), 𝑑(𝑛, 𝑝), 𝑑(𝑛, 𝑞), 𝑑(𝑛, 𝑟), 𝑑(𝑛, 𝑠) } = maks {4, 4, 4, 3, 3, 2, 2, 2, 3, 3, 4, 4, 1, 1, 2, 3, 4, 4} = 4 𝑒(𝑜)   = maks  { 𝑑(𝑜, 𝑎), 𝑑(𝑜, 𝑏), 𝑑(𝑜, 𝑐), 𝑑(𝑜, 𝑑), 𝑑(𝑜, 𝑒), 𝑑(𝑜, 𝑓), 𝑑(𝑜, 𝑔), 𝑑(𝑜, ℎ), 𝑑(𝑜, 𝑖), 𝑑(𝑜, 𝑗), 𝑑(𝑜, 𝑘), 𝑑(𝑜, 𝑙), 𝑑(𝑜, 𝑚), 𝑑(𝑜, 𝑛) 𝑑(𝑜, 𝑝), 𝑑(𝑜, 𝑞), 𝑑(𝑜, 𝑟), 𝑑(𝑜, 𝑠) } = maks {4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 3, 3, 1, 1, 1, 2, 3, 3} = 4 𝑒(𝑝)   = maks  { 𝑑(𝑝, 𝑎), 𝑑(𝑝, 𝑏), 𝑑(𝑝, 𝑐), 𝑑(𝑝, 𝑑), 𝑑(𝑝, 𝑒), 𝑑(𝑝, 𝑓), 𝑑(𝑝, 𝑔), 𝑑(𝑝, ℎ), 𝑑(𝑝, 𝑖), 𝑑(𝑝, 𝑗), 𝑑(𝑝, 𝑘), 𝑑(𝑝, 𝑙), 𝑑(𝑝, 𝑚), 𝑑(𝑝, 𝑛), 𝑑(𝑝, 𝑜), 𝑑(𝑝, 𝑞), 𝑑(𝑝, 𝑟), 𝑑(𝑝, 𝑠) } = maks {4, 4, 4, 3, 3, 2, 3, 2, 1, 1, 2, 2, 2, 2, 1, 1, 2, 2} = 4 𝑒(𝑞)   = maks  { 𝑑(𝑞, 𝑎), 𝑑(𝑞, 𝑏), 𝑑(𝑞, 𝑐), 𝑑(𝑞, 𝑑), 𝑑(𝑞, 𝑒), 𝑑(𝑞, 𝑓), 𝑑(𝑞, 𝑔) 𝑑(𝑞, ℎ), 𝑑(𝑞, 𝑖), 𝑑(𝑞, 𝑗), 𝑑(𝑞, 𝑘), 𝑑(𝑞, 𝑙), 𝑑(𝑞, 𝑚), 𝑑(𝑞, 𝑛), (𝑞, 𝑜), 𝑑(𝑞, 𝑜), 𝑑(𝑞, 𝑝), 𝑑(𝑞, 𝑟), 𝑑(𝑞, 𝑠) } = maks {4, 4, 4, 3, 3, 2, 3, 3, 2, 1, 1, 1, 3, 3, 2, 1, 1, 1} = 4 𝑒(𝑟)   = maks  { 𝑑(𝑟, 𝑎), 𝑑(𝑟, 𝑏), 𝑑(𝑟, 𝑐), 𝑑(𝑟, 𝑑), 𝑑(𝑟, 𝑒), 𝑑(𝑟, 𝑓), 𝑑(𝑟, 𝑔), 𝑑(𝑟, ℎ), 𝑑(𝑟, 𝑖), 𝑑(𝑟, 𝑗), 𝑑(𝑟, 𝑘), 𝑑(𝑟, 𝑙), 𝑑(𝑟, 𝑚), 𝑑(𝑟, 𝑛), 𝑑(𝑟, 𝑜), 𝑑(𝑟, 𝑝), 𝑑(𝑟, 𝑞), 𝑑(𝑟, 𝑠) } = maks {5, 5, 5, 4, 4, 3, 4, 4, 3, 2, 2, 2, 4, 4, 3, 2, 1, 1} = 5 𝑒(𝑠)   = maks  { 𝑑(𝑠, 𝑎), 𝑑(𝑠, 𝑏), 𝑑(𝑠, 𝑐), 𝑑(𝑠, 𝑑), 𝑑(𝑠, 𝑒), 𝑑(𝑠, 𝑓), 𝑑(𝑠, 𝑔), 𝑑(𝑠, ℎ), 𝑑(𝑠, 𝑖), 𝑑(𝑠, 𝑗), 𝑑(𝑠, 𝑘), 𝑑(𝑠, 𝑙), 𝑑(𝑠, 𝑚), 𝑑(𝑠, 𝑛), 𝑑(𝑠, 𝑜), 𝑑(𝑠, 𝑝), 𝑑(𝑠, 𝑞), 𝑑(𝑠, 𝑟) } = maks {5, 5, 5, 4, 4, 3, 4, 4, 3, 2, 2, 2, 4, 4, 3, 2, 1, 1}
= 5
Berdasarkan  eksentrisitas  titik-titik  pada  graf 𝐺 𝑃 ,  diperoleh  eksentrisitas  minimum 𝑟(𝐺 𝑃 )   =  3 . Karena 𝑒(𝑓) = 𝑒(𝑖) = 𝑒(𝑗) = 𝑒(𝑘) = 3, maka titik sentral graf 𝐺 𝑃 berada di titik 𝑓 ,titik 𝑖, titik 𝑗, dan titik 𝑘. Sehingga pusat graf 𝐺 𝑃 adalah himpunan yang terdiri dari tiga titik, yaitu {𝑓, 𝑖, 𝑗, 𝑘}.
Untuk melengkapi penentuan lokasi  strategis,  digunakan konsep pusat  berat yakni melalui  pohon  perentang  minimum  dari  graf 𝐺 𝑃 .  Karena  di  dalam  penentuan  pohon perentang  minimum  dibutuhkan  bobot  (nilai)  pada  sisi  Graf 𝐺 𝑃 ,  maka  terlebih  dahulu diberikan  bobot setiap sisi  pada  graf 𝐺 𝑃 yakni jarak setiap dua  kantor  wali nagari. Jarak tersebut diperoleh berdasarkan pengukuran jarak dari masing-masing kantor wali nagari yang  wilayahnya  berbatasan  langsung,  dengan  mengambil  data  pada  Google  Map. Berdasarkan data tersebut diperoleh graf berbobot 𝐺 𝑃 sebagai berikut:

## Gambar 3. Bobot pada graf 𝑮 𝒑
Selanjutnya,  dicari  pohon  perentang  minimum  Graf 𝐺 𝑃 menggunakan  Algoritma Kruskal dengan langkah-langkah sebagai berikut:
1. Memilih  sisi  dari  graf 𝐺 𝑃 yang  berbobot  minimum  yaitu  sisi (𝑚, 𝑛), sehingga  kita memiliki 𝑇{(𝑚, 𝑛)} .
2. Selanjutnya pilih sisi (𝑛, 𝑜) karena sisi tersebut berbobot minimum yaitu 11, 3 yang bersisian dengan simpul 𝑛 , sehingga kita memiliki 𝑇{(𝑚, 𝑛), (𝑛, 𝑜)} .
3. Selanjutnya pilih sisi (𝑜, 𝑝) karena  sisi tersebut berbobot minimum yaitu 10, 4 yang bersisian dengan simpul 𝑜 , sehingga kita memiliki 𝑇{(𝑚, 𝑛), (𝑛, 𝑜), (𝑜, 𝑝)}
4. Selanjutnya  pilih  sisi (𝑝, 𝑗) karena  sisi  tersebut  berbobot  minimum  yaitu 7, 4 yang bersisian dengan simpul 𝑝 , sehingga kita memiliki 𝑇{(𝑚, 𝑛), (𝑛, 𝑜), (𝑜, 𝑝), (𝑝, 𝑗)}
5. Selanjutnya  pilih  sisi (𝑗, 𝑖) karena  sisi  tersebut  berbobot  minimum  yaitu 7, 7 yang bersisian dengan simpul 𝑗, sehingga kita memiliki 𝑇{(𝑚, 𝑛), (𝑛, 𝑜), (𝑜, 𝑝), (𝑝, 𝑗), (𝑗, 𝑖)}
6. Selanjutnya  pilih  sisi (𝑗, 𝑞) karena  sisi  tersebut  berbobot  minimum  yaitu 9, 4 yang bersisian dengan simpul 𝑗 , sehingga kita memiliki
𝑇{(𝑚, 𝑛), (𝑛, 𝑜), (𝑜, 𝑝), (𝑝, 𝑗), (𝑗, 𝑖), (𝑗, 𝑞)}
7. Selanjutnya  pilih  sisi (𝑞, 𝑙) karena  sisi  tersebut  berbobot  minimum  yaitu 8, 5 yang bersisian dengan simpul 𝑞 , sehingga kita memiliki
𝑇{(𝑚, 𝑛), (𝑛, 𝑜), (𝑜, 𝑝), (𝑝, 𝑗), (𝑗, 𝑖), (𝑗, 𝑞), (𝑞, 𝑙)}
8. Selanjutnya  pilih  sisi (𝑙, 𝑘) karena  sisi  tersebut  berbobot  minimum  yaitu 7, 8 yang bersisian dengan simpul 𝑙, sehingga kita memiliki
𝑇{(𝑚, 𝑛), (𝑛, 𝑜), (𝑜, 𝑝), (𝑝, 𝑗), (𝑗, 𝑖), (𝑗, 𝑞), (𝑞, 𝑙), (𝑙, 𝑘)}
9. Selanjutnya  pilih  sisi (𝑖, ℎ) karena  sisi  tersebut  berbobot  minimum  yaitu 12, 8 yang bersisian dengan simpul 𝑖 , sehingga kita memiliki
𝑇{(𝑚, 𝑛), (𝑛, 𝑜), (𝑜, 𝑝), (𝑝, 𝑗), (𝑗, 𝑖), (𝑗, 𝑞), (𝑞, 𝑙), (𝑙, 𝑘), (𝑖, ℎ)}
10. Selanjutnya pilih sisi (𝑞, 𝑟) karena  sisi tersebut berbobot minimum yaitu 15, 4 𝑦 ang bersisian dengan simpul 𝑞 , sehingga kita memiliki
𝑇{(𝑚, 𝑛), (𝑛, 𝑜), (𝑜, 𝑝), (𝑝, 𝑗), (𝑗, 𝑖), (𝑗, 𝑞), (𝑞, 𝑙), (𝑙, 𝑘), (𝑖, ℎ), (𝑞, 𝑟)}
11. Selanjutnya pilih sisi (ℎ, 𝑔) karena sisi tersebut berbobot minimum yaitu 16, 6 yang bersisian dengan simpul ℎ , sehingga kita memiliki
𝑇{(𝑚, 𝑛), (𝑛, 𝑜), (𝑜, 𝑝), (𝑝, 𝑗), (𝑗, 𝑖), (𝑗, 𝑞), (𝑞, 𝑙), (𝑙, 𝑘), (𝑖, ℎ), (𝑞, 𝑟), (ℎ, 𝑔)}
12. Selanjutnya pilih sisi (ℎ, 𝑓) karena sisi tersebut berbobot minimum yaitu 18, 9 yang bersisian dengan simpul ℎ , sehingga kita memiliki
𝑇{(𝑚, 𝑛), (𝑛, 𝑜), (𝑜, 𝑝), (𝑝, 𝑗), (𝑗, 𝑖), (𝑗, 𝑞), (𝑞, 𝑙), (𝑙, 𝑘), (𝑖, ℎ), (𝑞, 𝑟), (ℎ, 𝑔), (ℎ, 𝑓)}
13. Selanjutnya  pilih  sisi (𝑓, 𝑒) karena  sisi  tersebut  berbobot  minimum  yaitu 8, 9 yang bersisian dengan simpul 𝑓 , sehingga kita memiliki
𝑇{(𝑚, 𝑛), (𝑛, 𝑜), (𝑜, 𝑝), (𝑝, 𝑗), (𝑗, 𝑖), (𝑗, 𝑞), (𝑞, 𝑙), (𝑙, 𝑘), (𝑖, ℎ), (𝑞, 𝑟), (ℎ, 𝑔), (ℎ, 𝑓), (𝑓, 𝑒)}
14. Selanjutnya  pilih  sisi (𝑒, 𝑑) karena  sisi  tersebut  berbobot  minimum  yaitu 5 yang bersisian dengan simpul 𝑒 , sehingga kita memiliki
𝑇{(𝑚, 𝑛), (𝑛, 𝑜), (𝑜, 𝑝), (𝑝, 𝑗), (𝑗, 𝑖), (𝑗, 𝑞), (𝑞, 𝑙), (𝑙, 𝑘), (𝑖, ℎ), (𝑞, 𝑟),
(ℎ, 𝑔), (ℎ, 𝑓), (𝑓, 𝑒), (𝑒, 𝑑)}
15. Selanjutnya  pilih  sisi (𝑞, 𝑠) karena  sisi tersebut berbobot minimum yaitu 25, 7 yang bersisian dengan simpul 𝑞 , sehingga kita memiliki
𝑇{(𝑚, 𝑛), (𝑛, 𝑜), (𝑜, 𝑝), (𝑝, 𝑗), (𝑗, 𝑖), (𝑗, 𝑞), (𝑞, 𝑙), (𝑙, 𝑘), (𝑖, ℎ), (𝑞, 𝑟),
(ℎ, 𝑔), (ℎ, 𝑓), (𝑓, 𝑒), (𝑒, 𝑑), (𝑞, 𝑠), }
16. Selanjutnya pilih sisi (𝑑, 𝑐) karena  sisi tersebut berbobot minimum yaitu 26, 3 yang bersisian dengan simpul 𝑒 , sehingga kita memiliki
𝑇{(𝑚, 𝑛), (𝑛, 𝑜), (𝑜, 𝑝), (𝑝, 𝑗), (𝑗, 𝑖), (𝑗, 𝑞), (𝑞, 𝑙), (𝑙, 𝑘), (𝑖, ℎ), (𝑞, 𝑟), (ℎ, 𝑔), (ℎ, 𝑓), (𝑓, 𝑒), (𝑒, 𝑑), (𝑞, 𝑠), (𝑑, 𝑐), }
17. Selanjutnya  pilih  sisi (𝑐, 𝑏) karena  sisi  tersebut  berbobot  minimum  yaitu 4, 3 yang
bersisian dengan simpul 𝑐, sehingga kita memiliki
𝑇{(𝑚, 𝑛), (𝑛, 𝑜), (𝑜, 𝑝), (𝑝, 𝑗), (𝑗, 𝑖), (𝑗, 𝑞), (𝑞, 𝑙), (𝑙, 𝑘), (𝑖, ℎ), (𝑞, 𝑟),
(ℎ, 𝑔), (ℎ, 𝑓), (𝑓, 𝑒), (𝑒, 𝑑), (𝑞, 𝑠), (𝑑, 𝑐), (𝑐, 𝑏)}
18. Selanjutnya pilih sisi (𝑐, 𝑎) karena  sisi tersebut berbobot minimum yaitu 27, 3 yang bersisian dengan simpul 𝑐 , sehingga kita memiliki
𝑇{(𝑚, 𝑛), (𝑛, 𝑜), (𝑜, 𝑝), (𝑝, 𝑗), (𝑗, 𝑖), (𝑗, 𝑞), (𝑞, 𝑙), (𝑙, 𝑘), (𝑖, ℎ), (𝑞, 𝑟),
(ℎ, 𝑔), (ℎ, 𝑓), (𝑓, 𝑒), (𝑒, 𝑑), (𝑞, 𝑠), (𝑑, 𝑐), (𝑐, 𝑏), (𝑐, 𝑎)}
Sehingga diperoleh gambar pohon perentang minimum sebagai berikut:

## Gambar 4. Pohon Perentang Minimum 𝑻 𝒑
Menentukan Pusat Berat Graf
Pusat berat merupakan himpunan dari titik berat suatu ohon Perentang minimum, di mana titik berat atau 𝜔(𝑇)   =  𝑚𝑖𝑛{𝜔(𝑢) | 𝑢  ∈  𝑉 (𝑇)}. Pohon perentang minimum dari Graf 𝐺 𝑃 disebut  sebagai  pohon 𝑇 𝑃 .  Maka,  akan  dicari  titik  yang  menjadi  pusat  berat  dari Minimum Spanning Tree tersebut, dengan cara menentukan terlebih dahulu bobot pada setiap titik pohon 𝑇 𝑃 . Menurut Hasmawati (2023), bobot yang dimaksud yaitu banyaknya sisi pada suatu cabang pohon. Artinya, dalam mencari pusat berat, bobot yang digunakan adalah jumlah maksimum sisi di antara semua cabang di titik pohon 𝑇 𝑃 .
𝜔(𝑎) = 𝑚𝑎𝑘𝑠{18} = 18, 𝜔(𝑏) = 𝑚𝑎𝑘𝑠{18} = 18, 𝜔(𝑐) = 𝑚𝑎𝑘𝑠{1, 1, 16} = 16, 𝜔(𝑑) = 𝑚𝑎𝑘𝑠{3,15} = 15 , 𝜔(𝑒) = 𝑚𝑎𝑘𝑠{4,14} = 14, 𝜔(𝑓) = 𝑚𝑎𝑘𝑠{5,13} = 13, 𝜔(𝑔) = 𝑚𝑎𝑘𝑠{18} = 18, 𝜔(ℎ) = 𝑚𝑎𝑘𝑠{1,6,11} = 11, 𝜔(𝑖) = 𝑚𝑎𝑘𝑠{8,10} = 10, 𝜔(𝑗) = 𝑚𝑎𝑘𝑠{5, 4, 9}   =  9, 𝜔(𝑘) = 𝑚𝑎𝑘𝑠{18} = 18, 𝜔(𝑙) = 𝑚𝑎𝑘𝑠{1,17} = 17, 𝜔(𝑚) = 𝑚𝑎𝑘𝑠{18} = 18, 𝜔(𝑛) = 𝑚𝑎𝑘𝑠{1, 17} = 17, 𝜔(𝑜) = 𝑚𝑎𝑘𝑠{2,16} = 16, 𝜔(𝑝) = 𝑚𝑎𝑘𝑠{3,15} = 15, 𝜔(𝑞) = 𝑚𝑎𝑘𝑠{1,1,2,14} = 14, 𝜔(𝑟) = 𝑚𝑎𝑘𝑠{18} = 18, 𝜔(𝑠) = 𝑚𝑎𝑘𝑠{18} = 18
Berdasarkan  bobot-bobot  dari  setiap  pohon 𝑇 𝑃 ,  didapat  bobot  minimum  yaitu 9 , dimana 𝜔(𝑗)   =  𝑚𝑎𝑥{5, 4, 9}   =  9 .  Jadi, 𝜔(𝑗) merupakan  titik  berat  dari  pohon 𝑇 𝑃 . Sehingga pusat berat pohon 𝑇 𝑃 adalah himpunan yang terdiri dari satu titik yaitu {𝑗}. Dari pembahasan pusat dan pusat berat dari graf 𝐺 𝑃 diperoleh pusat Graf 𝐺 𝑃 yaitu {𝑓, 𝑖, 𝑗, 𝑘} dan diperoleh pusat berat pohon 𝑇 𝑃 yaitu {𝑗}. Dapat dilihat bahwa titik 𝑗 adalah titik yang paling representatif  pada  graf 𝐺 𝑃 dan  pohon 𝑇 𝑃 .  Oleh  karena  itu,  nagari  Lingkuang  Aua  yang direpresentasikan  sebagai  titik 𝑗 merupakan  lokasi  yang  dianggap  strategis  untuk pembangunan sekolah unggulan di Kabupaten Pasaman Barat.

## SIMPULAN
Berdasarkan  penelitian  yang  telah  dilakukan,  maka  diperoleh  pusat  dari  graf Pasaman Barat adalah titik { 𝑓, 𝑖, 𝑗, 𝑘}, sementara pusat berat dari graf pohon 𝑇 𝑃 terletak pada titik {𝑗}. Titik 𝑗 merupakan titik yang paling representatif pada graf Pasaman Barat maupun pada graf pohon 𝑇 𝑃 . Dengan demikian, Nagari Lingkuang Aua, yang diwakili oleh titik 𝑗, secara signifikan menjadi wilayah yang paling strategis untuk pembangunan sekolah  unggulan  di  Kabupaten  Pasaman  Barat.  Sebagai  saran  untuk  penelitian selanjutnya dengan karakteristik serupa, disarankan untuk memperluas cakupan wilayah yang dianggap sebagai simpul pada graf yang mencakup desa-desa di suatu kota atau kabupaten.

## DAFTAR PUSTAKA
Antu, A. B. (2022). Analisis Lokasi Sekolah SMA yang Ideal di Kabupaten Bone Bolango dengan Sistem Informasi Geografis. Journal of Applied Geoscience and Engineering, 1(1), 49 – 60.
Balakrisnan,  R.,  &  K.  Ranganathan.  (2020). A  Textbook  of  Graph  Theory.  Department  of Mathematics Bharathidasan University Tiruchirappalli India.
Daniel, F., & Taneo, P. N. L. (2019). Teori Graf. Deepublish.
Deo,  N.  (2016). Graph  Theory  with  Applications  to  Engineering  &  Computer  Science.  Dover Publication, INC.
Dili,  Y.  N.  (2021).  Penyelesaian  Masalah  Transportasi  Untuk  Mencari  Solusi  Optimal  Dengan Pendekatan Minimum Spanning Tree (Mst) Menggunakan Algoritma Kruskal Dan Algoritma Prim. KUBIK: Jurnal Publikasi Ilmiah Matematika, 6(1), 44 – 50.
Djafar,  I.,  &  Ibrahim,  A.  (2011).  Implementasi  Pohon  Merentang  Minimum  Dalam  Menentukan Prioritas Pemeliharaan Jalur Jalan Kota Dengan Biaya Minimal. Jurnal Digit, 1(2), 132 – 142.
Hafsah,  S.,  Hasamawati,  &  Erawaty,  N.  (2022).  Penentuan  Lokasi  Strategis  untuk  Membangun Rumah Sakit di Wilayah Kabupaten Berau Menggunakan Pusat dan Pusat Berat. Jurnal Ilmiah Matematika, 1(1), 61 – 69.
Harison, & Syarif, A. (2016). Sistem Informasi Geografis Sarana Pada Kabupaten Pasaman Barat. Jurnal Teknoif, 4(2), 40 – 50.
Hasmawati. (2020). Pengantar Dan Jenis-Jenis Graf. UPT Unhas Press.
Hasmawati. (2023). Pengantar Teori Dan Jenis-Jenis Graf. UPT Unhas Press.
Kusmira, M., & Taufiqurrochman. (2017). Pemanfaatan Aplikasi Graf Pada Pembuatan Jalur Angkot 05 Tasikmalaya. Seminar Nasional Sains Dan Teknoligi, 11, 1 – 6.
Marsudi. (2016). Teori Graf. Universitas Brawijaya Press.
Munir, R. (2010). Matematika Diskrit Edisi 3. Informatika Bandung.
Nieminen,  J.  (1987).  Distance  center  and  centroid  of  a  median  graph. Journal  of  the  Franklin Institute, 323(1), 89 – 94.
Rahayuningsih, S. (2018). Teori Graph dan Penerapanya (U. W. P. M. (Unidha Press) (ed.)).
Setyawan,  D.,  Nugraha,  A.  L.,  &  Sudarsono,  B.  (2018).  Analisis  Potensi  Desa  Berbasis  Sistem Informasi  Geografis  (Studi  Kasus:  Kelurahan  Sumurboto,  Kecamatan  Banyumanik, Kabupaten Semarang). Jurnal Geodesi Undip, 7(4), 1 – 7.
Siregar, M. K. (2008). Matematika Diskrit. Perahu Litera.
Slater, P. J. (1978). Centers to centroids in graphs. Journal of Graph Theory, 2(3), 209 – 222.
Waluya, B. (2009). Geografi (G. K. Pasya (ed.)). Departemen Pendidikan Nasional. Wijaya, A. (2009). Matematika Diskrit. Politeknik Telkom Bandung.