August 21, 2009
doc.tex
\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
\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
\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
\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
\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