Dalam teori grafik, Cactus adalah grafik yang terhubung sehingga setiap dua siklus sederhana yang berbeda dalam grafik berbagi paling banyak satu titik.

Berikut ini adalah Cactus dengan 3 siklus sederhana yang diuraikan dengan garis putus-putus.

Grafik berikut ini mirip dengan yang digambarkan di atas tetapi bukan Cactus karena dua simpul berlabel merah dibagi oleh dua siklus sederhana.

Berbagai hal bisa menjadi sedikit lebih rumit, misalnya grafik berikut:

Mungkin terlihat seperti Kaktus tetapi tidak. Ini dapat ditunjukkan dengan menyoroti siklus berikut:

Siklus ini berbagi lebih dari satu titik dengan banyak siklus yang lebih jelas dalam grafik.

Definisi

Grafik terhubung adalah grafik sedemikian rupa sehingga ada setidaknya satu jalur antara dua simpul.
Siklus sederhana adalah jalur pada grafik yang dimulai dan berakhir pada titik yang sama dan tidak mengunjungi titik lebih dari sekali.
Grafik sederhana adalah grafik tanpa arah, tidak tertimbang sedemikian rupa sehingga tidak ada simpul yang terhubung satu sama lain dengan lebih dari satu sisi dan tidak ada simpul yang terhubung dengan dirinya sendiri. Grafik sederhana adalah jenis grafik paling dasar dan itulah yang dimaksud kebanyakan orang ketika mereka mengatakan grafik.

Tugas

Ambil grafik sederhana sebagai input dan putuskan apakah itu adalah grafik Cactus. Anda harus menampilkan dua nilai berbeda satu untuk Benar dan satu untuk Salah. Anda dapat mengambil input dalam format apa pun yang Anda inginkan.

Ini adalah kode-golf sehingga Anda harus berusaha meminimalkan jumlah byte jawaban Anda.

Uji Kasus

Menguji Kasus sebagai Matriks Adjacency

code-golf decision-problem graph-theory Wisaya Gandum
sumber

Bisakah Anda melihat solusi saya, beri tahu saya apakah itu valid? Saya jatuh seperti pola yang jelas terlalu jelas dan saya telah melewatkan sesuatu.

Shaggy

@ Shaggy Saya tidak bisa membaca JavaScript, Jika Anda menjelaskannya, saya mungkin bisa.

Wheat Wizard

Saya dapat mencoba. Saya memeriksa 2 hal: 1) Apakah emengandung persis satu elemen DAN memang vmengandung persis 2 DAN vsama dengan elemen pertama e? 2) ATAU Apakah vsama dengan set gabungan elemen pertama dari setiap elemen e? Kasus tes kedua melewati pemeriksaan pertama ( v=[1,2]=e[0]=[1,2]) dan kasus uji lain yang harus pertandingan benar kedua, misalnya kasus # 4: v=[1,2,3,4,5,6]=[e[0][0],e[1][0],e[2][0],e[4][0]]=[1,2,3,4,5,6].

Shaggy

@Shaggy Ini tidak berfungsi misalnya diagram pertama yang diberikan gagal.

console.log(f([1,2,3,4,5,6,7,8,9,10,11,12,13])([[1,2],[1,3],[3,4],[2,4],[3,5],[5,6],[6,7],[7,8],[8,5],[7,9],[9,10],[10,11],[11,7],[8,12],[8,13]]))

Wheat Wizard

Haruskah itu kembali trueatau false?

Shaggy

Apakah itu Kaktus?

Definisi

Tugas

Jawaban:

Mathematica, 62 byte