15.6: Ejercicios
- Page ID
- 118258
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
Reconocer caminos y senderos.
En cada uno de los Ejercicios 1—4, se te da un paseo por una gráfica. Determinar si la caminata es un sendero, un sendero, o ninguno. Determinar también si la caminata es abierta o cerrada.
\(v_1, e_1, v_2, e_2, v_3, e_3, v_4, e_{12}, v_6, e_6, v_3 \text{.}\)
\(v_1, e_1, v_2, e_2, v_3, e_3, v_4, e_4, v_5, e_5, v_6, e_6, v_3, e_7, v_7, e_8, v_1 \text{.}\)
\(v_1, e_8, v_7, e_7, v_3, e_7, v_7, e_8, v_1 \text{.}\)
\(v_3, e_3, v_4, e_4, v_5, e_5, v_6, e_6, v_3 \text{.}\)
Considera la gráfica en la Figura\(\PageIndex{1}\).
- Determinar cuatro trayectorias diferentes de vértice\(1\) a vértice\(5\text{.}\)
- Determine cuatro senderos diferentes de vértice\(1\) a vértice,\(5\text{,}\) ninguno de los cuales son caminos.
- Determinar cuatro caminatas diferentes de vértice\(1\) a vértice,\(5\text{,}\) ninguno de los cuales son senderos.
Considera la gráfica en la Figura\(\PageIndex{2}\).
- Cuantos senderos diferentes hay de vértice\(1\) a vértice\(5\text{?}\)
- Cuantos caminos diferentes hay de vértice\(1\) a vértice\(5\text{?}\) (Pista: Ver Proposición 15.2.1.)
- Cuantos paseos diferentes hay de vértice\(1\) a vértice\(5\text{?}\)
Reconocer puentes.
En cada uno de los Ejercicios 7—10, identifica cada borde que es un puente.
La gráfica completa con\(n\) vértices.
Entre todas las gráficas posibles no conectadas con\(n\) vértices, deja\(H\) ser una con el número máximo de aristas. Demostrar que\(H\) tiene exactamente dos componentes conectados.
- Pista.
-
Argumentar por contradicción.
Supongamos que\(G\) es una gráfica conectada que contiene un camino cerrado que también es un sendero. Demostrar que es posible eliminar cualquier borde único de este camino y dejarse con un subgrafo conectado de Es\(G\text{.}\) decir, probar que ningún borde en este camino podría ser un puente.
Demostrar que una gráfica en la que cada borde es un puente no puede tener un camino cerrado que también sea un sendero.