11.2: Definiciones básicas, terminología y notación
- Page ID
- 114410
\( \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}\)Ahora que tenemos una comprensión intuitiva de lo que es una gráfica, es el momento de hacer una definición formal.
Definiciones: Gráfica, Vértice y Borde
Una gráfica\(G\) consta de dos conjuntos:
\(V\), cuyos elementos se denominan vértices de\(G\) (el singular de vértices es vértice); y
\(E\), cuyos elementos son pares desordenados de\(V\) (es decir,\(E ⊆ \{\{v_1, v_2\} | v_1, v_2 ∈ V \}\)). Los elementos de\(E\) se refieren como los bordes de\(G\).
Para mayor claridad en situaciones en las que se está estudiando más de una gráfica, podemos usar\(E(G)\) para\(E\) y\(V(G)\) para\(V\).
De acuerdo con esta definición, el modelo de Euler de los puentes de Königsberg no es en realidad una gráfica, porque algunos de los vértices tienen más de un borde entre ellos (por ejemplo, hay dos aristas entre\(A\) y\(B\)), lo que hace\(E\) un multiconjunto en lugar de un conjunto. Esto lleva naturalmente a otra definición.
Definición: Multigraph y Multigraph
Para algunos propósitos, podemos\(E\) permitir que sea un multiconjunto en lugar de un conjunto. Cuando hacemos esto, un elemento que aparece más de una vez en\(E\) se llama multi-edge o multiedge. Un gráfico que incluye al menos un borde múltiple se llama multígrafo.
Otra situación que nos gustaría permitir para algunos fines pero no permitir para otros, es la posibilidad de una conexión que vaya de un nodo de vuelta a sí mismo.
Definición: Bucle y Gráfica Simple
Un borde de la forma\(\{v, v\}\) para algunos\(v ∈ V\), se llama bucle.
Una gráfica simple es una gráfica que no tiene bucles ni múltiples aristas.
Para la mayor parte de la teoría gráfica que cubrimos en este curso, solo consideraremos gráficas simples. Sin embargo, hay algunos resultados para los que la prueba es idéntica tanto si la gráfica es simple como si no, y otros resultados que en realidad se vuelven más fáciles de probar si permitimos multígrafos y/o bucles, que si solo permitimos gráficas simples. Vale la pena y a veces importante pensar cuál de nuestros resultados se aplica a los multígrafos (y/o gráficas con bucles), y cuáles no. A partir de este punto, a menos que se especifique lo contrario, se debe asumir que cada vez que se utilice la palabra “graph”, significa una gráfica simple. Sin embargo, ten en cuenta que muchas de nuestras definiciones y resultados se generalizan a multígrafos y a gráficas o multígrafos con bucles, incluso donde no lo especifiquemos.
Todavía hay una terminología más básica que debemos establecer antes de poder decir mucho sobre una gráfica.
Definición: Endvertex
Si\(e = \{u, v\}\) es un borde de una gráfica (o un multígrafo, con o sin bucles), entonces decimos eso\(u\) y\(v\) son endvertices (singular: endvertex) de\(e\). Decimos que\(e\) es incidente con\(u\) y\(v\) (o viceversa, los vértices también son incidentes con el borde), y eso\(u\) y\(v\) son adyacentes ya que hay un borde que los une, o que\(u\) es vecino de \(v\).
Notación
Usamos la notación\(u ∼ v\) para denotar que\(u\) es adyacente a\(v\). También podemos denotar el borde\(e = \{u, v\}\) por\(uv\) o por\(vu\).
Después de una definición más, pasaremos por algunos ejemplos utilizando la terminología que hemos establecido.
Definición: Valencia y Vértice Aislado
Si\(v ∈ V\) es un vértice de una gráfica (simple o multi, con o sin bucles), entonces el número de veces\(v\) aparece como el vértice final de algún borde se llama la valencia de\(v\) in\(G\). (Muchas fuentes usan grado en lugar de valencia, pero la palabra grado tiene muchos significados en matemáticas, haciendo de la valencia un término preferible para esto). Un vértice de valencia\(0\) se llama vértice aislado.
Nota
En una gráfica sin bucles, podemos definir la valencia de cualquier vértice\(v\) como el número de aristas que inciden con\(v\). Para la mayoría de los propósitos, esta es una buena manera de pensar en la valencia. Sin embargo, cuando una gráfica tiene bucles, muchas fórmulas funcionan más bien si consideramos que cada bucle contribuye\(2\) a la valencia de su vértice final. Esto se ajusta a la definición que hemos dado, ya que un vértice\(v\) aparece dos veces como el vértice final de cualquier incidente de bucle con\(v\).
Notación
La valencia de\(v\) se denota por\(\text{val}(v)\) o\(\text{deg}(v)\) o\(d(v)\) o\(d_G(v)\).
Ejemplo\(\PageIndex{1}\)
En la Figura 11.2.2, los vértices son\(a\)\(b\),\(c\),\(A\),\(B\), y\(C\), y
\(E = \{\{a, A\}, \{a, B\}, \{a, C\}, \{b, A\}, \{b, B\}, \{b, C\}, \{c, A\}, \{c, B\}, \{c, C\}\}\).
¡Quizás ya puedas ver por qué la mayoría de la gente prefiere usar un diagrama en lugar de una lista de vértices y bordes para describir una gráfica!
El vértice a es adyacente a\(A\),\(B\) y\(C\). El vértice no\(C\) es adyacente a\(B\). El borde\(\{a, C\}\) es incidente con el vértice\(a\); el vértice\(C\) es también un vértice final de este borde. Cada vértice de esta gráfica tiene valencia\(3\), por lo que ninguno de los vértices está aislado. Se trata de una gráfica sencilla, ya que no tiene bucles ni múltiples aristas.
Aunque un diagrama es una forma conveniente y a menudo útil de visualizar una gráfica, es importante tener en cuenta que debido a que una gráfica está definida por los conjuntos\(V\) y\(E\), a menudo es posible dibujar una gráfica en particular de formas que se ven bastante diferentes. A pesar de los dibujos de aspecto diferente, siempre\(V\) y cuando y\(E\) sean iguales, la gráfica también es la misma. En la Figura 11.2.3, vemos dos dibujos diferentes de la gráfica dada por\(V = \{a, b, c, d\}\) y\(E = \{\{a, b\}, \{a, c\}, \{a, d\}, \{b, c\}, \{b, d\}, \{c, d\}\}\).
Ejemplo\(\PageIndex{2}\)
Deje que la gráfica\(G\) se defina por\(V = \{w, x, y, z\}\) y\(E = \{e_1, e_2\}\), dónde\(e_1 = \{w, x\}\) y\(e_2 = \{w, y\}\). No hay bucles ni múltiples aristas, por lo que\(G\) es una gráfica simple. El borde\(e_2\) tiene endvertices\(w\) y\(y\). El vértice\(w\) es incidente con ambos\(e_1\) y\(e_2\). Los vértices\(x\) y no\(y\) son adyacentes. El vértice\(z\) es un vértice aislado, ya que no tiene vecinos. El vértice\(y\) tiene sólo un vecino,\(w\). La valencia de\(w\) es\(2\). La valencia de\(x\) y la valencia de\(y\) son ambas\(1\). Al verificar todas estas declaraciones, dibujar un diagrama de la gráfica podría ayudarte.
Ejercicio\(\PageIndex{1}\)
Para cada una de las siguientes gráficas (que pueden o no ser simples, y pueden tener o no bucles), encuentra la valencia de cada vértice. Determinar si la gráfica es simple o no, y si hay algún vértice aislado. Enumere los vecinos de\(a\), y todos los bordes con los que\ (a es incidente.
- \(G\)Sea definido por\(V = \{a, b, c, d, e\}\) y\(E = \{e_1, e_2, e_3, e_4, e_5, e_6\}\) con\(e_1 = \{a, c\}\),\(e_2 = \{b, d\}\),\(e_3 = \{c, d\}\),\(e_4 = \{c, e\}\),\(e_5 = \{d, e\}\), y\(e_6 = \{e, e\}\).
- Dejar\(G\) ser definido por\(V = \{a, b, c\}\) y\(E = \{e_1, e_2, e_3\}\) con\(e_1 = \{a, b\}\),\(e_2 = \{a, c\}\), y\(e_3 = \{a, c\}\).
- Dejar\(G\) ser definido por\(V = \{a, b, c, d\}\) y\(E = \{e_1, e_2, e_3\}\) con\(e_1 = \{a, b\}\),\(e_2 = \{a, c\}\), y\(e_3 = \{b, c\}\).
Ejercicio\(\PageIndex{2}\)
- Dejar\(G\) ser la gráfica cuyos vértices son los subconjuntos\(2\) -elemento de\(\{1, 2, 3, 4, 5\}\), con vértices\(\{a, b\}\) y\(\{c, d\}\) adyacentes si y sólo si\(\{a, b\} ∩ \{c, d\} = ∅\). Empate\(G\).
- El número de aristas en el cubo\(k\) -dimensional\(Q_k\) (que es una estructura importante en el diseño de red, pero no es necesario conocer la estructura para resolver esto) se puede encontrar por la relación de recurrencia:
\(e(Q_0) = 0; e(Q_n) = 2e(Q_{n−1}) + 2^{n−1}\)para\(n ≥ 1\).
Utilice funciones de generación para resolver esta relación de recurrencia y, por lo tanto, determinar el número de aristas en el cubo\(k\) -dimensional