Brainscape's Knowledge GenomeTM

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


See full index

Uni Maths > Graphs, Networks & Algorithms > Flashcards

Graphs, Networks & Algorithms Flashcards

1
Q

Adjacent vertices

A

Two vertices are adjacent if they are connected by an edge. If vertex i is adjacent to vertex j, we write i ∼ j.
{i,j} = ε(e) for some edge e ∈ E

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

Describe A_n graphs

A

straight line of n vertices

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

Describe D_n graphs

A

n≥4
Straight line of of n-2 vertices, with an extra 2 vertex connected to the leftmost vertex
(Or a straight line of n-1 vertices, with an extra vertex connected to the second left most vertex)

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

Describe E_n graphs

A

(n≥6)

straight line of n-1 vertices, with an extra vertex connected to the third left most vertex

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

Circuit/cycle

A

a path begins and ends at the same vertex

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

Eulerian Path

A

Paths that use every edge in the graph precisely once

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

Power set of V [P(V) and P_n(V)]

A

P(V)
the set of all subsets of V
P_n(V)
the set of subsets of V containing n elements

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

Finite Graph

A

(V,E,ε)

V and E are finite sets

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

Loop free graph

A

(V,E,ε)

Im(ε) ⊂ P_2(V)

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

Simple graph

A

Loop free, and ε injective

There is at most one edge between 2 vertices

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

Complete graph (K_n)

A

Simple, and Im(ε)=P_2(V)

(No loops, and there is exactly one edge between each pair of vertices

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

Automorphism

A

of graph G is an isomorphism G->G

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

Define cardinality

A

the number of elements in a set

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

Define Injective function

A

(one-to-one function)

each element of the codomain (ouptput) is mapped to by at most one element of the domain (input)

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

Define surjective function

A

each element of the codomain (output) is mapped to by at least one element of the domain

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

Define Bijective function

A

Injective and surjective

each element of the codomain is mapped to by exactly one element of the domain

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

What is the relation between morphisms and cycles?

A

Morphisms of graphs must take cycles of a given length to cycles of the same length.

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

Another term for a homomorphism

A

morphism

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

Directed graph

A

Digraph/Quiver.
Edges are allocated one direction of travel

Quadruple (V,E,h,t)
V vertices
E edges/ARROWS
h,t: E → V declaring the head and tail of each arrow respectively

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

Inverse to an isomorphism (Ф,ψ)

A

( Ф^(-1), ψ^(-1) )

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

Chromatic number?

give a practical definition

A

The smallest number of colours needed to colour the vertices in such a way that adjacent vertices have distinct colours.

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

Relation between chromatic number and chromatic polynomial

A

By definition, the chromatic number is the smallest natural number n s.t. P_G(n) is non zero

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

The chromatic polynomial for the complete graph K_r

A

P_G(n) = n(n-1)(n-2)…(n-r+1)

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

Simple definition of an algorithm

A

A set of rules by which the answer to a problem can be found

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

Attributes of an algorithm

A 
Finiteness
Definiteness
Input
Output
Effectiveness
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Simple definition for the complexity of an algorithm

A

The time taken for the algorithm to terminate as a function of its inputs

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

What do P and NP stand for?

A 
P: The class of all polynomial-time problems
NP: The class of all non-deterministic polynomial-time problems
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Polynomial-Time problem

A

Can be solved by a polynomial-time algorithm

on a deterministic Turing Machine

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

What is a non-deterministic Turing machine?

A

Hypothetical machine that follows instructions
But is allowed to make guesses
And always guesses correctly

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

What do P and NP stand for?

A 
P: The class of all polynomial-time problems
NP: The class of all non-deterministic polynomial-time problems
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Δ(G)

A

Maximum degree of graph G

max v∈V, deg(v)

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

Additional step to make the greedy colouring algorithm the Welsh-Powell algorithm?

A

[Given a non-empty loop-free graph G=(V,E,ε).]

Sort the vertices into order of decreasing vertex degrees deg(v1) ≥ deg(v2) ≥ … .

33
Q

Define the degree of a vertex

A

The degree of vertex v, deg(v), is the number of edges that contain v as an endpoint

34
Q

Planar Graph

A

The graph can be drawn in the plane in such a way that the vertices are distinct points and edges only meet at incident vertices

35
Q

Kuratowski’s Theorem

A

A graph is planar iff it does not contain K5 or K3,3 as a minor

36
Q

Equation satisfied by a SIMPLE, PLANAR, CONNECTED graph

A

3f ≤ 2e
[f ≤ 2e/3]
Every edge bounds 2 faces
Every face has at least 3 edges bounding it

37
Q

Graph G is a minor of G’ if …

A 
G can be obtained from G' by
deleting edges
deleting vertices (and incident edges)
contracting edges (removing an edge while simultaneously merging the two vertices that it joined)
38
Q

The surface of genus 0

A

sphere

plane

39
Q

Practical explanation of genus in relation to surface

A

The genus counts the number of ‘holes’ in the surface

40
Q

Leg(u)

A

u is vertex
Leg(u) = w^(-1)(u)
The set of half-edges incident/attached to u
Cardinality of Leg(u) = size of set Leg(u) = deg(u)

41
Q

Ribbon graph

A

Is a graph defined as a quadruple (V, H, τ, w)
AND
a cyclic ordering of the half-edges at each vertex

42
Q

What makes 2 RIBBON graphs the ‘same’ i.e. isomorphic

A

The graphs are isomorphic

Ordering of edges around each vertex coincides under the graph isomorphism

43
Q

What is the maximum number of vertices of a graph to guarantee it is planar?

A

4

44
Q

Do loops and multiple edges affect planarity?

A

No

45
Q

The Graph Minor Theorem

A

In any infinite list of graphs, some graph is a minor of another

46
Q

Every planar map can be coloured using no more than … colours

A

6

47
Q

Planar decomposition of a graph (V,E,ε)

A

A partition of the edge set E
in such a way that
each induced subgraph Gi=( V, Ei, ε|_(Ei) )
is PLANAR

48
Q

Thickness of graph G, i.e. t(G)

A

smallest number of disjoint edge sets Ei

required in planar decomposition of G

49
Q

Connected graph G

A

For any distinct vertices v=/=u

there is a path in G from v to u

50
Q 
A is the adjacency matrix
What does (A^n)_i,j denote
A

The number of paths of length n from vertex i to j

51
Q

Non-trivial cycle in G

A

A cycle in which each edge is used no more than once

52
Q

Tree

A

A finite, connected graph

that contains NO non-trivial cycles

53
Q

Complexity of Kruskal’s Algorithm

A

O( |E| ⋅ log|E| )

54
Q

Complexity of Prim’s Algorithm

A

O( |V| |E| )

55
Q

Complexity of Dijkstra’s Algorithm

A

O( |V|^2 )

56
Q

What is the type of graph that can be used in Kruskal’s/Prim’s algorithm?

A

Finite, connected, metric graph

G=(V,E,ε,μ)

57
Q

Define metric graph

A

A graph together with a metric

58
Q

Spanning tree of G=(V,E,ε)

A 
G is a finite connected graph
A spanning tree of a G is a 
subgraph T=(V_T, E_T, ε_T) of G
s.t. T is a tree, and V_T=V
(T contains every vertex in V)
59
Q

Define a metric on G

A

Function μ:E→ℝ+

assigning a strictly positive number to each edge of G

60
Q

Length of a graph H=(V_H, E_H, ε_H)

l(H)

A

l(H) = l(E_H)

The sum of all the metrics of all the edges in the set E_H

61
Q

Length of a set of edges E’

l(E’)

A

G=(V,E,ε,μ)
E’⊂E finiite subset of the edges in G
l(E’) = Σe∈E μ(e)
i.e. the sum of all the metrics of all the edges in the set E’

62
Q

Describe a graph in terms of ‘connected components’

A

A graph is a disjoint union of its connected components

63
Q

s and t in a directed graph

A

s ~ source

t ~ sink

64
Q

Another name for ‘feasilble flow’

A

flow

65
Q

Define a feasible flow

A

function f:E→ℝ+ satisfying

1) 0 ≤ f(e) ≤ c(e) ∀e∈E
2) Outflow at each vertex = inflow (except s & t)

