Graphs (oh god why)

Question 1

What is a digraph?

Answer 1

A digraph G = (V, E) is a finite nonempty set V of nodes together with a (possibly empty) set E of ordered pairs of nodes of G called arcs

Question 2

What is a graph?

Answer 2

A graph G = (V, E) is a finite nonempty set V of vertices together with a (possibly empty) set E of unordered pairs of vertices of G called edges

Question 3

Let G = (V, E) be a digraph

If (u, v) ∈ E what can we say with respect to adjacency, outer/inner neighbours?

Answer 3

v is adjacent to u

v is an out-neighbor of u

u is an in-neighbor of v

Question 4

Let G = (V, E) be a digraph

what is the order?

what is the size?

Answer 4

order: | V |, the number of nodes (often denoted by variable n)
size: | E |, the number of arcs. (often denoted by variable m or e)

Question 5

Let G = (V, E) be a digraph

what is the out-degree of a node, v? If it is 0 what do we call this?

what is the in-degree of a node, v? If it is 0 what do we call this?

Answer 5

The out-degree of a node v is the number of arcs leaving v

The in-degree of v is the number of arcs entering v

A node of in-degree 0 is called a source and a node of out-degree 0 is called a sink

Question 6

What is a walk, length of a walk, path and a cycle?

Answer 6

A walk in a digraph G is a sequence of nodes v₀ v₁ . . . v_n such that, for each i with 0 ≤ i < n, (v_i , v_i+1) is an arc in G

The length of the walk v₀ v₁ . . . v_n is the number n (that is, the number of arcs involved)

A path is a walk in which no node is repeated

A cycle is a walk in which v₀ = v_n and no other nodes are repeated

note:

A cycle in a graph is of length at least 3.

If there is a walk from u to v, then there is at least one path from u to v

Question 7

Walks, paths and cycles in digraphs example

Answer 7

Question 8

Walks, paths and cycles in graphs example

Answer 8

Note: e g e is not a cycle because it has only 2 arcs (e,g) and (g,e)

and by convention is said a cycle must have at least 3 arcs

Question 9

The distance from u to v in G (digraph), denoted by d(u, v), is…?

Answer 9

the minimum length of a path from u to v.

If no path exists, the distance is undefined (or + ∞, positive infinity)

(For graphs, we have d(u, v) = d(v, u) for all vertices u and v)

Question 10

What is the diameter of a digraph?

What is the relation of the radius of a digraph?

Answer 10

maximum distance between any two vertices

diameter: max_u,v∈V [d(u, v)]
radius: min_u∈Vmax_v∈V [d(u, v)].

Question 11

Examples of path distances in digraphs

Answer 11

Question 12

Examples of path distances in graphs

Answer 12

Question 13

What is the underlying graph of a digraph G = (V, E)?

Answer 13

G’ = (V, E’ ) where E’ = {{u, v} | (u, v) ∈ E}.

essentially a digraph with unidirectional lines replaced with bidirectional lines

Question 14

What is a subdigraph of a digraph G = (V, E)?

Answer 14

is a digraph G’ = (V’ , E’ ) where V’ ⊆ V and E’ ⊆ E.

Question 15

What is a spanning subdigraph?

Answer 15

Is one with V’ = V; that is, it contains all nodes

Question 16

What is a subdigraph induced?

Answer 16

a subset V’ of V is the digraph G’ = (V’ , E’ ) where E’ = {(u, v) ∈ E | u ∈ V’ and v ∈ V’}

Question 17

Let G be a digraph of order n.

What is an adjacency matrix?

Answer 17

Adjacency matrix of G is the n × n boolean matrix (often encoded with 0’s and 1’s) such that entry (i, j) is true if and only if there is an arc from the node i to node j.

In the example below the first row is formed by:

does 0 travel to 0? false so 0 is put into matrix at row 0 column 0

does 0 travel to 1? true so 1 is put into matrix at row 0 column 1

does 0 travel to 2? false so 0 is put into matrix at row 0 column 2

does 0 travel to 3? true so 1 is put into matrix at row 0 column 3

and so on…

Question 18

For a digraph G of order n

what is an adjacency list?

Answer 18

An adjacency lists representation is a sequence of n sequences, L₀, . . . , L_n−1. Sequence L_i contains all nodes of G that are adjacent to node i.

• In the example below everything under numeric heading is the adjacency list.*
• The first entry is the number of nodes.*
• Entries after that can be obtained by checking what nodes travel to which*
• for example node a travels to b and d and we have set nodes a, b, c … to be 0, 1 , 2… respectively.*
• we can insert 1 corresponding to b and 3 corresponding to d into the first row of the adjacency list.*

Question 19

Digraph operations in terms of data structures

(self explanatory)

Answer 19

Question 20

Comparative performance of adjacency lists and matrices

Answer 20

note: d denotes size of the adjacency list for vertex i.

Question 21

Illustrating the general traversal algorithm

Answer 21

Question 22

What is a search forest?

Answer 22

There may remain unvisited nodes in the digraph. In this case, we may choose another white node as root and continue. Eventually, we obtain a set of disjoint trees spanning the digraph, which we call the search forest

Question 23

Suppose we have performed a traversal of a digraph G, resulting in a search forest F. Let (u, v) ∈ E(G) be an arc

