# Various Graph Theory Questions

Through the use of appropriate algorithms minimal spanning tree solutions and optimal networking routes are discovered and explained. The document contains detailed solutions and drawings to help understand how to use the included algorithms.

© BrainMass Inc. brainmass.com October 17, 2018, 1:54 am ad1c9bdddfhttps://brainmass.com/math/discrete-math/various-graph-theory-questions-357361

#### Solution Preview

** Please see the attached file for the complete solution response **

1. In creating minimal spanning trees its best to use either Prim's Algorithm or Kruskal's Algorithm.

Prim's is as follows:

Step 1: Pick any vertex as a starting vertex. (Call it S). Mark it with any given color, say red.

Step 2: Find the nearest neighbor of S (call it P1). Mark both P1 and the edge SP1 red. cheapest unmarked (uncolored) edge in the graph that doesn't close a colored circuit. Mark this edge with same color of Step 1.

Step 3: Find the nearest uncolored neighbor to the red subgraph (i.e., the closest vertex to any red vertex). Mark it and the edge connecting the vertex to the red subgraph in red.

Step 4: Repeat Step 3 until all vertices are marked red. The red subgraph is a minimum spanning tree.

And Kruskal's:

Step 1: Find the cheapest edge in the graph (if there is more than one, pick one at random). Mark it with any given color, say red.

Step 2: Find the cheapest unmarked (uncolored) edge in the graph that doesn't close a colored or red circuit. Mark this edge ...

#### Solution Summary

This solution includes the detailed steps to solving various discrete math graph theory questions. It includes minimal spanning trees, optimal paths, and optimal flow.

Graph Theory and Parse Tree

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.