Graphs

Question 1

Graph

Answer 1

A graph consists of end points (vertices/nodes) that are joined by lines(edges/arcs)

Question 2

degree of a vertex

Answer 2

the number of edges(lines) going away from a vertex

Question 3

Isolated Vertex

Answer 3

has no neighboring vertices connected to it

Question 4

Cycle

Answer 4

edges creating returns to connected vertices

Question 5

examples of use of graphs

Answer 5

-modelling gas pipelines
-managing air transport systems
-representing computer networks

Question 6

types of graph

Answer 6

-labeled/unlabeled
-weighted/unweighted
-directional/unidirectional

Question 7

Adjacent Matrix

Answer 7

representing vertex connections to other vertices (grid)

Question 8

adjacency list

Answer 8

collection of lists which represents the neighbors of each vertex(node) in a graph

Question 9

adjacency (list vs matrix)

Answer 9

+more space efficient (not storing 0s/ repeats for undirected graphs)
-longer programming time if you want to make object based list for weighted graphs

Question 10

Tree Graph

Answer 10

graph that is…undirected…has no cycles

Question 11

Binary tree

Answer 11

undirected graph with no cycles where…each vertex has two children at most and there is a clear root node

Question 12

Creating binary trees from list of strings

Answer 12

1. Put them in via the order they are given (i.e. first is root)
2. compare the weight for subsequent letters (heavier nodes go right) (lighter nodes go left) and go below a node that takes a side
3. move onto second letter if they have the same first letter