New answers tagged

1

This is a generalization of the Uniqueness property of minimum spanning trees, and the proof is almost the same: Note there is at least one edge that belongs to exactly one of $T$ and $T'$. Among such edges, let $e_1$ be the one with least weight. Without loss of generality, assume $e_1 \in T$. As $T'$ is an MST, $e_1\cup T'$ must contain a cycle $C$ with $...


2

The standard way to create soft constraints in MaxSAT is to use label variables: For each $AMO_j$ constraint, create a new variable $l_j$. Then create an unit clause $(\lnot l_j)$ with weight $1$ and add the literal $l_j$ to every clause of the standard $AMO_j$ encoding that contains only hard (infinite weight) clauses. Now the label variable $l_j$ acts ...


2

Saad Balbiyad's answer is correct. This answer spells out some of the ideas in more detail. A set is countably infinite if its elements can be paired up with natural numbers so that (a) no elements are paired up with the same number, (b) no element is paired with two numbers, (c) there are no numbers or elements left unpaired. In other words, a set is ...


3

You are confusing countable and finite. A finite set is always countable, however a countable set can be infinite. You only need to find an injection from your set and $\mathbb{N}$, it means that you can identify each element of your set using a natural number (a code if you prefer). For instance you can code the set of functions from $\{a,b\}$ to $\mathbb{...


Top 50 recent answers are included