2

I want to make all my captions the same i.e normal font and unitalicized just like the first diagram. I don't know why they are different whilst using pretty much the same code.

\begin{center}
    \includegraphics[scale= 0.7]{diagram} \\
    \caption{Figure 2. The Königsberg problem graphed}
\end{center}

Which outputs: This Diagram

\begin{center}
    \includegraphics[scale= 0.8]{graph} \\
    \caption{Figure 3. Representation of the graph V}
\end{center}

Which outputs: This

%-----------------------------------------------------------------------------------------
% Final year project report/dissertation template
%-----------------------------------------------------------------------------------------
% R F L Evans (2019)
% Licensed under the public domain (CC0) licence:
%
% The person who associated a work with this deed has dedicated the work to the public 
% domain by waiving all of his or her rights to the work worldwide under copyright law, 
% including all related and neighboring rights, to the extent allowed by law.
%
% You can copy, modify, distribute and perform the work, even for commercial purposes,
%  all without asking permission.
%----------------------------------------------------------------------------------------
%

%-----------------------------------------------------------------------------------------
% Determines the type of document and font size
%-----------------------------------------------------------------------------------------
\documentclass[12pt,a4paper]{article}
\newtheorem{defn}{Definition}[section]
\newtheorem{thm}{Theorem}[section]
\newtheorem{ex}{Example}[section]
\newtheorem{prop}{Proposition}[section]


%-----------------------------------------------------------------------------------------
% Font control
%-----------------------------------------------------------------------------------------
\usepackage{mathptmx} % Times Roman Font
%-----------------------------------------------------------------------------------------
%\usepackage{helvet} % Arial/Helvetica font
%\renewcommand{\familydefault}{\sfdefault} % Makes serif text all Helvetica
%-----------------------------------------------------------------------------------------
% Set up the page margins
%-----------------------------------------------------------------------------------------
\usepackage[left=3.5cm, right=3cm, top=4cm]{geometry} % Sets the page margins
%-----------------------------------------------------------------------------------------
% Allow graphics
%-----------------------------------------------------------------------------------------
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{}
\pagenumbering{arabic}

%-----------------------------------------------------------------------------------------
% Add your report title here
%-----------------------------------------------------------------------------------------
\title{\huge{\textbf{Graph Theory}}}

% Add your name here
\author{
        Adeel Ali \\
                Department of Mathematics\\
        University of York\\
        }
\date{\today}



%-----------------------------------------------------------------------------------------
% The start of the document
%-----------------------------------------------------------------------------------------
\begin{document}

%-----------------------------------------------------------------------------------------
% This adds the title page
%-----------------------------------------------------------------------------------------
\maketitle
\thispagestyle{empty}

 % moves to the next page

%-----------------------------------------------------------------------------------------
% This adds the abstract
%-----------------------------------------------------------------------------------------
\begin{abstract}
This project first introduces basic graph theory concepts and then applies the theory to shortest path problems finding solutions using algorithmic methods, in particular Djikstra’s and the A* algorithm. Following this, it uses Kruskal’s and Prim’s algorithm to find minimum spanning trees. It then attempts to show the limitation of using these methods. Finally, the project attempts to synthesise methods of solving the travelling salesman problem.\end{abstract}
\thispagestyle{empty}

%-----------------------------------------------------------------------------------------
% Move to a new page and set the page numbering from here
%-----------------------------------------------------------------------------------------
\clearpage

\tableofcontents

\clearpage % moves to the next page


\section{Introduction - What is Graph Theory?} % The start of a new section


Graph Theory is a topic within discrete mathematics which involves the study of vertices/nodes and their interrelation with edges. This area of mathematics has application in far ranging fields from economics to computer science. For instance economists model supply chains using flow networks and principles of graph theory, and computer scientists utilise graph theory concepts in organising data structures. Social media also networks use graph theory to represent friendship graphs which can be used to determine how people know each other. Due to Graph Theory having simple beginnings (see below) its prerequisites are minimal and so this subject is very accessible to an inquisitive mind.


