Win a copy of Kotlin in Action this week in the Kotlin forum!
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

Graph

Arjun Shastry
Ranch Hand
Posts: 1906
1
A graph has 50 edges.How many least number of vertices it can have?(no loops or multiple edges between two vertices please)

Nick George
Ranch Hand
Posts: 815
erhm... if an edge is defined to be the line between two vertecies, and the graph is continuous, wouldn't that make the only possible answers be 51 for a non-loop, and 50 for a loop?

Arjun Shastry
Ranch Hand
Posts: 1906
1
Complete graph?

Bert Bates
author
Sheriff
Posts: 8945
17
could you define your terms more precisely ?

Barbara Norway
Ranch Hand
Posts: 150
Sounds like maybe someone is working on some homework problems

Try this:

Or not....

Arjun Shastry
Ranch Hand
Posts: 1906
1
Originally posted by Barbara Norway:
Sounds like maybe someone is working on some homework problems
Try this:
Or not....

No,I m not doing any homework problem. .
Graph has 50 edges.How many least vertices it can have?
This is the exact problem statement .I have taken this from
Applied combinatorics

Nick George
Ranch Hand
Posts: 815
That being said, none of us (at least not me) understand what you're asking. Care to elucidate?

Jim Yingst
Wanderer
Sheriff
Posts: 18671
I think the main problem here is with "no loops". It's not clear what's a loop. Is this a loop?

Arjun Shastry
Ranch Hand
Posts: 1906
1
Thats circuit or cycle I think.AFAIK,loop means edge from one vertex to itself.

Arjun Shastry
Ranch Hand
Posts: 1906
1
Yes.
Cycle/Circuit
Loop
so if loop is allowed,then only one vertex will suffice.
Now I think the problem is easy.
I think I unnecessarily added that no loops statement.Not aware it will create confusion.

[ September 08, 2004: Message edited by: Arjun Shastry ]
[ September 08, 2004: Message edited by: Arjun Shastry ]

fred rosenberger
lowercase baba
Bartender
Posts: 12542
48
if you make a chart of # verticies vs. max. number of edges, then look at the delta...

1 0 0
2 1 1
3 3 2
4 6 3
5 10 4
6 15 5

the pattern is pretty clear. and it makes sense. if i have x verticies, each vertex will have x-1 edges coming into it, but that counts each edge twice. so i'd have (x * (x-1)) / 2 edges. simplify to (x^2 - x)/2

if i have x+1 verticies, i'd have ((x+1) * ((x+1)-1))/2, simplify to (x^2 + x)/ 2.

the difference between these is

anyway, if you continue this pattern, you can see that 11 are needed.

that's my quick take, but i'm probably wrong.

[ September 09, 2004: Message edited by: fred rosenberger ]
[ September 09, 2004: Message edited by: fred rosenberger ]

Arjun Shastry
Ranch Hand
Posts: 1906
1
.I too got the same answer.11 vertices.
So complete graph with 11 vertices.
Total degree = 11*10 = 110
Hence total edges = 110/2 = 55
If we take complete graph with 10 vertices,then we get 45 edges.
[ September 09, 2004: Message edited by: Arjun Shastry ]

 Consider Paul's rocket mass heater.