next up previous contents
Next: Literatur Up: Matchings in Graphen Previous: Grundlagen

Matchings maximaler Kardinalität in bipartiten Graphen

Gegeben: G=(V1,V2,E) bipartiter Graph.

Simultane BFS zur Bestimmung der Länge eines kürzesten augmentierten Pfades.

$\textstyle\parbox{100mm}{ \ttfamily \begin{tabbing} \hspace{5mm} \= \hspace{5m... ...d} \\ $R:=$\space Menge der freien Knoten in R; \\ $\llcorner$\end{tabbing} }$
\begin{picture} (30,35) \multiput(5,15)(0,5){5}{\circle*{1}} \multiput(25,15)(... ...2,1){20}} \put(5,30){\line(2,-1){20}} \put(5,35){\line(2,-1){20}}\end{picture}


\begin{picture} (100,60) \color {red} \multiput(25,47.5)(-2.5,0){8}{\bezier... ...}}} \put(65,20){\oval(5,15)} \put(60,6.5){\makebox(5,5)[tr]{$L$}}\end{picture}


Abbas-Bardia Kabiri-Jarghouyeh
3/3/1999