Saltar al contenido principal
LibreTexts Español

4.E: Teoría de Gráficas (Ejercicios)

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

    Template:mathJaxLevin

    4.1: Definiciones

    1

    Si 10 personas cada una se dan la mano entre sí, ¿cuántos apretones de manos se llevaron a cabo? ¿Qué tiene que ver esta pregunta con la teoría gráfica?

    Contestar

    Esto es pedir el número de aristas en\(K_{10}\text{.}\) Each vertex (person) has degree (shook hands with) 9 (people). So the sum of the degrees is \(90\text{.}\) However, the degrees count each edge (handshake) twice, so there are 45 edges in the graph. That is how many handshakes took place.

    2

    Entre un grupo de 5 personas, ¿es posible que todos sean amigos exactamente de 2 de las personas del grupo? ¿Y qué pasa con 3 de las personas del grupo?

    Contestar

    Es posible que todos sean amigos exactamente de 2 personas. Podrías organizar a las 5 personas en círculo y decir que todos son amigos de las dos personas a cada lado de ellas (así obtienes la gráfica\(C_5\)). However, it is not possible for everyone to be friends with 3 people. That would lead to a graph with an odd number of odd degree vertices which is impossible since the sum of the degrees must be even.

    3

    ¿Es posible que dos gráficas diferentes (no isomórficas) tengan el mismo número de vértices y el mismo número de aristas? ¿Y si los grados de los vértices en las dos gráficas son los mismos (entonces ambas gráficas tienen vértices con grados 1, 2, 2, 3 y 4, por ejemplo)? Dibuja dos de esas gráficas o explica por qué no.

    Contestar

    Sí. Por ejemplo, ambas gráficas a continuación contienen 6 vértices, 7 aristas y tienen grados (2,2,2,2,3,3).

    image-88.svgimage-89.svg

    4

    ¿Son iguales las dos gráficas siguientes? ¿Son isomórficos? Si son isomórficos, dan el isomorfismo. Si no, explique.

    • Gráfica 1:\(V = \{a,b,c,d,e\}\text{,}\) \(E = \{\{a,b\}, \{a,c\}, \{a,e\}, \{b,d\}, \{b,e\}, \{c,d\}\}\text{.}\)
    • Graph 2:

    image-90.svg

    Answer

    The graphs are not equal. For example, graph 1 has an edge \(\{a,b\}\) but graph 2 does not have that edge. They are isomorphic. One possible isomorphism is \(f:G_1 \to G_2\) defined by \(f(a) = d\text{,}\) \(f(b) = c\text{,}\) \(f(c) = e\text{,}\) \(f(d) = b\text{,}\) \(f(e) = a\text{.}\)

    5

    Consider the following two graphs:

    \(G_1\)

    • \(V_1=\{a,b,c,d,e,f,g\}\)
    • \(E_1=\{\{a,b\},\{a,d\},\{b,c\},\{b,d\},\{b,e\},\{b,f\},\{c,g\},\{d,e\},\)
    • \(\{e,f\},\{f,g\}\}\text{.}\)

    \(G_2\)

    • \(V_2=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7\}\text{,}\)
    • \(E_2=\{\{v_1,v_4\},\{v_1,v_5\},\{v_1,v_7\},\{v_2,v_3\},\{v_2,v_6\},\)
    • \(\{v_3,v_5\},\{v_3,v_7\},\{v_4,v_5\},\{v_5,v_6\},\{v_5,v_7\}\}\)
    1. Let \(f:G_1 \rightarrow G_2\) be a function that takes the vertices of Graph 1 to vertices of Graph 2. The function is given by the following table:
      \(x\) \(a\) \(b\) \(c\) \(d\) \(e\) \(f\) \(g\)
      \(f(x)\) \(v_4\) \(v_5\) \(v_1\) \(v_6\) \(v_2\) \(v_3\) \(v_7\)

      Does \(f\) define an isomorphism between Graph 1 and Graph 2? Explain.

    2. Define a new function \(g\) (with \(g\not=f\)) that defines an isomorphism between Graph 1 and Graph 2.
    3. Is the graph pictured below isomorphic to Graph 1 and Graph 2? Explain.

    image-91.svg

    6

    Which of the graphs below are bipartite? Justify your answers.

    image-92.svg image-93.svg image-94.svg image-95.svg

    Answer

    Three of the graphs are bipartite. The one which is not is \(C_7\) (second from the right). To see that the three graphs are bipartite, we can just give the bipartition into two sets \(A\) and \(B\text{,}\) as labeled below:

    image-96.svg image-97.svg image-98.svg

    La gráfica\(C_7\) is not bipartite because it is an odd cycle. You would want to put every other vertex into the set \(A\text{,}\) but if you travel clockwise in this fashion, the last vertex will also be put into the set \(A\text{,}\) leaving two \(A\) vertices adjacent (which makes it not a bipartition).

    7

    For which \(n \ge 3\) is the graph \(C_n\) bipartite?

    8

    For each of the following, try to give two different unlabeled graphs with the given properties, or explain why doing so is impossible.

    1. Two different trees with the same number of vertices and the same number of edges. A tree is a connected graph with no cycles.
    2. Two different graphs with 8 vertices all of degree 2.
    3. Two different graphs with 5 vertices all of degree 4.
    4. Two different graphs with 5 vertices all of degree 3.
    Answer
    1. For example:

    image-99.svg image-100.svg

    1. Esto no es posible si requerimos que las gráficas estén conectadas. Si no, podríamos tomar\(C_8\) as one graph and two copies of \(C_4\) as the other.
    2. No es posible. Si tienes una gráfica con 5 vértices todos de grado 4, entonces cada vértice debe ser adyacente a cada otro vértice. Esta es la gráfica\(K_5\text{.}\)
    3. Esto no es posible. De hecho, ni siquiera hay una gráfica con esta propiedad (tal gráfica tendría\(5\cdot 3/2 = 7.5\) edges).

    4.2: Gráficas Planares

    1

    ¿Es posible que una gráfica plana tenga 6 vértices, 10 aristas y 5 caras? Explique.

    Contestar

    No. Un gráfico plano (conectado) debe satisfacer la fórmula de Euler:\(v - e + f = 2\text{.}\) Here \(v - e + f = 6 - 10 + 5 = 1\text{.}\)

    2

    La gráfica\(G\) tiene 6 vértices con grados\(2, 2, 3, 4, 4, 5\text{.}\) ¿Cuántos bordes\(G\) tiene? ¿Podría\(G\) ser plano? Si es así, cuántas caras tendría. Si no, explique.

    Contestar

    \(G\) has 10 edges, since \(10 = \frac{2+2+3+4+4+5}{2}\text{.}\) It could be planar, and then it would have 6 faces, using Euler's formula: \(6-10+f = 2\) means \(f = 6\text{.}\) To make sure that it is actually planar though, we would need to draw a graph with those vertex degrees without edges crossing. This can be done by trial and error (and is possible).

    3

    Estoy pensando en un poliedro que contiene 12 caras. Siete son triángulos y cuatro son cuadralaterales. El poliedro tiene 11 vértices incluyendo los que rodean la cara misteriosa. ¿Cuántos lados tiene la última cara?

    Contestar

    Digamos que el último poliedro tiene\(n\) edges, and also \(n\) vertices. The total number of edges the polyhedron has then is \((7 \cdot 3 + 4 \cdot 4 + n)/2 = (37 + n)/2\text{.}\) In particular, we know the last face must have an odd number of edges. We also have that \(v = 11 \text{.}\) By Euler's formula, we have \(11 - (37+n)/2 + 12 = 2\text{,}\) and solving for \(n\) we get \(n = 5\text{,}\) so the last face is a pentagon.

    4

    Considera algunos poliedros clásicos.

    1. Un octaedro es un poliedro regular compuesto por 8 triángulos equiláteros (parece como dos pirámides con sus bases pegadas entre sí). Dibuja una representación gráfica plana de un octaedro. ¿Cuántos vértices, aristas y caras tiene un octaedro (y tu gráfica)?
    2. El diseño tradicional de una pelota de fútbol es de hecho una (proyección esférica de un) icosaedro truncado. Este consta de 12 pentágonos regulares y 20 hexágonos regulares. No hay dos pentágonos adyacentes (por lo que los bordes de cada pentágono son compartidos solo por hexágonos). ¿Cuántos vértices, aristas y caras tiene un icosaedro truncado? Explica cómo llegaste a tus respuestas. Bonificación: dibuja la representación gráfica plana del icosaedro truncado.
    3. Tu “amigo” afirma que ha construido un poliedro convexo a partir de 2 triángulos, 2 cuadrados, 6 pentágonos y 5 octágonos. Demuestra que tu amigo miente. Pista: cada vértice de un poliedro convexo debe bordear al menos tres caras.

    5

    Demostrar la fórmula de Euler usando inducción en el número de bordes en la gráfica.

    Responder

    Prueba

    Let\(P(n)\) be the statement, “every planar graph containing \(n\) edges satisfies \(v - n + f = 2\text{.}\)” We will show \(P(n)\) is true for all \(n \ge 0\text{.}\) Base case: there is only one graph with zero edges, namely a single isolated vertex. In this case \(v = 1\text{,}\) \(f = 1\) and \(e = 0\text{,}\) so Euler's formula holds. Inductive case: Suppose \(P(k)\) is true for some arbitrary \(k \ge 0\text{.}\) Now consider an arbitrary graph containing \(k+1\) edges (and \(v\) vertices and \(f\) faces). No matter what this graph looks like, we can remove a single edge to get a graph with \(k\) edges which we can apply the inductive hypothesis to. There are two possibilities. First, the edge we remove might be incident to a degree 1 vertex. In this case, also remove that vertex. The smaller graph will now satisfy \(v-1 - k + f = 2\) by the induction hypothesis (removing the edge and vertex did not reduce the number of faces). Adding the edge and vertex back gives \(v - (k+1) + f = 2\text{,}\) as required. The second case is that the edge we remove is incident to vertices of degree greater than one. In this case, removing the edge will keep the number of vertices the same but reduce the number of faces by one. So by the inductive hypothesis we will have \(v - k + f-1 = 2\text{.}\) Adding the edge back will give \(v - (k+1) + f = 2\) as needed. Therefore, by the principle of mathematical induction, Euler's formula holds for all planar graphs.

    6

    Demostrar la fórmula de Euler usando inducción en el número de vértices en la gráfica.

    7

    La fórmula de Euler (\(v - e + f = 2\)) es válida para todas las gráficas planas conectadas. ¿Y si una gráfica no está conectada? Supongamos que una gráfica plana tiene dos componentes. ¿Cuál es el valor del\(v - e + f\) ahora? ¿Y si tiene\(k\) componentes?

    8

    Demostrar que la gráfica Petersen (abajo) no es plana.

    image-111.svg

    Responder

    ¿Cuál es la duración del ciclo más corto? (Esta cantidad suele llamarse circunferencia de la gráfica).

    9

    Demostrar que cualquier gráfico plano con\(v\) vértices y\(e\) aristas satisface\(e \le 3v - 6\text{.}\)

    Responder

    Prueba

    Conocemos en cualquier gráfica plana el número de caras\(f\) satisfies \(3f \le 2e\) since each face is bounded by at least three edges, but each edge borders two faces. Combine this with Euler's formula:

    \ begin {ecuación*} v - e + f = 2\ end {ecuación*}\ begin {ecuación*} v - e +\ frac {2e} {3}\ ge 2\ end {ecuación*}\ begin {ecuación*} 3v - e\ ge 6\ end {ecuación*}\ begin {ecuación*} 3v - 6\ ge e.\ end {ecuación*}

    10

    Demostrar que cualquier gráfica plana debe tener un vértice de grado 5 o menos.

    4.3: Colorear

    1

    Cuál es el menor número de colores que necesitas para colorear correctamente los vértices de Es\(K_{4,5}\text{?}\) decir, encuentra el número cromático de la gráfica.

    image-121.svgimage-122.svgimage-123.svgimage-124.svgimage-125.svg

    Responder

    2, ya que la gráfica es bipartita. Un color para el conjunto superior de vértices, otro color para el conjunto inferior de vértices.

    2

    Dibuja una gráfica con el número cromático 6 (es decir, que requiere 6 colores para colorear correctamente los vértices). ¿Podría su gráfica ser plana? Explique.

    Responder

    Por ejemplo,\(K_6\text{.}\) If the chromatic number is 6, then the graph is not planar; the 4-color theorem states that all planar graphs can be colored with 4 or fewer colors.

    3

    Encuentra el número cromático de cada una de las siguientes gráficas.

    Responder

    Los números cromáticos son 2, 3, 4, 5 y 3 respectivamente de izquierda a derecha.

    4

    Un grupo de 10 amigos decide dirigirse a una cabaña en el bosque (donde nada podría salir mal). Desafortunadamente, varios de estos amigos han salido en el pasado, y las cosas siguen siendo un poco incómodas. Para conseguir la cabina, necesitan dividirse en algún número de autos, y no hay dos personas con las que salieron deberían estar en el mismo auto.

    1. ¿Cuál es el menor número de autos que necesitas si todas las relaciones fueran estrictamente heterosexuales? Representar un ejemplo de tal situación con una gráfica. ¿Qué tipo de gráfica obtienes?
    2. Debido a que varios de estos amigos salieron también hay conflictos entre amigos del mismo género, enumerados a continuación. Ahora, ¿cuál es el menor número de autos libres de conflictos que podrían llevar a la cabina?
      Amiga A B C D E F G H I J
      Conflictos con BEJ ADG HJ BF AI DJ B CI EHJ ACFI
    3. ¿Qué tienen que ver estas preguntas con la coloración?

    5

    ¿Cuál es el menor número de colores que se pueden usar para colorear los vértices de un cubo de manera que no haya dos vértices adyacentes de manera idéntica?

    image-126.svg

    Responder

    El cubo se puede representar como un gráfico plano y coloreado con dos colores de la siguiente manera:

    Ya que sería imposible colorear los vértices con un solo color, vemos que el cubo tiene el número cromático 2 (es bipartito).

    6

    Demostrar que el número cromático de cualquier árbol es dos. Recordemos, un árbol es una gráfica conectada sin ciclos.

    1. image-127.svg
    1. Describa un procedimiento para colorear el árbol a continuación.
    2. El número cromático de\(C_n\) es dos cuando\(n\) es par. ¿Qué sale mal cuando\(n\) es extraño?
    3. Demuestre que su procedimiento de la parte (a) siempre funciona para cualquier árbol.
    4. Ahora, demuestre usando inducción que cada árbol tiene el número cromático 2.

    7

    Demostrar el teorema de 6 colores: cada gráfica plana tiene el número cromático 6 o menos. No asuma el teorema de 4 colores (cuya prueba es MUCHO más dura), pero puede suponer el hecho de que cada gráfica plana contiene un vértice de grado como máximo 5.

    8

    No todas las gráficas son perfectas. Dé un ejemplo de una gráfica con número cromático 4 que no contenga copia de Es\(K_4\text{.}\) decir, no debería haber 4 vértices todos por pares adyacentes.

    Responder

    El gráfico de rueda a continuación tiene esta propiedad. El exterior de la rueda forma un ciclo impar, por lo que requiere 3 colores, el centro de la rueda debe ser diferente a todos los vértices exteriores.

    image-128.svg

    9

    Demostrar por inducción en vértices que cualquier gráfica\(G\) which contains at least one vertex of degree less than \(\Delta(G)\) (the maximal degree of all vertices in \(G\)) has chromatic number at most \(\Delta(G)\text{.}\)

    10

    You have a set of magnetic alphabet letters (one of each of the 26 letters in the alphabet) that you need to put into boxes. For obvious reasons, you don't want to put two consecutive letters in the same box. What is the fewest number of boxes you need (assuming the boxes are able to hold as many letters as they need to)?

    Answer

    If we drew a graph with each letter representing a vertex, and each edge connecting two letters that were consecutive in the alphabet, we would have a graph containing two vertices of degree 1 (A and Z) and the remaining 24 vertices all of degree 2 (for example, \(D\) would be adjacent to both \(C\) and \(E\)). By Brooks' theorem, this graph has chromatic number at most 2, as that is the maximal degree in the graph and the graph is not a complete graph or odd cycle. Thus only two boxes are needed.

    11

    Prove that if you color every edge of \(K_6\) either red or blue, you are guaranteed a monochromatic triangle (that is, an all red or an all blue triangle).

    4.4: Euler Paths and Circuits

    1

    You and your friends want to tour the southwest by car. You will visit the nine states below, with the following rather odd rule: you must cross each border between neighboring states exactly once (so, for example, you must cross the Colorado-Utah border exactly once). Can you do it? If so, does it matter where you start your road trip? What fact about graph theory solves this problem?

    image-139.svg

    Answer

    This is a question about finding Euler paths. Draw a graph with a vertex in each state, and connect vertices if their states share a border. Exactly two vertices will have odd degree: the vertices for Nevada and Utah. Thus you must start your road trip at in one of those states and end it in the other.

    2

    Which of the following graphs contain an Euler path? Which contain an Euler circuit?

    1. \(K_4\)
    2. \(K_5\text{.}\)
    3. \(K_{5,7}\)
    4. \(K_{2,7}\)
    5. \(C_7\)
    6. \(P_7\)
    Answer
    1. \(K_4\) does not have an Euler path or circuit.
    2. \(K_5\) has an Euler circuit (so also an Euler path).
    3. \(K_{5,7}\) does not have an Euler path or circuit.
    4. \(K_{2,7}\) has an Euler path but not an Euler circuit.
    5. \(C_7\) has an Euler circuit (it is a circuit graph!)
    6. \(P_7\) has an Euler path but no Euler circuit.

    3

    Edward A. Mouse has just finished his brand new house. The floor plan is shown below:

    image-140.svg

    1. Edward wants to give a tour of his new pad to a lady-mouse-friend. Is it possible for them to walk through every doorway exactly once? If so, in which rooms must they begin and end the tour? Explain.
    2. Is it possible to tour the house visiting each room exactly once (not necessarily using every doorway)? Explain.
    3. After a few mouse-years, Edward decides to remodel. He would like to add some new doors between the rooms he has. Of course, he cannot add any doors to the exterior of the house. Is it possible for each room to have an odd number of doors? Explain.

    4

    For which \(n\) does the graph \(K_n\) contain an Euler circuit? Explain.

    Answer

    When \(n\) is odd, \(K_n\) contains an Euler circuit. This is because every vertex has degree \(n-1\text{,}\) so an odd \(n\) results in all degrees being even.

    5

    For which \(m\) and \(n\) does the graph \(K_{m,n}\) contain an Euler path? An Euler circuit? Explain.

    Answer

    If both \(m\) and \(n\) are even, then \(K_{m,n}\) has an Euler circuit. When both are odd, there is no Euler path or circuit. If one is 2 and the other is odd, then there is an Euler path but not an Euler circuit.

    6

    For which \(n\) does \(K_n\) contain a Hamilton path? A Hamilton cycle? Explain.

    Answer

    Add texts here. Do not delete this text first.

    All values of \(n\text{.}\) In particular, \(K_n\) contains \(C_n\) as a subgroup, which is a cycle that includes every vertex.

    7

    For which \(m\) and \(n\) does the graph \(K_{m,n}\) contain a Hamilton path? A Hamilton cycle? Explain.

    Answer

    As long as \(|m-n| \le 1\text{,}\) the graph \(K_{m,n}\) will have a Hamilton path. To have a Hamilton cycle, we must have \(m=n\text{.}\)

    8

    A bridge builder has come to Königsberg and would like to add bridges so that it is possible to travel over every bridge exactly once. How many bridges must be built?

    Answer

    If we build one bridge, we can have an Euler path. Two bridges must be built for an Euler circuit.

    image-141.svg

    9

    A continuación se muestra una gráfica que representa las amistades entre un grupo de estudiantes (cada vértice es un estudiante y cada borde es una amistad). ¿Es posible que los alumnos se sienten alrededor de una mesa redonda de tal manera que cada alumno se sienta entre dos amigos? ¿Qué tiene que ver esta pregunta con los caminos? image-142.svg

    Responder

    Estamos buscando un ciclo hamiltoniano, y esta gráfica sí tiene uno:

    image-143.svg

    10

    1. Supongamos que una gráfica tiene un camino Hamilton. ¿Cuál es el número máximo de vértices de grado uno que puede tener la gráfica? Explica por qué tu respuesta es correcta.
    2. Encuentra una gráfica que no tenga un camino Hamilton aunque ningún vértice tenga grado uno. Explica por qué funciona tu ejemplo.

    11

    Considera la siguiente gráfica:

    image-144.svg

    1. Encuentra un camino de Hamilton. ¿Se puede extender tu camino a un ciclo Hamilton?
    2. ¿La gráfica es bipartita? Si es así, ¿cuántos vértices hay en cada “parte”?
    3. Usa tu respuesta a la parte (b) para demostrar que la gráfica no tiene ciclo Hamilton.
    4. Supongamos que tiene una gráfica bipartita\(G\) en la que una parte tiene al menos dos vértices más que la otra. Demostrar que\(G\) no tiene un camino Hamilton.

    4.5: Coincidencia en Gráficas Bipartitas

    1

    Encuentre una coincidencia de las gráficas bipartitas a continuación o explique por qué no existe ninguna coincidencia.

    image-146.svgimage-147.svgimage-148.svg

    Responder

    Los gráficos primero y tercero tienen una coincidencia, que se muestra en negrita (también hay otros emparejamientos). La gráfica del medio no tiene coincidencia. Si miras los tres vértices rodeados, ves que solo tienen dos vecinos, lo que viola la condición coincidente\(\card{N(S)} \ge \card{S}\) (the three circled vertices form the set \(S\)).

    image-149.svgimage-150.svgimage-151.svg

    2

    Una gráfica bipartita que no tiene una coincidencia podría tener todavía una coincidencia parcial. Con esto nos referimos a un conjunto de aristas para las que ningún vértice pertenece a más de un borde (pero posiblemente no pertenece a ninguno). Cada gráfica bipartita (con al menos un borde) tiene una coincidencia parcial, por lo que podemos buscar la coincidencia parcial más grande en una gráfica.

    Tu “amiga” afirma que ha encontrado la mayor coincidencia parcial para la gráfica a continuación (su coincidencia está en negrita). Ella explica que no se puede agregar otro borde, porque todos los bordes no utilizados en su coincidencia parcial están conectados a vértices coincidentes. ¿Está en lo cierto?

    image-152.svg

    3

    Una forma de verificar si una coincidencia parcial es máxima es construir una ruta alterna. Esta es una secuencia de aristas adyacentes, que alternan entre aristas en la coincidencia y aristas no en la coincidencia (no se puede usar ninguna arista más de una vez). Si un camino alterno comienza y se detiene con un borde que no está en la coincidencia, entonces se denomina camino de aumento.

    1. Encuentra la ruta alterna más grande posible para la coincidencia parcial de la gráfica de tu amigo. ¿Es un camino de aumento? ¿Cómo te ayudaría esto a encontrar una coincidencia más grande?

    image-153.svg

    1. Encuentre la ruta alterna más grande posible para la coincidencia parcial a continuación. ¿Hay alguna senda de aumento? ¿La coincidencia parcial es la más grande que existe en la gráfica?

    image-154.svg

    4

    Las dos familias más ricas de Poniente han decidido entrar en alianza por matrimonio. La primera familia tiene 10 hijos, la segunda tiene 10 niñas. Las edades de los niños de las dos familias coinciden. Para evitar la incorrección, las familias insisten en que cada niño debe casarse con alguien de su edad, o con alguien de una posición menor o mayor. De hecho, la gráfica que representa matrimonios agradables se ve así:

    image-155.svg

    La pregunta: ¿cuántos arreglos matrimoniales aceptables diferentes que casen a los 20 hijos son posibles?

    1. ¿Cuántos arreglos matrimoniales son posibles si insistimos en que hay exactamente 6 niños que se casan con niñas que no son de su edad?
    2. ¿Podría generalizar la respuesta anterior para llegar al número total de arreglos matrimoniales?
    3. ¿Cómo sabes que tienes razón? Intenta contar de una manera diferente. Mira los tamaños familiares más pequeños y obtén una secuencia.
    4. ¿Se puede dar una relación de recurrencia que se ajuste al problema?

    5

    Decimos que un conjunto de vértices\(A \subseteq V\) es una cubierta de vértice si cada borde de la gráfica es incidente a un vértice en la cubierta (por lo que una cubierta de vértice cubre los bordes). Dado que\(V\) en sí es una cubierta de vértice, cada gráfica tiene una cubierta de vértice. La pregunta interesante es encontrar una cubierta mínima de vértices, una que utilice el menor número posible de vértices.

    1. Supongamos que tenías una coincidencia de una gráfica. ¿Cómo puedes usar eso para obtener una cobertura mínima de vértice? ¿Tu método siempre funcionará?
    2. Supongamos que tenías una cubierta mínima de vértice para una gráfica. ¿Cómo puedes usar eso para obtener una coincidencia parcial? ¿Tu método siempre funcionará?
    3. ¿Cuál es la relación entre el tamaño de la cubierta mínima del vértice y el tamaño de la coincidencia parcial máxima en una gráfica?

    6

    Para muchas aplicaciones de emparejamientos, tiene sentido usar gráficas bipartitas. Podría preguntarse, sin embargo, si hay alguna manera de encontrar emparejamientos en las gráficas en general.

    1. \(n\)¿Para qué tiene coincidencia la gráfica\(K_n\) completa?
    2. Demostrar que si una gráfica tiene una coincidencia, entonces\(\card{V}\) es par.
    3. ¿Es cierto lo contrario? Es decir, ¿todas las gráficas con\(\card{V}\) par tienen una coincidencia?
    4. ¿Y si también requerimos la condición coincidente? Demostrar o desacreditar: Si una gráfica con un número par de vértices satisface\(\card{N(S)} \ge \card{S}\) para todos\(S \subseteq V\text{,}\) entonces la gráfica tiene una coincidencia.

    4.E: Teoría de Gráficas (Ejercicios) is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.