You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 

106 lines
3.6 KiB

\documentclass{article}
\usepackage{bstr}
\fancyhead[L]{MA4701 - Optimización Combinatorial}
\fancyhead[R]{Primavera 2013}
\fancyfoot[C]{}
\title{Auxiliar 4}
\date{}
\begin{document}
\maketitle
\thispagestyle{fancy}
\subsection*{P1}
Veremos que durante todo el algoritmo el conjunto $S$ es independiente. Por
inducción en $S$:
\begin{itemize}
\item $S=\varnothing$ $\checkmark$
\item Si $S$ es independiente, entonces $r(S) = |S|$. Como
$e_i\not\in\spn(S)$, entonces $r(S+e_i)>r(S)=|S|$. Luego, $r(S+e_i) =
r(S)+1 = |S|+1$, por lo que $S+e_i$ es independiente.
\end{itemize}
Como $S+e_i$ es independiente, $r(S+e_i) = |S|+1 = r(S) + 1 > r(S) =
|S|$. Luego, $e_i\not\in\spn(S)$.
En conclusión, verificar si $e_i$ está en $\spn(S)$ es equivalente a verificar
independencia.
\subsection*{P2}
\subsubsection*{a)}
Tenemos que $(M/X)^* = M^*\setminus X$. Luego,
\[(M^*/X) = (M^{**}\setminus X) \Rightarrow M^*/X = (M\setminus X) ^*\]
\subsubsection*{b)}
Tenemos que $r_{M^*}(U) = |U| + r_M(E\setminus U) - r_M(E)$. Luego,
\begin{align*}
\spn^*(E-X) = E &\iff r_{M^*}(E-X) = r_{M^*}(E) \\
&\iff |E| - |X| + r_M(X) - r_M(E) = |E| - r_M(E) \\
&\iff r_M(X) = |X| \iff X\in\I
\end{align*}
\subsubsection*{c)}
\textbf{Pdq} $X\in\I$ y $E-X\in\I^*$ $\Rightarrow$ $X$ base y $E-X$ cobase.
Por un lado, $r_M(E) + r_{M^*}(E) = |E|$. Además,
\begin{align*}
X\in\I &\Rightarrow r_M(E) \geq |X| \\
E-X\in\I^* &\Rightarrow r_{M^*}(E) \geq |E| - |X|
\end{align*}
Si $X$ no es base, entonces $r_M(E)>|X|$. Además, si $X$ no es base, $E-X$ no es
cobase, por lo que $r_{M^*}(E) > |E| - |X|$. Sumando,
\[r_M(E) + r_{M^*}(E) > |E|\ \contra\]
\subsection*{P3}
\subsubsection*{a)}
Recordemos que $X\in\I^* \iff E\setminus X$ es conexo. Entonces, tenemos
\begin{align*}
\text{$F\not\in\I^*$ minimal} &\iff \text{$E\setminus F$ no es conexo, pero
$\forall e\in E, E\setminus F + e$ es conexo} \\
& \iff \text{$\cc(E\setminus F) = 2$, pero $\forall e\in F, E\setminus
F+e$ es conexo}
\end{align*}
\textbf{Pdq} $\text{$F$ cocircuito } \iff \exists S\subseteq V, F = \delta(S),
\delta(S)$ minimal.
\begin{itemize}
\item[$\Rightarrow$] Sea $S$ una de las componentes conexas de $E\setminus
F$. Entonces, $F = \delta(S)$. Veamos que $F$ es minimal para el conjunto
$\{\delta(X) | \varnothing\subsetneq X\subsetneq V\}$. Si no lo fuera,
existiría $S'$ tal que $\delta(S')\subsetneq F \Rightarrow
G\setminus\delta(S')$ no es conexo $\contra$.
\item[$\Leftarrow$] Sea $S$ tal que $\delta(S)$ es minimal. Luego,
$G\setminus\delta(S)$ no es conexo. Entonces, $\delta(S)\not\in\I^*$. Si no es
cocircuito, existe $F'\subsetneq \delta(S)$ tal que $G\setminus F'$ no es
conexo. Más aún, $\cc(G\setminus F')=2$. Sea $S'$ una de las componentes
conexas de $G\setminus F'$. Tenemos que
$F'=\delta(S')\subsetneq\delta(S)\contra$.
\end{itemize}
\subsubsection*{b)} Por contradicción, sea $C\cap C^*\{e\}$. Entonces,
$C^*-e\in\I^*$. Luego, existe una cobase $B_1^*$ tal que $C^*-e\subseteq B_1^*$.
Por lo tanto, $E-C^*+e\supseteq (B_1^*)^c = B_1$ base.
Además, $C-e \subseteq E - C^* + e$. Extendamos $C-e$ a una base $B_2$.
Ahora, encontraremos una base $B$ tal que $C-e \subseteq B\subseteq E-C^*+e$.
Tomemos $B_2$. Si existe $x\in B_2$ tal que $x\not\in E-C^*+e$, entonces $x\in
C^*-e$. Luego, existe $y\in B_1$ tal que $B_2-x+y$ es base. Tenemos que $y\in
E-C^*+e$. Repitiendo el procedimiento, llegamos a $B$.
Finalmente, tenemos que si $e\in B$, entonces $C\subseteq B$, por lo que $C\in\I$ $\contra$.
Luego, $e\not\in B$. Entonces $C-e\subseteq B\subseteq E-C^*$. Por lo tanto,
$B^c\supseteq C^* \Rightarrow C^*\in\I^*$ $\contra$.
\end{document}