\subsection{Motivation}
The history of graph theory goes back to one man, Leonhard Euler. Königsberg was a city in then Prussia now Russia, which contained the Pregel River and 7 bridges upon which you could cross. Carl Ehler, a mathematician who later became the mayor of a nearby town, grew obsessed with these islands and bridges. The problem he posited was: ‘Is it possible to find a path over every one of the 7 bridges without crossing any bridge twice?’ \\

\begin{center}
    \includegraphics[scale= 0.4]{Aerial} \\
    \caption{Figure 1. Aerial view of the Königsberg problem~\cite{maps}}
\end{center}

He asked Euler for help, however Euler was initially dismissive stating in a letter: [The solution] “bears little relationship to mathematics ... for the solution is based on reason alone, and its discovery does not depend on any mathematical principle.”~\cite{paper}

He did eventually become intrigued by the problem and it seemed there might be something mathematical. The answer he came up with had to do with a type of geometry that did not quite exist yet, what he called the Geometry of Position,
now known as Graph Theory.

Looking at Figure 1, we can see that there are 4 landmasses: Northern, Middle, Southern and Eastern. To simplify the problem we can draw a diagram. 

\begin{center}
    \includegraphics[scale= 0.7]{diagram} \\
    \caption{Figure 2. The Königsberg problem graphed}
\end{center}

Here, each of the black dots (A-D) represent one of the aforementioned landmasses, and each of the lines (e1-e7) represent a potential bridge crossing. 

Attempting some possibilities for ourselves:
\{e1, e3, e4, e5, e6, e7\} → We’re stuck since the other bridges incident to e7 have already been used.
Trying: \{e2, e4, e3, e1, e5, e6\} → We’re stuck since the other bridges incident to e6 have already been crossed.

There seems to be no solution - In fact, this is the case. We will see in the next section, after introducing some basic theory, how he proved it and thus sparked the beginning of graph theory. 



\section{Foundational Concepts}\label{methods}

In this chapter I will introduce some basic concepts that are integral to the field of Graph Theory.
\subsection{Graphs}



\begin{defn}
An (undirected) graph G is an ordered pair G=(V,E) where V is a (finite) set of elements and E is a set of 2-subsets of V.
\\
\textbf{Note:} V is known as the vertex set and E the edge set.
\end{defn}


The most common way to represent graphs is to draw them. Typically, each element of the vertex set V is mapped to a point on the plane and each element of the edge set E is mapped to the line inbetween the two corresponding verticies.

\begin{ex}
Draw the graph with $V= \{1,2,3,4,5\}$ and\\ $E=\{\{1,2\},\{2,3\},\{2,4\},\{3,5\},\{4,5\}\}$

\begin{center}
    \includegraphics[scale= 0.8]{graph} \\
    \caption{Figure 3. Representation of the graph V}
\end{center}



\end{ex}
\begin{defn}
Let V be a vertex in a graph G. The (open) neighbourhood of V in G is:\\

  \centering $N_G(v) = \{u | \{u,v\} \in E(G)\}\\$ 


\end{defn}


\begin{defn}
The degree of a vertex v $d_G(v)$ is the number of edges at V denoted $|E(V)|.$


\end{defn}

\begin{ex}
$N_G(1) = \{2,3,4\}$ therefore the degree of vertex 1 is $|\{2,3,4\}| = 3,\\$
$N_G(2) = \{1,4\}$ therefore the degree of vertex 2 is $|\{1,4\}| = 2.$


\begin{center}
    \includegraphics[scale= 0.5]{graph2} \\
    \caption{Figure 4.  ~\cite{maps}}
\end{center}


\end{ex}

Now that we have the prerequisites, we can also represent graphs using matrices. 

\begin{defn}

The adjacency Matrix is defined:\\

\centering

