由于內(nèi)容附大量圖, 附圖原文鏈接如下?<一個github鏈接, 還沒post出來,過幾天改掉>?

你想一天全理解是不可能的, 至少三天, 寫得比較精煉, 可能會漏些細(xì)節(jié).?

handshaking theorem: ∑{d(v): v ∈ V}

corollary: The number of odd degree must be even

complementary graph G’ +G =complete graph

adjacency list

adjacency matrix head in left and tail in top

incidence matrix? vertex in left and edge in top

To show not isomorphism:

check # vertices and edge OR # degree Sequence?

OR k-cycle length OR (cycle) region of each vertex

To show isomorphism:

corresponding each vertex in two graph and check there is a edge between these vertex OR show each vertex has the same neighbour-set

trail: no edge repeat; circuit: closed trail

path: no edge repeat and no vertices repeats; cycle: closed path

path/cycle ? trail/circuit

Cut vertex OR cut edge: remove and become two graph

Strong/Weak graph

homeomorphic graph (就是把G的edge打骨折)

matrix multiplication theorem

The number of walks from Vi to Vk of length r is the (i,j)th entry of A^r.

Euler’s Definition:

A circuit walk through all edge in the graph

Euler’s Theorem

A graph G has a Euler circuit iff G is connected and every vertex has even degree.

A graph G has a Euler trail but not Euler circuit iff G is connected and exactly two vertices have odd degree.

Euler’s Formula:

|V|-|E|+|R|=2

Dirac’s Theorem 任何一個vertex has at least n/2 degree

If G is a simple graph with n vertices where n ≥ 3 such that the degree of each vertex is at least n/2, then G has a Hamilton cycle

Ore’s Theorem 兩個不相鄰點的degree和≥n 就行

If G is a simple graph with n vertices where n ≥ 3 and for every pair of nonadjacent vertices u and v, deg(u) + deg(v) ≥ n, then G has a Hamilton cycle.

Dirac’s Theorem ? Ore’s Theorem

Kuratowski’s Theorem
A graph G is not planar if and only if G contains a subgraph homeomorphic to either K5 or K3,3.?

Redei’s theorem? Tournaments: direct complete graph

Every tournament has a directed Hamilton path

Hamilton Paths in a graph G is paths pass through each vertex exactly once.

To show a graph is Hamilton path:

Satisfy Dirac’s theorem or Ore’s theorem, or give the path directly

To show a graph is not Hamilton cycle:

If connected graph have a cut edge or cut vertex, then it is

To show a graph is not planar,?

it should satisfy |E|>3|V|-6 OR |E|>2|V|-4 which with no cycle length3;

OR Use Kuratowski’s theorem as:

? (has a subgraph)(which is isomorphic to)(homeomorph of) K3,3/K5;

To show a graph is planar, ?

only way is show a plane representation of it

dual graph(對偶圖) G^d

# edge in G = # edge in G^d

# vertex in G = # region in G^d

# region in G = # vertex in G^d

如果兩片區(qū)域有倆段edge,連接一條dual edge就好

Chromatic number: χ(G)

Famous four color theorem

Tree it is connected and has no cycle (property followed)

1.there is a unique path between two vertex

2.removal of any edge dispart it into two tree

3.|E| = |V|-k for k tree forest

Generalized Pigeonhole Principle: If N pigeon occupy k pigeonhole, one pigeonhole at least contain ?N/k? pigeons.

permutation&combination

no-repetition: nPr= n!/(n-r)!? ? ; repetition: nPr=n^r

no-repetition: nCr= n!/(n-r)!/r!; repetition: nCr=(n-1+r)!/(n-1)!/r!

C repetition==> n-1 bars and r object selected? ?

Binomial theorem ?

Find permutation is next in the lexicographic order?

1. find the last number n followed by a larger number

2. looking for the smallest number m following n

3. interchange number m and n

4. arrange/flip order behind m, original n position

EX: 15843762.next()=15846237

Generating r-combinations?

1. find largest combination in r in ASC

2. comparing each element start from back?

3. if element i ≠ element in largest combination

4. element i+=1, following number increase follow element i

inclusion and exclusion?

Derangement:?

probability of derangement?

n—> ∞ =e^-1 ≈ 0.368

inclusion & exclusion 各類題型

find # of prime? ? ? distinguish object(divider) into indistinguish box?

x1+x2+x3=n ? ? ? ? indistinguish object into distinguish box?

# of onto function? distinguish object into distinguish box?

derangement? ? ? ? ? distinguish object into indistinguish box

from m object get n correct and other derangement

(m nCr n)*D(m-n)/m!

why combination choose one less: if we choose the n-1 then n is fix

?

Find recurrence

Linear Recurrence Relations

an=r^k , an-k=1, an-k+1=r?

relation?

Defn Where x and y are integers, and m is a positive integer, x≡y(mod m) if and only if m | x-y

notices: -3|3 since -3/3=-1 (除數(shù), 被除數(shù))?

example of relation:? R4: second set 3-1 | 2? ?

-matrix of relation:

1 if (a,b) ∈ R

0 if (a,b) not ∈ R

(left, top)

Property of relation

- reflexive

?a ∈ A, (a,a) ∈ R

- symmetric?

If (a,b) ∈ R, then (b,a) ∈ R called symmetric relation

- antisymmetric

If (a,b) ∈ R and (b,a) ∈ R, then a=b called antisymmetric

- transitive

If (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R

R called an equivalence relation if it is reflexive, symmetric and transitive.

R on set A called a partial order relation if it is reflexive, antisymmetric and transitive. Then A is called partial ordered set.

minimal element: nobody come into it ie: start element ?

maximal element: it can not go out ? ? ? ie: end element

schedule job to days: show a path from min to max element have three vertex?

? (p->q) = p & ? q

NP: a way to make yes always work

coNP: a way to make no always work

P: a way to make yes or no always work

All proof

Euler formula:?

If G=(V,E) is a connected plane graph, then |V|-|E|+|R|=2

Base case:

If G has 0 edge that is 1 vertex and 1region, satisfy |V|-|E|+|R|=2

Induction Hypothesis:?

Assume H is a connected plane graph with <k edge,?

then |V(H)|-|E(H)|+|R(H)|=2

Let G be a connected plane graph with K edge, let e be an edge of G

Case1: e is a loop

H=G-e, by IH |V(H)|-|E(H)|+|R(H)|=2

Adding edge in G makes |E(G)|=|E(H)|+1; |R(G)|=|R(H)|+1

|V(G)|-|E(G)|+|R(G)|=|V(H)|-|E(H)|-1+|R(H)|+1=2

Case2: e is not a cut edge

H=G-e, by IH |V(H)|-|E(H)|+|R(H)|=2

Adding edge in G makes |E(G)|=|E(H)|+1; |R(G)|=|R(H)|+1

|V(G)|-|E(G)|+|R(G)|=|V(H)|-|E(H)|-1+|R(H)|+1=2

Case3: e is a cut edge

G-e has two connected component F and H, F and H edge both <k so that |V(F)|-|E(F)|+|R(F)|=2; |V(H)|-|E(H)|+|R(H)|=2

|V(G)|=|V(F)|+|V(H)|

|E(G)|=|E(F)|+|E(H)|+1

|R(G)|=|R(F)|+|R(H)|-1

|V(G)|-|E(G)|+|R(G)|=|V(F)|+|V(H)|-(|E(F)|+|E(H)|+1)+(|R(F)|+|R(H)|-1)

=|V(F)|+|V(H)|-|E(F)|-|E(H)|+|R(F)|+|R(H)|-2

=(|V(F)|-|E(F)|+|R(F)|)+(|V(H)|-|E(H)|+|R(H)|)-2

=2+2-2=2

thus, |V(G)|-|E(G)|+|R(G)|=2

Each simple planner graph has a vertex degree at most 5

Contradiction proof:

|E|≤3|V|-6 and 2|E|=∑{d(v): v ∈ V}

If at least 6, 2|E|≥6|V| =>|E|≥3|V|

3|V|≤|E|≤3|V|-6 is impossible

Six colour theorem

If G=(V,E) is a simple graph, G can be coloured with 6 colours

Base case: the statement is obviously true for any simple group with at most 6 vertices.

Induction hypothesis:

Every simple planar graph < k vertices can be properly with at most 6 colour.

Let G be a graph with K vertices with a vertex of degree(x)≤5

By IH, G-e has k-1 vertices which can be properly with at most 6 colour.

(At most color will be used for vertices joined to x)

Adding edge x at most connect 5 vertex with 5 colour.?

There is an extra color for x

Thus, G can be coloured with 6 colours.

Pascal’s identity

!combinatorial proof

Proof of derangement

My Proof:

For a simple graph |V|>1, there are two vertex in same degree.

For a simple graph that have n vertex, each vertex has at most n-1 degree.?

There are {0,1,2,…,n-1} kinds of degree for n vertex to choose.?

However, if there is a vertex have n-1 degree that is connect to every vertex except itself, then there can not a vertex have 0 degree.

So there is only {0,1,2,…,n-2} or {1,2,…,n-1} in total is n-1 kind of degree for n vertex to choose.?

There is n-1 pigeonhole and n pigeon.?

So there must be two vertex in the same degree.