Graph/Tree

Question 1

What are two sets that determine a graph?

Answer 1

G(V, E). A set of vertices | V | and set of edges | E |.

Question 2

What are graph properties?

Answer 2

1. Weight (weighted/unweighted)
2. Directionality (directed/undirected)
3. Path
4. Cycle
5. Connectivity
6. Vertex Degree

Question 3

What is a weighted graph vs an un-weighted graph?

Answer 3

A graph that has numerical weights associated with every edge, while there are no weights in an un-weighted graph.

Question 4

What is a directed graph vs un-directed graph?

Answer 4

In a directed graph, there are certain ways that could be travelled between nodes (like a one-way street) while in an undirected graph, either way can be travelled through edges (bidirectional).

Question 5

What is a path?

Answer 5

A path is a sequence of vertices that are connected to edges.
ex. A->B->C->B->C

Question 6

What is a simple path?

Answer 6

A simple path is a path with no vertices repeated.

ex. A->B->C

Question 7

What is a cycle?

Answer 7

A cycle is a simple path that start and end at the same node.

ex. A->B->C->A

Question 8

What is a connected graph?

Answer 8

A graph where there exists a path between every 2 vertices (otherwise disconnected).

Question 9

What is a bipartite graph?

Answer 9

A graph where all vertices can be divided into two sets: V1 and V2 such that

V1 ⋃ V2 = V (all vertices are used) (Union is OR)

AND

V1 ⋂ V2 = Ø (no vertices belong to both V1 and V2) (Intersection is AND)

AND
Vertexes are adjacent only between elements of V1 and V2.

Question 10

What is a vertex degree in an UNDIRECTED graph?

Answer 10

The number of edges adjacent to the particular vertex.

Question 11

What are vertex degrees in a DIRECTED graphs composed of?

Answer 11

Indegrees and outdegrees.

Question 12

What is an indegree in a directed graph?

Answer 12

The number of edges that point to a vertex.

Question 13

What is an outdegree in a directed graph?

Answer 13

The number of edges that start from a particular vertex.

Question 14

What is a clique?

Answer 14

A strongly connected, undirected graph in which every two vertices have an edge.

Question 15

An “n-clique” clique has n edges.

Question 16

What is the relationship amongst number of edges in a clique and the number of vertices.

Answer 16

Arithmetic series.

|E| = (V(V-1))/2

Question 17

What are two ways graphs are represented?

Answer 17

Adjacency List / Adjacency Matrix (V x V).

Question 18

When should you use an adjacency matrix to represent a graph?

Answer 18

Use an adjacency matrix when time is critical (only O(1), compared to O(n) for list).

Question 19

When should you use an adjacency list to represent a graph?

Answer 19

Use an adjacency list when space is critical (O(E) (or O(n^2) for worst case compared to O(n^2) for matrix).

Question 20

What is a tree?

Answer 20

A tree is a graph that is connected, acyclic, and undirected.

Question 21

What is a root node in a tree?

Answer 21

The topmost node of a tree that does not have any parent node.

Question 22

What can you do if a tree does not have a specified root?

Answer 22

You can take any vertex and name it as root.

Question 23

What is a leaf node in a tree?

Answer 23

Leaf nodes are nodes which do not have any child nodes.

Question 24

What is a parent node in a tree?

Answer 24

The node which is a predecessor of a node is called the parent of that node.

Question 25

What is a child node in a tree?

Answer 25

The node which is the immediate successor of a node is called the child of that node.