The treewidth grafik yang tidak terarah adalah konsep yang sangat penting dalam Teori Grafik. Banyak algoritma grafik telah ditemukan yang berjalan cepat jika Anda memiliki dekomposisi grafik dengan treewidth kecil.
Pohon cemara sering didefinisikan dalam istilah dekomposisi pohon. Berikut ini adalah grafik dan dekomposisi pohon dari grafik itu, milik Wikipedia:
Dekomposisi pohon adalah pohon tempat setiap simpul dikaitkan dengan subset dari simpul dari grafik asli, dengan properti berikut:
- Setiap simpul dalam grafik asli setidaknya satu dari himpunan bagian.
- Setiap sisi dalam grafik asli memiliki kedua simpulnya di setidaknya satu dari himpunan bagian.
- Semua simpul dalam dekomposisi yang himpunan bagiannya berisi simpul asli yang diberikan terhubung.
Anda dapat memeriksa bahwa dekomposisi di atas mengikuti aturan-aturan ini. Lebar dekomposisi pohon adalah ukuran subset terbesarnya, minus satu. Oleh karena itu, dua untuk dekomposisi di atas. Treewidth dari grafik adalah lebar terkecil dari setiap penguraian pohon dari grafik itu.
Dalam tantangan ini, Anda akan diberikan grafik yang terhubung dan tidak diarahkan, dan Anda harus menemukan treewidth-nya.
Meskipun sulit menemukan dekomposisi pohon, ada cara lain untuk menghitung pohon treewidth. Halaman Wikipedia memiliki lebih banyak informasi, tetapi satu metode penghitungan treewidth tidak disebutkan di sana yang sering digunakan dalam algoritma untuk menghitung treewidth adalah lebar minimum eliminasi pemesanan. Lihat di sini untuk makalah yang menggunakan fakta ini.
Dalam urutan eliminasi, kita menghilangkan semua simpul dari grafik satu per satu. Ketika setiap simpul dihilangkan, tepi ditambahkan yang menghubungkan semua tetangga simpul itu satu sama lain. Ini diulangi sampai semua simpul hilang. Lebar pemesanan eliminasi adalah jumlah tetangga terbanyak yang dimiliki oleh simpul mana pun yang dihilangkan selama proses ini. Treewidth sama dengan minimum atas semua pemesanan lebar pemesanan eliminasi. Berikut adalah contoh program menggunakan fakta ini untuk menghitung treewidth:
import itertools
def elimination_width(graph):
max_neighbors = 0
for i in sorted(set(itertools.chain.from_iterable(graph))):
neighbors = set([a for (a, b) in graph if b == i] + [b for (a, b) in graph if a == i])
max_neighbors = max(len(neighbors), max_neighbors)
graph = [edge for edge in graph if i not in edge] + [(a, b) for a in neighbors for b in neighbors if a < b]
return max_neighbors
def treewidth(graph):
vertices = list(set(itertools.chain.from_iterable(graph)))
min_width = len(vertices)
for permutation in itertools.permutations(vertices):
new_graph = [(permutation[vertices.index(a)], permutation[vertices.index(b)]) for (a, b) in graph]
min_width = min(elimination_width(new_graph), min_width)
return min_width
if __name__ == '__main__':
graph = [('a', 'b'), ('a', 'c'), ('b', 'c'), ('b', 'e'), ('b', 'f'), ('b', 'g'),
('c', 'd'), ('c', 'e'), ('d', 'e'), ('e', 'g'), ('e', 'h'), ('f', 'g'), ('g', 'h')]
print(treewidth(graph))
Contoh:
[(0, 1), (0, 2), (0, 3), (2, 4), (3, 5)]
1
[(0, 1), (0, 2), (1, 2), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (3, 4), (4, 6), (4, 7), (5, 6), (6, 7)]
2
[(0, 1), (0, 3), (1, 2), (1, 4), (2, 5), (3, 4), (3, 6), (4, 5), (4, 7), (5, 8), (6, 7), (7, 8)]
3
[(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
4
Anda akan menerima grafik sebagai input, dan Anda harus mengembalikan treewidth sebagai output. Format input fleksibel. Anda dapat mengambil daftar tepi, peta adjacency, atau matriks adjacency sebagai input. Jika Anda ingin menggunakan format input lain, tanyakan di komentar. Anda dapat mengasumsikan input terhubung, dan Anda dapat membangun asumsi itu ke dalam format input Anda, misalnya dengan menggunakan daftar tepi.
EDIT: Operasi bawaan yang menghitung treewidth tidak diizinkan. Saya minta maaf karena tidak menentukan ini di muka.
Kode terpendek menang.
sumber
(V,E)
apakah ini akan menjadi input yang valid?Jawaban:
Oktaf, 195 byte
Sebuah fungsi yang digunakan sebagai input matriks adjacency. Ini mengkonsumsi sejumlah besar memori sehingga tidak berguna jika jumlah simpul lebih dari 10-12.
endfunction
namun harus ditambahkan ke tio.Cobalah online!
Tidak Disatukan:
sumber
SageMath,
29 bytetidak bersaing ** Jawaban ini diposting sebelum perubahan pertanyaan OP bahwa "Builtin dilarang", jadi saya membuatnya tidak bersaing.
Demo online!
sumber
Haskell (Lambdabot),
329321245 byteInilah solusi saya, berkat fleksibilitas input yang berfungsi pada grafik dengan grafik yang berisi jenis apa pun yang merupakan instance dari
Eq
.Cobalah online!
Versi tidak disatukan:
sumber