Notions and Notation

Question 1

graph. :

Answer 1

a finite, nonempty set V (vertex set) and a set E (edge set) whose elements e in E are pairs (a,b) with a,b in V

Question 2

digraph:

Answer 2

a directed graph, where edges go only 1 way - undirected graphs are well. undirected, they go both

Question 3

multigraph:

Answer 3

a graph with parallel edges

Question 4

2 vertices connected by an edge are:

Answer 4

adjacent, neighbours, the edge is incident on the 2 vertices

Question 5

start and end vertex of a directed edge:

Answer 5

start = tail (vertex), predecessor
end = tip (vertex), successor

Question 6

complete graphs:

Answer 6

Kn, all vertices are connected to each other
|E|=(n(n-1))/2

Question 7

path graphs:

Answer 7

Pn, a line, string of vertices connected by 1 or 2 edges depending on if its an end one or not
|E|=|V|-1

Question 8

cycle graphs:

Answer 8

Cn, aka circuit graphs, 1 cycle, a ring of however many vertices, what if you connected the end vertices of a path graph
|E|=|V|

Question 9

complete bipartite graphs:

Answer 9

Km,n - vertex set is the union of 2 sets, and the edge set is each vertex of one set connecting to every vertex of the other
|E|=|V1|*|V2|

Question 10

bipartite graph:

Answer 10

each vertex from the first set can be connected to only some of the vertices of the second, but the 2 vertex sets are still disjoint and each edge connects one vertex from one set to one in the other

Question 11

cube graphs:

Answer 11

Id - the d-dimensional cube graph, each vertex is a string of d 0s and 1s, and all possible vertex labels occur. edges connect the vertices that differ by exactly one digit
|V|=2^d, |E|=d2^(d-1)

Question 12

degree:

Answer 12

the degree of a vertex (deg(v)) is the number of edges connected to that vertex, or the number of times it appears in the edge set - digraphs have deg(in)(v) and deg(out)(v)

Question 13

handshaking lemma:

Answer 13

if G(V,E) is an undirected graph, Σdeg(v)=2|E|

Question 14

corollary of the handshaking lemma:

Answer 14

in an undirected graph, there must be an even number of vertices with odd degree

Question 15

edge list:

Answer 15

take a vertex set {1,2,3}. the edge set is smth like E={(1,2),(2,3),(1,3)} - if every vertex is contained within the edge list, we can just use the edge list

Question 16

adjacency matrix:

Answer 16

the adjacancy matrix A has elements Aij=1 if an edge between the vertices i and j exist, and 0 otherwise - row is the first/tail vertex, column is the second/tip in a digraph - if it’s a multigraph, take the number of edges

Question 17

degree and adjecancy matrix:

Answer 17

you can calculate the degree of a vertex by summing the row/column, and for deg(out) you take the row and deg(in) take the column

Question 18

adjacency list:

Answer 18

a list of all the vertices a given vertex v is connected to, Av, in a digraph you have the predecessor and successor lists for the vertices that precede or succeed v

Question 19

isomorphism:

Answer 19

2 graphs are isomorphic if there exists a bijection f:V1->V2 such that the edge (F(a),F(b)) in E2 iff (a,b) in E1
|V1|=|V2| and |E1|=|E2|
deg(v)=deg(F(v))

Question 20

degree sequence:

Answer 20

a list of degrees of vertices of an undirected graph, arranged in ascending order
isomorphic graphs have the same degree sequence, but 2 graphs with the same degree sequence aren’t necessarily isomorphic

Question 21

subgraph:

Answer 21

a subgraph G’(V’,E’) is a part of a graph G(V,E) such that V’⊆V and E’⊆E
a subgraph induced by V’ is a subgraph that only contains vertices in V’ and edges that only involve vertices in V’

Question 22

k-colouring:

Answer 22

a function f:V->{1,…,k} that assigns distinct values to adjacent vertices - adjacent vertices must have different colours - if a graph has a k colouring we say it’s k-colourable

Question 23

examples of graphs and colourings:

Answer 23

the complete graphs Kn are n-colourable
Km,n (the complete bipartite graph) is 2-colourable (1 for each set)

Question 24

chromatic number:

Answer 24

the chromatic number χ(G) is the smallest number k such that G is k-colourable

Question 25

lemmas from the chromatic number:

Answer 25

any graph has χ(G)=2 iff it’s bipartite
if H is a subgraph of G and G is k-colourable, so is H
if H is a subgraph of G, χ(H)<=χ(G)

Question 26

the greedy colouring algorithm:

Answer 26

order the vertices, order some colours, colour the first one the first colour, go through each vertex choosing the first possible colour that isn’t the same as that of an adjacent vertex, stop when they’re all coloured
may not give χ(G), but will give an upper bound
basic step is lookin at neighbour’s colours, with 2|E| basic steps

