1 | intro to networks; DFS and BFS Flashcards
Informal definition of a graph
a graph (𝐺)
- abstract representation of a set of components (nodes/vertices)
- where some pairs of the components are connected by links (edges).
Formal definition of a graph
- A graph is a pair 𝐺 =(𝑉,𝐸) , such that 𝐸 ⊆ {{𝑢, 𝑣}|𝑢, 𝑣 ∈ 𝑉}.
- We refer to 𝑉 as a set of nodes (or vertices) and 𝐸 as a set of edges.
Brackets for sets:
difference between {} and ()
{} = non ordered
() = ordered
Cartesian product of two sets?
eg A and B
A = {1, 2}
B = {3, 4, 5}
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)}.
Cartesian product of the same set X = {x1, x2, …}?
X x X = {(x1, x1), (x1, x2), … | x1, x2, … ∈ X}
What do we know about E(G) and the cartesian product V(G) x V(G) ?
E(G) <= V(G) x V(G)
What is incidence in graph theory?
If 𝑒 = {𝑢, 𝑣} is an edge, then
- 𝑢 and 𝑣 are incident with 𝑒 (and vice versa)
- Elements from different sets (nodes/edges)
What is adjacence in graph theory?
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)
Can a node be adjacent to a node?
yes
Can a node be adjacent to an edge?
no, it’s incident to the edge
What is the cardinality of a graph?
𝑛 = |𝑉(𝐺)|
the number of nodes it contains
also known as order of the graph
What is a multi-edge?
Parallel edges
Two edges 𝑒 and 𝑓 are called parallel, if they connect the same vertices.
Simple graph?
A graph is called simple, if it does not contain multi-edges or loops.
Otherwise it is called a multi-graph.
Opposite of a simple graph?
multi-graph
Directed graph - formal definition?
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
Weighted directed graph?
- Directed graph with a weight function 𝑤: 𝐸 → ℝ.
- Eg: V = {v1, v2}; e1 = (v1, v2), w(e1) = 2
- Weight = distance / resource availability / capacity etc
Ways to represent a graph on a computer ?
Adjacency matrix
Incidence matrix
Adjacency list
Adjacency matrix
Rows and columns?
Nodes and nodes
OR
Edges and edges
Adjacency matrix - undirected graphs
Values in the matrix?
- 𝐴[𝑢, 𝑣] = 1 𝑖𝑓 (𝑢, 𝑣) ∈ 𝐸(𝐺)
- 𝐴[𝑢, 𝑣] = 0 𝑖𝑓 (𝑢, 𝑣) ∉ 𝐸(𝐺)
- Edge weights can be considered (instead of 1).
Adjacency matrix - undirected graphs
Complexity to check for presence of an edge between two nodes
Constant time
Adjacency matrix - undirected graphs
Shape?
Symmetry?
Always square
Symmetric
Adjacency matrix - directed graphs
Shape? Symmetry?
Always square
May not be symmetrical
Adjacency matrix - only for nodes?
No, can also be for edges
Incidence matrix
Shape?
Not always square
Incidence matrix - undirected graphs
Values in matrix?
- 𝐴 𝑢, 𝑒 = 1 𝑖𝑓 𝑢 ∈ 𝑒
- 𝐴 𝑢, 𝑒 = 0 𝑖𝑓 𝑢 ∉ 𝑒
- Edge weights can be considered (instead of 1).
Incidence matrix
Rows? Columns?
- Rows = nodes
- Columns = edges
Incidence matrix - directed graphs
Values in matrix?
- 𝐴[𝑢,𝑒] = −1 𝑖𝑓𝑒 = (𝑢,𝑣)
- 𝐴[𝑢,𝑒] = 1 𝑖𝑓 𝑒 = (𝑣,𝑢)
- 𝐴[𝑢,𝑒] = 0, 𝑢 ∉ 𝑒
How can you get from an adjacency matrix A(n x n) to an incidence matrix B (n x m)
- Transpose B
- B (n x m) x B’ (m x n) = C (n x n)
- Is there a relationship between C and A?
How to represent a graph on a computer - data structure?
- We attach to each node u a list of neighbors
- type listgraph = array [1 . . 𝑛] 𝑜𝑓
record
value: information
neighbors: list
Sparse vs dense graphs?
sparse:
- m \in O(n) (check VL? )
- 0 <= D < 1/2
dense:
- m \in O(n^2)
- 1/2 < D <= 1
Formal definition of density?
Possible values?
(extra knowledge)
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
Density D of a graph dense graph?
1/2 < D <= 1
Density D of a graph sparse graph?
0 <= D < 1/2
Advantages and disadvantages of different representations?
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
Weighted directed hypergraph - example
𝑉 = {𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5}
𝑤({𝑣1, 𝑣6}) = {−1,−2}
𝑤 ({𝑣4, 𝑣7}) = {1,1}
Weighted directed hypergraph - formal definition
A weighted directed hypergraph is a pair 𝐺 = (𝑉,𝐸)
such that 𝐸 ⊆ (𝑆,𝑄), 𝑆, 𝑄 ∈ 𝒫(𝑉) (powerset)
with a weight function 𝑤𝑆: 𝑆 → ℝ
Weight = resource demand/production
Powerset? Relevance for hypergraph?
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
How can you represent a hypergraph on a computer?
With an incidence matrix
Example of relevance of hypergraphs?
virtually every chemical reaction needs hypergraphs to be represented
Graph basics:
size of a graph?
number of edges
Walk - formal definition
- Let 𝐺 = (𝑉,𝐸) be a simple graph.
- A walk is a sequence 𝑊 = (𝑣1, 𝑒1, 𝑣2,… 𝑒𝑘−1, 𝑣𝑘) …
- with 𝑣𝑖 ∈ 𝑉(𝐺), 1 ≤ 𝑖 ≤ 𝑘 and
- 𝑒𝑖 = {𝑣𝑖, 𝑣𝑖+1} ∈ 𝐸(𝐺) , 1 ≤ 𝑖 ≤ 𝑘 − 1
Walk - when is it closed?
A walk: a sequence 𝑊 = (𝑣1, 𝑒1, 𝑣2,… 𝑒𝑘−1, 𝑣𝑘) of a simple graph 𝐺 =(𝑉,𝐸)
A walk is closed if 𝑣1 = 𝑣𝑘
Walk - requirement of sequence?
Has to alternate node-edge-node-edge-…
Walk - can nodes and edges be repeated?
Yes
Path - formal definition
- Let 𝐺 = (𝑉,𝐸) be a graph.
- A path is a walk 𝑊 = (𝑣1, 𝑒1, 𝑣2,… 𝑒𝑘−1, 𝑣𝑘) …
- if 𝑣𝑖 ≠ 𝑣𝑗 , 1 ≤ 𝑖,𝑗 ≤ 𝑘, 𝑖 ≠ 𝑗.
When is a path a cycle?
A path is a cycle if if 𝑣1 = 𝑣𝑘
What do minimal and minimum refer to?
- minimal refers to subgraphs (or subsets)
- minimum refers to cardinality (number of nodes/edges)
When is a subgraph H of G minimal with respect to a property P? (analogously maximal vs maximum)
- If 𝐻 satisfies 𝑃 and
- If there exists no strict subgraph 𝐻′ of 𝐻 that also satisfies 𝑃.
Connectedness definition
- Let 𝐺 = (𝑉,𝐸) be a graph.
- 𝐺 is connected if there exists a path between every two nodes 𝑢 and 𝑣
Connected component?
= maximal connected subgraph
= maximal component with respect to connectedness
Tree definition
A graph 𝐺 is a tree if it is connected and has no cycles.
= a connected forest
Forest definition
A graph 𝐺 is a forest if it has no cycles.
(a connected forest is a tree.)
Rooted tree?
A tree is called a rooted tree if one vertex has been designated the root.
Rooted tree - parent of a vertex?
- 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
Rooted tree - child of a vertex?
a child of a vertex v is a vertex of which v is the parent
Rooted tree - leaf
a leaf is a vertex without children
Rooted tree - node that is not a leaf?
a node that is not a leaf is call internal
Rooted tree - ancestor?
Node u is an ancestor of v if it lies on the path from the root to v
How can we (efficiently) determine if a graph is connected?
Traverse the graph → detect connected components
DFS and BFS