When is an arc called a tree arc?

If it is not a tree arc what are the 3 other possibilities?

Answer 23

if it belongs to one of the trees of F

1. a forward arc if u is an ancestor of v in F
2. a back arc if u is a descendant of v in F
3. a cross arc if neither u nor v is an ancestor of the other in F

Question 24

Facts about traversal trees

Answer 24

Suppose we run algorithm traverse on G, resulting in a search forest F.

Let v, w ∈ V(G).

1 Let T1 and T2 be different trees in F and suppose that T1 was explored before T2. Then there are no arcs from T1 to T2.

2 Suppose that G is a graph. Then there can be no edges joining different trees of F.

3 Suppose that v is visited before w and w is reachable from v in G. Then v and w belong to the same tree of F.

4 Suppose that v and w belong to the same tree T in F. Then any path from v to w in G must have all nodes in T .

Question 25

Run-time analysis of traverse

Answer 25

In the while-loop of subroutine visit let:

• a and A be lower and upper bounds on the time to choose a grey node.
• b and B be lower and upper bounds on the time to choose a white node.

The running time of traverse is:

• O(An + Bm) and Ω(an + bm) if adjacency lists are used, and
• O(An + Bn² ) and Ω(an + bn² ) if adjacency matrices are used

Question 26

A DFS example

Answer 26

Question 27

Basic properties of depth-first search

Answer 27

Each call to dfs_visit(v) terminates only when all nodes reachable from v via a path of white nodes have been seen.

Suppose that (v, w) is an arc. Cases:

• tree or forward arc: seen[v] < seen[w] < done[w] < done[v];
• back arc: seen[w] < seen[v] < done[v] < done[w];
• cross arc: seen[w] < done[w] < seen[v] < done[v].

Hence on a graph, there are no cross edges.

Question 28

Using DFS to determine ancestors of a tree

Answer 28

If v is an ancestor of w in F, then seen[v] < seen[w] < done[w] < done[v] .

If v is not an ancestor of w in F, then seen[v] < done[v] < seen[w] < done[w]

Question 29

A BFS example

Answer 29

Question 30

How does DFS allow us to give a so-called pre-order and post-order labeling to a digraph?

Answer 30

The pre-order label indicates the order in which the nodes were turned grey.

The post-order label indicates the order in which the nodes were turned black.

Question 31

Suppose that there is a cycle in G and let v be the node in the cycle visited first by DFS. If (u, v) is an arc in the cycle then it must be a…?

Answer 31

back arc

Question 32

a digraph is acyclic iff there are no…?

Answer 32

back arcs from DFS

Question 33

An acyclic digraph is called…?

Answer 33

directed acyclic graph (DAG)

Question 34

An acyclic graph is a…?

Answer 34

forest

Question 35

Arithmetic expression digraphs example

Answer 35

Question 36

What is topological sorting?

What is its main applications?

Answer 36

• To place nodes of a digraph on a line so all arcs go in one direction.

Possible if and only if digraph is a DAG

• Main application:

scheduling events (arithmetic expressions, university prerequisites, etc)

Question 37

Topological sorting via DFS

Answer 37

Question 38

A graph G is connected if…?

Answer 38

for each pair of vertices u, v ∈ V(G), there is a path between them

Question 39

A graph G is disconnected if…?

Answer 39

it is not connected and the maximum induced connected subgraphs are call the components of G

Question 40

Nice DFS application: strong components

Answer 40

Nodes v and w are mutually reachable if there is a path from v to w and a path from w to v. The nodes of a digraph divide up into disjoint subsets of mutually reachable nodes, which induce strong components.

(Strong) components are precisely the equivalence classes under the mutual reachability relation.

A digraph is strongly connected if it has only one strong component.

Components of a graph are found easily by BFS or DFS. However, this doesn’t work well for digraphs (a digraph may have a connected underlying graph yet not be strongly connected). A new idea is needed.

Question 41

What is the girth of a graph?

Answer 41

the length of the shortest cycle is called the girth of the graph.

If the graph has no cycles then the girth is undefined but may be viewed as +∞

Question 42

Fact:

For a digraph we use the term girth for its underlying graph and the (maybe non-standard) term directed girth for the length of the smallest directed cycle

Answer 42

memes

Question 43

Computing girth of a graph

Answer 43

• If vertex v is on at least one cycle then BFS starting at v will find it.
• On detection of a cross arc between descendants u and w, determine whether u and w are in different subtrees.
  
  • If yes, then a cycle of length d[u] + d[w] + 1 is found.
  • If no, then a cycle of shorter length is found (but avoids v).
• If d[u] = d[w] then odd length, where v common ancestor.
• Otherwise, WLOG, d[u] + 1 = d[w] and even length.
• To compute girth, we run the above procedure once for each v ∈ V(G) and take minimum.

Question 44

k-colorable graphs

Answer 44

Let k be a positive integer. A graph G has a k-coloring if V(G) can be partitioned into k nonempty disjoint subsets such that each edge of G joins two vertices in different subsets (colors)

Question 45

Bipartite graphs (digraphs)

Answer 45

A graph G is bipartite if V(G) can be partitioned into two nonempty disjoint subsets V₀, V₁ such that each edge of G has one endpoint in V₀ and one in V₁.

[Similar for digraphs.]