Question about graph

Printable View

Dec 6th 2012, 07:42 AM
kakatomy

Question about graph

The question is Calculate the maximum number of edges in a simple graph with nnodes and k components.

I dont really understand what the question means .. and how to solve this..

Thanks...
Dec 6th 2012, 08:32 AM
Plato

Re: Question about graph

Quote:

Originally Posted by kakatomy

[FONT=arial]The question is Calculate the maximum number of edges in a simple graph with nnodes and k components.
I dont really understand what the question means .. and how to solve this..

A component is a maximally connected subgraph of a graph.
You need to check your text material. Some authors allow degenerate components, one vertex, most do not.

Here is an example: Consider a twelve vertex graph with three components having three, four and five vertices.
Then the graph could be $K_3\cup K_4\cup K_5$ .
That is a maximum of $3+6+10=19$ edges in all.

That said, I don't know how to solve the general case.
Dec 6th 2012, 09:03 AM
kakatomy

Re: Question about graph

Quote:

Originally Posted by Plato

A component is a maximally connected subgraph of a graph.
You need to check your text material. Some authors allow degenerate components, one vertex, most do not.

Here is an example: Consider a twelve vertex graph with three components having three, four and five vertices.
Then the graph could be $K_3\cup K_4\cup K_5$ .
That is a maximum of $3+6+10=19$ edges in all.

That said, I don't know how to solve the general case.

The question didnt provide anything else so I also dont understand the question....

SOsad :(