Saltar al contenido principal
LibreTexts Español

4.S: Teoría de Gráficas (Resumen)

  • Page ID
    115790
  • \( \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

    Ojalá este capítulo te haya dado algún sentido para la amplia variedad de temas de teoría de grafos así como por qué estos estudios son interesantes. Hay muchas más áreas interesantes a considerar y la lista va en aumento todo el tiempo; la teoría de grafos es un área activa de la investigación matemática.

    Una razón por la que la teoría gráfica es un área de estudio tan rica es que trata de un concepto tan fundamental: cualquier par de objetos puede estar relacionado o no relacionado. Lo que son los objetos y lo que significa “relacionado” varía según el contexto, y esto lleva a muchas aplicaciones de la teoría de grafos a la ciencia y otras áreas de las matemáticas. Los objetos pueden ser países, y dos países pueden estar relacionados si comparten frontera. Los objetos podrían ser masas de tierra que están relacionadas si hay un puente entre ellos. Los objetos podrían ser sitios web que están relacionados si hay un enlace de uno a otro. O podemos ser completamente abstractos: los objetos son vértices que están relacionados si su es un borde entre ellos.

    La pregunta que hacemos sobre la gráfica depende de la aplicación, pero a menudo nos lleva a preguntas más profundas, generales y abstractas que vale la pena estudiar por derecho propio. Aquí hay un breve resumen de los tipos de preguntas que hemos considerado:

    • ¿Se puede dibujar la gráfica en el plano sin que los bordes se crucen? Si es así, ¿en cuántas regiones divide este dibujo el plano?
    • ¿Es posible colorear los vértices de la gráfica para que los vértices relacionados tengan diferentes colores usando una pequeña cantidad de colores? ¿Cuántos colores se necesitan?
    • ¿Es posible trazar cada borde de una gráfica exactamente una vez sin levantar el lápiz? ¿Qué otro tipo de “caminos” podría poseer una gráfica?
    • ¿Puedes encontrar subgrafías con ciertas propiedades? Por ejemplo, ¿cuándo una gráfica (bipartita) contiene una subgrafía en la que todos los vértices solo están relacionados con otro vértice?

    No en vano, estas preguntas suelen estar relacionadas entre sí. Por ejemplo, el número cromático de una gráfica no puede ser mayor que 4 cuando la gráfica es plana. Si la gráfica tiene una ruta de Euler depende de cuántos vértices esté adyacente cada vértice (y de si esos números son siempre pares o no). Incluso la existencia de emparejamientos en gráficas bipartitas se puede probar usando caminos.

    Revisión del Capítulo

    1

    ¿Cuáles (si las hay) de las siguientes gráficas son las mismas? ¿Cuáles son diferentes? Explique.

    Solución

    La primera y la tercera gráficas son las mismas (intenta arrastrar vértices alrededor para que las imágenes coincidan hacia arriba), pero la gráfica media es diferente (que puedes ver, por ejemplo, al señalar que la gráfica media tiene solo un vértice de grado 2, mientras que las otras tienen dos de esos vértices).

    2

    ¿Cuál de las gráficas de la pregunta anterior contiene caminos o circuitos de Euler? ¿Cuáles de las gráficas son planas?

    Solución

    La primera (y tercera) gráficas contienen una ruta de Euler. Todas las gráficas son planas.

    3

    Dibuja una gráfica que tenga un circuito de Euler pero que no sea plana.

    Solución

    Por ejemplo,\(K_5\text{.}\)

    4

    Dibuja una gráfica que no tenga una trayectoria de Euler y tampoco sea plana.

    Solución

    Por ejemplo,\(K_{3,3}\text{.}\)

    5

    Si una gráfica tiene 10 vértices y 10 aristas y contiene un circuito de Euler, ¿debe ser plana? ¿Cuántas caras tendría?

    Solución

    Sí. Según la fórmula de Euler tendría 2 caras. Lo hace. El único gráfico de este tipo es\(C_{10}\text{.}\)

    6

    Supongamos que\(G\) es una gráfica con\(n\) vértices, cada uno teniendo grado 5.

    1. \(n\)¿Para qué valores de esto tiene sentido?
    2. \(n\)¿Para qué valores de la gráfica tiene una ruta de Euler?
    3. ¿Cuál es el valor más pequeño\(n\) para el cual la gráfica podría ser plana? (complicado)
    Solución
    1. Sólo si\(n \ge 6\) and is even.
    2. Ninguno.
    3. 12. Tal gráfica tendría\(\frac{5n}{2}\) edges. If the graph is planar, then \(n - \frac{5n}{2} + f = 2\) so there would be \(\frac{4+3n}{2}\) faces. Also, we must have \(3f \le 2e\text{,}\) since the graph is simple. So we must have \(3\left(\frac{4 + 3n}{2}\right) \le 5n\text{.}\) Solving for \(n\) gives \(n \ge 12\text{.}\)

    7

    En un baile escolar, 6 niñas y 4 niños se turnan para bailar (en pareja) entre sí.

    1. ¿Cuántas parejas bailaron si cada chica baila con cada chico?
    2. ¿Cuántas parejas bailaban si todos bailaban con todos los demás (independientemente del género)?
    3. Explique qué gráficas se pueden utilizar para representar estas situaciones.
    Solución
    1. Había 24 parejas: 6 opciones para la niña y 4 opciones para el chico.
    2. Había 45 parejas:\({10 \choose 2}\) since we must choose two of the 10 people to dance together.
    3. Para la parte (a), estamos contando el número de aristas en\(K_{4,6}\text{.}\) In part (b) we count the edges of \(K_{10}\text{.}\)

    8

    Entre un grupo de\(n\) personas, ¿es posible que todos sean amigos de un número impar de personas del grupo? Si es así, ¿qué puedes decir sobre\(n\text{?}\)

    Solución

    Sí, siempre y cuando\(n\) is even. If \(n\) were odd, then corresponding graph would have an odd number of odd degree vertices, which is impossible.

    9

    Tu amigo te ha desafiado a crear un poliedro convexo que contenga 9 triángulos y 6 pentágonos.

    1. ¿Es posible construir un poliedro de este tipo usando solo estas formas? Explique.
    2. Usted decide incluir también un heptágono (polígono de siete lados). ¿Cuántos vértices contiene tu nuevo poliedro convexo?
    3. Asumiendo que tienes éxito en la construcción de tu nuevo poliedro de 16 caras, ¿cada vértice podría ser la unión del mismo número de caras? ¿Podría cada vértice unir 3 o 4 caras? Si es así, ¿cuántos de cada tipo de vértice habría?
    Solución
    1. No. Los 9 triángulos aportan 3 bordes cada uno, y los 6 pentágonos aportan 5 bordes. Esto da un total de 57, que es exactamente el doble del número de aristas, ya que cada borde bordea exactamente 2 caras. Pero 57 es extraño, así que esto es imposible.
    2. Ahora sumando todos los bordes de todos los 16 polígonos da un total de 64, lo que significa que habría 32 bordes en el poliedro. Entonces podemos usar la fórmula de Euler\(v - e + f = 2\) to deduce that there must be 18 vertices.
    3. Si suma todos los vértices de cada polígono por separado, obtenemos un total de 64. Esto no es divisible por 3, por lo que no puede ser que cada vértice pertenezca exactamente a 3 caras. ¿Podrían pertenecer todos a 4 caras? Eso significaría que había\(64/4 = 16\) vertices, but we know from Euler's formula that there must be 18 vertices. We can write \(64 = 3x + 4y\) and solve for \(x\) and \(y\) (as integers). We get that there must be 10 vertices with degree 4 and 8 with degree 3. (Note the number of faces joined at a vertex is equal to its degree in graph theoretic terms.)

    10

    ¿Existe un poliedro convexo que requiera 5 colores para colorear correctamente los vértices del poliedro? Explique.

    Solución

    No. Cada poliedro se puede representar como una gráfica plana, y el Teorema de los Cuatro Colores dice que cada gráfica plana tiene un número cromático como máximo 4.

    11

    ¿Cuántos bordes tiene la gráfica\(K_{n,n}\)? \(n\)¿Para qué valores de la gráfica contiene un circuito de Euler? ¿Para qué valores de\(n\) es plana la gráfica?

    Solución

    \(K_{n,n}\) has \(n^2\) edges. The graph will have an Euler circuit when \(n\) is even. The graph will be planar only when \(n \lt 3\text{.}\)

    12

    La gráfica\(G\) tiene 6 vértices con grados\(1, 2, 2, 3, 3, 5\text{.}\) ¿Cuántos bordes\(G\) tiene? Si\(G\) fuera plano ¿cuántas caras tendría? ¿\(G\)Tiene un camino de Euler?

    Solución

    \(G\) has 8 edges (since the sum of the degrees is 16). If \(G\) is planar, then it will have 4 faces (since \(6 - 8 + 4 = 2\)). \(G\) does not have an Euler path since there are more than 2 vertices of odd degree.

    13

    ¿Cuál es el menor número de colores que necesitas para colorear correctamente los vértices de ¿\(K_{7}\text{.}\)Puedes decir si\(K_7\) es planar en base a tu respuesta?

    Solución

    \(7\) colors. Thus \(K_7\) is not planar (by the contrapositive of the Four Color Theorem).

    14

    ¿Cuál es el menor número de colores que necesitas para colorear correctamente los vértices de ¿\(K_{3,4}\text{?}\)Puedes decir si\(K_{3,4}\) es planar en base a tu respuesta?

    Solución

    El número cromático de\(K_{3,4}\) is 2, since the graph is bipartite. You cannot say whether the graph is planar based on this coloring (the converse of the Four Color Theorem is not true). In fact, the graph is not planar, since it contains \(K_{3,3}\) as a subgraph.

    15

    Un dodecaedro es un poliedro convexo regular compuesto por 12 pentágonos regulares.

    1. Supongamos que coloreas cada pentágono con uno de tres colores. Demostrar que debe haber dos pentágonos adyacentes coloreados de manera idéntica.
    2. ¿Y si usas cuatro colores?
    3. ¿Y si en lugar de un dodecaedro colorearas las caras de un cubo?
    Solución

    Para todas estas preguntas, realmente estamos coloreando los vértices de una gráfica. Se obtiene la gráfica dibujando primero una representación plana del poliedro y luego tomando su doble plano: poner un vértice en el centro de cada cara (incluyendo el exterior) y conectar dos vértices si sus caras comparten una arista.

    1. Dado que el doble plano de un dodecaedro contiene una rueda de 5, su número cromático es de al menos 4. Alternativamente, supongamos que podría colorear las caras usando 3 colores sin que dos caras adyacentes tengan el mismo color. Toma cualquier cara y colorea azul. Los 5 pentágonos que bordean este pentágono azul no pueden ser coloreados de azul. Colorea el primero rojo. Sus dos vecinos (adyacentes al pentágono azul) se ponen de color verde. Los 2 restantes no pueden ser azules ni verdes, pero tampoco pueden ser ambos rojos ya que están adyacentes entre sí. Por lo tanto, se necesita un 4º color.
    2. El doble plano del dodecaedro es en sí mismo una gráfica plana. Así, por el teorema de 4 colores, se puede colorear usando solo 4 colores sin que dos vértices adyacentes (correspondientes a las caras del poliedro) sean coloreados de manera idéntica.
    3. El cubo puede ser adecuadamente de 3 colores. Colorea el rojo “superior” y “inferior”, el azul “frontal” y “trasero”, y el verde “izquierdo” y “derecho”.

    16

    Si una gráfica plana\(G\) con\(7\) vértices divide el plano en 8 regiones, ¿cuántas aristas deben\(G\) tener?

    Solución

    \(G\) has \(13\) edges, since we need \(7 - e + 8 = 2\text{.}\)

    17

    Considera la gráfica a continuación:

    1. ¿La gráfica tiene una trayectoria o circuito de Euler? Explique.
    2. ¿La gráfica es plana? Explique.
    3. ¿La gráfica es bipartita? ¿Completa? ¿Bipartito completo?
    4. Cuál es el número cromático de la gráfica.
    Solución
    1. El gráfico sí tiene un camino de Euler, pero no un circuito de Euler. Hay exactamente dos vértices con grado impar. El camino comienza en uno y termina en el otro.
    2. La gráfica es plana. A pesar de que como se dibuja bordes cruzados, es fácil redibujarlo sin que los bordes se crucen.
    3. La gráfica no es bipartita (hay un ciclo impar), ni completa.
    4. El número cromático de la gráfica es 3.

    18

    Para cada parte a continuación, diga si la afirmación es verdadera o falsa. Explique por qué las afirmaciones verdaderas son verdaderas, y dé contraejemplos para las declaraciones falsas.

    1. Cada gráfica bipartita es plana.
    2. Cada gráfica bipartita tiene el número cromático 2.
    3. Cada gráfica bipartita tiene un camino de Euler.
    4. Cada vértice de una gráfica bipartita tiene grado par.
    5. Una gráfica es bipartita si y sólo si la suma de los grados de todos los vértices es par.
    Solución
    1. Falso. Por ejemplo,\(K_{3,3}\) is not planar.
    2. Cierto. La gráfica es bipartita por lo que es posible dividir los vértices en dos grupos sin aristas entre vértices en un mismo grupo. Así podemos colorear todos los vértices de un grupo rojo y el otro grupo azul.
    3. Falso. \(K_{3,3}\) has 6 vertices with degree 3, so contains no Euler path.
    4. Falso. \(K_{3,3}\) again.
    5. Falso. La suma de los grados de todos los vértices es par para todas las gráficas por lo que esta propiedad no implica que la gráfica sea bipartita.

    19

    Considera la afirmación “Si una gráfica es plana, entonces tiene una trayectoria de Euler”.

    1. Escribe lo contrario de la declaración.
    2. Escribir el contrapositivo de la declaración.
    3. Escribir la negación de la declaración.
    4. ¿Es posible que el contrapositivo sea falso? Si lo fuera, ¿qué te diría eso?
    5. ¿La declaración original es verdadera o falsa? Demuestra tu respuesta.
    6. ¿Es cierto o falso lo contrario de la afirmación? Demuestra tu respuesta.
    Solución
    1. Si una gráfica tiene una trayectoria de Euler, entonces es plana.
    2. Si una gráfica no tiene una ruta de Euler, entonces no es plana.
    3. Hay una gráfica que es plana y no tiene un camino de Euler.
    4. Sí. De hecho, en este caso es porque la declaración original es falsa.
    5. Falso. \(K_4\) is planar but does not have an Euler path.
    6. Falso. \(K_5\) has an Euler path but is not planar.

    20

    Recuerda que un árbol es una gráfica conectada sin ciclos.

    1. Conjetura una relación entre los vértices y aristas de un gráfico de árbol. (Por ejemplo, ¿puedes tener un árbol con 5 vértices y 7 bordes?)
    2. Explica por qué cada árbol con al menos 3 vértices tiene una hoja (es decir, un vértice de grado 1).
    3. Demuestra tu conjetura a partir de la parte (a) por inducción en el número de vértices. Sugerencia: Para el paso inductivo, asumirás que tu conjetura es cierta para todos los árboles con\(k\) vértices, y demostrarás que también es cierto para un árbol arbitrario con\(k+1\) vértices. Considera lo que sucede cuando cortas una hoja y luego la dejas volver a crecer.

    This page titled 4.S: Teoría de Gráficas (Resumen) is shared under a CC BY-SA license and was authored, remixed, and/or curated by Oscar Levin.