Greedy algoritm problem

[gauravdott]

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
please help me solve these questions

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.

Please help........

[darkagn]

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 :)

[ganesh sk]

#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
                    added */
    int i, j;
    int aux;

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

    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];
                last_added[i] = j;
            }

    for (i = 0; i <= W; ++i)
        if (last_added[i] != -1)
            printf("Weight %d; Benefit: %d; To reach this weight I added object %d (%d$ %dKg) to weight %d.\n", i, a[i], last_added[i] + 1, v[last_added[i]], c[last_added[i]], i - c[last_added[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)) {
        printf("Added object %d (%d$ %dKg). Space left: %d\n", last_added[aux] + 1, v[last_added[aux]], c[last_added[aux]], aux - c[last_added[aux]]);
        aux -= c[last_added[aux]];
    }

    printf("Total value added: %d$\n", a[W]);
}

int main(int argc, char *argv[]) {
    fill_sack();

    return 0;
}