Skip to main content
Computer Science

Return to Answer

using we instead of you, and ending some setneces.
Source Link
user742
user742

Suppose in a graph $G$ there is one pebble on each vertex except one vertex $v$ with $p(v) = 2$, then above pebbling problem has solution on $G \space iff \space G$ has a Hamiltonian circuit. It's easy to check if there is a Hamiltonian circuit, then there is a solution for pebbling on $G$, on. On the other hand, in any solution forto the pebbling, we should start from vertex $v$, suppose. Suppose that we visit some vertex $u$ twice such that this $u$ is the first vertex which visited twice in $G$ by pebbling algorithm, then youwe have a loop which starts from $u$ and ends in $u$ and finally because $u$ is the first for making loop then we have $p(u) = 1$ so youwe cannot continue pebbling algorithm, so. Indeed if yourthe algorithm has a solution then youwe have $u=v$ which means youwe found a Hamiltonian circuit, which starts fromin $v$.

Suppose in a graph $G$ there is one pebble on each vertex except one vertex $v$ with $p(v) = 2$, then above pebbling problem has solution on $G \space iff \space G$ has a Hamiltonian circuit. It's easy to check if there is a Hamiltonian circuit, then there is a solution for pebbling on $G$, on the other hand, in any solution for pebbling we should start from vertex $v$, suppose that we visit some vertex $u$ twice such that this $u$ is the first vertex which visited twice in $G$ by pebbling algorithm, then you have a loop which starts from $u$ and ends in $u$ and finally because $u$ is the first for making loop then we have $p(u) = 1$ so you cannot continue pebbling algorithm, so if your algorithm has a solution then you have $u=v$ which means you found Hamiltonian circuit, starts from $v$.

Suppose in a graph $G$ there is one pebble on each vertex except one vertex $v$ with $p(v) = 2$, then above pebbling problem has solution on $G \space iff \space G$ has a Hamiltonian circuit. It's easy to check if there is a Hamiltonian circuit, then there is a solution for pebbling on $G$. On the other hand, in any solution to the pebbling, we should start from vertex $v$. Suppose that we visit some vertex $u$ twice such that this $u$ is the first vertex which visited twice in $G$ by pebbling algorithm, then we have a loop which starts from $u$ and ends in $u$ and finally because $u$ is the first for making loop then we have $p(u) = 1$ so we cannot continue pebbling algorithm. Indeed if the algorithm has a solution then we have $u=v$ which means we found a Hamiltonian circuit which starts in $v$.

added 44 characters in body
Source Link
user742
user742

Suppose in a graph $G$ there is one pebble on each vertex except one vertex $v$ with $p(v) = 2$, then above pebbling problem has solution on $G \space iff \space G$ has a Hamiltonian circuit. It's easy to check if there is a Hamiltonian circuit, then there is a solution for pebbling on $G$, on the other hand, in any solution for pebbling we should start from vertex $v$, suppose that we visit some vertex $u$ twice such that this $u$ is the first vertex which visited twice in $G$ by pebbling algorithm, then you have a loop which starts from $u$ and ends in $u$ and finally because $u$ is the first for making loop then we have $p(u) = 1$ so you cannot continue pebbling algorithm except, so if your algorithm has a solution then you have $u=v$ which means you found Hamiltonian circuit, starts from $v$.

Suppose in a graph $G$ there is one pebble on each vertex except one vertex $v$ with $p(v) = 2$, then above pebbling problem has solution on $G \space iff \space G$ has a Hamiltonian circuit. It's easy to check if there is a Hamiltonian circuit, then there is a solution for pebbling on $G$, on the other hand, in any solution for pebbling we should start from vertex $v$, suppose that we visit some vertex $u$ twice such that this $u$ is the first vertex which visited twice in $G$ by pebbling algorithm, then you have a loop which starts from $u$ and ends in $u$ and finally because $u$ is the first for making loop then we have $p(u) = 1$ so you cannot continue pebbling algorithm except $u=v$ which means you found Hamiltonian circuit, starts from $v$.

Suppose in a graph $G$ there is one pebble on each vertex except one vertex $v$ with $p(v) = 2$, then above pebbling problem has solution on $G \space iff \space G$ has a Hamiltonian circuit. It's easy to check if there is a Hamiltonian circuit, then there is a solution for pebbling on $G$, on the other hand, in any solution for pebbling we should start from vertex $v$, suppose that we visit some vertex $u$ twice such that this $u$ is the first vertex which visited twice in $G$ by pebbling algorithm, then you have a loop which starts from $u$ and ends in $u$ and finally because $u$ is the first for making loop then we have $p(u) = 1$ so you cannot continue pebbling algorithm, so if your algorithm has a solution then you have $u=v$ which means you found Hamiltonian circuit, starts from $v$.

Source Link
user742
user742

Suppose in a graph $G$ there is one pebble on each vertex except one vertex $v$ with $p(v) = 2$, then above pebbling problem has solution on $G \space iff \space G$ has a Hamiltonian circuit. It's easy to check if there is a Hamiltonian circuit, then there is a solution for pebbling on $G$, on the other hand, in any solution for pebbling we should start from vertex $v$, suppose that we visit some vertex $u$ twice such that this $u$ is the first vertex which visited twice in $G$ by pebbling algorithm, then you have a loop which starts from $u$ and ends in $u$ and finally because $u$ is the first for making loop then we have $p(u) = 1$ so you cannot continue pebbling algorithm except $u=v$ which means you found Hamiltonian circuit, starts from $v$.