Graphs (oh god why) Flashcards
What is a digraph?
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
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/844/498/a_image_thumb.png?1466340306)
What is a graph?
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
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/845/745/a_image_thumb.png?1466340376)
Let G = (V, E) be a digraph
If (u, v) ∈ E what can we say with respect to adjacency, outer/inner neighbours?
v is adjacent to u
v is an out-neighbor of u
u is an in-neighbor of v
Let G = (V, E) be a digraph
what is the order?
what is the size?
order: | V |, the number of nodes (often denoted by variable n)
size: | E |, the number of arcs. (often denoted by variable m or e)
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?
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
What is a walk, length of a walk, path and a cycle?
A walk in a digraph G is a sequence of nodes v0 v1 . . . vn such that, for each i with 0 ≤ i < n, (vi , vi+1) is an arc in G
The length of the walk v0 v1 . . . vn 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 v0 = vn 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
Walks, paths and cycles in digraphs example
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/846/215/a_image_thumb.png?1466341346)
Walks, paths and cycles in graphs example
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
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/846/225/a_image_thumb.png?1466341383)
The distance from u to v in G (digraph), denoted by d(u, v), is…?
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)
What is the diameter of a digraph?
What is the relation of the radius of a digraph?
maximum distance between any two vertices
diameter: maxu,v∈V [d(u, v)]
radius: minu∈Vmaxv∈V [d(u, v)].
Examples of path distances in digraphs
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/846/558/a_image_thumb.png?1466342215)
Examples of path distances in graphs
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/846/559/a_image_thumb.png?1466342272)
What is the underlying graph of a digraph G = (V, E)?
G’ = (V, E’ ) where E’ = {{u, v} | (u, v) ∈ E}.
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/846/624/a_image_thumb.png?1466342540)
essentially a digraph with unidirectional lines replaced with bidirectional lines
What is a subdigraph of a digraph G = (V, E)?
is a digraph G’ = (V’ , E’ ) where V’ ⊆ V and E’ ⊆ E.
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/846/644/a_image_thumb.jpg?1466342801)
What is a spanning subdigraph?
Is one with V’ = V; that is, it contains all nodes
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/846/730/a_image_thumb.jpg?1466342941)
What is a subdigraph induced?
a subset V’ of V is the digraph G’ = (V’ , E’ ) where E’ = {(u, v) ∈ E | u ∈ V’ and v ∈ V’}
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/846/773/a_image_thumb.jpg?1466343176)
Let G be a digraph of order n.
What is an adjacency matrix?
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…
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/846/802/a_image_thumb.png?1466343325)
For a digraph G of order n
what is an adjacency list?
An adjacency lists representation is a sequence of n sequences, L0, . . . , Ln−1. Sequence Li contains all nodes of G that are adjacent to node i.
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/846/925/a_image_thumb.png?1466343655)
- 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.*