August 21, 2009

Independent Set, Vertex Cover, and Clique

funes latex

doc.tex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
\documentclass{article}
\usepackage[papersize={200mm, 60mm}, text={190mm, 55mm}]{geometry}
\usepackage{subfigure, tikz}
 
\begin{document}
\begin{figure}[H]
 \centering
 \subfigure[Original Graph]{\input{graph.tex}}
 \quad
 \subfigure[Independent Set]{\input{ind_set.tex}}
 \quad
 \subfigure[Vertex Cover]{\input{vc.tex}}
 \quad
 \subfigure[Clique]{\input{clique.tex}}
 \caption{Relations among Independent Set, Vertex Cover, and Clique}
\end{figure}
 
\end{document}

graph.tex

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
\begin{tikzpicture}
  [
    line/.style = {draw=gray, ultra thick},
  ]
 
  \coordinate (O) at (-.5cm, .3cm);
  % in polar coordinates system
  \coordinate (A) at (  0: 2cm);
  \coordinate (B) at ( 60: 2cm);
  \coordinate (C) at (120: 2cm);
  \coordinate (D) at (180: 2cm);
  \coordinate (E) at (240: 2cm);
  \coordinate (F) at (300: 2cm);
 
  % edges
  \path[line] (A) -- (B);
  \path[line] (B) -- (C);
  \path[line] (C) -- (D);
  \path[line] (D) -- (E);
  \path[line] (E) -- (F);
  \path[line] (F) -- (A);
  \path[line] (B) -- (O);
  \path[line] (O) -- (F);
  \path[line] (B) -- (D);
  \path[line] (D) -- (F);
 
  % nodes
  \shade[ball color=gray] (O) circle (4pt);
  \shade[ball color=gray] (A) circle (4pt);
  \shade[ball color=gray] (B) circle (4pt);
  \shade[ball color=gray] (C) circle (4pt);
  \shade[ball color=gray] (D) circle (4pt);
  \shade[ball color=gray] (E) circle (4pt);
  \shade[ball color=gray] (F) circle (4pt);
\end{tikzpicture}

ind_set.tex

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
\begin{tikzpicture}
  [
    line/.style = {draw=gray, ultra thick},
  ]
 
  \coordinate (O) at (-.5cm, .3cm);
  % in polar coordinates system
  \coordinate (A) at (  0: 2cm);
  \coordinate (B) at ( 60: 2cm);
  \coordinate (C) at (120: 2cm);
  \coordinate (D) at (180: 2cm);
  \coordinate (E) at (240: 2cm);
  \coordinate (F) at (300: 2cm);
 
  % edges
  \path[line] (A) -- (B);
  \path[line] (B) -- (C);
  \path[line] (C) -- (D);
  \path[line] (D) -- (E);
  \path[line] (E) -- (F);
  \path[line] (F) -- (A);
  \path[line] (B) -- (O);
  \path[line] (O) -- (F);
  \path[line] (B) -- (D);
  \path[line] (D) -- (F);
 
  % nodes
  \shade[ball color=blue!80]  (O) circle (4pt);
  \shade[ball color=blue!80]  (A) circle (4pt);
  \shade[ball color=gray] (B) circle (4pt);
  \shade[ball color=blue!80]  (C) circle (4pt);
  \shade[ball color=gray] (D) circle (4pt);
  \shade[ball color=blue!80]  (E) circle (4pt);
  \shade[ball color=gray] (F) circle (4pt);
\end{tikzpicture}

vc.tex

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
\begin{tikzpicture}
  [
    line/.style = {draw=gray, ultra thick},
  ]
 
  \coordinate (O) at (-.5cm, .3cm);
  % in polar coordinates system
  \coordinate (A) at (  0: 2cm);
  \coordinate (B) at ( 60: 2cm);
  \coordinate (C) at (120: 2cm);
  \coordinate (D) at (180: 2cm);
  \coordinate (E) at (240: 2cm);
  \coordinate (F) at (300: 2cm);
 
  % edges
  \path[line] (A) -- (B);
  \path[line] (B) -- (C);
  \path[line] (C) -- (D);
  \path[line] (D) -- (E);
  \path[line] (E) -- (F);
  \path[line] (F) -- (A);
  \path[line] (B) -- (O);
  \path[line] (O) -- (F);
  \path[line] (B) -- (D);
  \path[line] (D) -- (F);
 
  % nodes
  \shade[ball color=gray] (O) circle (4pt);
  \shade[ball color=gray] (A) circle (4pt);
  \shade[ball color=red ] (B) circle (4pt);
  \shade[ball color=gray] (C) circle (4pt);
  \shade[ball color=red ] (D) circle (4pt);
  \shade[ball color=gray] (E) circle (4pt);
  \shade[ball color=red ] (F) circle (4pt);
\end{tikzpicture}

clique.tex

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
\begin{tikzpicture}
  [
    line/.style = {draw=gray, ultra thick},
  ]
 
  \coordinate (O) at (-.5cm, .3cm);
  % in polar coordinates system
  \coordinate (A) at (  0: 2cm);
  \coordinate (B) at ( 60: 2cm);
  \coordinate (C) at (120: 2cm);
  \coordinate (D) at (180: 2cm);
  \coordinate (E) at (240: 2cm);
  \coordinate (F) at (300: 2cm);
 
  % edges
  \path[line] (A) -- (O);
  \path[line] (A) -- (C);
  \path[line] (A) -- (D);
  \path[line] (A) -- (E);
  \path[line] (B) -- (E);
  \path[line] (B) -- (F);
  \path[line] (C) -- (A);
  \path[line] (C) -- (E);
  \path[line] (C) -- (F);
  \path[line] (C) -- (O);
  \path[line] (D) -- (O);
  \path[line] (E) -- (O);
 
  % nodes
  \shade[ball color=green] (O) circle (4pt);
  \shade[ball color=green] (A) circle (4pt);
  \shade[ball color=gray]  (B) circle (4pt);
  \shade[ball color=green] (C) circle (4pt);
  \shade[ball color=gray]  (D) circle (4pt);
  \shade[ball color=green] (E) circle (4pt);
  \shade[ball color=gray]  (F) circle (4pt);
\end{tikzpicture}
, , , , , ,
Comments Off on Independent Set, Vertex Cover, and Clique