Graphs

Question 1

Graph Definition

Answer 1

a collection of vertices (or nodes) and the connections between them

Question 2

simple graph G = (V, E)

Answer 2

consists of a nonempty set V of vertices and a possibly empty set E of edges, each edge being a set of two vertices from V.

Question 3

The number of vertices and edges is denoted by ___ and ____, respectively.

Answer 3

|V|, |E|

Question 4

A directed graph, or a digraph, G = (V, E)

Answer 4

consists of a nonempty set V of vertices and a set E of edges (also called arcs), where each edge is a pair of verices from V.

Question 5

One edge of a simple graph is of the form ___ and ____ = _____

Answer 5

{v_i, v_j}; {v_i, v_j​} = {v_j, v_i}

Question 6

In a digraph, each edge is of the form ___ and ____ != _____

Answer 6

(v_i, v_j); (v_i, v_j​) != (v_j, v_i)

Question 7

Miltigraph

Answer 7

• a graph in which two vertices can be joing by multiple edges

a multigraph G = (V, E, f) is composed of a set of vertices V, a set of edges E, and a function f: E → {{v_i,v_j} : v_i,v_j ∈ V and vi != v_j}

Question 8

Pseudograph

Answer 8

a multigraph that allows edges that connect vertices to themselves – these edges are known as loops

Question 9

Path

Answer 9

a path from v₁ to v_n is a sequence of edges edge(v₁ v₂), edge(v₂ v₃), . . . ,

edge (v_n-1 v_n) and is denoted as a sequence of vertices v₁, v₂, v₃, . . . , v_n-1 , v_n

Question 10

Circiut

Answer 10

a path where v₁ = v_n and no edge is repeated

Question 11

Cycle

Answer 11

path where all vertices in a circuit are different

Question 12

Weighted Graph

Answer 12

A graph where each edge has an assigned number.

The number assigned to an edge is called its weight, cost, distance, length . . . depending on the context

Question 13

Complete Graph

Answer 13

A graph with n vertices such that for each pair of distinct vertices there is exactly one edge connecting them; that is, each vertex can be connected to any other vertex.

Question 14

degree of a vertex

Answer 14

The degree of a vertex v, deg(v), is the number of edges incident with v.

Question 15

isolated vertex

Answer 15

vertex where degree is 0

( deg(v) = 0 )

Question 16

Adjacent Vertices

Answer 16

Two vertices v_i and v_j if the edge(v_i v_j) is in E.

edge(v, w) in E:

* w is said to be adjacent to v

* if graph is undirected then v is also adjacent to w

* such an edge is called incident with the vertices v and w

Question 17

Subgraph

Answer 17

A subgraph G’ of graph G = (V, E) such that V’ ⊆ V and E’ ⊆ E.

Question 18

A subgraph _______ by vertices V’ is a graph (V’, E’) such that an edge e ∈ E if ______

Answer 18

induced, e ∈ E’

Question 19

A path’s length

Answer 19

is the number of edges that compose it

Question 20

Acyclic Graph (DAG)

Answer 20

A directed graph without cycles

Question 21

A ____ in a directed graph is a path of lengtha at least __ such that v₁ = v_n

Answer 21

cycle, 1

Question 22

Adjacency List

Answer 22

A simple representation of a graph which specifies all vertices adjacent to each vertex of the graph.

Implementations:

• Star representation: list implemented as a table
• Linked List

Question 23

Adjacency Matrix of Graph G = (V, E)

Answer 23

a binary |V| x |V| matrix indexed form 0 to n-1 such that each entry of this matrix:

a_ij = 1 if edge e_j is incident with vertex v_i; 0 otherwise

*Each row i represents vertices adjacent to vertex v_i, with

** order of vertices in adjacency matrix is arbitrary; there are n! possible adjacency matrices for the same graph G

Question 24

An incidence matrix of graph G = (V, E)

Answer 24

Representation of a graph based on the incidence of vertices and edges.

|V| x |E| matrix such that a_{<strong>ij</strong> =}

1 if edge e_j is incident with vertex v_i

0 otherwise

Question 25

The density of the edges in a graph should drive the choice of adjacency representation: sparse, use _____; dense use ______

Answer 25

list, matrix

Question 26

Two primary ways to traverse a graph

Answer 26

Depth-first search

Breadth-first search

Question 27

Deapth-First Search

Answer 27

• each vertex is visited and then all the unvisited vertices adjacent to that vertex are visited
• If the vertex has no adjacent vertices, or if they have all been visited, we backtrack to that vertex’s predecessor
• This continues until returning to the vertex where the traversal started
• If any vertices remain unvisited at this point, the traversal restarts at one of the unvisited vertices

* “last visited, first explored” strategy (think stack)

Question 28

Depth First Search Pseudocode (Recursive)

Answer 28

void Graph::dfs( Vertex v )
{
  v.visited = true;
  for each Vertex w adjacent to v
    if ( !w.visited )
      dfs( w );
}

Question 29

Depth First Search Implentation (Recursive)

Answer 29

vod DFS( Graph* G, int v )
{
  PreVisit(G, v);
  G->setMark(v, VISITED);
  for (int w=G->first(v); w < G->n(); w = G->next(v,w))
    if (G->getMark(w) == UNVISITED)
      DEF(G, w);
  PostVisit(G, v);

}

Question 30

Depth First Search Pseudocode (Iterative)

Answer 30

DFS(vertex s)
  S = new stack
  S.push(s)
  while not S.empty
    pop v from S
    if not v.visited
      v.visited = true
      foreach edge(v, u)
        if not u.visited
          S.push(u)

Question 31

Breadth-First Search

Answer 31

• BFS places vertices in a queue as they are visited
• The first vertex in the queue is then removed, and the process repeated
• No visited nodes are revisted
• if a node has no accessible nodes, the next node in the queue is removed and processed

* “first visited, first explored” strategy (think queue)

Question 32

BFS Pseudocode

Answer 32

BFS(vertex s)
  Q = new queue
  Q.enqueue(s)
  s.visited = true
  while not Q.empty
    v = Q.dequeue
    if not v.visited
      v.visited = true
    foreach edge (v, u)
      if not u.visited
        u.visited = true
        Q.enqueue(u)

Question 33

BFS Implementation

Answer 33

void BFS(Graph* G, int start, Queue< int >* Q)
{
  int v, w;
  Q->enqueue(start);
  G->setMark(start, VISITED);
  while (Q->length() != 0) // Process all vertices on Q
  {
    v = Q->dequeue();
    PreVisit(G, v);
    for (w = G->first; w < G->n(); w = G->next(v, w))
      if (G->getMark(w) == VISITED)
      {
        G->setMark(w, VISITED);
        Q->enqueue(w);
      }
  }
}

Question 34

Dijkstra’s Algorithm is . . .

Answer 34

The general method to solve the single-source shortest-path problem

Question 35

Two classic algorithms for finding MST of a graph

Answer 35

• Prim’s Algorithm
• Kruskal’s Algorithm

Question 36

Spanning Tree of a graph G is . . .

Answer 36

a tree (=no cycles) that includes:

• All vertices of the G
• some or all of the edges G

Question 37

Topological Sorting

Answer 37

Given an acyclic digraph G = (V, E), find a linear ordering of vertices such that:

for all edges (v, m) in E, v precedes w in the ordering.