%!TEX root = /Users/ego/Boulot/TKZ/tkz-berge/doc-us/TKZdoc-berge-main.tex %<–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> \section{Classic Graphs} %<–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> %<––––––––––––––––––––––– graphes classiques –––––––––––––––––––––––––> %<–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> \subsubsection{Cycle graph} \begin{NewMacroBox}{grCycle}{\oarg{local options}\var{order}} \medskip \emph{A cycle graph $C_n$ is a graph on $n$ nodes containing a single cycle through all nodes. Cycle graphs can be generated using \tkzcname{grCycle} in the \tkzname{tkz-berge.sty} package. Special cases include the triangle graph and the square graph.} \medskip External links : \medskip \begin{itemize} \item \href{http://mathworld.wolfram.com/CycleGraph.html}% {\textcolor{blue}{MathWorld - CycleGraph}} by % \href{http://en.wikipedia.org/wiki/Eric_W._Weisstein}% {\textcolor{blue}{E.Weisstein}} \item \href{http://en.wikipedia.org/wiki/Cycle_graph}% {\textcolor{blue}{Wikipedia}} \end{itemize} \end{NewMacroBox} \subsubsection{Special cases : the triangle graph and the square graph} \begin{center} \begin{tkzexample}[small] \begin{tikzpicture} \GraphInit[vstyle=Shade] \grCycle[prefix=a,RA=3]{5} \grCycle[x=4,y=3,prefix=b,RA=2]{3} \grCycle[prefix=d,y=6,rotation=30,RA=2]{4} \end{tikzpicture} \end{tkzexample} \end{center} \newpage \subsubsection{Complete graph} \begin{NewMacroBox}{grComplete}{\oarg{local options}\var{order}} \medskip \emph{The more simple definition is "an undirected graph with an edge between every pair of vertices" or a complete graph is a simple graph in which each pair of graph vertices is connected by an edge. The complete graph with $n$ graph vertices is denoted $K_n$. This graph has $\frac{n(n-1)}{2}$ undirected edges.\\ Geometrically, $K_3$ relates to a triangle,$ K_4$ a tetrahedron is the tetrahedral graph as well as the wheel graph , $K_5$ a pentachoron, etc \dots} \medskip External links : \medskip \begin{itemize} \item \href{http://en.wikipedia.org/wiki/Complete_graph}% {\textcolor{blue}{Wikipedia}} \item \href{http://mathworld.wolfram.com/grComplete.html}% {\textcolor{blue}{MathWorld - Complete graph}} by % \href{http://en.wikipedia.org/wiki/Eric_W._Weisstein}% {\textcolor{blue}{E.Weisstein}} \end{itemize} \end{NewMacroBox} \subsubsection{Complete Graph order 4} \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture} \renewcommand*{\VertexBallColor}{green!50!black} \GraphInit[vstyle=Shade] \grComplete[RA=5]{7} \end{tikzpicture} \end{tkzexample} \end{center} \vfill\newpage\null \subsubsection{Complete Graph order 4} \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture} \renewcommand*{\VertexBallColor}{green!50!black} \GraphInit[vstyle=Shade] \SetVertexNoLabel \grComplete[RA=7]{16} \end{tikzpicture} \end{tkzexample} \end{center} %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> \newpage \subsubsection{Circulant graph} \begin{NewMacroBox}{grCirculant}{\oarg{local options}\var{order}} \medskip \emph{The circulant graph is defined for any order $n$ at least 3, and every subset $L$ of integers which are less than or equal to $n/2$. A circulant graph is a graph in which the $i$th graph vertex is adjacent to the ($i+j$)th and ($i-j$)th graph vertices for each $j$ in a list $L$ . The circulant graphs with $L=\{1;\dots;[n/2]\}$ gives the complete graphs and the circulant graph with $L=\{1\}$ gives the cyclic graphs. The Möbius ladders are examples of circulant graphs.\\ In graph theory, a graph whose adjacency matrix is circulant is called a circulant graph.\\ The circulant graph on vertices on a list of nodes is implemented as \tkzcname{grCirculant} in the \tkzname{tkz-berge.sty} package.} \medskip External links : \href{http://mathworld.wolfram.com/CirculantGraph.html}% {\textcolor{blue}{MathWorld - CirculantGraph}} by % \href{http://en.wikipedia.org/wiki/Eric_W._Weisstein}% {\textcolor{blue}{E.Weisstein}} \end{NewMacroBox} \tikzset{VertexStyle/.style = {shape = circle, shading = ball, ball color = green!40!black,% minimum size = 16pt,% draw}} \SetUpEdge[style = {thick,% double = orange,% double distance = 1pt}] \SetVertexNoLabel \tikzset{EdgeStyle/.style = {thick, double= orange, double distance = 1pt}} \subsubsection{ \opt{Graph order 5 with L=\{1\}}} This is a cycle graph. \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture} \grCirculant[RA=3]{5}{1}% \end{tikzpicture} \end{tkzexample} \end{center} \subsubsection{\opt{Graph order 5 with L=\{2\}}} \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture} \grCirculant[RA=3]{5}{2}% \end{tikzpicture} \end{tkzexample} \end{center} \subsubsection{\opt{Graph order 5 with L=\{1,2\}}} This graph is complete with an order $5$. \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture} \grCirculant[RA=3]{5}{1,2}% \end{tikzpicture} \end{tkzexample} \end{center} \subsubsection{\opt{Graph order 10 with L=\{1,2,3,4,5\}}} This graph is also complete \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture} \grCirculant[RA=4]{10}{1,2,3,4,5}% \end{tikzpicture} \end{tkzexample} \end{center} It's interesting to remark that the numbers 3 and 10 are primer, so if $L=\{3\} $ the graph is containing an Eulerian circuit. \subsubsection{\opt{Graph order 10 with L=\{3\}}} \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture} \grCirculant[RA=4]{10}{3}% \end{tikzpicture} \end{tkzexample} \end{center} \vfill\newpage\null \tikzset{VertexStyle/.style = {shape = circle, shading = ball, ball color = gray!30,% minimum size = 24pt,% draw}} \tikzset{EdgeStyle/.style = {thick,% double = orange,% double distance = 1pt}} \SetVertexMath \subsubsection{\opt{Graph order 21 with L=\{1,3,10\}}} \SetVertexNoLabel \begin{tikzpicture} \grCirculant[Math,RA=7]{21}{1,3,10} \end{tikzpicture} %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> %<––––––––––––––––––––––––––– STAR –––––––––––––––––––––––––––––––––––> %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> \newpage \subsubsection{Star graph} \begin{NewMacroBox}{grStar}{\oarg{local options}\var{order}} \medskip \emph{A star graph $S_n$ is a n-graph with one node having vertex degree $n-1$ and the other $n-1$ having vertex degree $1$. Star graphs can be generated using \tkzcname{grStar} in the \tkzname{tkz-berge.sty} package.} \medskip External links : \medskip \begin{itemize} \item \href{http://mathworld.wolfram.com/StarGraph.html}% {\textcolor{blue}{MathWorld - StarGraph}} by % \href{http://en.wikipedia.org/wiki/Eric_W._Weisstein}% {\textcolor{blue}{Weisstein}} \end{itemize} \end{NewMacroBox} \tikzset{VertexStyle/.style = {shape = circle, shading = ball, ball color = orange!40!,% minimum size = 26pt,% draw}} \SetUpEdge[style={thick,% double = orange,% double distance = 1pt}] \SetVertexNoLabel \tikzset{EdgeStyle/.style = {thick, double= orange, double distance = 1pt }} \subsubsection{Star graph} \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture}[rotate=30,scale=.8] \grStar[RA=7]{8}% \end{tikzpicture} \end{tkzexample} \end{center} %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> \newpage \subsubsection{Square graph} \begin{NewMacroBox}{grSQCycle}{\oarg{local options}\var{Number}} \medskip \emph{A star graph $S_n$ is a n-graph with one node having vertex degree $n-1$ and the other $n-1$ having vertex degree $1$. Star graphs can be generated using \tkzcname{grStar} in the \tkzname{tkz-berge.sty} package.} \medskip External links : \medskip \begin{itemize} \item \href{http://mathworld.wolfram.com/SquareGraph.html}% {\textcolor{blue}{MathWorld - SquareGraph}} by % \href{http://en.wikipedia.org/wiki/Eric_W._Weisstein}% {\textcolor{blue}{Weisstein}} \end{itemize} \end{NewMacroBox} \subsubsection{Square Cycle graph} \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture}[scale=.8] \grSQCycle[RA=7]{10}% \end{tikzpicture} \end{tkzexample} \end{center} %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> %<–––––––––––––––––––––––––––– WHEEL –––––––––––––––––––––––––––––> %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> \newpage \subsubsection{Wheel graph} \begin{NewMacroBox}{grWheel}{\oarg{local options}\var{Number}} \medskip \emph{A wheel graph of order $n$ is a graph that contains a cycle of order $n-1$, and for which every vertex in the cycle is connected to one other vertex. The wheel can be defined as the graph , where is the singleton graph and is the cycle graph.} \medskip External links : \medskip \begin{itemize} \item \href{http://mathworld.wolfram.com/WheelGraph.html}% {\textcolor{blue}{MathWorld - WheelGraph}} by % \href{http://en.wikipedia.org/wiki/Eric_W._Weisstein}% {\textcolor{blue}{Weisstein}} \end{itemize} \end{NewMacroBox} \tikzset{VertexStyle/.style = {shape = circle, shading = ball, ball color = orange!40,% minimum size = 24pt,% draw}} \SetUpEdge[style={thick,% double = orange,% double distance = 1pt}] \SetVertexNoLabel \tikzset{EdgeStyle/.style = {thick,double= orange,double distance = 1pt}} \vfill \subsubsection{\tkzname{Wheel graph}} \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture}[scale=.8] \grWheel[RA=7]{13}% \end{tikzpicture} \end{tkzexample} \end{center} %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> %<–––––––––––––––––––––––––––– LADDER ––––––––––––––––––––––––––> %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> \newpage \subsubsection{Ladder graph} \begin{NewMacroBox}{grLadder}{\oarg{local options}\var{Number}} \medskip \begin{tabular}{llc} \toprule options & default & definition \\ \midrule \TOline{RA } { |4| } {radius circle n°1 } \TOline{RS } { |0| } {distance between two lines } \TOline{prefix } { |a| } {prefix for vertices } \TOline{prefixx} { |b| } {prefix for vertices } \TOline{Math } { |false|} {math mode } \bottomrule \end{tabular} \medskip \emph{The ladder graph $L_n$ or cyclic ladder graph is equivalent to the grid graph having two rails and $n$ rungs between them.} \medskip External links : \medskip \begin{itemize} \item \href{http://mathworld.wolfram.com/LadderGraph.html}% {\textcolor{blue}{MathWorld - LadderGraph}} by % \href{http://en.wikipedia.org/wiki/Eric_W._Weisstein}% {\textcolor{blue}{Weisstein}} \end{itemize} \end{NewMacroBox} \vfill \subsubsection{\tkzname{Ladder graph}} \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture} \grLadder[RA=2,RS=4]{6}% \end{tikzpicture} \end{tkzexample} \end{center} \vfill %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> %<––––––––––––––––––––––––––– Prism CYCLE LADDER –––––––––––––––––––––––> %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> \newpage \subsubsection{Prism graph} \begin{NewMacroBox}{grPrism}{\oarg{local options}\var{Number}} \medskip \begin{tabular}{llc} \toprule options & default & definition \\ \midrule \TOline{RA } { |4| } {radius circle n°1 } \TOline{RB } { |3| } {radius circle n°2 } \TOline{prefix } { |a| } {prefix for vertices } \TOline{prefixx } { |b| } {prefix for vertices } \TOline{Math } { |false|} {math mode } \bottomrule \end{tabular} \medskip \emph{An $n$-prism graph has $2n$ nodes and $3n$ edges, and is equivalent to the generalized Petersen graph with arguments $n$ and $1$. For odd $n$, the $n$-prism is isomorphic to the circulant graph with an order $2n$ and with arguments $2$ and $n$.\\ The 3-prism graph is the line graph of the complete bipartite graph with arguments $2$ and $3$ . The 4-prism graph is isomorphic with the cubical graph.} \medskip External links : \medskip \begin{itemize} \item \href{http://mathworld.wolfram.com/PrismGraph.html}% {\textcolor{blue}{MathWorld - Prism Graph}} by % \href{http://en.wikipedia.org/wiki/Eric_W._Weisstein}% {\textcolor{blue}{Weisstein}} \end{itemize} \end{NewMacroBox} \subsubsection{\tkzname{Cycle Ladder graph}} \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture}[rotate=15,scale=.7] \grPrism[RA=6,RB=3]{6}% \end{tikzpicture} \end{tkzexample} \end{center} \subsubsection{\tkzname{Cycle Ladder graph number 3}} \begin{center} \begin{tkzexample}[] \begin{tikzpicture}[scale=.7] \grPrism[RA=6,RB=3]{3}% \end{tikzpicture} \end{tkzexample} \end{center} \subsubsection{\tkzname{Cycle Ladder graph number 4}} \begin{center} \begin{tkzexample}[] \begin{tikzpicture}[scale=.7] \grPrism[RA=6,RB=3]{4}% \end{tikzpicture} \end{tkzexample} \end{center} %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> %<––––––––––––––––––––––––––––– bipartite ––––––––––––––––––––––––––––––––> %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> \newpage \subsubsection{Complete Bipartite graph} \begin{NewMacroBox}{grCompleteBipartite}{\oarg{local options}\var{Number 1}\var{Number 2}} \medskip \begin{tabular}{llc} \toprule options & default & definition \\ \midrule \TOline{RA }{|4| } {radius circle n°1} \TOline{RB }{|3| } {radius circle n°2 } \TOline{RS }{|1| } {distance between two lines } \TOline{form }{|1| } {integer to obtain a new embedding of a graph} \TOline{prefix }{|a| } {prefix for vertices } \TOline{prefixx}{|b| } {prefix for vertices } \TOline{Math }{|false| } {math mode } \bottomrule \end{tabular} \medskip \emph{A complete bipartite graph is a bipartite graph (i.e., a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent) such that every pair of graph vertices in the two sets are adjacent.} \medskip External links : \medskip \begin{itemize} \item \href{http://mathworld.wolfram.com/CompleteBipartiteGraph.html}% {\textcolor{blue}{MathWorld - CompleteBipartite Graph}} by % \href{http://en.wikipedia.org/wiki/Eric_W._Weisstein}% {\textcolor{blue}{Weisstein}} \end{itemize} \end{NewMacroBox} \subsubsection{\tkzname{Bipartite graph 1,5}}\label{cl17} \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture} \grCompleteBipartite[RA=4,RB=2.5,RS=4]{1}{5} \end{tikzpicture} \end{tkzexample} \end{center} \subsubsection{\tkzname{Bipartite graph 3,5}}\label{bi1} \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture} \grCompleteBipartite[RA=4,RB=3,RS=6]{3}{5} \end{tikzpicture} \end{tkzexample} \end{center} %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> \newpage \subsubsection{Triangular Grid graph} \begin{NewMacroBox}{grTriangularGrid}{\oarg{local options}\var{Number}} \medskip \begin{tabular}{llc} \toprule options & default & definition \\ \bottomrule \TOline{RA }{|4| }{distance between two vertices } \TOline{form }{|1| }{integer to obtain a new embedding of a graph} \TOline{prefix}{|a| }{prefix for vertices } \TOline{Math }{|false|}{math mode } \bottomrule \end{tabular} \emph{\tkzname{Number=$n$} is the number of vertices of the first row then the graph order is $\dfrac{n(n-1)}{2} $. There are three embeddings. You can use the option \tkzname{form} with an integer between $1$ and $3$.} \end{NewMacroBox} \medskip \subsubsection{\opt{n=8 order=$28$} form 1}\label{cl18a} \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture} \GraphInit[vstyle=Shade] \SetVertexLabel \grTriangularGrid[prefix=G,Math,RA=1.5]{8}% \end{tikzpicture} \end{tkzexample} \end{center} \subsubsection{\opt{n=6 order=$15$} form 2} \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture} \GraphInit[vstyle=Shade] \SetVertexNoLabel \grTriangularGrid[RA=2,form=2]{6}% \end{tikzpicture} \end{tkzexample} \end{center} \subsubsection{\opt{n=6 order=$15$} form 3} \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture} \GraphInit[vstyle=Shade] \SetVertexNoLabel \grTriangularGrid[RA=2,form=3]{6}% \end{tikzpicture} \end{tkzexample} \end{center} %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> \newpage \subsubsection{\tkzname{LCF Lederberg-Coxeter-Fruchte}} \begin{NewMacroBox}{grLCF}{\oarg{RA=\meta{Number}} \var{List of numbers} \var{Number}} \emph{LCF = Lederberg-Coxeter-Fruchte (see the link below for some examples).} \medskip External links : \medskip \begin{itemize} \item \href{http://mathworld.wolfram.com/LCFNotation.html}% {\textcolor{blue}{MathWorld-LCF Notation}} by % \href{http://en.wikipedia.org/wiki/Eric_W._Weisstein}% {\textcolor{blue}{Weisstein}} \end{itemize} \end{NewMacroBox} \subsubsection{\tkzname{$\big[2,-2\big]^2$}} \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture}% \grLCF[RA=5]{2,-2}{2}% \end{tikzpicture} \end{tkzexample} \end{center} \subsubsection{\tkzname{$\big[3,-3\big]^4$}} \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture}% \grLCF[RA=5]{3,-3}{4}% \end{tikzpicture} \end{tkzexample} \end{center} \subsubsection{Ljubljana graph} From Wikipedia \url{http://en.wikipedia.org/wiki/Ljubljana_graph} \emph{The Ljubljana graph was first published in 1993 by Brouwer, Dejter and Thomassen. In 1972, Bouwer was already talking of a 112-vertices edge- but not vertex-transitive cubic graph found by R. M. Foster, but unpublished. Conder, Malnič, Marušič, Pisanski and Potočnik rediscovered this 112-vertices graph in 2002 and named it the Ljubljana graph after the capital of Slovenia. They proved that it was the unique 112-vertices edge- but not vertex-transitive cubic graph and therefore that was the graph found by Foster.} It can be represented in LCF notation as : \[ \begin{array}{l} \Big[ 47, -23, -31, 39, 25, -21, -31, -41, 25, 15, 29, -41, -19, 15, -49, 33, 39, -35, -21, 17,\\ -33, 49, 41, 31, -15, -29, 41, 31, -15, -25, 21, 31, -51, -25, 23, 9, -17, 51, 35, -29, 21,\\ -51, -39, 33, -9, -51, 51, -47, -33, 19, 51, -21,29, 21, -31, -39\Big]^2 \end{array} \] \begin{center} \begin{tikzpicture} \GraphInit[vstyle=Art] \SetGraphArtColor{black!50}{darkgray} \tikzset{VertexStyle/.append style = { minimum size = 3pt}} \grLCF[RA=7]{47, -23, -31, 39, 25, -21, -31, -41, 25, 15, 29, -41, -19, 15, -49, 33, 39, -35, -21, 17, -33, 49, 41, 31, -15, -29, 41, 31, -15, -25, 21, 31, -51, -25, 23, 9, -17, 51, 35, -29, 21, -51, -39, 33, -9, -51, 51, -47, -33, 19, 51, -21, 29, 21, -31, -39}{2}% \end{tikzpicture} \end{center} \begin{tkzexample}[code only] \GraphInit[vstyle=Art] \SetGraphArtColor{black!50}{darkgray} \tikzset{VertexStyle/.append style = { minimum size = 3pt}} \begin{tikzpicture}% \grLCF[RA=7]{47, -23, -31, 39, 25, -21, -31, -41, 25, 15, 29, -41, -19, 15,% -49, 33, 39, -35, -21, 17, -33, 49, 41, 31, -15, -29, 41, 31, -15, -25, 21,% 31, -51, -25, 23, 9, -17, 51, 35, -29, 21, -51, -39, 33, -9, -51, 51, -47,% -33, 19, 51, -21, 29, 21, -31, -39}{2}% \end{tikzpicture} \end{tkzexample} \vfill \endinput