Archive for June, 2012

\mathcal{R} as an ordered field with lubp
Rational number system (\frac{m}{n} with m,n\in Q) has gaps (e.g., p can not be find in rational set if p^2=2), in spite of the fact that between any two rationals there is another: if r<s with both r, s\in Q, then r<(r+s)/2<s. The real number system, denoted by R, 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 R is an ordered set, where r<s (r,s\in R) is defined as that s-r 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 E\subset R, E is not empty, and E is bounded above, then supE exists in R.

Here supE is the least upper bound of E, which is defined that supE is an upper bound of E, and for any \gamma <\text{sup}E , \gamma is not an upper bound of E. 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 R 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 R 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 \sqrt{n} for any n\in N_+.

As an extension to the real number system, we add two symbols,  +\infty, -\infty, such that  -\infty< x <+\infty for every  x\in R. In this case, any unbounded subset E of  R now has sup E=+\infty 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  R^k with definitions of inner product and norm is called Euclidean  k- 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 X be a metric space,
A neighborhood of  p is a set  N_r(p) consisting of all q such that  d(p,q)<r for some r>0.
A point  p is a limit point of the set  E if every neighborhood of p contains a point q\neq p such that  q\in E.
E is closed if every limit point of  E is a point of  E.
A point  p is called an interior point of  E if there is a neighborhood  N of  p such that  N\subset E.
E is open if every point of  E is an interior point of  E.

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

Next we combine the above definitions with least-upper-bound in real system. Suppose E\subset X and X is a metric space, let E^{\prime} denote the set of all limit points of E, we define the closure of E: \bar{E}=E\cup E^{\prime}. The theorem we have is:

Theorem 1 supE is a limit point of E
Let E be a nonempty set of real numbers which is bounded above, then supE\in \bar{E}. Hence supE\in E if E 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 »