Kalkulator Dimensi Multiset

Untuk graf terhubung G dan himpunan W ⊆ V(G), representasi multiset r_m(v|W) adalah multiset jarak dari v ke setiap titik W. Urutan diabaikan, kemunculan berulang dihitung. Notasi parameter di literatur berbeda-beda; di aplikasi ini dipakai singkatan berikut.

md(G), dimensi multiset

|W| terkecil sehingga setiap dua titik berbeda punya representasi berbeda. Bernilai ∞ kalau tidak ada W seperti itu. Diperkenalkan Simanjuntak, Siagian, dan Vetrík (arXiv:1711.00225).

lmd(G), dimensi multiset lokal

Syaratnya hanya untuk pasangan titik yang bertetangga. Bisa ∞. Dikaji Alfarisi dkk., misalnya AIMS Mathematics 8(4), 2023.

omd(G), dimensi multiset luar

Syaratnya hanya untuk pasangan titik di luar W. Selalu hingga, paling besar n − 1. Gil-Pons, Ramírez-Cruz, Trujillo-Rasua, dan Yero (Appl. Math. Comput. 363, 2019).

lomd(G), dimensi multiset luar lokal

Syaratnya hanya untuk pasangan titik bertetangga yang keduanya di luar W. Selalu hingga. Simanjuntak, Hasan, dan Anggarawan (arXiv:2507.15071).

Cara menghitung

1. Ukuran k dicoba dari batas bawah ke atas, dan semua himpunan berukuran k diperiksa. Syaratnya tidak monoton (menambah titik ke W bisa merusak), jadi k pertama yang berhasil adalah nilai eksak.
2. Untuk md dan lmd, kalau tidak ada himpunan yang berhasil sampai k = n, nilainya ∞ dan statusnya "∞ lewat pencarian lengkap".
3. Pemangkasan: untuk pasangan u, v, tabrakan hanya bergantung pada W ∩ S(u,v) dengan S(u,v) = {x : d(u,x) ≠ d(v,x)}. Begitu titik-titik itu sudah diputuskan, tabrakan langsung dipotong.
4. Pada graf transitif-titik, tanpa mengurangi keumuman satu titik tetap dipaksa masuk W.

Aturan cepat yang dipakai

• Tiga titik yang saling kembar (lingkungan buka atau tutup sama) membuat md = ∞, karena setiap pasang kembar butuh tepat satu titik di W. Untuk lmd berlaku hal yang sama pada kembar sejati.
• Diameter ≤ 2 dan n ≥ 4 membuat md = ∞: titik di W hanya bisa dibedakan oleh derajatnya di G[W], padahal setiap graf dengan dua titik atau lebih punya dua titik berderajat sama.
• lmd = lomd = 1 tepat untuk graf bipartit (dengan sisi). Graf tak bipartit punya sisi di dalam satu lapisan BFS dari titik mana pun, jadi butuh ≥ 2.
• Batas bawah pencacahan: ada n − k titik di luar W yang harus mendapat multiset berbeda berukuran k dari nilai 1 sampai diam(G).

Semua hasil diperoleh dengan perhitungan eksak, tetapi hanya pada rentang n yang diuji. Pola konstan perlu dibuktikan secara matematis sebelum dijadikan teorema.