Saltar al contenido principal
LibreTexts Español

6.5: Ejercicios

  • Page ID
    109946
  • \( \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}}} \)

    \(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)
    1. Responde las siguientes preguntas con base en la gráfica a continuación.

    1. ¿Cuáles son los vértices?
    2. ¿Esta gráfica está conectada?
    3. ¿Cuál es el grado de vértice C?
    4. Edge FE es adyacente a qué bordes?
    5. ¿Esta gráfica tiene algún puente?
    1. Responde las siguientes preguntas con base en la gráfica a continuación.

    1. ¿Cuáles son los vértices?
    2. ¿Cuál es el grado de vértice u?
    3. ¿Cuál es el grado de vértice s?
    4. ¿Qué es un circuito en la gráfica?
    1. Dibuja un subgrafo de expansión en la gráfica de abajo.

    1. Encuentra el árbol de expansión mínimo en la gráfica a continuación usando el algoritmo de Kruskal.

    1. Encuentra el árbol de expansión mínimo en la gráfica a continuación usando el algoritmo de Kruskal.

    1. Encuentra un camino de Euler en la gráfica de abajo.

    1. Encuentra un circuito de Euler en la gráfica de abajo.

    1. ¿Qué gráficas a continuación tienen Euler Paths? ¿Qué gráficas tienen circuitos de Euler?

    1. Resalta un circuito de Euler en la gráfica de abajo.

    1. Para cada una de las gráficas a continuación, escriba el grado de cada vértice junto a cada vértice.
    1. Circula si cada una de las gráficas a continuación tiene un circuito de Euler, una ruta de Euler, o ninguna.
    1. Circuito de Euler
    2. Camino de Euler
    3. Tampoco
    1. Circuito de Euler
    2. Camino de Euler
    3. Tampoco
    1. Circuito de Euler
    2. Camino de Euler
    3. Tampoco
    1. ¿Cuántos circuitos Hamilton tiene una gráfica completa con 6 vértices?
    1. Supongamos que necesita comenzar en A, visitar los tres vértices y regresar al punto de partida A. Usando el algoritmo de fuerza bruta, encuentre la ruta más corta si los pesos representan distancias en millas.

    1. Si se conecta una gráfica y __________________, la gráfica tendrá un circuito de Euler.
    1. la gráfica tiene un número par de vértices
    2. la gráfica tiene un número par de aristas
    3. la gráfica tiene todos los vértices de grado par
    4. la gráfica tiene solo dos vértices impares
    1. Comenzando en el vértice A, use el algoritmo del vecino más cercano para encontrar la ruta más corta si los pesos representan distancias en millas.

    1. Encuentra un circuito Hamilton usando el Algoritmo Repetitivo del Vecino Más cercano.

    1. Encuentra un circuito de Hamilton usando el algoritmo de enlace más bajo.

    1. ¿Cuál es un circuito que atraviesa cada borde de la gráfica exactamente una vez?

    A. Circuito de Euler b. Circuito Hamilton c. Árbol de expansión mínimo

    1. ¿Cuál es un circuito que atraviesa cada vértice de la gráfica exactamente una vez?

    A. Circuito de Euler b. Circuito Hamilton c. Árbol de expansión mínimo

    1. Para cada situación, ¿encontrarías un circuito de Euler o un Circuito Hamilton?
    1. El departamento de Obras Públicas deberá inspeccionar todas las calles de la ciudad para retirar escombros peligrosos.
    2. Los suministros de alimentos de socorro deben entregarse en ocho refugios de emergencia ubicados en diferentes sitios de una gran ciudad.
    3. El Departamento de Obras Públicas deberá inspeccionar los semáforos en las intersecciones de la ciudad para determinar cuáles siguen funcionando.
    4. Un ajustador de reclamos de seguros debe visitar 11 viviendas en varios barrios para redactar informes.

    This page titled 6.5: Ejercicios is shared under a CC BY-SA 4.0 license and was authored, remixed, and/or curated by Maxie Inigo, Jennifer Jameson, Kathryn Kozak, Maya Lanzetta, & Kim Sonier via source content that was edited to the style and standards of the LibreTexts platform.