Question 27

floor and ceiling:

Answer 27

x is a real number
the floor ⌊x⌋ is the greatest integer <=x
the ceiling ⌈x⌉ is the least integer >=x
for all real x, x<⌊x⌋+1

Question 28

logs and lengths in decimal digits:

Answer 28

the decimal representation of a natural number n has exactly d=1+log10(n) digits
NOTE!! this is the number of digits and Not a decimal number it’s just named confusingly :(

Question 29

square matrix multiplication:

Answer 29

basic step is arithmetic operations of 2 real numbers (addition and multiplication)
ABij=(n)Σ(k=1)AikBkj
that’s n^2(n+(n-1))=2n^3+n^2 total operations
cause n multiplications and n-1 additions for 1 entry, and n^2 entries

Question 30

primality testing:

Answer 30

in these cases we use the worst case efficiency, cause you test for primes by testing all divisors from 2 to root(n) and if there’s no divisors it’s prime, so it could be 1 step or it could be root(n)-1 or inbetween, take the worst case root(n)-1
measure size of input with d=log10(n) (no. of digits)
basic step is n mod b (does b divide n, if yes, n mod b = 0)

Question 31

upper bound of asymptotic growth:

Answer 31

f(n)=O(g(n)) if ∃ c1>0 such that for all sufficiently large n, f(n)<=c1(g(n))
primality testing takes O(10^(d/2)) steps

Question 32

lower bound of asymptotic growth:

Answer 32

f(n)=Ω(g(n)) if ∃ c2>0 such that for all sufficiently large n, f(n)>=c2(g(n))

Question 33

both bounds of asymptotic growth:

Answer 33

f(n)=Θ(g(n)) if f(n)=O(g(n)) and f(n)=Ω(g(n))
greedy colouring takes Θ(|E|) basic steps, taking c1 as 1 and c2 as 3
matrix multiplication takes Θ(n^3) steps, by putting n^3 or 3n^3 on either side of 2n^3-n^2 and combining

Question 34

walk:

Answer 34

a series of edges, if v0=vn, it’s a closed walk

Question 35

length of a walk:

Answer 35

no. of edges in the sequence

Question 36

trail:

Answer 36

a walk where all the edges are distinct, closed trail has v0=vn

Question 37

path:

Answer 37

a trail where all the vertices are distinct

Question 38

cycle:

Answer 38

a closed trail with all distinct vertices except v0 and vn, which are the same

Question 39

trails paths and walks connection:

Answer 39

all trails are walks and all paths are trails, venn diagram is 3 concentric circles with walks on the outside and paths in the centre

Question 40

connected:

Answer 40

2 vertices are connected if there’s a walk between them, a graph is connected if all vertices are connected

Question 41

equivalence relation:

Answer 41

a relation ~ is equivalent if it’s:
reflexive - a~a
symmetric - a~b -> b~a
transitive - a~b and b~c -> a~c
equivalance class is the disjoint subset of all the equivalent things, such as areas of rectangles on a 2d plane - each area has its own equivalence class of rectangles that don’t overlap

Question 42

equivalence relation in undirected graphs:

Answer 42

they are reflexive by definition
they are symmetric as a walk can be reversed
they are transitive cause you can attach 2 walks together to create a walk between the first vertex of the first walk and the last of the second

Question 43

connected component:

Answer 43

of an undirected graph
a subgraph induced by an equivalence class under the relation ‘is-connected-to’ on V
p sure on a connected graph, there is only one connected component, just showing how many bits there are
the equivalence class then contains the vertices that are part of that connected subgraph

Question 44

accessibility:

Answer 44

a vertex b is accessible (or reachable) from another vertex a if a digraph G contains a walk from a to b - also all vertices are accessible from themselves

Question 45

strongly/weakly connected:

Answer 45

in a digraph, 2 vertices a and b are strongly connected if there exists a walk from a to b and from b to a
they’re weakly connected if only one of those walks exists
a digraph is strongly connected if all vertices are strongly connected
it’s weakly connected if all vertices are weakly connected, same as saying if all edges were converted to undirected ones, it would be connected

Question 46

|G|:

Answer 46

the graph you get when you convert all directed edges of a directed multigraph to undirected ones - if you have a->b and b<-a, it becomes 2 parallel edges

Question 47

connected vertices are always joined by a path proof:

Answer 47

going a to b
if all vertices in the sequence of the walk are distinct, it’s a path, you’re done
if not, remove everything before the last appearance of a and after the first appearance of b
then, for each other repeated vertex, remove everything between their first appearance and the first vertex after the last appearance (so take out the last one)
do that for all of them and voila a path, as there can only be so many repeated vertices