my dog learned polymorphism*
The moose likes Programming Diversions and the fly likes Graph Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Graph" Watch "Graph" New topic
Author

Graph

Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
A graph has 50 edges.How many least number of vertices it can have?(no loops or multiple edges between two vertices please)


MH
Nick George
Ranch Hand

Joined: Apr 04, 2004
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?


I've heard it takes forever to grow a woman from the ground
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
Complete graph?
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8805
    
    5
could you define your terms more precisely ?


Spot false dilemmas now, ask me how!
(If you're not on the edge, you're taking up too much room.)
Barbara Norway
Ranch Hand

Joined: Sep 30, 2003
Posts: 150
Sounds like maybe someone is working on some homework problems

Try this:
someone's homework answer

Or not....


farmkitty
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
Originally posted by Barbara Norway:
Sounds like maybe someone is working on some homework problems
Try this:
someone's homework answer
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

Joined: Apr 04, 2004
Posts: 815
That being said, none of us (at least not me) understand what you're asking. Care to elucidate?
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
I think the main problem here is with "no loops". It's not clear what's a loop. Is this a loop?

How about this? One loop? Two? Three? Zero?


"I'm not back." - Bill Harding, Twister
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
Thats circuit or cycle I think.AFAIK,loop means edge from one vertex to itself.
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
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

Joined: Oct 02, 2003
Posts: 11170
    
  16

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 ]

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
.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 ]
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Graph
 
Similar Threads
How to detect circle in a directed graph?
Making a collection modifiable only in a specific class
WA #2 ..... word association
minimal subgraph in a graph
I need graph representation API