1 | intro to networks; DFS and BFS

Question 1

Informal definition of a graph

Answer 1

a graph (𝐺)
- abstract representation of a set of components (nodes/vertices)
- where some pairs of the components are connected by links (edges).

Question 2

Formal definition of a graph

Answer 2

• A graph is a pair 𝐺 =(𝑉,𝐸) , such that 𝐸 ⊆ {{𝑢, 𝑣}|𝑢, 𝑣 ∈ 𝑉}.
• We refer to 𝑉 as a set of nodes (or vertices) and 𝐸 as a set of edges.

Question 3

Brackets for sets:

difference between {} and ()

Answer 3

{} = non ordered
() = ordered

Question 4

Cartesian product of two sets?

eg A and B
A = {1, 2}
B = {3, 4, 5}

Answer 4

Cartesian Product of sets A and B is defined as the set of all ordered pairs (x, y) such that x belongs to A and y belongs to B.

Cartesian Product of A and B is {(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)}.

Question 5

Cartesian product of the same set X = {x₁, x₂, …}?

Answer 5

X x X = {(x₁, x₁), (x₁, x₂), … | x₁, x₂, … ∈ X}

Question 6

What do we know about E(G) and the cartesian product V(G) x V(G) ?

Answer 6

E(G) <= V(G) x V(G)

Question 7

What is incidence in graph theory?

Answer 7

If 𝑒 = {𝑢, 𝑣} is an edge, then
- 𝑢 and 𝑣 are incident with 𝑒 (and vice versa)
- Elements from different sets (nodes/edges)

Question 8

What is adjacence in graph theory?

Answer 8

Adjacence
- If 𝑒 = {𝑢, 𝑣} is an edge, then 𝑢 and 𝑣 are adjacent = are neighbors
- If 𝑒 = {𝑢, 𝑣} is an edge, and f = {u, w} is an edge then e and f are

adjacent = are neighbours

Elements from the same set (nodes/edges)

Question 9

Can a node be adjacent to a node?

Answer 9

yes

Question 10

Can a node be adjacent to an edge?

Answer 10

no, it’s incident to the edge

Question 11

What is the cardinality of a graph?

Answer 11

𝑛 = |𝑉(𝐺)|

the number of nodes it contains

also known as order of the graph

Question 12

What is a multi-edge?

Answer 12

Parallel edges

Two edges 𝑒 and 𝑓 are called parallel, if they connect the same vertices.

Question 13

Simple graph?

Answer 13

A graph is called simple, if it does not contain multi-edges or loops.
Otherwise it is called a multi-graph.

Question 14

Opposite of a simple graph?

Answer 14

multi-graph

Question 15

Directed graph - formal definition?

Answer 15

From general graph definition:
- A directed graph is a pair 𝐺 =(𝑉, 𝐸) , such that 𝐸 ⊆ {(𝑢, 𝑣) | 𝑢, 𝑣 ∈ 𝑉}.
- We refer to 𝑉 as a set of nodes (or vertices) and 𝐸 as a set of (directed) edges.
additionally:
- For the edge 𝑒 = (𝑢, 𝑣), 𝑢 is the head and 𝑣 is the tail

Question 16

Weighted directed graph?

Answer 16

• Directed graph with a weight function 𝑤: 𝐸 → ℝ.
• Eg: V = {v1, v2}; e1 = (v1, v2), w(e1) = 2
• Weight = distance / resource availability / capacity etc

Question 17

Ways to represent a graph on a computer ?

Answer 17

Adjacency matrix
Incidence matrix
Adjacency list

Question 18

Adjacency matrix

Rows and columns?

Answer 18

Nodes and nodes

OR

Edges and edges

Question 19

Adjacency matrix - undirected graphs

Values in the matrix?

Answer 19

