September 15, 2012

Tree

funes latex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
\documentclass{article}
\usepackage[papersize={45mm, 30mm}, text={40mm, 35mm}]{geometry}
\usepackage{tikz}
\usetikzlibrary{arrows}
 
\begin{document}
 
\begin{figure}
  \centering
  \begin{tikzpicture}[node distance=1cm,>=stealth',elem/.style={circle,draw,fill=orange!40}]
    \node [elem] (b2) {2};
    \node [elem] (b4) [below of=b2, xshift=-10mm] {4} edge [->] (b2);
    \node [elem] (b3) [below of=b2, xshift=  8mm] {3} edge [->] (b2);
    \node [elem] (b1) [below of=b4, xshift= -8mm] {1} edge [->] (b4);
    \node [elem] (b0) [below of=b4, xshift=  8mm] {0} edge [->] (b4);
    \node [elem] (b5) [below of=b3, xshift=  4mm] {5} edge [->] (b3);
  \end{tikzpicture}
\end{figure}
 
\end{document}
, , ,
Comments Off on Tree
November 7, 2011

A Simple Counterexample

funes latex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
\documentclass{article}
 
\usepackage[papersize={85mm, 25mm}, text={75mm, 20mm}]{geometry}
 
\usepackage{pgf, tikz}
\usetikzlibrary{arrows,automata}
 
\begin{document}
\begin{figure}[h]
  \footnotesize
  \centering
  \begin{tikzpicture}[
    % type of arrow head
    >=stealth',
    % keep arrow head from touching the surface
    shorten >= 1pt,
    % automatic node positioning
    auto,
    %
    node distance=1.5cm,
    % line thickness
    semithick,
    % text for the initial state arrow. I left it as blank
    initial text=]
    \tikzstyle{every state}=[draw=blue!50, thick, fill=blue!20,
    minimum size=4mm]
     
    \node[state] (v1) {$v_1$};
    \node[state] (v2) [right of=v1] {$v_2$};
    \node[state] (v3) [right of=v2] {$v_3$};
    \node[state] (v4) [right of=v3] {$v_4$};
    \node[state] (v5) [right of=v4] {$v_5$};
     
    \path[->] (v1) edge (v2);
    \path[->] (v3) edge (v4);
    \path[->] (v4) edge (v5);
 
    \path[->, bend right, bend angle = 5] (v2) edge (v5);
    \path[->, bend left, bend angle = 25] (v1) edge (v3);
  \end{tikzpicture}
\end{figure}
\end{document}
, , , ,
Comments Off on A Simple Counterexample
April 17, 2011

Spectral Graph Theory

funes Uncategorized

Let G be a d-regular bipartite graph and AG is its adjacency matrix. Prove that the eigenvalue of AG is -d.

One example:

  • Let G be a graph where the left vertices are {1,3,5} and the right vertices are {2,4,6}.
  • The undirected edges are (1,2), (1,4), (3,4), (3,6), (5,1), (5,6).
octave:1> B=zeros(6,6)
B =

   0   0   0   0   0   0
   0   0   0   0   0   0
   0   0   0   0   0   0
   0   0   0   0   0   0
   0   0   0   0   0   0
   0   0   0   0   0   0

octave:2> B(1,2)=1; B(1,4)=1; B(3,4)=1; B(3,6)=1; B(5,2)=1; B(5,6)=1
B =

   0   1   0   1   0   0
   0   0   0   0   0   0
   0   0   0   1   0   1
   0   0   0   0   0   0
   0   1   0   0   0   1
   0   0   0   0   0   0

octave:3> B = B + B'
B =

   0   1   0   1   0   0
   1   0   0   0   1   0
   0   0   0   1   0   1
   1   0   1   0   0   0
   0   1   0   0   0   1
   0   0   1   0   1   0

octave:4> [EVEC, EVAL] = eig(X)
EVEC =

  -0.50000   0.65328   0.50000  -0.27060
  -0.50000   0.27060  -0.50000   0.65328
  -0.50000  -0.27060  -0.50000  -0.65328
  -0.50000  -0.65328   0.50000   0.27060

EVAL =

Diagonal Matrix

   1.7413e-16            0            0            0
            0   5.8579e-01            0            0
            0            0   2.0000e+00            0
            0            0            0   3.4142e+00

octave:5>
, , , ,
Comments Off on Spectral Graph Theory