Hubungan ekivalensi mencakup masalah (dalam teori grafik)

Relasi ekivalensi pada himpunan vertex terbatas dapat diwakili oleh grafik tidak terarah yang merupakan persatuan cliques yang terpisah. Himpunan simpul mewakili elemen dan tepi mewakili bahwa dua elemen setara.

Jika saya memiliki grafik dan grafik , kita mengatakan bahwa ditutupi oleh jika set dari tepi sama dengan serikat dari set tepi . Tepi set tidak perlu menguraikan. Perhatikan bahwa setiap graf yang tidak diarahkan $G$ $G_1,\dots,G_k$ $G$ $G_1,\dots,G_k$ $G$ $G_1,\dots,G_k$ $G_1,\dots,G_k$ $G$ dapat dicakup oleh sejumlah terbatas hubungan ekuivalensi (yaitu, disjoint union of cliques graph).

Saya punya beberapa pertanyaan:

Apa yang bisa dikatakan tentang jumlah minimal hubungan ekivalensi yang diperlukan untuk mencakup grafik ? $G$
Bagaimana kita bisa menghitung angka minimal ini?
Bagaimana kita bisa menghitung sampul minimum eksplisit , yaitu seperangkat relasi ekivalensi yang ukurannya minimal dan yang mencakup ? $G$ $G$
Apakah masalah ini memiliki aplikasi selain dari logika partisi ( dual logika subset )?
Apakah masalah ini memiliki nama mapan?

Mengingat berbagai kesalahpahaman yang ditunjukkan oleh komentar, berikut adalah beberapa gambar untuk menggambarkan konsep-konsep ini. Jika Anda memiliki ide untuk terminologi yang lebih mudah dipahami (alih-alih "menutupi", "hubungan ekivalensi", "perpaduan kelompok klik-klik" dan "tidak perlu saling lepas" gabungan set perangkat tepi), jangan ragu untuk memberi tahu saya.

Berikut adalah gambar grafik dan satu relasi ekivalensi yang meliputinya:

Berikut adalah gambar dari grafik dan dua hubungan ekivalensi yang meliputinya:
Seharusnya cukup jelas bahwa setidaknya dua hubungan ekivalen diperlukan.

Berikut ini adalah gambar dari grafik dan tiga relasi ekivalensi yang meliputinya: grafik dan tiga hubungan ekivalensi yang meliputinya
Kurang jelas bahwa setidaknya tiga relasi ekivalen diperlukan. Lemma 1.9 dari Dual Logic of Subsets dapat digunakan untuk menunjukkan bahwa ini benar. Generalisasi lemma to nand operasi dengan lebih dari dua input ini adalah motivasi untuk pertanyaan ini.

algorithms graph-theory clique Thomas Klimpel
sumber

Ini adalah masalah NP-Complete yang terkenal . en.wikipedia.org/wiki/Clique_cover_problem

gardenhead

@StephenBly Mungkin ini masalah yang sudah diketahui, tetapi tautan wikipedia yang Anda berikan tidak benar-benar membantu saya. Artikel ini berbicara tentang masalah penutup sudut, tetapi pertanyaan di sini berkaitan dengan masalah penutup tepi. Juga catat bahwa suatu relasi ekivalensi bukanlah suatu klik, tetapi suatu persatuan klik yang terpisah.

Thomas Klimpel

Apa maksud Anda hubungan ekivalensi adalah penyatuan klik-klik? Himpunan simpul mewakili elemen dan tepi mewakili bahwa dua elemen setara. Jika itu bukan representasi yang Anda gunakan maka Anda harus membuatnya jelas.

gardenhead

n - 1

$n-1$

n

$n$

n - 1

$n-1$

@YuvalFilmus Pertanyaan yang diajukan tentang jumlah paling sedikit hubungan ekivalensi yang penyatuannya persis merupakan hubungan tepi dari grafik yang diberikan, bukan yang penyatuannya hanya mencakup grafik yang diberikan.

David Richerby

Jawaban:

$\text{eq}(G)$ $\text{cc}(G)$

Ada kelas grafik khusus di mana nilai pastinya atau batas atas yang baik untuk salah satu angka diketahui. Secara umum, sejauh yang saya ketahui, batasan terbaik diberikan oleh Alon [1]:

{catatan}_{2} n - {catatan}_{2} d \leq eq (G) \leq cc (G) \leq 2 e^{2} (Δ + 1)^{2} dalam n,

$\log_2 n - \log_2 d \leq \text{eq}(G) \leq \text{cc}(G) \leq 2e^2 (\Delta+1)^2 \ln n,$

$\Delta$ $G$ $\lceil n^2/4 \rceil$

$\sf NP$ $\text{eq}(G)$ $\sf NP$

[1] Alon, Noga. "Meliputi grafik dengan jumlah minimum hubungan ekivalensi." Combinatorica 6.3 (1986): 201-206.

[2] Blokhuis, Aart, dan Ton Kloks. "Pada ekuivalensi yang meliputi jumlah splitgraph." Surat pemrosesan informasi 54.5 (1995): 301-304.

[3] Kučera, Luděk, Jaroslav Nešetřil, dan Aleš Pultr. "Kompleksitas dimensi tiga dan beberapa karakteristik grafik yang berhubungan dengan sisi-tepi yang terkait." Ilmu Komputer Teoritis 11.1 (1980): 93-106.

Juho
sumber

Konsol 1.3 dari [1] adalah persis apa yang saya butuhkan (dalam versi yang berlaku untuk komplemen jalan). Sekarang saya tidak lagi punya alasan untuk tidak menulis makalah tentang implikasi umum "(A, B, C, ...) menyiratkan (Z, Y, X, ...)" (urutan dari kalkulus berurutan) di partisi logika dan logika non-klasik serupa. Tapi kurasa aku tidak akan menulisnya setidaknya setengah tahun lagi. Dan mungkin saya bahkan menemukan alasan baru untuk sementara.

Thomas Klimpel

@ThomasKlimpel Bagus sekali! (Bukan fakta bahwa Anda mungkin menemukan alasan baru, tetapi bahwa ini membantu :-))

Juho

Meskipun saya tidak tahu nama untuk masalah seperti itu, saya dapat menunjukkan masalah ini NP-hard.

Untuk grafik bebas segitiga, semua kelas ekivalensi harus cocok. Jumlah minimum kelas ekivalensi yang mencakup grafik sama dengan indeks kromatik grafik.

Menurut artikel ini , menemukan indeks kromatik untuk grafik bebas segitiga adalah NP-complete.

Chao Xu
sumber