66
Q

Define the value of a flow

A

v(f)

net flow into the sink t

67
Q

What is the aim of the Ford-Fulkerson algorithm?

A

Computes a maximal flow

68
Q

Max-flow Min-cut theory

A

The maximal flow value from s to t

the minimum of the capacities of the cuts separating s from t
(if a network is operating to capacity then a bottle neck is guaranteed)

69
Q

If A is symmetric, what other assumptions can you make about A?

A

eigenvalues of A are real

A is diagonisable

70
Q

Spectrum of A

A

The set of eigenvalues of A

Represented as an increasing sequence of (real) numbers

71
Q

Heuristic method

A

An algorithm that produces a good solution, with no guarantee of optimality.

72
Q

Sensitivity analysis

A

Analysing the behaviour of an algorithm as we change some input

73
Q

Fixed point free graph

A

E.g. τ(h) ≠ h

74
Q

Involution graph

A

The graph composed with itself is the identity function

75
Q

Combinatorial metric

A

every edge is given length 1

76
Q

Key difference between Kruskal’s and Prim’s

A

Kruskal’s: add edges of lowest weight unless they make a non trivial cycle
Prim’s: start with a vertex, and add shortest edges from that vertex and the following corresponding vertices added unless they make a non trivial cycle

77
Q

Acyclic graph

A

Graph that contains no cyclic subgraphs

78
Q

Maximal flow

A

feasible flow

v(f) >= v(f’) for feasible flows f’

79
Q

Flow augmenting chain

A

A path along which the flow can be increased

Uni Maths (10 decks)

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