Mengubah penutup sewenang-wenang menjadi penutup simpul

Diberikan adalah grafik planar dan biarkan menunjukkan penyisipannya di bidang st setiap tepi memiliki panjang . Saya juga memiliki himpunan titik mana setiap titik terkandung dalam . Selain itu, ia berlaku untuk titik dalam yang ada dengan jarak geodesik ke paling banyak satu. (Jarak diukur sebagai jarak terpendek dalam .) $G=(V,E)$ $\mathcal{G}$ $1$ $C$ $c \in C$ $\mathcal{G}$ $p$ $\mathcal{G}$ $c \in C$ $p$ $\mathcal{G}$

Saya ingin berargumentasi bahwa dengan diberikannya mana kondisi di atas berlaku, saya dapat dengan mudah mengubahnya menjadi penutup verteks, atau dengan kata lain, mengubahnya menjadi dengan kardinalitas yang sama dengan ditempatkan dalam pada titik dari , dan masih mencakup . $C$ $C'$ $c \in C'$ $\mathcal{G}$ $G$ $C'$ $G$

Pendekatan saya adalah mengorientasikan tepi dan memindahkan titik-titik dalam pada titik akhir dari busur. Tapi sejauh ini saya tidak menemukan orientasi yang benar yang menghasilkan dari . $C$ $C'$ $C$

Adakah yang punya ide?

algorithms graph-theory set-cover pengguna695652
sumber

Saya tidak begitu mengerti masalahnya. Apa artinya " dalam "? Bagaimana tepatnya Anda mengukur jarak? Jika Anda maksudkan bahwa selalu berada di tepi, maka tampaknya jika Anda meletakkannya di kedua ujung, maka setiap titik pada jarak paling banyak darinya - yaitu kedua titik akhir - masih pada jarak paling banyak darinya. Untuk orientasi apa pun.

p

$p$

G

$\mathcal{G}$

p

$p$

1

$1$

1

$1$

Yuval Filmus

@Yuval Filmus

adalah gambar busur jordan dari

, yaitu subset dari

hanya berarti bahwa titik tersebut harus terkandung dalam gambar dan bukan hanya di mana saja di pesawat. Jarak diukur sebagai jarak geodesik dalam

, yaitu jalur terpendek yang menghubungkan dua titik dalam gambar. Untuk komentar terakhir Anda, ambil siklus 4 dan letakkan dua poin di tengah tepi pertama dan ketiga. Ini mencakup seluruh grafik, tetapi jika Anda sekarang memindahkan satu titik pada titik akhir simpul searah jarum jam dan satu titik di ujungnya searah jarum jam titik ujung itu melakukan penutup

G

$\mathcal{G}$

G

$G$

\mathhbb R^{2}

$\mathhbb{R}^2$

p \in G

$p \in \mathcal{G}$

G

$\mathcal{G}$

user695652

Jawaban:

Jika tidak ada poin dalam berbaring tepat pada titik tengah dari tepi di , maka itu sudah cukup untuk mengasosiasikan setiap titik di ke titik terdekat di . Saya akan meninggalkannya sebagai latihan bagi pembaca untuk membuktikan ini (petunjuk: buktikan dengan kontradiksi). $C$ $\mathcal{G}$ $C$ $\mathcal{G}$

Di sisi lain, jika titik dalam dibiarkan terletak di titik tengah tepi, maka kami dapat memberikan contoh tandingan: $C$

masukkan deskripsi gambar di sini

Garis biru dan lingkaran adalah dan salib merah . $\mathcal{G}$ $C$

DIedit UNTUK MENAMBAH: Contoh dengan grafik biconnected

masukkan deskripsi gambar di sini

mhum
sumber

Terima kasih banyak atas contoh tandingannya. Apakah Anda setuju bahwa jika kami membatasi grafik agar tidak terhubung, maka klaim itu benar, bahkan jika semua titik ada di tengah?

user695652

Saya tidak berpikir bi-keterhubungan akan menyelamatkan Anda. Saya telah mengedit jawaban saya dengan contoh baru.

mhum

Ini pertanyaan yang agak berbeda. Mungkin masuk akal untuk mempostingnya secara terpisah.

mhum

@ mhum Bagaimana Anda membuat gambar grafik? Apakah ada beberapa program untuk itu?

Tacet

@Tetet Saya tidak ingat persis bagaimana saya melakukan ini. Saya pikir yang pertama mungkin MS Paint atau GIMP. Yang kedua bisa berupa GIMP atau Geogebra.

mhum