Thursday, October 25, 2012

Pearls of Latex and Matlab

1.1 Insert a graph
\usepackage{graphicx}

\begin{figure}[tbp]
\centering
\includegraphics{psu.jpg}
\caption{Including an external graphics file with...}
\end{figure}

1.2 List
\begin{itemize}
\item First Item
\item Second Item.
\item Third item.
\end{itemize}

\begin{enumerate}
\item First Item
\item Second Item.
\item Third item. \bf{Different} labels here.
        \begin{enumerate}
        \item First nested item
        \item Second item.
        \end{enumerate}
\end{enumerate}

1.3 Font
Bold Font
\\        %line break
{\bf This is a test}
\textbf{This is a test}
\textsc{This is a test}        %small capital letter
\emph{Emphasize part here}
footnote \footnote{A foot note}        %footnote format


Matlab

whos   and who       % show variables
load file.m              % load m file
vps(pi, 300)                         Display the first 300 digits of pi
p = 'hello world'
x = input('Accept a number: ')   % default is number
y = input('Accept a string', 's')   % accept a string
x = double(char('9'))                 % the ASCII number of '9'


>> for i='a':'z'        % demonstrate the for loop and type cast
double(char(i))
end


A=[1 2 3 4 5]                      Vector
size(A)            1x5
length(A)         length of A
A(3)                the third item of array
disp(A(3))       display the third item of array

A=[1,2,3; 4,5,6; 7,8,9]        Define a matrix
A=[A;[1 2 3]], [1;2;3;4]];    semicolon at the end of the statement suppresses the display of such a matrix.The size of a matrix can be expanded or reduced dynamically.

zeros(4)                  zero matrix square with 4*4
magic(4)                 magic matrix square with 4*4
rand(4)                   4*4 matrix with rand values
randsrc(m,n)           generate a matrix which elements are 1 or -1 with probability
b = A(:,[3])            get the first and last column
c = A(2,:)               get the first row
A'                          Transpose matrix
c = [A;B]               vertically concatenation
c = [A B]               horizontally concatenates
size(A)                   size of a matrix
A = ones(8,7)
A = reshape(A, 14, 4)    The number of elements must be equal

A(2:3,2:3)              2,3 row and 2,3 column
A(1:2:end,:)            get the odd row
A(:,1:2:end)            get the even column
v=[1 2 3]               
A=ones(3,1000)
>> for i=1:1000
A(:,i)=v                  for colume fill
end

>> linspace(F,L,N)    % F start point; L End point; N segments
>> v=F:G:L              % F start point; step size G; L End point

>> x=[1,2,3,4]; y=[1,3,3,0]
>> plot(x,y)
>> axis('equal')      % will use the same scaler on both x-coo and y-coo
>> xlable('x')      
>> ylable('y')
>> title('Title part')
>> hold on            % add more graphs until hold off

Tuesday, October 23, 2012

Graph, Tree and Spanner

欧拉图:经过图G的每条边一次且仅一次的路径,称为欧拉路径。经过图G的每条边一次且仅一次的回路,称为欧拉回路
定理1:无向图是欧拉图的充要条件是图中各顶点度数为偶数。
定理2:有向图是欧拉图的充要条件是图中各顶点的入度和出度相等。

哈密顿图:如果图G中存在一条通过图G中各个顶点一次且仅一次的回路,则称此回路为图G的哈密顿回路。具有哈密顿回路的图称为哈密顿图
定理3:具有n个顶点的无向图,如果G中任意两个不同顶点的度数之和大于等于n,则G具有哈密顿回路。(充分条件)
定理4:设图G=(V,E)是哈密顿图,则对于V的任意一个非空子集S,若以|S|表示S中元素的数目,G-S表示G中删去了S中的点以及这些点所关联的边后得到的子图,则w(G-S) ≤ |S|成立。其中w(G-S)是G-S中连通分支数。(必要条件)

A clique in an undirected graph G=(V,E) is a subset of the vertex set C⊆V, such that for every two vertices in C, there exists an edge connecting the two. This is equivalent to saying that the subgraph induced by C is complete.
A maximal clique is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique.
A maximum clique is a clique of the the largest possible size in a given graph. The clique number ω(G) of a graph G is the number of vertices in a maximum clique in G. The intersection number of G is the smallest number of cliques that together cover all edges of G.

To measure how good a network is, several quality measures have been used (<Geometric Spanner Network> P6):
1. Size is defined as the number of edges in the network. (few)
2. Weight is defined as the sum of the weights o the edges. (small)
3. Stretch Factor (Dilation) for two given points is defined as the ratio of the distance between the two points in the network to the metric distance between them. This is also called T spanner. Spanners with small size and/or weight are referred to as sparse spanners.
4. Degree is the maximum number of edges incident on any point in the network, often required to be bounded by a small constant. For a network, bounded degree implies small size, but not vice verse.
5. Diameter is the maximum number of edges along a shortest path connecting any two vertices in the network. (small)
6. Connectivity is the vertex or edge connectivity of the network.It is a measure of how fault-tolerant the network is, since it signifies the number of points or links that must fail in order for the network to be disconnected.
7. Fault Tolerance is the number of points or links that must fail in order for the network to fail to have some desirable properties.
8. Number of Steiner Points: better networks can be designed by adding Steiner points (points not in the input set). However one may be constrained to have very few or no Steiner points in the network.
9. Load Factor of an edge can be defined as the number of shortest paths between some pair of vertices that use this edge. (small)


Steiner trees
Consider a graph G=(V, E), whose vertex set V contains the set S. The vertices of V\S are called Steiner points. Let SMT(S) be such a graph G of minumum weight, where the weight wt(G) of G is defined to be the sum of the lengths of its edges. This graph is called a Steiner minimum tree of S.
The problem of finging a Steiner minimum tree of the vertices of a triangle is called the Fermat problem.
It is clear that wt(SMT(S))wt(MST(S)).
Let S be a finite set of points in Rd. Then wt(MST(S)) ≤ 2wt(SMT(S)). Proof?