Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

#1 2013-04-11 02:19:38

rhymin
Member

Offline

Graph Question

I haven't studied graphs in a long time and was wondering how to go about answering these 2 questions:

1) Random graphs are a fascinating subject of applied and theoretical research. These can be generated with a fixed vertex set V and edges added to the edge set E based on some probability model, such as a coin flip. Speculate on how many connected components a random graph might have if the likelihood of an edge (v1,v2) being in the set E is 50%. Do you think the number of components would depend on the size of the vertex set V? Explain why or why not.

2) You are an electrical engineer designing a new integrated circuit involving potentially millions of components. How would you use graph theory to organize how many layers your chip must have to handle all of the interconnections, for example? Which properties of graphs come into play in such a circumstance?

#2 2013-05-14 13:42:56

John E. Franklin
Star Member

Offline

Re: Graph Question

2.) if the graph cannot be drawn without lines crossing each other, then you need another layer probably to get the 3-d effect, like knot theory sort of.


igloo myrtilles fourmis

Board footer

Powered by FluxBB