Brainscape's Knowledge GenomeTM

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


See full index

Networks and Graphs > midterm > Flashcards

midterm Flashcards

1
Q

counting two disjoint events A and B

A

add the possibilities of A with B

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

disjoint events A and B

A

A or B are possible

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

counting possibilities of A and B, where the ordering matters

A

multiply the possibilities A by possibilities of B

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

How many ways are there to order n elements? =

A

Permutations of n elements
=> n!

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

How many ways are there to choose an ordered set of k elements from a set of n possible elements?

A

Permutations of k elements with n choices
=> n! / (n - k)!

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

permutation <-> combination

A

ordering matters <-> ordering doesn’t matter

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

How many subsets of size k does a set with n elements have?

A

= possible subsets
n over k = n! / k!(n - k)!

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

edge e incident on u and v =>

A

between u and v

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

simple undirected graph

A

at most one edge between every pair of vertices
at most one edge in each direction
a vertex cannot have edges to itself
cannot have more edges than there are other vertices

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

degree in undirected graph

A

num of neighbours

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

degree sequence

A

degrees in decreasing order

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

complete graph

A

undirected simple graph in which there is an edge between every pair of vertices
denoted by Kn

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

Handshaking lemma

A

The number of vertices with an odd degree in an undirected graph is even.

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

number of possible bijections between 2 isomorphic graphs

A

n!

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

How do we prove if two graphs are not isomorphic?

A

If the size of vertex sets, edge sets, or the degree sequence are not the same, we know with certainty that the two graphs are not isomorphic.

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

Every (undirected) graph with minimum degree at least 2 contains a

A

cycle

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

Connectivity in undirected graph G is an equivalence relation, which means it is:

A

Reflexive: ∀u ∈ V (G), u is connected to itself.
Symmetric: ∀u, v ∈ V (G), u is connected to v =⇒ v is connected to u.
Transitive: ∀u, v, w ∈ V (G), u is connected to v and v is connected to w⇒u is connected to w.

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

connected component

A

a maximal connected subgraph, that is a subgraph that is not strictly contained in another connected subgraph of G

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

forest

A

(possibly disconnected) undirected graph with no cycles

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

tree

A

an undirected connected graph with no cycles

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

spanning subgraph

A

a subgraph obtained only by edge deletions, i.e. the vertex set is the entire vertex set of G
S the set of deleted edges
=> denoted by G\S

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

theorem spanning forest

A

Every graph G has a spanning subgraph that is a forest. If G is connected then this spanning subgraph is a tree, called a spanning subtree.

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

induced subgraph

A

if there is an edge in G between u,v ∈ V′, then it should also be included in any induced subgraph

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

What can we say about the structure of induced subgraphs of Kn?
What is a subgraph of Kn that is not induced?

A

Any induced subgraph of ( K_n ) for ( k ) vertices will be a complete graph, denoted as ( K_k ). This is because all edges connecting the selected vertices are present in ( K_n )

A non-induced subgraph can be formed by selecting vertices but omitting some edges

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

theorem average degree

A

Every graph with average degree at least 2k, for a positive integer k, has an induced subgraph with minimum degree at least k + 1.

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

What is the space complexity of the adjacency-list of a graph with n vertices and m edges?

A

Array Adj has size n and each list Adj[v] has size deg(v). So the total number of elements in the list is therefore 2m (by handshaking lemma), and space complexity is O(m + n)

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

What is the time-complexity of checking if (u,v) ∈ E?

A

To check if v is a neighbour of u, we have to scan the list Adj(u), which takes O(deg(u)) time.

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

What is the space complexity of the adjacency-matrix of a graph with n vertices and m edges?

A

n^2

29
Q

What is the time-complexity of checking if (i , j ) ∈ E in an adjacency matrix?

A

Constant-time, just checking element A[i,j].

30
Q

list <-> matrix

A

list
- better space complexity for sparse graphs
- higher time complexity for checking an edge (deg(u) and higher)

matrix
- better choice for dense graphs with m = Ω(n2)

31
Q

BFS running time

A

O(n) for initialisation + O(m) for main loop
=> O(m + n)

32
Q

in BFS edges that cause a vertex to be enqueued form a

A

tree

33
Q

Shortest Paths via BFS theorem

A

Let G = (V , E ) be a (possibly directed) graph. After running BFS on G for a source s ∈ V, the value dist[v] = dG(s,v) is the shortest path distance between s and v.

34
Q

DSF running time

A

O(n) for initialisation + O(m) for main loop
=> O(m + n)

35
Q

DFS idea

A

Instead of exploring wide (breadth), explore far (deep): just keep walking until see a vertex already seen, then backtrack
For each vertex v we keep track of two labels d (v ) (discovery time), and f (v ) (finish time)

