Math Is Fun Forum

rhymin

Member

Registered: 2013-03-26

Posts: 20

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?

John E. Franklin

Member

Registered: 2005-08-29

Posts: 3,588

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