Definitions

Question 1

Simple Graph

Answer 1

A simple graph is an ordered pair G = (V,E), where V is a non empty finite set called the set of vertices of G and E is a set of unordered pairs of V called edges

Question 2

Adjacent

Answer 2

If {x,y} € E then x and y are called adjacent and are incident with the edge {x,y}

Question 3

Complete Graph

Answer 3

A complete graph of n vertices denoted K_n, is a graph such that every pair of vertices is connected with an edge.

Question 4

Empty Graph

Answer 4

The empty graph on n vertices denoted E_n is a graph with n vertices and no edges

Question 5

Subgraph

Answer 5

G’=(V’,E’) is a subgraph of G=(V,E) iff V’ C= V and E’ C=E

Question 6

Spanned Subgraph

Answer 6

G’=(V’,E’) is a spanned subgraph of G=(V,E) iff it is a subgraph of G for all x,y € V’, {x,y} € E implies {x,y} € E’

Question 7

Isomorphic

Answer 7

The graphs G and G’ are isomorphic iff there exists a function ø: V U E -> V’ U E’ such that ø gives a bijection between V and V’ and between E and E’ and furthermore for any edge {x,y} € E, ø({x,y}) = {ø(x),ø(y)}

Question 8

Order of a graph

Answer 8

The order of a graph, G=(V,E) is |V|, the number of vertices

Question 9

Size of a graph

Answer 9

The size of a graph G=(V,E) is |E|, the number of edges

Question 10

Degree of a vertex

Answer 10

The degree of a vertex x € V, denoted d(x), is the number of edges incident with it

Question 11

Walk

Answer 11

A walk is an alternating sequence of vertices and edges. x0e1x1e2….enxn such that x0….xn are vertices and e1…en are edges where ei connects xi-1 and xi

Question 12

Path

Answer 12

A path is a walk with unique vertices

Question 13

Cycle

Answer 13

A cycle is a closed walk with no repeated vertices other than the x0 = xn

Question 14

The relation ~ on V by x~y

Answer 14

Let G=(V,E) be a graph. Define the relation ~ on V by x~y iff there exists a path beginning at x which ends at y

Question 15

Connected

Answer 15

G is called connected iff it has one connected component

Question 16

Tree

Answer 16

A graph G is a tree iff it is connected and contains no cycles

Question 17

Forest

Answer 17

G is a forest iff it contains no cycles

Question 18

Spanning Tree

Answer 18

A spanning tree of G is a is a subgraph of G which is a tree and contains all the vertices of G

Question 19

Weight of a subgraph T

Answer 19

The weight of a subgraph T is w(t) = (mult.)_e€E(T) 1/R_e For an edge xy, N(x,y) = (Sum.)_T w(T)

Question 20

Flow or feasible flow

Answer 20

A flow is a function f: E(G)->Re_>=0 such that 0<=f(x,y)<=c(x,y) for every edge xy and every vertex x except for s and t we have (Sum.)_xy€E(G) f(x,y) = (Sum.)_yx€E(G) f(y,x)

Question 21

Value of a flow

Answer 21

The value of a flow f is v(f)=(Sum.)_sy€E(G) f(s,y) - (Sum.)_ys€E(G) f(y,s)

Question 22

Kirchoffs 1st Law

Answer 22

Let x be a vertex other than s or t, then SUM I_xy = 0 for y adjacent to x

Question 23

Kirchoffs 2nd Law

Answer 23

Let x0x1…xn be a cycle then, SUM R_(xi-1,xi) I_(xi-1,xi) = 0 If x0=s and xn=t then the summation is equal to U, the potential difference between s and t

Question 24

Ordinary Power Function

Answer 24

The ordinary power series generating function of a sequence {an}∞n=0 is the formal power series f(x) = (SUM_0^∞) a_n x^n. Notation: f(x) ←ops→ {an}∞n=0

Question 25

Exponential Generating Function

Answer 25

The ordinary power series generating function of a sequence {an}∞n=0 is the formal power series f(x) = (SUM\_0^∞) (a\_n x^n)/n! . Notation: f(x) ←egf→ {an}∞n=0

Question 26

Matrix Tree Theorem

Answer 26

Let G be a graph with vertices labelled x1, x2, . . . , xn. Let = { d(xi) if i = j, aij = { −1 if i != j and xi,xj is an edge of G, = { 0 if i != j and xi,xj is not an edge G, and let A be the n × n matrix whose ij entry is aij . (a) The number of spanning trees of G is the modulus of any (n−1)×(n−1)minor of A.

Question 27

Describe the method of spanning trees used to calculate the currents in the edges of G

Answer 27

.