===========================================================================
CSC 363H              Tutorial Exercises for Week 11 (UTM)       Fall 2004
===========================================================================

1) Show that HAM-CYCLE = { <G> | G is a directed graph that 
			contains a Hamiltonian cycle } is NP-Complete.

A Hamiltonian cycle in a graph G is a simple cycle that includes every
vertex of G, i.e., a list of the vertices v_1, v_2, ..., v_n such that
every vertex occurs exactly once in the list and G contains all of the
edges (v1,v2), (v2,v3), ..., (v_{n-1}, v_n), (v_n,v_1).


2) Show that UHAMPATH = { <G,s,t> | G is an UNDIRECTED graph that contains a 
Hamiltonian path from s to t} is NP-COMPLETE.

3) Let PARTITTION = { T=<a1,a2,....,an> | there is a subset $S$ of T so that
sum of numbers in S = sum of numbers not in S}.
example : <1,2,3,4> is in PARTITTION since 1+4 = 2+3, and similarily 
<1,10,11> is in PARTITION, but <7,8,10,13> is not in PARTITION.