/sci/ - Science & Math » Thread #11111781

41KiB, 1200x793, graph theory.png

View Same Google iqdb SauceNAO

Graph theory

Anonymous Sat 02 Nov 09:07:13 2019 No.11111781 View Reply Original Report

Quoted By: >>11111811 >>11112763 >>11112769 >>11112772

Let’s say I have a graph where I found minimal connected vertex cover.
How can I mathematically prove that it is indeed minimal one?

Anonymous

Anonymous Sat 02 Nov 2019 09:44:07 No.11111811 Report

Quoted By: >>11111854 >>11112373 >>11112800 >>11112986 >>11113539

>>11111781
Suppose you have found a vertex cover of size k. It is sufficient to show that there exists no vertex cover of size k-1.

Anonymous

Anonymous Sat 02 Nov 2019 10:26:57 No.11111854 Report

Quoted By: >>11112763

>>11111811
Thanks.
Can I just say something like "I brute forced all the options and there isn't one " or is there more elegant solution?

Anonymous

Anonymous Sat 02 Nov 2019 16:10:43 No.11112373 Report

Quoted By:

>>11111811
k-2 then?

Anonymous

Anonymous Sat 02 Nov 2019 19:48:40 No.11112763 Report

Quoted By:

>>11111781
>minimal
Are you aware that "minimal" is not the same "minimum"? If you really mean "minimal", then simply go over each vertex in the cover one by one and show that removing it results in an infeasible solution.

>>11111854
If you use an algorithm to solve a problem, and that algorithm has been mathematically proven to always give the correct solution for the problem, then it really suffices to say that "this is what the algorithm gave as the solution."

Anonymous

Anonymous Sat 02 Nov 2019 19:50:14 No.11112769 Report

Quoted By:

>>11111781
Fuck you, P=NP is mine.

Anonymous

Anonymous Sat 02 Nov 2019 19:52:25 No.11112772 Report

Quoted By:

>>11111781
"Minimal" in this context usually means a local minimum, i.e. no proper subset of it is a cover. Is that what you mean? Or do you truly want the smallest possible one?

Anonymous

Anonymous Sat 02 Nov 2019 20:09:36 No.11112800 Report

Quoted By:

>>11111811
I think I figured it out.
I can show that in order to cover 2 specific vertexes I have to use certain amount of vertexes but if I do that and want to have it all connected I would have to use more than k-1 vertexes in total and therefore my k size solution has to be correct.
This should hold right?

Anonymous

Anonymous Sat 02 Nov 2019 22:00:29 No.11112986 Report

Quoted By: >>11113069

>>11111811
incorrect

Anonymous

Anonymous Sat 02 Nov 2019 22:51:15 No.11113069 Report

Quoted By: >>11113538

>>11112986
Really, what's your counterexample?

I reason that, supposing there exits a vertex cover $C$ of size $k$ , then for all $k'$ s.t. $k \leq k' \leq |V|$ there exists a vertex cover of size $k'$ (simply add vertices from $V-C$ ).

Therefore, if we have found a vertex cover of size $k$ , and the minimum vertex cover has size $m$ , if $m<k$ , then there exists a vertex cover of size $k-1$ ; and if $m=k$ then by definition there is none of size $k-1$ .

Anonymous

Anonymous Sun 03 Nov 2019 03:05:38 No.11113538 Report

Quoted By:

>>11113069
this (trivially) proves the existence of a minimum vertex cover
it doesn't prove that whatever vertex cover you found is the minimum one of size m

Anonymous

Anonymous Sun 03 Nov 2019 03:07:56 No.11113539 Report

Quoted By:

>>11111811
>It is sufficient to show that there exists no vertex cover of size k-1.
so is there any way to do this other than exhaustively showing that you can't remove any vertex without leaving an edge uncovered?

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches