Notes on mathematical analysis 1: preliminaries

as an ordered field with lubp
Rational number system ( with ) has gaps (e.g., can not be find in rational set if ), in spite of the fact that between any two rationals there is another: if with both , then . The real number system, denoted by , fills these gaps. This is the principle reason for the fundamental role which it plays in analysis. To formalize this property, we have the least-upper-bound property of real system.

As a preliminary, note that is an ordered set, where is defined as that is positive. For an ordered set, we have the definition of bounded set. The least-upper-bound property is stated as follows:

Property 1 least-upper-bound property
If , is not empty, and is bounded above, then sup exists in .

Here sup is the least upper bound of , which is defined that sup is an upper bound of , and for any , is not an upper bound of . It can be proved that an ordered set with least-upper-bound property also has the greatest-lower-bound property, which can be similarly stated.

Another property that is as important as this one is that  is a field, an algebraic structure which defines the axioms for two operations: addition and multiplication. The importance comes from that the arithmetic laws derived from the definition of field.

To sum up, the set  of real numbers is an ordered field which has the least-upper-bound property. For the details of the proof, you may refer to rudin’s book. With such properties, we can prove the unique existence of for any .

As an extension to the real number system, we add two symbols,  , such that   for every  . In this case, any unbounded subset  of   now has sup  in the extended real number system.

Basic topology 1: Euclidean space as a metric space
A metric space is a space where distance (or norm) between elements of this space is defined. The properties of distance is not going to be presented here. The vector space   with definitions of inner product and norm is called Euclidean   space.

As preliminaries for getting to know metric space, we may have the definitions of countability first. With the definition of distance, we then immediately derive the definition of bounded set in metric space.

The important concepts in metric space include:

Definition 1 Let be a metric space,
A neighborhood of   is a set   consisting of all such that   for some .
A point   is a limit point of the set   if every neighborhood of contains a point  such that  .
is closed if every limit point of   is a point of  .
A point   is called an interior point of   if there is a neighborhood   of   such that  .
is open if every point of   is an interior point of  .

Based on the above definition, we have the theorem that 1) every neighborhood is an open set. 2) if is a limit point of , then every neighborhood of contains infinitely many points of .

Next we combine the above definitions with least-upper-bound in real system. Suppose and is a metric space, let denote the set of all limit points of , we define the closure of : . The theorem we have is:

Theorem 1 sup is a limit point of
Let be a nonempty set of real numbers which is bounded above, then sup. Hence sup if is closed.

Now we continues the exploration of concepts in Definition 1 (to be cont..)

Basic topology 2: compact subset of a metric space

[The following notes are written in pdf, you may contact me if you think it useful…]

Advertisements

Read Full Post »

Graph problem list

1. Single-source shortest paths (directed (simpler for undirected), weighted)
NB. single-pair shortest path is as hard as SSSP.
a. Dijkstra’s algorithm (O(|V|log|V|+|E|), O((|V|+|E|)·log|V|) if common heap), works only for non-negative weighted graphs.
b. Bellman-Ford (O(|V|·|E|)), can handle graphs with negative weighted edges (such case will be reported), works even for graphs with negative cycles.
Special case: DAG, O(|V|+|E|), can handle graphs with negative weighted edges.

2. All-pair shorted paths
a. Dynamic-programming algorithm O(|V|^3 ·log|V|)
b. Ford-Warshall algorithm O(|V|^3)
c. Johnson’s algorithm (O(|V|^2 ·log|V|+|V|·|E| )), changes the edge weights so that Dijkstra’s algorithm can be used.
NB1. Graph modification (a useful idea).
NB2. all above algorithms can not handle graphs with negative cycles.

3. Maximum flow
a. Ford-Fulkerson method, based on Max-flow min-cut Theorem.
number of iterations in Edmonds-Karp is O(|V|·|E|), therefore, the running time is O(|V|·|E|^2)
Applications:
1). Edge(vertex) disjoint path problem
2). Maximum matching in bipartite graphs
3). Capacity limitation for vertices
4). Point-to-rectangle problem
5). Edge(vertex) connectivity number problem (directed and undirected versions). This connectivity number problem of undirected graph can be solved by solving the edge disjoint-path problem O(|V|-1) times.

4. NP-Complete problems:
1). Clique
2). Vertex cover
3). Hamiltonian Cycle
4). TSP
5). Minimal vertex(edge) disjoint cycle covers
Minimum-Weight Cycle Cover Problem (MWCCP)
NB1. the proof of NP-hardness can be proceed by following the reduction path: 1->2->3->4.
NB2. approximation algorithms exists for vertex cover, and TSP if certain conditions are satisfied.

5. Bisimulation

6. Modular decomposition
a. Incremental method, O(|V|^2)
b. Linear complexity O(|V|+|E|), proposed in 2005.

—————————————————————————
Above are the graph related problems I met and studied so far. To know more about them if you are interested, you may refer to the book Introduction to algorithms by T.H.Cormen et al. Also, the slides given by Dr. Mark de Berg is quite helpful, which can be found here: http://www.win.tue.nl/~mdberg/Onderwijs/Algoritmiek_2012/2IL15.htm.

Read Full Post »