\documentclass[13pt]{beamer}
\usepackage[polutonikogreek,british]{babel}
\usepackage{fontspec}
\usefonttheme{serif}
\usetheme{Berlin}
\usecolortheme{rose}
\setmainfont{Times New Roman}
\title{Μέγιστες ροές και Tαιριάσματα: Εξερεύνηση της συσχέτισης
μεταξύ τους.}
\author{Μαρία Ξανθίππη Ψαροπά}
\institute{Τμήμα Μαθηματικών, Πανεπιστήμιο Ιωαννίνων}
\date{\today}
\begin{document}
\frame{\titlepage}
\begin{frame}
	\frametitle{Περιεχόμενα}
	\tableofcontents
\end{frame}
\section{Εισαγωγή}
\begin{frame}
	\transboxin
	\frametitle{Εισαγωγή}
	\begin{itemize}
	\item Στην επιστήμη της πληροφορικής, οι \color{blue}μέγιστες ροές \color{black} και τα \color{blue} ταιριάσματα \color{black}
	είναι δύο βασικά προβλήματα της Θεωρίας Γραφημάτων με πολλές θεωρητικές και πρακτικές εφαρμογές.
	\pause
	\item Αν και εκ πρώτης όψεως φαίνονται διαφορετικά προβλήματα, υπάρχει μια θεμελειώδης συσχέτιση μεταξύ τους η οποία θα αναλυθεί σε αυτή την παρουσίαση.
	\end{itemize}
\end{frame}

\subsection{Χρήσιμοι ορισμοί}
\begin{frame}
	\frametitle{Τι είναι οι Μέγιστες Ροές και τι τα Ταιριάσματα;}
	\begin{block}{Ορισμός - Μέγιστες Ροές}
	 Το πρόβλημα της μέγιστης ροής αφορά ένα κατευθυνόμενο γράφημα όπου
	 κάθε ακμή έχει μία χωρητικότητα. Σε αυτή, θέλουμε να υπολογίσουμε
	 την μέγιστη ροή που μπορεί να περάσει από μία πηγή (source) προς 
	 ένα τερματισμό (sink) χωρίς να παραβιάζονται οι περιορισμοί χωρητικότητας. 
	\end{block}
	\pause
	\begin{block}{Ορισμός - Ταίριασμα}
	 Σε ένα γράφημα $G=(V,E)$, το ταίριασμα Μ είναι
	 ένα υποσύνολο όλων των ακμών έτσι ώστε καμία κορυφή $u \in V$ να μην
	 χρησιμοποιείται από περισσότερες από μια ακμές του Μ. 
	\end{block}	
\end{frame}

\begin{frame}
	\frametitle{Επιπλέον χρήσιμες έννοιες}
	\begin{block}{Ορισμοί}
	\begin{itemize}
		\item \textbf{Μέγεθος Ταιριάσματος:} Ο αριθμός των ακμών που περιέχει το ταίριασμα: |M|.
		\pause
		\item \textbf{Μέγιστο Ταίριασμα:} Αυτό του οποίου το μέγεθος |M| είναι το μέγιστο.
		\pause
		\item \textbf{Μέγεθος Ταιριάσματος:} Ο αριθμός των ακμών που περιέχει το ταίριασμα: |M|.
		\pause
		\item \textbf{Διμερές Γράφημα:} Γράφημα $G=(A,B,E)$ στο οποίο το σύνολο των κορυφών $u$ χωρίζεται
	σε 2 ξεχωριστά σύνολα Α και Β και όλες οι ακμές Ε συνδέουν κορυφή 
	του Α με κορυφές του Β \textbf{μόνο}.
	\end{itemize}
	\end{block}
\end{frame}

\section{Πρόβλημα υπό εξέταση}
\subsection{Θεωρητική κατεύθυνση}
\begin{frame}
	\transglitter
	\frametitle{Πώς σχετίζονται οι έννοιες μέσω θεωρίας;}
	Οι έννοιες της μέγιστης ροής και του ταιριάσματος συμπίπτουν και 
	έχει ιδιαίτερο ενδιαφέρον η μελέτη τους, όταν εξετάζουμε διμερή γραφήματα (bipartite graphs).
	Πιο συγκεκριμένα, υπάρχει ένα θεώρημα που αναδεικνύει την συσχέτισή τους.
	\pause
	\begin{block}{Θεώρημα}
	\textit{Κάθε πρόβλημα μέγιστου ταιριάσματος σε διμερές γράφημα μπορεί να 
	μετατραπεί σε ισοδύναμο πρόβλημα μέγιστης ροής σε κατευθυνόμενο γράφημα,
	έτσι ώστε το μέγεθος της μέγιστης ροής να ισούται με το μέγεθος του μέγιστου ταιριάσματος.}
	\end{block}
\end{frame}

\subsection{Πρακτική κατεύθυνση}
\subsubsection{Πρόβλημα}
\begin{frame}
	\frametitle{Πρακτικό παράδειγμα}
	Τώρα θα μελετήσουμε την αντιστοίχιση μεταξύ του δικτύου $N$ και του πλήρους διμερούς γραφήματος $K_{3,3}$ μέσω του παρακάτω πίνακα: \\
	\pause
	\resizebox{\textwidth}{!}{
	\begin{tabular}{ccc}
		\textbf{Διμερές γράφημα } $\mathbf{K_{3,3}}$ & 
		\textbf{Δίκτυο ροής Ν=(Η,c,s,t)} &
		\textbf{Σχόλιο}\\
		\hline
		Κορυφές $A=\{a_1,a_2,a_3\}$ &
		$a_i \in V_H$ &
		Μία πλευρά του διμερούς γραφήματος \\
		Κορυφές $B=\{b_1,b_2,b_3\}$ &
		$b_j \in V_H$ &
		Η άλλη πλευρά του διμερούς γραφήματος \\
		Ακμές $(a_i,b_j) \in E$ &
		$(a_i,b_j) \in E_H$ &
		Υποψήφιες ακμές ταιριάσματος \\
		--- & 
		$s$ και $t$ &
		Πηγή και προορισμός \\
		--- & 
		$(s,a_i)$ &
		Ροή από πηγή προς Α \\
		--- &
		$(b_j,t)$ &
		Ροή από Β προς προορισμό \\
		Δεν ορίζεται χωρητικότητα &
		$c(e)=1$ &
		Μοντελοποιεί μοναδικότητα ταιριάσματος \\
		Μέγιστο ταίριασμα &
		Μέγιστη ροή απο s προς t & 
		Κάθε μονάδα ροής = 1 αντιστοίχιση 		
	\end{tabular} 
	}
\end{frame}

\subsubsection{Οπτικοποίηση}
\begin{frame}
	\frametitle{Οπτικοποίηση $K_{3,3}$ σε δίκτυο ροής}
	Αφού αναλύσαμε την συσχέτιση των εννοιών μέσω συγκεκριμένου παραδείγματος,
	παρακάτω παραθέτεται και η οπτικοποίηση του διμερούς γραφήματος $K_{3,3}$
	ως μέγιστο δίκτυο ροής για περαίτερω κατανόηση της συσχέτισής τους. 
	
	\includegraphics[height=4.5cm]{K3,3.png}	
\end{frame}
\end{document}