• 𝐴[𝑢, 𝑣] = 1 𝑖𝑓 (𝑢, 𝑣) ∈ 𝐸(𝐺)
• 𝐴[𝑢, 𝑣] = 0 𝑖𝑓 (𝑢, 𝑣) ∉ 𝐸(𝐺)
• Edge weights can be considered (instead of 1).

Question 20

Adjacency matrix - undirected graphs

Complexity to check for presence of an edge between two nodes

Answer 20

Constant time

Question 21

Adjacency matrix - undirected graphs

Shape?
Symmetry?

Answer 21

Always square
Symmetric

Question 22

Adjacency matrix - directed graphs

Shape? Symmetry?

Answer 22

Always square
May not be symmetrical

Question 23

Adjacency matrix - only for nodes?

Answer 23

No, can also be for edges

Question 24

Incidence matrix

Shape?

Answer 24

Not always square

Question 25

Incidence matrix - undirected graphs

Values in matrix?

Answer 25

• 𝐴 𝑢, 𝑒 = 1 𝑖𝑓 𝑢 ∈ 𝑒
• 𝐴 𝑢, 𝑒 = 0 𝑖𝑓 𝑢 ∉ 𝑒
• Edge weights can be considered (instead of 1).

Question 26

Incidence matrix

Rows? Columns?

Answer 26

• Rows = nodes
• Columns = edges

Question 27

Incidence matrix - directed graphs
Values in matrix?

Answer 27

• 𝐴[𝑢,𝑒] = −1 𝑖𝑓𝑒 = (𝑢,𝑣)
• 𝐴[𝑢,𝑒] = 1 𝑖𝑓 𝑒 = (𝑣,𝑢)
• 𝐴[𝑢,𝑒] = 0, 𝑢 ∉ 𝑒

Question 28

How can you get from an adjacency matrix A(n x n) to an incidence matrix B (n x m)

Answer 28

• Transpose B
• B (n x m) x B’ (m x n) = C (n x n)
• Is there a relationship between C and A?

Question 29

How to represent a graph on a computer - data structure?

Answer 29

• We attach to each node u a list of neighbors
• type listgraph = array [1 . . 𝑛] 𝑜𝑓
  record
  value: information
  neighbors: list

Question 30

Sparse vs dense graphs?

Answer 30

sparse:
- m \in O(n) (check VL? )
- 0 <= D < 1/2

dense:
- m \in O(n^2)
- 1/2 < D <= 1

Question 31

Formal definition of density?
Possible values?
(extra knowledge)

Answer 31

