Hi, I am new to algorithms and i have following assingment to do, although i understand Greedy algorithm but i have no idea how to proceed

1. Prove that a graph with n nodes and more than n-1 edges must contain at least one cycle.

2. Suppose the cost of laying a telephone cable from point a to point b is proportional to the Euclidean distance from a to b. A certain number of towns are to be connected at minimum cost. Find an example where it costs less to lay are connected at minimum cost. Find an example where it costs less to lay the cables via an exchange situated in between the towns than to use only direct links.

Hi gauravdott and welcome to DaniWeb,

For number 1, I would use the mathematical proof by iteration - ie prove the statement true for n=2 then assume true for n=k and prove true for n=k+1.

Number 2 is a little trickier but this link might help:
http://en.wikipedia.org/wiki/Kruskal's_algorithm
Kruskal's algorithm determines the minimum spanning tree of a graph. If you imagine each town to be a node in a graph and the telephone lines to be the edges, can you think of how you might find the minimum cost? I'm sure once you work out this part of the question, the next will be much simpler.

Good luck :)

``````#include <stdio.h>

#define MAXWEIGHT 100

int n = 3; /* The number of objects */
int c[10] = {8, 6, 4}; /* c[i] is the *COST* of the ith object; i.e. what
YOU PAY to take the object */
int v[10] = {16, 10, 7}; /* v[i] is the *VALUE* of the ith object; i.e.
what YOU GET for taking the object */
int W = 10; /* The maximum weight you can take */

void fill_sack() {
int a[MAXWEIGHT]; /* a[i] holds the maximum value that can be obtained
using at most i weight */
int last_added[MAXWEIGHT]; /* I use this to calculate which object were
int i, j;
int aux;

for (i = 0; i <= W; ++i) {
a[i] = 0;
}

a[0] = 0;
for (i = 1; i <= W; ++i)
for (j = 0; j < n; ++j)
if ((c[j] <= i) && (a[i] < a[i - c[j]] + v[j])) {
a[i] = a[i - c[j]] + v[j];
}

for (i = 0; i <= W; ++i)
else
printf("Weight %d; Benefit: 0; Can't reach this exact weight.\n", i);

printf("---\n");

aux = W;
while ((aux > 0) && (last_added[aux] != -1)) {
}