GRAPHS

Question 1

What is graph

Answer 1

Mathematically, a graph is a set V of vertices and a set E of edges, such that each edge in E connects two of the vertices in V
We use node as a synonym for vertex

Question 2

Draw unlabeled, labeled and weighted graphs

Answer 2

*See notes for graph

Question 3

When are vertices adjacent to each other?

Answer 3

One vertex is adjacent to another vertex if there is an edge connecting the two vertices (neighbors)

Question 4

What is a path?

Answer 4

Sequence of edges that allows one vertex to be reached from another vertex in a graph

Question 5

What is the length of a path and the degree of a vertex?

Answer 5

Length of a path: Number of edges on the path

Degree of a vertex: Number of edges connected to it

Question 6

Define and illustrate simple path and cycles

Answer 6

Simple path: Path that does not pass through the same vertex more than once
Cycle: Path that begins and ends at the same vertex

Question 7

When is a graph said to be connected?

Answer 7

A graph is connected if there is a path from each vertex to every other vertex
*See notes for pic

Question 8

When is a graph said to be complete?

Answer 8

A graph is complete if there is an edge from each vertex to every other vertex

Question 9

What are the two types of graphs? Illustrate each

Answer 9

Graphs can be undirected or directed (digraph)

*See notes for pic

Question 10

Define: Directed edges and incident edges

Answer 10

A directed edge has a source vertex and a destination vertex

Edges emanating from a given source vertex are called its incident edges

Question 11

How does one convert an undirected graph to a directed graph

Answer 11

To convert undirected graph to equivalent directed graph, replace each edge in undirected graph with a pair of edges pointing in opposite directions

Question 12

What is a DAG?

Answer 12

A special case of digraph that contains no cycles is known as a directed acyclic graph, or DAG

Question 13

Give examples of graph applications?

Answer 13

A roadmap
A map of airline routes
A schematic of the computers and connections that make up the Internet
The links between pages on the Web
The relationship between students and courses i.e courses and their pre-requisites
A diagram of the flow capacities in a communications or transportation network

Question 14

What are the common ways to represent graphs?

Answer 14

The adjacency matrix

The adjacency list

Question 15

What is an adjacency list?

Answer 15

The adjacency list for the graph is an array of N linked lists
Each individual list shows what vertices a given vertex is adjacent to.
Adjacency list shows which vertices are adjacent to—that is, one edge away from—a given vertex, not paths from vertex to vertex.

*See notes for illustration

Question 16

What are the different types of graph traversal

Answer 16

A depth-first search (DFS), uses a stack

A breadth-first search (BFS), uses a queue

Question 17

List the rules of Depth First Search

Answer 17

RULE 1: If possible, visit an adjacent unvisited vertex, mark it, and push it on the stack
RULE 2: If you can’t follow Rule 1, then, if possible, pop a vertex off the stack.
RULE 3: If you can’t follow Rule 1 or Rule 2, you’re done

Question 18

List the rules of Breadth First Search

Answer 18

1: Visit the next unvisited vertex(if there is one) that’s adjacent to the current vertex, mark it and insert it into the que
2: If you can’t carry out rule 1 because there are no more unvisited vertices remove a vertex from the queue(if possible) and make it the current vertex
3: If you can’t follow Rule 1 or Rule 2, you’re done

Question 19

Describe the minimum spanning tree

Answer 19

Subset of edges whose sum of edge weights is as small as possible
In a weighted graph, you can sum the weights for all edges in a spanning tree and attempt to find a spanning tree that minimizes this sum
There are several algorithms for finding a minimum spanning tree for a component.
For example, to determine how an airline can service all cities, while minimizing the total length of the routes it needs to support

Question 20

Describe the topological sort

Answer 20

A directed acyclic graph (DAG) has an order among the vertices
A topological order assigns a rank to each vertex such that the edges go from lower- to higher- ranked vertices
Topological sort: process of finding and returning a topological order of vertices in a graph
*See notes for examples

Question 21

What is a subgraph?

Answer 21

A subgraph consists of a subset of a graph’s vertices and a subset of its edges

Question 22

Write down java code to create a graph

Answer 22

*See notes for code

Question 23

Discuss two types of algorithms that have been used by taxi hailing applications to improve the customer experience today

Answer 23

Dijkstra’s search algorithm to find out the best route

DFS to find shortest route