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.