Lesson 2

Question 1

A _G, consists of two sets V and E.
V is a finite non-empty set of vertices. V(G) = {Vi, Vj…Vn} E is the set of pairs of vertices. E(G) = {(Vi,Vj),(Vk,Vl…)} These pair of vertices are called edges.

Answer 1

Graphs

Question 2

Kinds of Graphs

Answer 2

Undirected Graph
Directed Graph

Question 3

The pair of vertices representing any edge in unordered.
Uses a pair of parentheses to denote an edge in an _ graph
(V1, V2) = (V2, V1)

Answer 3

Undirected Graph

Question 4

The pair of vertices representing any edge is ordered.
Uses angled brackets to denote edges in a _ graph
Also known as digraph
<V1,V2> != <V2, V1>
<V1,V2> where V1 = tail, V2 = head.

Answer 4

Directed Graph

Question 5

The maximum number of edges in any n vertex is n(n-1)/2

Answer 5

Undirected Graph

Question 6

The maximum number of edges in any n vertex is n(n-1).

Answer 6

Directed Graph

Question 7

A “walk” from one vertex to another along directed edges.

Answer 7

Path

Question 8

A path wherein all vertices except the first and the last are distinct.

Answer 8

Simple Path

Question 9

A simple path where the first and the last vertices are the same.

Answer 9

Cycle

Question 10

Degree of a vertex (Directed Graph)

Answer 10

In-degree
Out-degree

Question 11

The number of edges for which the vertex is the head/2nd component.

Answer 11

In-degree

Question 12

The number of edges for which the vertex is the tail/1st component.

Answer 12

Out-degree

Question 13

Number of edges incident to that vertex.

Answer 13

Degree of a vertex (Undirected Graph)

Question 14

An undirected/directed graph is said to be connected if for every pair of distinct
vertices Vi, Vj in V(G), there is a path from
Vi to Vj.

Answer 14

Connected

Question 15

A directed graph is said to be strongly connected if for every pair of vertices Vi, Vj in V(G), there is a directed path from Vi to
Vj and from Vj to Vi

Answer 15

Strongly Connected (Directed graph)

Question 16

an N vertex graph G is a two-dimensional array (NxN), say A, with the property such that A[i,j] = 1 IFF the edge (Vi, Vj) ((<Vi, Vj>) for directed graph) is in E(G). Otherwise, A[i,j]=0

Answer 16

Adjacency Matrix

Question 17

N rows of the adjacency matrix are
represented as N linked lists. The nodes in each list represented the vertices adjacent from vertex. Each node has at least 2 fields: vertex and link.

Answer 17

Adjacency List

Question 18

Graph Traversals

Answer 18

DFS (Depth First Search)
BFS (Breadth First Search)

Question 19

The starting vertex v is visited
An unvisited vertex w adjacent to v is selected and a _from w is initiated
When a vertex u is reached such that all its adjacent vertices have been visited, back up to the last vertex visited which has an unvisited vertex w adjacent to it and initiate _ from w.
The search terminates when no visited vertex can be reached from any of the unvisited ones.

Answer 19

DFS (Depth First Search)

Question 20

Starting at vertex v and marking it as visited. In _, all unvisited vertices adjacent to v are visited next.
Then, the unvisited adjacent to these vertices are visited and so on.

Answer 20

BFS (Breadth First Search)

Question 21

A connected non-cyclic graph
A minimal connected subgraph (by minimal, it means one with the fewest number of edges.)
Any tree consisting solely of edges in the graph including all vertices in the graph.

Answer 21

Spanning Trees

Question 22

Finding a spanning tree with the cost.
The cost of the spanning tree is the sum of all the costs of the edges in that tree
One approach = algorithm

Answer 22

Minimum Cost Spanning Trees
Kruskal’s

Question 23

The minimum cost spanning tree is built, edge by edge. An edge is included in the tree if it does not form a cycle with edges
already in the tree.

Answer 23

Kruskal’s ALgorithm