Purchase Solution

# Graph Theory and Parse Tree

Not what you're looking for?

1. Path Analysis
Here is a Question for you:
For the diagram below find all the "simple paths" from A to F.
A------------B------------C
| | / |
| | / |
| | / |
|D------------E------------F

2. Note a Hamiltonian circuit visits each vertex only once but may repeat edges. A Eulerian graph traverses every edge once, but may repeat vertice. Looking at the figure below tell me if they are Hamiltonian and/or Eulerian.
*-------*--------*
| / | |
| / | |
|/ | |
*-------*--------*

3. Graphs and Circuit Design
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?

4. Random Graphs
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

5. Trees and Language Processing
Trees occur in various venues in computer science: decision trees in algorithms, search trees, and so on. In linguistics, one encounters trees as well, typically as parse trees, which are essentially sentence diagrams, such as those you might have had to do in primary school, breaking a natural-language sentence into its components--clauses, subclauses, nouns, verbs, adverbs, adjectives, prepositions, and so on. What might be the significance of the depth and breadth of a parse tree relative to the sentence it represents? If you need to, look up parse tree and natural language processing on the Internet to see some examples.

##### Solution Summary

This solution offers to-the-point answers to some assorted questions on graph theory and parse tree.

##### Solution Preview

Graph Theory and Trees
1. Path Analysis
Here is a Question for you:
For the diagram below find all the "simple paths" from A to F.
2. Note a Hamiltonian circuit visits each vertex only once but may repeat edges. A Eulerian graph traverses every edge once, but may repeat vertice. Looking at the figure below tell me if they are Hamiltonian and/or Eulerian.
3. Graphs and Circuit Design
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?
4. Random Graphs
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 ...

Solution provided by:
• BSc (Hons),
• MSc,
• PhD,
###### Recent Feedback
• "Thankyou for the feedback. I have a few question though; With the first statistic about cost below... “According to Sigma-Aldrich catalog, cost of 1L octane is AUD \$ 392.00, whereas the cost of 1L ethanol is AUD \$196.00. Moreover, if ethanol is obtained from sugar industry as a by-product, it may cost even less. Source of oxygen is ambient atmosphere, so it costs nothing. So ethanol is much cheaper than petrol, in fact it is half-priced: AUD \$ (392-196) = \$ 196.” I didn't think it made sense because the cost of petrol per litre is normally a dollar something or even less than a dollar not a couple of hundred of dollars. For example, a statistic that I found in america was: "U.S. ethanol production costs are about \$1.20 per gallon of ethanol, or \$1.82 per gallon on a gasoline-equivalent basis." However, I was wondering whether you could find an Australian statistic. Also, you mentioned that H20 is not a greenhouse gas. However, in the combustion equations it is actually carbon dioxide and water vapour which are produced and they are both greenhouse gases. Finally, how do I calculate the energy efficiency of ethanol and petrol? "
• "Thank you!"
• "Didnt really answer my questions but gave me a start at least."
• "Once again this is tremendous help I can't thank you enough for not only working the problem but explaining in detail how and why!! KR"
• "Awesome thank you so much for the help!!!"

##### Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

##### Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.