Graph Theory

Question 1

What is the complement of a graph?

Answer 1

Graph on the same vertices on the original such that two distinct vertices are adjacent iff they are not adjacent to the original
(LEARN NOTATION)

Question 2

What is the FT of GT?

Answer 2

Sum of the degrees of vertices is equal to twice the number of edges
Sum from i=1 to p, deg(vi) = 2q

Question 3

What is the handshaking lemma?

Answer 3

Every graph contains an even number of odd vertices

Question 4

What is the degree of an undirected graph and what other aspect is it equal to?

Answer 4

Number of vertices that a vertex is adjacent to.
Equal to the cardinality of its Neighbourhood

Question 5

What is the minimum degree of a vertex?

Answer 5

sigma(G) = min(1 <= i <= p){degG(vi)}

Question 6

What is the maximum degree of a vertex?

Answer 6

delta(G) = max(1 <= i <= p){degG(vi)}

Question 7

What is the degree of directed graphs?

Answer 7

Out-degree: cardinality of out neighbourhood of vertex
(odD(v) = |N+D(v))
In-degree: cardinality of in-neighbourhood of vertex
(idD(v) = |N-D(v))

therefore degD(v) = id + od

Question 8

What is the cardinality of a set?

Answer 8

Number of elements in a set
Denoted by |S(a)|

Question 9

What is the neighbourhood of an undirected graph?

Answer 9

Neighbourhood of v in V is set containing all vertices u such that uv is an element of the graph’s edges.

Question 10

What is the difference between open neighbourhood and closed neighbourhood, and what other measure is influenced by these?

Answer 10

out when vertex being evaluated is not included in the set (then it is equal to the degree)
in when evaluated vertex is included

Question 11

What is the notation of the open and closed neighbourhood sets?

Answer 11

Check notes

Question 12

What is the out-neighbouthood of a directed graph?

Answer 12

Set of its out-neighbours, which is a vertex that has an edge from a vertex.

Set of all vertices u in V, such that arc vu is an element of V(D)

Question 13

What is the in-neighbourhood of a directed graph?

Answer 13

Set of its in-neighbours, which is a vertex that has an edge to a vertex

Set of all vertices u in V(D), such that the arc uv is an element of V(D)

Question 14

What is the adjacency matrix of an undirected graph?

Answer 14

A(G) is symmetric binary matrix with a_ij = 1 iff v_i is adjacent to v_j in G (and i dne j), otherwise a =0

Question 15

What is the sum of all the elements in an adjacency matrix of an undirected graph?

Answer 15

Sum from j=1 to p for:
a_ij or a_ji = degree of vertex vi

Question 16

What is the adjacency matrix of an undirected graph?

Answer 16

A(D) is a p x p asymmetric binary matrix where aij = 1 iff the arc vi vj exists in the edge set, otherwise it is zero

Question 17

How are out-neighbourhoods calculated using the adjacency matrix?

Answer 17

od = sum(from k=1 to p) of a_(ik)

therefore sum of column elements in row i

Question 18

How are in-neighbourhoods calculated using the adjacency matrix?

Answer 18

id = sum(from k=1 to p of a_(ki)

therefore sum of row elements in column i

Question 19

What is the weighted matrix?

Answer 19

pxp matrix where a = 0 if i =j
if edge between two vertices exist, then aij = weight
infinity if the edge between two vertices dont exist

Question 20

How do you perform vertex deletion?

Answer 20

Delete vertex and all edges associated with it

G - {v4}

Question 21

How do you perform edge deletion / edge insertion?

Answer 21

Delete edges given by set G - {v3v4, v5v6}

Question 22

What is the FT of DG?

Answer 22

Sum of out-degrees = sum of in-degrees = edges in graph