D</sub>D</sub >(V,E) = |E| / ( Max</sub>D</sub>(V) = |E| / (|V|(|V|-1) = 1/2 D</sub>U</sub>(V,E)

interval [0,1]
D = 0 –> empty graph
D = 1 –> fully connected

Question 32

Density D of a graph dense graph?

Answer 32

1/2 < D <= 1

Question 33

Density D of a graph sparse graph?

Answer 33

0 <= D < 1/2

Question 34

Advantages and disadvantages of different representations?

Answer 34

Space required is quadratic in the number of nodes
For sparse graphs (number of edges which grows linearly with the number of edges), list representation is space efficient

Question 35

Weighted directed hypergraph - example

Answer 35

𝑉 = {𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5}
𝑤({𝑣1, 𝑣6}) = {−1,−2}
𝑤 ({𝑣4, 𝑣7}) = {1,1}

Question 36

Weighted directed hypergraph - formal definition

Answer 36

A weighted directed hypergraph is a pair 𝐺 = (𝑉,𝐸)
such that 𝐸 ⊆ (𝑆,𝑄), 𝑆, 𝑄 ∈ 𝒫(𝑉) (powerset)
with a weight function 𝑤𝑆: 𝑆 → ℝ
Weight = resource demand/production

Question 37

Powerset? Relevance for hypergraph?

Answer 37

powerset P(X)
set of all subsets of elements of X
= {S | S is a subset of X)
eg P(X) = { emptyset, {a}, {b}, {c}, {a,b}, …}
powerset tells us what a hyperedge represents = bags of nodes

Question 38

How can you represent a hypergraph on a computer?

Answer 38

With an incidence matrix

Question 39

Example of relevance of hypergraphs?

Answer 39

virtually every chemical reaction needs hypergraphs to be represented

Question 40

Graph basics:

size of a graph?

Answer 40

number of edges

Question 41

Walk - formal definition

Answer 41

• Let 𝐺 = (𝑉,𝐸) be a simple graph.
• A walk is a sequence 𝑊 = (𝑣1, 𝑒1, 𝑣2,… 𝑒𝑘−1, 𝑣𝑘) …
• with 𝑣𝑖 ∈ 𝑉(𝐺), 1 ≤ 𝑖 ≤ 𝑘 and
• 𝑒𝑖 = {𝑣𝑖, 𝑣𝑖+1} ∈ 𝐸(𝐺) , 1 ≤ 𝑖 ≤ 𝑘 − 1

Question 42

Walk - when is it closed?

Answer 42

A walk: a sequence 𝑊 = (𝑣1, 𝑒1, 𝑣2,… 𝑒𝑘−1, 𝑣𝑘) of a simple graph 𝐺 =(𝑉,𝐸)
A walk is closed if 𝑣1 = 𝑣𝑘

Question 43

Walk - requirement of sequence?

Answer 43

Has to alternate node-edge-node-edge-…

Question 44

Walk - can nodes and edges be repeated?

Answer 44

Yes

Question 45

Path - formal definition

Answer 45

• Let 𝐺 = (𝑉,𝐸) be a graph.
• A path is a walk 𝑊 = (𝑣1, 𝑒1, 𝑣2,… 𝑒𝑘−1, 𝑣𝑘) …
• if 𝑣𝑖 ≠ 𝑣𝑗 , 1 ≤ 𝑖,𝑗 ≤ 𝑘, 𝑖 ≠ 𝑗.

Question 46

When is a path a cycle?

Answer 46

A path is a cycle if if 𝑣1 = 𝑣𝑘

Question 47

What do minimal and minimum refer to?

Answer 47

• minimal refers to subgraphs (or subsets)
• minimum refers to cardinality (number of nodes/edges)

Question 48

When is a subgraph H of G minimal with respect to a property P? (analogously maximal vs maximum)

Answer 48

• If 𝐻 satisfies 𝑃 and
• If there exists no strict subgraph 𝐻′ of 𝐻 that also satisfies 𝑃.

Question 49

Connectedness definition

Answer 49

• Let 𝐺 = (𝑉,𝐸) be a graph.
• 𝐺 is connected if there exists a path between every two nodes 𝑢 and 𝑣

Question 50

Connected component?

Answer 50

= maximal connected subgraph
= maximal component with respect to connectedness

Question 51

Tree definition

Answer 51

A graph 𝐺 is a tree if it is connected and has no cycles.
= a connected forest

Question 52

Forest definition

Answer 52

A graph 𝐺 is a forest if it has no cycles.
(a connected forest is a tree.)

Question 53

Rooted tree?

Answer 53

A tree is called a rooted tree if one vertex has been designated the root.

Question 54

Rooted tree - parent of a vertex?

Answer 54

• the parent of a vertex is the vertex connected to it on the path to the root
• every vertex except the root has a unique parent

Question 55

Rooted tree - child of a vertex?

Answer 55

a child of a vertex v is a vertex of which v is the parent

Question 56

Rooted tree - leaf

Answer 56

a leaf is a vertex without children

Question 57

Rooted tree - node that is not a leaf?

Answer 57

a node that is not a leaf is call internal

Question 58

Rooted tree - ancestor?

Answer 58

Node u is an ancestor of v if it lies on the path from the root to v

Question 59

How can we (efficiently) determine if a graph is connected?

Answer 59

Traverse the graph → detect connected components
DFS and BFS