main.tex (12056B)
1 \documentclass[a4paper]{article} 2 3 4 \usepackage[T1]{fontenc} 5 \usepackage[utf8]{inputenc} 6 \usepackage{mathptmx} 7 8 %\usepackage{ngerman} % Sprachanpassung Deutsch 9 10 \usepackage{graphicx} 11 \usepackage{geometry} 12 \geometry{a4paper, top=15mm} 13 14 \usepackage{minted} 15 \usepackage{subcaption} 16 \usepackage[shortlabels]{enumitem} 17 \usepackage{amssymb} 18 \usepackage{amsthm} 19 \usepackage{mathtools} 20 \usepackage{braket} 21 \usepackage{bbm} 22 \usepackage{graphicx} 23 \usepackage{float} 24 \usepackage{yhmath} 25 \usepackage{tikz} 26 \usetikzlibrary{patterns,decorations.pathmorphing,positioning} 27 \usetikzlibrary{calc,decorations.markings} 28 29 \usepackage[backend=biber, sorting=none]{biblatex} 30 \addbibresource{uni.bib} 31 32 \usepackage[framemethod=TikZ]{mdframed} 33 34 \tikzstyle{titlered} = 35 [draw=black, thick, fill=white,% 36 text=black, rectangle, 37 right, minimum height=.7cm] 38 39 40 \usepackage[colorlinks=true,naturalnames=true,plainpages=false,pdfpagelabels=true]{hyperref} 41 \usepackage[parfill]{parskip} 42 \usepackage{lipsum} 43 44 45 \usepackage{tcolorbox} 46 \tcbuselibrary{skins,breakable} 47 48 \pagestyle{myheadings} 49 50 \markright{Popovic\hfill 1st Exercise \hfill} 51 52 53 \title{University of Vienna\\ Faculty of Mathematics\\ 54 \vspace{1.25cm}Seminar: Introduction to complex network analysis \\ 1st 55 Exercise 56 } 57 \author{Milutin Popovic} 58 \date{11. October, 2021} 59 60 \begin{document} 61 \maketitle 62 63 \textbf{Exercise 1:} \textit{Königsberg Problem} 64 \begin{enumerate} 65 \item Which of the shown graphs can be drawn without raising the 66 pencil from the paper and without drawing one line more than.u 67 once. Why?(2 pts)n. 68 \begin{figure}[h!] \centering 69 \begin{tikzpicture}[ 70 dot/.style = {draw, circle, inner sep=0.06cm}, 71 no/.style = {}, 72 ] 73 \node[dot](l0) at (2,0) [] {$B$}; 74 \node[dot](l1) at (2,-1) [] {$C$}; 75 \node[dot](l2) at (1,0) [] {$A$}; 76 \node[dot](l3) at (1,-1) [] {$D$}; 77 \draw (l0) -- (l1) -- (l2) -- (l3) -- (l1); 78 \draw (l3) -- (l0); 79 \draw (l2) -- (l0); 80 81 \node[dot](r0) at (7,0) [] {$A$}; 82 \node[dot](r1) at (8,-1) [] {$D$}; 83 \node[dot](r2) at (8,0) [] {$C$}; 84 \node[dot](r3) at (7,-1) [] {$E$}; 85 \node[dot](r4) at (7.5,0.75) [] {$B$}; 86 \draw (r3) -- (r0) -- (r4) -- (r2) -- (r0) -- (r1) -- (r3) -- (r2) -- 87 (r1); 88 \end{tikzpicture} 89 \end{figure} 90 91 \item Find two graphs with and two without having this property.(2 pts) 92 93 \end{enumerate} 94 95 \textbf{Solution 1.1:} The left graph has only vertices with an odd degree, 96 thus it cannot be draw without lifting the pencil. On the other hand the 97 right graph has exactly two vertices with odd degree, vertex $E$ and vertex 98 $D$ meaning it has an Eulerian path, e.g. 99 $E$-$A$-$B$-$C$-$A$-$D$-$C$-$E$-$D$. 100 \newline 101 102 \textbf{Solution 1.2:} 103 104 \begin{figure}[h!] \centering 105 \begin{tikzpicture}[ 106 dot/.style = {draw, circle, inner sep=0.06cm}, 107 no/.style = {}, 108 ] 109 \node[dot](l0) at (2,0) [] {}; 110 \node[dot](l1) at (2,-1) [] {}; 111 \node[dot](l2) at (1,0) [] {}; 112 \node[dot](l3) at (1,-1) [] {}; 113 \node[dot](l4) at (3,-1) [] {}; 114 \draw (l0) -- (l1) -- (l2) -- (l3) -- (l1); 115 \draw (l2) -- (l0) -- (l4) -- (l1); 116 117 \node[dot](r0) at (7,0) [] {}; 118 \node[dot](r1) at (7,-0.75) [] {}; 119 \node[dot](r2) at (7,-1.5) [] {}; 120 \node[dot](r3) at (9, -0.75) [] {}; 121 \draw (r0) -- (r3) -- (r2); 122 \draw (r1) -- (r3); 123 \draw[bend right, -] (r0) to node [auto] {} (r1); 124 \draw[bend right, -] (r1) to node [auto] {} (r2); 125 \draw[bend left, -] (r0) to node [auto] {} (r1); 126 \draw[bend left, -] (r1) to node [auto] {} (r2); 127 \end{tikzpicture} 128 \caption{Two graphs, that cannot be drawn without raising the pencil 129 (right graph Königsberg bridges)} 130 \end{figure} 131 132 \begin{figure}[h!] \centering 133 \begin{tikzpicture}[ 134 dot/.style = {draw, circle, inner sep=0.06cm}, 135 no/.style = {}, 136 ] 137 \node[dot](l0) at (2,-1) [] {}; 138 \node[dot](l1) at (1,-1) [] {}; 139 \node[dot](l2) at (0.75,0) [] {}; 140 \node[dot](l3) at (2.25,0) [] {}; 141 \node[dot](l4) at (1.5,0.6) [] {}; 142 \draw (l4) -- (l1) -- (l3) -- (l2) -- (l0) -- (l4); 143 144 \node[dot](r0) at (7,0) [] {}; 145 \node[dot](r1) at (8,-1) [] {}; 146 \node[dot](r2) at (8,0) [] {}; 147 \node[dot](r3) at (7,-1) [] {}; 148 \node[dot](r4) at (7.5,0.75) [] {}; 149 \node[dot](r5) at (7.5,-1.75) [] {}; 150 \draw (r3) -- (r0) -- (r4) -- (r2) -- (r0) -- (r1) -- (r3) -- (r2) -- 151 (r1); 152 \draw (r5) -- (r1); 153 \draw (r5) -- (r3); 154 \end{tikzpicture} 155 \caption {Two graphs, that can be drawn without raising the pencil} 156 \end{figure} 157 \textbf{Exercise 2:} \textit{Extended Königsberg Problem} 158 \begin{enumerate} 159 \item A Baron living in the blue castle wants to start at his place and 160 end up in the yellow bar on the island in the middle by walking all 161 bridges once before.Where should he build the 8th bridge without 162 enabling the Baroness in the red castle doing the same starting from 163 her place?Find one path.(2 pts) 164 \item The Baroness, on discovering this deception, comes up with her own 165 plan to build a 9th bridge. It should enable her to walk from her 166 castle to the bar using all bridges once, but it should make it now 167 impossible for the blue Baron to do the same thing from his castle. 168 Where should the 9th bridge go? Find one path.(2 pts) 169 \item The mayor now decides to scupper their plans and builds a 170 10th bridge allowing all citizens starting from either side ending up 171 in the bar by walking all the bridges. Where should it go?(1 pt) 172 \end{enumerate} 173 \textbf{Solution 2.1:} 174 The following is a graph of the Königsberg bridges: 175 \begin{figure}[H] \centering 176 \begin{tikzpicture}[ 177 dot/.style = {draw, circle, inner sep=0.06cm}, 178 no/.style = {}, 179 ] 180 \node[dot, fill=red](r0) at (7,0) [] {$A$}; 181 \node[dot, fill=yellow](r1) at (7,-0.75) [] {$B$}; 182 \node[dot, fill=blue](r2) at (7,-1.5) [] {$C$}; 183 \node[dot](r3) at (9, -0.75) [] {$D$}; 184 185 \draw[-, thick] (r0) to node [auto] {} (r3); 186 \draw[-, thick] (r3) to node [auto] {} (r2); 187 \draw[-,thick] (r1) to node [auto] {} (r3); 188 \draw[bend right, -, thick] (r0) to node [auto] {} (r1); 189 \draw[bend right, -, thick] (r1) to node [auto] {} (r2); 190 \draw[bend left, -, thick] (r0) to node [auto] {} (r1); 191 \draw[bend left, -, thick] (r1) to node [auto] {} (r2); 192 \end{tikzpicture} 193 \caption{Königsberg bridges in a Graph} 194 \end{figure} 195 According to the theorems of graph theory all of the vertices have odd 196 degree, thus no Eulerian path exits. By adding another edge connecting 197 vertices $A$ and $D$, we would be left with two vertices having odd degree, 198 $B$ and $C$. By the theorems of graph theory there exists and Eulerian path. 199 The path has to start at a vertex of odd degree and end at a vertex of odd 200 degree, leaving us with the choice to start at $C$ and end up at $B$ which is 201 exactly what the Baron wants. The path is the following 202 $C$-$B$-$C$-$D$-$A$-$B$-$A$-$D$-$B$ with an according graph bellow. 203 \begin{figure}[H] \centering 204 \begin{tikzpicture}[ 205 dot/.style = {draw, circle, inner sep=0.06cm}, 206 no/.style = {}, 207 ->-/.style={decoration={ 208 markings, mark=at position .5 with {\arrow[scale=2]{>}}},postaction={decorate}} 209 ] 210 \node[dot, fill=red](a) at (7,0) [] {$A$}; 211 \node[dot, fill=yellow](b) at (7,-1.5) [] {$B$}; 212 \node[dot, fill=blue](c) at (7,-3) [] {$C$}; 213 \node[dot](d) at (11, -1.5) [] {$D$}; 214 215 \draw[->-, bend left, thick] (c) to node [auto] {1} (b); 216 \draw[->-, thick, bend left] (b) to node [auto] {2} (c); 217 \draw[->-,thick] (c) to node [auto] {3} (d); 218 \draw[->-, thick] (d) to node [auto] {4} (a); 219 \draw[->-,bend left, thick] (a) to node [auto] {5} (b); 220 \draw[->-,bend left, thick] (b) to node [auto] {6} (a); 221 \draw[->-,bend left, thick] (a) to node [auto] {7} (d); 222 \draw[->-, thick] (d) to node [auto] {8} (b); 223 \end{tikzpicture} 224 \caption{Solution to Exercise 2.1} 225 \end{figure} 226 \textbf{Solution 2.2:} For the baroness in $A$ to walk all the bridges exactly 227 once and end up at the bar in $B$, the vertices $A$ and $B$ need to have odd 228 degree while $D$ and $C$ have to have even degree. This is easily done by 229 connecting $A$ and $C$ with a bridge, with the path 230 $A$-$B$-$A$-$D$-$A$-$C$-$B$-$C$-$D$-$B$. The following graph represents this. 231 232 \begin{figure}[H] \centering 233 \begin{tikzpicture}[ 234 dot/.style = {draw, circle, inner sep=0.06cm}, 235 no/.style = {}, 236 ->-/.style={decoration={ 237 markings, mark=at position .5 with {\arrow[scale=2]{>}}},postaction={decorate}} 238 ] 239 \node[dot, fill=red](a) at (7,0) [] {$A$}; 240 \node[dot, fill=yellow](b) at (7,-1.5) [] {$B$}; 241 \node[dot, fill=blue](c) at (7,-3) [] {$C$}; 242 \node[dot](d) at (11, -1.5) [] {$D$}; 243 244 \draw[->-, bend left, thick] (a) to node [auto] {1} (b); 245 \draw[->-, bend left, thick] (b) to node [auto] {2} (a); 246 \draw[->-, bend left, thick] (a) to node [auto] {3} (d); 247 \draw[->-, thick] (d) to node [auto] {4} (a); 248 \draw[->- ,bend right=90, thick] (a) to node [auto] {5} (c); 249 \draw[->-, bend left,thick] (c) to node [auto] {6} (b); 250 \draw[->-, bend left, thick] (b) to node [auto] {7} (c); 251 \draw[->-, thick] (c) to node [auto] {8} (d); 252 \draw[->-, thick] (d) to node [auto] {9} (b); 253 254 \end{tikzpicture} 255 \caption{Solution to Exercise 2.2} 256 \end{figure} 257 \textbf{Solution 2.3:} For everyone to start at the tavern $B$ and end up at 258 $B$ all of the vertices have to have even degree, meaning we have to add a 259 bridge such that every section of the city has an even number of bridges. 260 Vertices $A$ and $B$ have and odd number of edges, if we add another edge 261 between them the graph has an Eulerian path. 262 263 \begin{figure}[H] \centering 264 \begin{tikzpicture}[ 265 dot/.style = {draw, circle, inner sep=0.06cm}, 266 no/.style = {}, 267 ->-/.style={decoration={ 268 markings, mark=at position .5 with {\arrow[scale=2]{>}}},postaction={decorate}} 269 ] 270 \node[dot, fill=red](a) at (7,0) [] {$A$}; 271 \node[dot, fill=yellow](b) at (7,-1.5) [] {$B$}; 272 \node[dot, fill=blue](c) at (7,-3) [] {$C$}; 273 \node[dot](d) at (11, -1.5) [] {$D$}; 274 275 \draw[-, bend left, thick] (a) to node [auto] {} (b); 276 \draw[-, bend left, thick] (b) to node [auto] {} (a); 277 \draw[-, bend left, thick] (a) to node [auto] {} (d); 278 \draw[-, thick] (d) to node [auto] {} (a); 279 \draw[- ,bend right=90, thick] (a) to node [auto] {} (c); 280 \draw[-, bend left,thick] (c) to node [auto] {} (b); 281 \draw[-, bend left, thick] (b) to node [auto] {} (c); 282 \draw[-, thick] (c) to node [auto] {} (d); 283 \draw[-, thick] (d) to node [auto] {} (b); 284 \draw[-, ultra thick] (b) to node [auto] {} (a); 285 286 \end{tikzpicture} 287 \caption{Solution to Exercise 2.3} 288 \end{figure} 289 \textbf{Exercise 3:} Find examples in nature, society or from your daily 290 experience for an undirected network, a directed network and a network with 291 edge weights.(3 pts) 292 \newline 293 294 \textbf{Solution 3:} An example for an undirected network is a social 295 network. Just like Facebook, the vertices are people and the edges are friend connections. 296 \newline 297 298 An example for a directed network is the World Wide Web, where the 299 vertices are the websites and edges are hyperlinks which are directed to a 300 website. 301 \newline 302 303 An example for a network with edge weights would be a graph representing 304 coin flips ($p=\frac{1}{2}$) or a dice throws ($p=\frac{1}{6}$). 305 306 \textbf{Exercise 4:} Walk through the notebook tutorial\_1 and solve the 307 embedded exercises (3x4pts). 308 \newline 309 310 \textbf{Solution 4:} 311 Code can be pulled from my git instance \cite{code}, a copy is also shown 312 below and handed in in moodle. 313 \begin{minted}{python} 314 # EX 1: 315 get_leaves = lambda G: [node for node, degree in G.degree() if degree == 1] 316 # EX 2: 317 def max_degree(G): 318 m = max(G.degree(), key = lambda x: x[1])[1] 319 return [node for node, degree in G.degree() if degree == m] 320 # EX 3: 321 def mutual_friends(G, node0, node1): 322 return list(set(G.neighbors(node0)) & set(G.neighbors(node1))) 323 \end{minted} 324 325 \nocite{spazieren} 326 \printbibliography 327 \end{document}