Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

*M ACN > 1 | intro to networks; DFS and BFS > Flashcards

1 | intro to networks; DFS and BFS Flashcards

1
Q

Informal definition of a graph

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Formal definition of a graph

A
  • A graph is a pair 𝐺 =(𝑉,𝐸) , such that 𝐸 ⊆ {{𝑢, 𝑣}|𝑢, 𝑣 ∈ 𝑉}.
  • We refer to 𝑉 as a set of nodes (or vertices) and 𝐸 as a set of edges.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Brackets for sets:

difference between {} and ()

A

{} = non ordered
() = ordered

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Cartesian product of two sets?

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

A

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)}.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Cartesian product of the same set X = {x1, x2, …}?

A

X x X = {(x1, x1), (x1, x2), … | x1, x2, … ∈ X}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is incidence in graph theory?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is adjacence in graph theory?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Can a node be adjacent to a node?

A

yes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Can a node be adjacent to an edge?

A

no, it’s incident to the edge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the cardinality of a graph?

A

𝑛 = |𝑉(𝐺)|

the number of nodes it contains

also known as order of the graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a multi-edge?

A

Parallel edges

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Simple graph?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Opposite of a simple graph?

A

multi-graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Directed graph - formal definition?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Weighted directed graph?

A
  • Directed graph with a weight function 𝑤: 𝐸 → ℝ.
  • Eg: V = {v1, v2}; e1 = (v1, v2), w(e1) = 2
  • Weight = distance / resource availability / capacity etc
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Ways to represent a graph on a computer ?

A

Adjacency matrix
Incidence matrix
Adjacency list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Adjacency matrix

Rows and columns?

A

Nodes and nodes

OR

Edges and edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Adjacency matrix - undirected graphs

Values in the matrix?

A
  • 𝐴[𝑢, 𝑣] = 1 𝑖𝑓 (𝑢, 𝑣) ∈ 𝐸(𝐺)
  • 𝐴[𝑢, 𝑣] = 0 𝑖𝑓 (𝑢, 𝑣) ∉ 𝐸(𝐺)
  • Edge weights can be considered (instead of 1).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Adjacency matrix - undirected graphs

Complexity to check for presence of an edge between two nodes

A

Constant time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Adjacency matrix - undirected graphs

Shape?
Symmetry?

A

Always square
Symmetric

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Adjacency matrix - directed graphs

Shape? Symmetry?

A

Always square
May not be symmetrical

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Adjacency matrix - only for nodes?

A

No, can also be for edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Incidence matrix

Shape?

A

Not always square

25
Q

Incidence matrix - undirected graphs

Values in matrix?

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

Incidence matrix

Rows? Columns?

A
  • Rows = nodes
  • Columns = edges
27
Q

Incidence matrix - directed graphs
Values in matrix?

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

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

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

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

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

Sparse vs dense graphs?

A

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

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

31
Q

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

A

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

32
Q

Density D of a graph dense graph?

A

1/2 < D <= 1

33
Q

Density D of a graph sparse graph?

A

0 <= D < 1/2

34
Q

Advantages and disadvantages of different representations?

A

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

35
Q

Weighted directed hypergraph - example

A

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

36
Q

Weighted directed hypergraph - formal definition

A

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

37
Q

Powerset? Relevance for hypergraph?

A

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

38
Q

How can you represent a hypergraph on a computer?

A

With an incidence matrix

39
Q

Example of relevance of hypergraphs?

A

virtually every chemical reaction needs hypergraphs to be represented

40
Q

Graph basics:

size of a graph?

A

number of edges

41
Q

Walk - formal definition

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

Walk - when is it closed?

A

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

43
Q

Walk - requirement of sequence?

A

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

44
Q

Walk - can nodes and edges be repeated?

A

Yes

45
Q

Path - formal definition

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

When is a path a cycle?

A

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

47
Q

What do minimal and minimum refer to?

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

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

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

Connectedness definition

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

Connected component?

A

= maximal connected subgraph
= maximal component with respect to connectedness

51
Q

Tree definition

A

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

52
Q

Forest definition

A

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

53
Q

Rooted tree?

A

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

54
Q

Rooted tree - parent of a vertex?

A
  • 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
55
Q

Rooted tree - child of a vertex?

A

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

56
Q

Rooted tree - leaf

A

a leaf is a vertex without children

57
Q

Rooted tree - node that is not a leaf?

A

a node that is not a leaf is call internal

58
Q

Rooted tree - ancestor?

A

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

59
Q

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

A

Traverse the graph → detect connected components
DFS and BFS

*M ACN (14 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions