Determine whether each of the following graphs is a tree. If it is not a tree, explain why.
State whether the following statements are true about trees:
Adding one edge to any tree creates a new tree.
A tree has no Eulerian or Hamiltonian circuits.
If you remove any edge from a tree it creates a disconnected graph.
A tree has at least one Hamiltonian circuit, but not necessarily an Eulerian circuit.
Sarah has three children: Kate, Matt and Tom. Kate has four children, Lisa, Sandy, Amy and Robert. Matt has two sons, Joseph and Chris. Both Tom and Lisa have one child each: Barbara and Alex, respectively.
If the starting vertex represents Sarah, create a tree to represent the parent-child relationships in this family.
Bianca is writing a report and needs to create a table of contents. Her report consists of five chapters, each broken down into sections. The first chapter is her introduction, so it has just one section. Her second and third chapters both have three sections, while the fourth chapter has six sections. The fifth and final chapter is the conclusion which again has only one section.
Create a tree that represents the structure of Bianca's table of contents.
Mitchell is tracing his family lineage back three generations. His mother's name is Rebecca, and his father's name is Connor. Rebecca's parents are Mabel and Patrick, and Connor's parents are Juliet and Mark. Mitchell does not know Mabel's parents's names, but he knows that Patrick's parents are April and Todd. On the other side, Mitchell knows that Juliet's parents are Daisy and Leonard, and Mark's dad is called Richard. Mitchell does not know the name of Mark's mother.
If the initial vertex represents Mitchell, create a family tree of the last three generations from the information above. Use "Unknown" for the name of any ancestors that he doesn't know the name of.
Determine whether following networks have a spanning tree:
State the definition of:
A spanning tree
A minimum spanning tree
Create a distance table for the following weighted networks.
If there is no edge connecting two particular vertices, represent this with an X.
The distance table for a weighted network is shown below. Complete the network by labelling the vertices.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | - | 6 | - | - | 12 |
| B | 6 | - | - | 8 | 9 |
| C | - | - | - | 14 | 7 |
| D | - | 8 | 14 | - | - |
| E | 12 | 9 | 7 | - | - |
Construct the minimal spanning tree for each weighted network below.
In a certain area, the council wanted to lay down new electric cables. The given graph displays the map of the area:
To minimise the cost of cables, the council wants to connect the houses in such a way that they minimise the cable length. Construct a graph that will minimise the cable length.
Water pipes need to be laid down in a new area that is undergoing construction. The given graph shows the suggested plan where the numbers represent the lengths of the pipes:
To minimise the cost, the council wants to minimise the total length of water pipes used. Construct a graph that would achieve this.