36
Q

DAG

A

A directed graph G is a Directed Acyclic Graphs (DAG) if it has no directed cycles.

37
Q

DAG and DFS theorem

A

A directed graph G is a DAG if and only if DFS(G) has no back edges.

38
Q

theorem for G of SCC

A

For any digraph G, the SCC graph Gˆ is a DAG.

39
Q

sink

A

An SCC is a sink SCC if it has no outgoing edges (in G^), and it is a source if it has no incoming edges.
At least one sink SCC exists

40
Q

Lemma SCCs + implications

A

Let C1,C2 be distinct SCCs s.t. (v(C1),v(C2)) ∈ E(Gˆ). Then f (C1) > f (C2).

41
Q

DFS finish times for SCCs

A

in reverse order of SCC directions

42
Q

the source SCC

A

Vertex with max finish time

43
Q

Graph G^T formed by reversing edges of G

A

has the same SCCs, but also reversed edges in Gˆ

44
Q

Source SCC in GT

A

sink SCC in G

45
Q

Chinese postman problem

A

a mail career start from the postoffice, has to deliver the main along all streets and get back to the postoffice without going through a street more than once

46
Q

Euler tour graphs

A

A connected undirected graph G has an Euler tour if and only all vertices have even degree.

47
Q

Eulerian tour

A

a tour that visits all edges exactly once

48
Q

A weakly connected directed graph G has an Euler tour

A

if and only if the in-degree of each vertex is equal to its out degree. In other words: deg+(v) = deg−(v) for all
v ∈ V (G ).

49
Q

An undirected connected graph has an Eulerian trail

A

if and only if it has exactly two odd vertices
These two vertices of odd-degree can only be at the beginning and end of the path

50
Q

De Bruijn Graphs

A

graphs in which the vertices represents overlapping segments of a string

51
Q

trail

A

A walk (not necessarily starting or ending in the same place) in which no edges are repeated

52
Q

bipartite graph + cycles theorem

A

A graph is bipartite if and only if it has no odd cycles.

53
Q

planar graph

A

A simple and connected graph G is called a planar graph if it can be drawn on the plane so that no two edges of G intersect. This is called the planar embedding of G.

54
Q

Euler’s theorem

A

For any connected planar graph with n vertices, m edges, and r regions (in its planar embedding), we have n − m + r = 2.

55
Q

Subdivisions

A

process of adding or deleting vertices of degree 2 on edges. Note that this does not change planarity of the graph.

56
Q

Subgraphs of a planar graph

A

are also planar
A graph that has non-planar subgraph is also none planar.

57
Q

Kuratowski theorem

A

A graph is planar if and only if it contains no subgraph that can be obtained by subdivisions of K3,3 or K5.

58
Q

4-color theorem/conjecture

A

he vertices of any planar graph can be colored with 4 colors, such that no adjacent vertices get the same color.

59
Q

k-coloring

A

a proper coloring of the graph with k colors. Can be seen as partitioning vertices into k sets, each with a color.

60
Q

In a simple undirected graph, ∆(v)

A

∆(v) = n − 1

61
Q

Maximum diameter of a connected graph with n vertices

A

n − 1 (in a path graph Pn, a straight line)

62
Q

Minimum diameter of a connected graph

A

1 (in a complete graph Kn)

63
Q

d-regular

A

all vertices have degree d

64
Q

DFS edge types

A

(u,v)
forward edge d(v) < d(u) < f(u) < f(v)
back edge d(u) < d(v) < f(v) < f(u)
cross edge d(u) < f(u) < d(v) < f(v)

65
Q

topological sort correctness

A

Since G is a DAG, we never encounter a back edge during DFS. Thus:
* Every edge (v, u) with v as the source is either a forward or cross edge.
* This implies f(u) < f(v), so vertex u is already in the list when v is added to the beginning.

66
Q

A connected undirected graph G has an Eulerian tour

A

if and only if all vertices have even degrees
Proof: ⇒ Let T be an Eulerian tour in G that starts and ends at a vertex u. Each time T leaves u through some edge, it must return to u using a different edge. Similarly, each time T visits a vertex v ̸= u, it must leave it via another edge. Since each edge is traversed exactly once, this implies that we can group edges incident to each vertex v in pairs, so deg(v) is even.

67
Q

A directed graph is weakly connected

A

if the underlying undirected graph is connected

68
Q

complete bipartite graph Km,n

A

m + n vertices and mn edges

69
Q

Any planar graph can be coloured with at most 4 colours, according to

A

the Four-Colour Theorem

Networks and Graphs (4 decks)

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