Explore BrainMass
Share

Graph Theory and Parse Tree

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

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.

© BrainMass Inc. brainmass.com October 25, 2018, 9:54 am ad1c9bdddf
https://brainmass.com/math/discrete-math/graph-theory-parse-tree-590945

Solution Preview

Please see the attachment.

Answer to 590945
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 Summary

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

$2.19
See Also This Related BrainMass Solution

Identify and implement the role of fluency in reading and comprehension.

Identify and implement the role of fluency in reading and comprehension. Please see attachments.

The primary purpose of reading is to gain meaning from connected text. Important for this purpose is that recognition of text becomes a fluent process. Fluency is considered to be composed of three components: accuracy, automaticity, and prosody (Kuhn & Stahl, 2003; National Reading Panel, 2000). Accuracy entails the correct identification of a word. Automaticity is the immediate recognition of words that bypass the decoding process. Finally, prosody is the ability of an individual to read while providing the appropriate expression
implied by the text (e.g., intonation, stress, and timing). Although accurate identification of words is necessary for the comprehension of connected text, results reported from the National Assessment of Education Progress, which focused on reading performance
during the fourth grade, showed that accuracy alone is not related to reading comprehension in a strong manner (Pinnell et al., 1995). Further, this same research identified a small number of children who demonstrated average levels of comprehension with relatively low levels of accuracy. Although these results failed to establish a strong relationship between accuracy and reading comprehension, without accurate word identification, comprehension of
connected text would not be possible. It appears, therefore, that accurate identification of words is necessary but not sufficient to foster comprehension of written text.

View Full Posting Details