\( A_{i j}=\left\{\begin{array}{ll}1 & \text { if\ } ij \in E \\ 0 & \text 
{ otherwise }\end{array}\right. \)


\end{defn}



\begin{defn}

The incidence Matrix is defined:\\

 \centering
\( M_{i j}=\left\{\begin{array}{ll}1 &  \text{ if\ vertex\ i\ belongs\ to\ edge\ j\ } \\ 0 & \text {otherwise  }\end{array}\right. \)

    

    


\end{defn}





\begin{ex}
Given a Graph: 

\begin{center}
    \includegraphics[scale= 0.6]{graph3.png} \\
    \caption{Figure 1. Aerial view of the Königsberg problem~\cite{maps}}
\end{center}


The adjacency matrix is:\\



\begin{center}
    
    \begin{bmatrix}
0 & 1 & 1 & 0\\
1 & 0 & 1 & 1\\
1 & 1 & 0 & 1\\
0 & 1 & 1 & 0
\end{bmatrix}
    
    
    
\end{center}




\textbf{NOTE:} In the adjacency matrix the row sum = column sum which signify the degree of that vertex.\\


The incidence matrix is: \\

\begin{center}
    
    \begin{bmatrix}
1 & 0 & 0 & 1 & 0\\
0 & 0 & 1 & 1 & 1\\
1 & 1 & 0 & 0 & 1\\
0 & 1 & 1 & 0 & 0
\end{bmatrix}
    
    
\end{center}



\textbf{NOTE:} In the incidence matrix, the row sum also represent the degree of that corresponding vertex however the column sum is 2 and shows the 'ends' of edges. For ease of understanding, I have labelled the columns in alphabetical order.



\end{ex}

\subsubsection{Types of Edges}
Edges can be categorised into three types: 
\begin{enumerate}
    \item Undirected
    \item Directed
    \item Weighted
\end{enumerate}

\begin{center}
    \includegraphics[scale= 0.5]{Edgetype} \\
    \caption{Figure 3. Types of Edges~\cite{ebi}}
\end{center}
We interact with graphs on a daily basis, they are behind many of our technological advances.
For instance Google uses graphs in its algorithmic optimization of website searches. These graphs are directed since one can go from google to those websites via a link, yet the converse wouldn’t be true. 

Weighted graphs have applications whenever there is a measurable component such as distance, time, energy. For instance Google uses algorithms to find the quickest or shortest route, to get from one location to another. GPS, queuing systems and timetabling software all use weighted graphs to serve a function.


There are many different types of graphs, each with their own properties. For the purpose of conciseness, we will only look at a few here.

\subsubsection{Types of Graphs}
\begin{enumerate}
    \item A Simple Graph: 
     An undirected graph with no more than one edge between any 2 nodes and no loops (edges that begin and end at the same vertex)
\begin{center}
    \includegraphics[scale= 0.4]{simple.png} \\
    \caption{Figure 2. The simple graph}
\end{center}

    \item A Complete Graph:
    A graph in which every vertex is joined to every other vertex via an edge. It contains all possible edges.
    
\begin{center}
    \includegraphics[scale= 0.5]{complete.png} \\
    \caption{Figure 2. The complete graph}
\end{center}
    
    \item A Bipartite Graph:
    A graph in which the vertex set can be partitioned into two sets such that the edges only go between sets, not within them.
    
\begin{center}
    \includegraphics[scale= 0.3]{bipartite.png} \\
    \caption{Figure 2. The bipartite graph}
\end{center}
    
    \item A Regular Graph:
    A graph in which the degree of all vertices in the same. If a graph has vertices with degree X, then it is called a X-regular graph.
    
\begin{center}
    \includegraphics[scale= 0.4]{regular.png} \\
    \caption{Figure 2. The regular graph}
\end{center}
    
    \item A Cyclic Graph: A graph whose vertices can be arranged in a cyclic sequence, beginning and ending at the same vertex.
    
    
\begin{center}
    \includegraphics[scale= 0.4]{cyclic.png} \\
    \caption{Figure 2. The cyclic graph}
\end{center}
\end{enumerate}


\subsection{Paths and Cycles}

\begin{defn}
A Path P is a non-empty graph $P = (V,E)$ of the Form:
$V=\{V_1, V_2, ... , V_n\} \\ E=\{V_1V_2, … , V_{n-1}V_n\}$
Where all the vertices are distinct. 



\end{defn}

\begin{defn}

A Cycle is a non-empty graph whose vertices can be arranged in a  cyclical sequence $(V_{1}, ... ,V_n)$ such that the edge set $E = \{V_iV_{i+1} | i=1,...,n-1\} \bigcup \{V_1,V_n\}$



\end{defn}



\begin{ex}
Example here



\end{ex}


\begin{defn}

A graph is connected if for every pair of distinct verticies $u,v \in V$\\
there exists a path from u to v.

\end{defn}


\begin{thm}
The sum of the degrees is twice the number of edges. 
\begin{center}
    
    $\sum_{v \in V} \operatorname{deg} v=2|E|$
    
\end{center}

\textit{Proof.\\} 
let e $\in$ E(G) be any edge. Then e has 2 ends, say u and w.
When we sum the degrees of the vertices, edge e gets counted twice 
similarly, every edge gets counted twice. 
so the sum of the degrees are twice the number of edges as required.






\end{thm}



\begin{prop}

In any graph the number of vertices of odd degree is always even.

\textit{Proof.\\} 
Let $G = (V,E)$, Suppose $V = \{V_1, ... ,V_n\}$\\
Theorem 2.1 $\Rightarrow $  $deg(V_1) + ... + deg(V_n) = 2|E(G)|$\\
So by contradiction, there cannot be an odd number of odd degrees.


\end{prop}





\subsection{Trees}

\begin{defn}

A tree is a connected acyclic graph. 


\end{defn}



\section{Algorithms}
DIFFERENT ALGORITHMS AND WHY THEY ARE IMPORTANT


\subsection{Minimum Path}

\subsubsection{Djikstra's}
Finds a minimum-length path. \\

\noindent \textbf{STEP 1:} Set $ = \emptyset$ which will store the vertices of G for which a shortest path has been found    \\
\textbf{STEP 2:} Set $t(u) = 0$ and $t(v) = \infty $ $\forall v \in V(G), v \neq u$ and add u to s.   \\
\textbf{STEP 3:} Let w be the newest member of S:     \\
$\forall v \notin s, v \in N_G(w)$ set
t(v) = min\{t(v), t(w) + $\alpha(vw)$\} \\
\textbf{STEP 4:} Pick any $w \notin S$ with minimum t(w) and add w to S. \\
\textbf{STEP 5: }Repeat STEP 3 until every vertex is exhausted. \\

\subsubsection{A* Algorithm}

Comparison to A*

\begin{ex}




\end{ex}



\subsection{Minimum Spanning Tree}


\subsubsection{Kruskal's}
Finds a minimum spanning tree.\\

\noindent \textbf{STEP 1:} Sort all edges in increasing order of their edge weights.                       \\  
\textbf{STEP 2:} Pick the smallest edge.                    \\  
\textbf{STEP 3:} Check if the new edge creates a cycle or loop in a spanning tree. \\  
\textbf{STEP 4: }If it doesn’t form the cycle, then include that edge in MST. Otherwise, discard it.     \\
\textbf{STEP 5:} Repeat from step 2 until it includes $|V| - 1$ edges in MST. \\


\subsubsection{Prim's}


Comparison to Kruskal's



\begin{ex}




\end{ex}
\subsection{Search Algorithms}

The breadth first search - BFS - and depth first search - DFS - are search algorithms which, as their name suggests, traverse the entirety of a graph (in different ways) by which they can glean information on the structure of a graph.

\subsubsection{Breadth First Search}



\subsubsection{Depth First Search}







\section{The Travelling Salesman Problem}

The Travelling Salesman Problem - TSP for short - is at heart an optimisation problem by which a salesman must visit each of the N cities, without returning back to his starting position AND ensuring that he finishes his journey where he started. Cities are connected to each other via some method of transportation and each journey between the cities has an associated ‘cost’. This ‘cost’ is a representation of some factor that we would like to minimise i.e miles, time taken, ticket price. 

This class of problems has applications in many industries such as Engineering, Science, Supply Chains, Warehousing to name a few. When this type of problem gets large (a vast number of vertices and edges) it becomes very difficult to solve. According to computer scientists, this is an NP-hard problem. NP-hard problems are those which are hard to find the most optimal solution yet we can easily verify whether our solution is true or not.

\subsection{Method 1: Dynamic Programming}


\subsection{Method 2: Simulated Annealing}


\subsection{Method 3: The 2-opt}


\section{Conclusions}\label{conclusions}





\clearpage
\begin{thebibliography}{9}

\bibitem{maps} Google Maps (2021), Konigsberg Cathedral, 1:100. Available through: https://www.google.com/maps/@54.706411,20.5111463,16.92z [Accessed 03 December 2021].

\bibitem{paper} Alexanderson, Gerald. (2006). About the Cover: Euler and the Königsberg Bridges: A Historical View. Bulletin (New Series) of the American Mathematical Society. 

\bibitem{euler} Euler, Leonhard. (1741), "Solutio problematis ad geometriam situs pertinentis"  available through: https://scholarlycommons.pacific.edu/cgi/viewcontent.cgi?article=1052&context=euler-works [Accessed 18/04/21]

\bibitem{britannica} Carlson, S. C. (2020), Graph Theory. Encyclopedia Britannica. https://www.britannica.com/topic/graph-theory [Accessed 03 December 2021]

\bibitem{ebi} Ebi (2021). Graph theory: graph types and edge properties Available through: https://www.ebi.ac.uk/training/online/courses/network-analysis-of-protein-interaction-data-an-introduction/introduction-to-graph-theory/graph-theory-graph-types-and-edge-properties [Accessed 3 December 2021].

\bibitem{book} Diestel, R. (2005), Graph Theory (Graduate Texts in Mathematics), Springer

\bibitem{wiki} Wikipedia. (2022). Travelling salesman problem - Simple English Wikipedia, the free encyclopedia. [online] Available at: https://simple.wikipedia.org/wiki/Travelling\_salesman\_problem [Accessed 19 April 2022].

\bibitem{simp} Simplilearn. (2022). Kruskal's Algorithm. [online] Available at: https://www.simplilearn.com/tutorials/data-structure-tutorial/kruskal-algorithm [Accessed 19 April 2022].

\bibitem{alg} Needham, M. and Hodler, A., (2019). Graph Algorithms. 1st ed. O'Reilly.

\bibitem{med} Mallawaarachchi, V., (2022). 10 Graph Algorithms Visually Explained. [online] Medium. Available at: <https://towardsdatascience.com/10-graph-algorithms-visually-explained-e57faa1336f3> [Accessed 19 April 2022].

\end{thebibliography}


\end{document}

Click here to read the whole project: https://www.overleaf.com/read/gvbbjqrxbwzn

Thanks!

2
  • unrelated but you should not have \\ before the caption. May 7 at 17:59
  • Captions are only defined for certain environments (see \@captype). Note that figures use the figure counter and tables use the table counter. See also \captionof (caption package, possibly others). May 7 at 23:35

1 Answer 1

2

It's because it's inside \begin{ex} ... \end{ex}. Put it after \end{ex} You can see that other captions are ok.

Don't use \begin{center} ... \end{center}. Use \centering inside if needed. Don't put the numbers inside the caption: your numbers are repeated (how many figures 2 do you have?) and you can let LaTeX deal with them for you.

1
  • Ahhh. Thank you so much!
    – Esio Trot
    May 7 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.