summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/tkz/tkz-berge/NamedGraphs/doc/latex/NamedGraphs-Koenisberg.tex
blob: 525d493fe1fb2d5edb19ec5b7dcf7db9ae2ad4c1 (plain)
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
\newpage\section{The Seven Bridges of Königsberg}\label{seven}
%<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––>
%<––––––––––––––––––         Königsberg       ––––––––––––––––––––––––––––––>
%<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––>
\begin{NewMacroBox}{grKonisberg}{\oarg{options}\var{$k$}}

\medskip
From MathWorld : \url{http://mathworld.wolfram.com/KoenigsbergBridgeProblem.html}

\emph{The Königsberg bridge problem asks if the seven bridges of the city of Königsberg (left figure; Kraitchik 1942), formerly in Germany but now known as Kaliningrad and part of Russia, over the river Preger can all be traversed in a single trip without doubling back, with the additional requirement that the trip ends in the same place it began. This is equivalent to asking if the multigraph on four nodes and seven edges (right figure) has an Eulerian circuit. This problem was answered in the negative by Euler (1736), and represented the beginning of graph theory.}
\href{http://mathworld.wolfram.com/topics/GraphTheory.html}%
           {\textcolor{blue}{MathWorld}} by \href{http://en.wikipedia.org/wiki/Eric_W._Weisstein}%
           {\textcolor{blue}{E.Weisstein}} 

\medskip
From Wikipedia : \url{http://en.wikipedia.org/wiki/Seven_Bridges_of_Königsberg}

\emph{The paper written by Leonhard Euler on the Seven Bridges of Königsberg and published in 1736 is regarded as the first paper in the history of graph theory.\hfill\break
The Seven Bridges of Königsberg is a famous solved mathematics problem inspired by an actual place and situation. The city of Königsberg, Prussia (now Kaliningrad, Russia) is set on the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges. The problem is to decide whether it is possible to walk a route that crosses each bridge exactly once.\hfill\break
In 1736, Leonhard Euler proved that it was not possible. In proving the result, Euler formulated the problem in terms of graph theory, by abstracting the case of Königsberg — first, by eliminating all features except the landmasses and the bridges connecting them; second, by replacing each landmass with a dot, called a vertex or node, and each bridge with a line, called an edge or link. The resulting mathematical structure is called a graph.}
\end{NewMacroBox}

\subsection{\tkzname{Königsberg graph} with \tkzcname{grKonisberg}}
\begin{center}
\begin{tkzexample}[vbox]
 \begin{tikzpicture}[node distance=4cm]
  \grKonisberg
 \end{tikzpicture}
\end{tkzexample} 
\end{center}

\vfill\newpage
\subsection{\tkzcname{Königsberg graph} : fine embedding}
\begin{center}
\begin{tkzexample}[vbox]
 \begin{tikzpicture}
   \renewcommand*{\VertexBallColor}{orange!50!red} 
   \renewcommand*{\EdgeDoubleDistance}{2pt} 
   \SetGraphUnit{4}
   \GraphInit[vstyle=Shade]
   \tikzset{LabelStyle/.style =   {draw,
                                   fill  = yellow,
                                   text  = red}}
   \Vertex{A}
   \EA(A){B}
   \EA(B){C}
   {\SetGraphUnit{8} 
   \NO(B){D}}
   \Edge[label=1](B)(D)
   \tikzset{EdgeStyle/.append style = {bend left}}
   \Edge[label=4](A)(B)
   \Edge[label=5](B)(A)
   \Edge[label=6](B)(C)
   \Edge[label=7](C)(B)
   \Edge[label=2](A)(D)
   \Edge[label=3](D)(C)
 \end{tikzpicture}
\end{tkzexample} 
\end{center}

\endinput