13_tetel.tex

\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{polyglossia}
\usepackage{listings}
\usepackage{tcolorbox}
\usepackage{etoolbox}
\usepackage{setspace}
\usepackage{framed}
\usepackage[a4paper,margin=2cm,footskip=.5cm]{geometry}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Rn}[1]{$\mathbb{R}^{#1}$}
\newcommand{\Und}[1]{\underline{#1}}
\definecolor{shadecolor}{gray}{0.9}
%opening
\title{Bevezetés a Számításelméletbe 2.\\{\large 13. tétel}}
\author{Hegyi Zsolt}
\begin{document}
\maketitle
\begin{framed}
EGÉSZÉRTÉKŰSÉGI LEMMA Lemma: Ha (G,s,t,c) hálózatban minden e él c(e) kapacitása egész szám, akkor létezik olyan f maximális folyam, hogy f a G gráf minden élén egész értéket vesz fel. Az ilyen folyamot \textbf{egészfolyamnak} nevezzük.
\end{framed}
\begin{leftbar}
BIZONYÍTÁS: Az állítás nyilvánvaló, hiszen a kiindulási, azonosan 0 folyam rendelkezik a kívánt tulajdonsággal, majd az algoritmus során minden lépésben a folyamértékek minden élen csak egész számmal változhattak.
\end{leftbar}
\begin{framed}
A FOLYAMPROBLÉMA ÁLTALÁNOSÍTÁSAI: T.f.h. a hálózatban több termelő, $s_1, s_2,...,s_k$ és több fogyasztó, $t_1, t_2,..t_k$ van. A feladat az összes termelőtől az összes fogyasztóig eljutó folyam maximalizálása. Vegyünk fel két s', t' pontot, és kössük össze s'-t az összes termelővel, t'-t pedig az összes fogyasztóval, az élek kapacitása ezek között pedig legyen $\infty$.
\\
Ekkor az s' és a t'-t vesszük termelőnek és fogyasztónak, innen triviális a megoldás.
\\
\\
Ha nem csak élekhez, hanem pontokhoz is rendelhetünk c(v) kapacitásokat és megköveteljük, hogy minden v-re
$\sum_{u,v\in E}^{} f(u,v) \leq c(v)$
, akkor minden v pontot helyettesítsünk két ponttal, v' és v''-vel. Ha egy él az u pontból a v pontba mutatott, akkor helyette vegyünk fel egy u''-ból v'-be mutató élet a hozzá tartozó kapacitással együtt, ezen kívül minden v'-ből mutasson c(v) kapacitású él v''-be.
\\
\\
Amennyiben irányítatlan élek is szerepelnek a hálózatban, akkor cseréljük le őket két, átellenes irányított éllel, mindkettő kapacitása legyen az irányítatlan él kapacitásával egyenlő.
\end{framed}
\begin{framed}
DISZJUNKT FOLYAMOK: Ha a kapacitások egész számok, akkor van olyan maximális folyam, melyben minden élen a folyam értéke egész. Így nyilvánvaló, hogy ha a kapacitás minden élen 1 vagy 0, akkor van olyan maximális folyam, melynek minden élén a folyam értéke vagy 1 vagy 0. Ha elhagyjuk ez utóbbi éleket, akkor diszjunkt utakat kapunk s-ből t-be. Ezeknek a számát úgy is meg tudjuk kapni, hogy veszünk egy minimális vágást és az élhalmazának az elemszámával lesz egyenlő a diszjunkt utak száma.
\end{framed}
\begin{shaded}
DISZJUNKT UTAK Definíció: Vegyük (G,s,t,c) folyamot, ezen belül veszünk utakat. \textbf{Páronként éldiszjunkt útnak} nevezünk utakat, ha páronként nincsen közös élük. \textbf{Belsőleg pontdiszjunkt utaknak} nevezünk utakat, ha páronként nincs közös pontjuk.
\end{shaded}
Diszjukt folyam algoritmus: Vegyünk tetszőleges hálózatot, és futtassuk le a fentebb leírt módszert rajta úgy, hogy vegyünk egy minimális vágást a hálózatban. A visszaélek (tehát amik a t-t tartalmazó halmazból az s-et tartalmazó halmazba mennek) legyenek 0 értékűek, egyébként pedig 1 értékűek az élek. Ebben már meg lehet keresni a diszjunkt utakat.
\end{document}