diff options
Diffstat (limited to 'graf/n1.lyx')
| -rw-r--r-- | graf/n1.lyx | 107 |
1 files changed, 76 insertions, 31 deletions
diff --git a/graf/n1.lyx b/graf/n1.lyx index ea6dcba..c547ff0 100644 --- a/graf/n1.lyx +++ b/graf/n1.lyx @@ -1102,24 +1102,6 @@ Sea \end_inset . -\begin_inset Note Comment -status open - -\begin_layout Plain Layout -\begin_inset Formula -\begin{align*} -\sum_{i=1}^{k}o(i) & =\sum_{i=1}^{k}|\{j\in N(i):j\leq k\}|+\sum_{i=1}^{k}|\{j\in N(i):j>k\}|\\ - & =\sum_{i=1}^{k}o_{G_{\{1,\dots,k\}}}|N(i)|+\sum_{j=k+1}^{n}|\{i\in N(j):i\leq k\}|\leq2\binom{k}{2}+\sum_{j=k+1}^{n}\min\{k,d_{j}\}. -\end{align*} - -\end_inset - - -\end_layout - -\end_inset - - \end_layout \begin_layout Itemize @@ -1892,15 +1874,23 @@ circuito \series bold camino \series default - es un paseo en que -\begin_inset Formula $\forall i,j\in\{0,\dots,k\},(i\neq j\land\{i,j\}\neq\{0,k\}\implies v_{i}\neq v_{j})$ + o +\series bold +cadena +\series default + es un paseo en que +\begin_inset Formula +\[ +\forall i,j\in\{0,\dots,k\},(i\neq j\land\{i,j\}\neq\{0,k\}\implies v_{i}\neq v_{j}), +\] + \end_inset -, y un + y un \series bold ciclo \series default - es un camino cerrado. + es un camino cerrado de longitud al menos 3. \end_layout \begin_layout Standard @@ -1960,14 +1950,55 @@ Sea \end_deeper \begin_layout Enumerate -Todo paseo cerrado de longitud impar contiene un ciclo no trivial. +Todo paseo cerrado de longitud impar contiene un ciclo. \end_layout \begin_deeper \begin_layout Standard -Al tener longitud impar es no trivial y por tanto contiene un camino entre - los vértices inicial y final, que son el mismo y por tanto el camino es - un ciclo. +Al tener longitud impar es no trivial, y como no tiene longitud 1 por ser + cerrado, su longitud es al menos 3. + Sea +\begin_inset Formula $v_{0}v_{1}\cdots v_{k-1}v_{0}$ +\end_inset + + su lista de vértices, si fuera +\begin_inset Formula $\{v_{0},\dots,v_{k-1}\}=\{v_{0},v_{1}\}$ +\end_inset + + el ciclo sería de la forma +\begin_inset Formula $v_{0}v_{1}\cdots v_{1}v_{0}$ +\end_inset + + y su longitud sería par, luego existe +\begin_inset Formula $i\geq2$ +\end_inset + + con +\begin_inset Formula $v_{i}\neq v_{0},v_{1}$ +\end_inset + +, que podemos tomar mínimo. + Entonces los paseos +\begin_inset Formula $v_{1}\cdots v_{i}$ +\end_inset + + y +\begin_inset Formula $v_{i}\cdots v_{k-1}v_{0}$ +\end_inset + + contienen caminos no triviales respectivos +\begin_inset Formula $P$ +\end_inset + + y +\begin_inset Formula $Q$ +\end_inset + + entre los mismos nodos, de modo que +\begin_inset Formula $(v_{0},v_{1})PQ$ +\end_inset + + es un ciclo. \end_layout \end_deeper @@ -1993,10 +2024,17 @@ matriz de adyacencia \end_inset dada por -\begin_inset Formula $a_{ij}:=\chi_{E}(i,j)$ +\begin_inset Formula +\[ +a_{ij}:=\left\{ \begin{aligned}1, & (i,j)\in E;\\ +0, & \text{en otro caso}. +\end{aligned} +\right. +\] + \end_inset -.Como +Como \series bold teorema \series default @@ -2099,11 +2137,18 @@ matriz de incidencia \begin_inset Formula $(b_{ij})_{ij}\in{\cal M}_{n\times m}(\mathbb{Z})$ \end_inset - dada por -\begin_inset Formula $b_{ij}:=\chi_{\{(i,j):i\in e_{j}\}}(i,j)$ + dada por +\begin_inset Formula +\[ +b_{ij}:=\left\{ \begin{aligned}1, & i\in e_{j};\\ +0, & \text{en otro caso}. +\end{aligned} +\right. +\] + \end_inset -. + \end_layout \end_body |
