14.6: Ejercicios

Última actualización
Guardar como PDF

Page ID: 118018

\( \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}}\)

Ejercicio\(\PageIndex{1}\)

Considera la gráfica en la Figura 14.6.1.

Figura\(\PageIndex{1}\): Un gráfico de ejemplo.

¿Los vértices 1 y 2 son incidentes?
¿Hay vértices adyacentes a sí mismos?
¿El vértice 3 es adyacente al vértice 6?
¿Es esta una gráfica simple?
Compute el grado de cada vértice en la gráfica. Después verificar que la suma de los grados sea igual al doble del número de aristas. (Ver Teorema 14.2.1. )

Ejercicio\(\PageIndex{2}\)

¿Cuántos bordes tiene la gráfica completa con diez vértices?

Pista.: Ver Teorema 14.2.1.

Generaliza tu resultado a una fórmula para el número de aristas en la gráfica completa con\(n\) vértices.

Ejercicio\(\PageIndex{3}\)

Dibuja un ejemplo de una gráfica simple que no tenga vértices de grado impar.
Dibuja un ejemplo de una gráfica simple que no tenga vértices de grado par.

Ejercicio\(\PageIndex{4}\)

Dada una colección de conjuntos,\(A_1,A_2,\ldots,A_n\text{,}\) la gráfica de intersección de la colección es la gráfica simple que tiene un vértice para cada uno de los conjuntos de la colección, con dos vértices unidos por un borde si y solo si los dos conjuntos correspondientes tienen intersección no vacía. Dibuja la gráfica de intersección de la siguiente colección de conjuntos.

\ begin {reunir*} A_1 =\ {1,2,3,4,5\},\\ A_2 =\ {2,4,6,8\},\\ A_3 =\ {3,5,12\},\\ A_4 =\ {5,8,10\}. \ end {reunir*}

Complemento de una gráfica.

Los ejercicios 5—7 se refieren a la siguiente definición.

Definición: Complemento (de una gráfica simple\(G\))

el gráfico simple que tiene el mismo vértice establecido como\(G\text{,}\) pero en el que dos vértices están unidos por un borde si y solo si esos mismos dos vértices no están unidos por un borde en\(G\)

Ejercicio\(\PageIndex{5}\)

Dibuja el complemento de la gráfica simple en la Figura\(\PageIndex{2}\).

Figura\(\PageIndex{2}\): Una gráfica simple.

Ejercicio\(\PageIndex{6}\)

¿Cuál es el complemento de una gráfica completa?

Ejercicio\(\PageIndex{7}\)

Supongamos que\(G\) es una gráfica simple con\(n\) vértices. Determinar una relación entre el número de aristas en\(G\text{,}\) el número de aristas en el complemento de\(G\text{,}\) y el número de aristas en la gráfica completa\(K_n\) con\(n\) vértices.

Pista.: Recordemos que cada gráfico simple con\(n\) vértices es un subgrafo de\(K_n\text{.}\)