
タイトル：
Complete Graph Solution  Intro to Algorithms

概説：

I told you to use a mathematical formula, so I cheated a little bit.

I wrote a little piece of code to actually generate a complete graph

and then return the number of edges in that graph.

To make a complete graph, I just looped through all the pairs of nodes,

and if one node was smaller than the other, then I made a link between them.

That was mainly to just make sure I didn't make a link from nodes to themselves.

There is no reason not to make a link the other way.

It would have not counted against the total, but this seemed nicer and cleaner.

Let's look at what happens if you loop on all the different values of n

from 1 to 9 and print n and the number of edges in the clique.

A graph with one node has no edges.

A graph with 2 nodes fully connected has one edge, 3 has threethat's a triangle,

4 has six, which is the square with the x through the middle of it,

5 is that pentagramlooking thing that we just showed a minute ago,

and it continues growing up like that.

With that as our insight, can we actually write down what the formula is

for a graph with n nodes?

Essentially what happens is each node gets an edge to each other node,

which we can write as each node has an edge to each other node.

Notice what happens if we use that as our formula, we're going to count this edge,

as it goes from this node to this node.

We're also going to count it again, as it goes from this node to this node.

We've double counted everything, so that should be our formula,

which is Î(nÂ˛). Let's just doublecheck this.

If we print n, clique (n), which I counted by actually creating the clique,

compared that to the formula n * (n 1)/2,

you can see that it matches up perfectly.

So, really the answer that you should have given is this

shouldn't have bothered with any of this creating of stuff.

Now, in addition to all those graphs where the growth rate was linear, we now have one that's quadratic.