12.1: Gráficas dirigidas
- Page ID
- 114483
\( \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}}} \)
Algunas redes incluyen conexiones que solo permiten viajar en una dirección (caminos unidireccionales; transmisores que no son receptores, etc.). Estos se pueden modelar usando gráficas dirigidas.
Definición: Gráfica Dirigida
Una gráfica dirigida, o dígrafo para abreviar, consta de dos conjuntos:
\(V\), cuyos elementos son los vértices del dígrafo; y
\(A\), cuyos elementos son pares ordenados de\(V\), por lo
\[A ⊆ \{(v_1, v_2) | v_1, v_2 ∈ V \}.\]
Los elementos de\(A\) son referidos como los arcos del dígrafo.
Al dibujar un dígrafo, dibujamos una flecha en cada arco para que apunte desde el primer vértice del par ordenado hasta el segundo vértice.
Al igual que los multígrafos, no vamos a estudiar dígrafos en este curso, pero debes estar al tanto de la definición básica. Muchos de los resultados que cubriremos en este curso, se generalizan al contexto de los dígrafos.
Ejemplo\(\PageIndex{1}\)
Un dígrafo.
Daremos un ejemplo de generalización de un resultado en gráficas, al contexto de dígrafos. Para ello, necesitamos una definición.
Definición: Word
La outvalencia o outdegree de un vértice\(v\) en un dígrafo es el número de arcos cuya primera entrada es\(v\), i.e.
\[ |\{w ∈ V | (v, w) ∈ A\}|. \]
La invalencia o indegrana de un vértice\(v\) en un dígrafo es el número de arcos cuya segunda entrada es\(v\).
Notación
La outvalencia del vértice\(v\) se denota por\(d^+(v)\). La invalencia del vértice\(v\) se denota por\(d^−(v)\).
Lema\(\PageIndex{1}\): Euler's Handshaking Lemma For Digraphs
Para cualquier dígrafo,
\[\sum_{v∈V} d^+(v) = \sum_{v∈V} d^-(v) = |A|. \]
- Prueba
-
Para el lado izquierdo de la ecuación, en cada vértice contamos el número de arcos que comienzan en ese vértice. Como cada uno de estos arcos termina en algún vértice, obtenemos el mismo resultado en la parte media de la ecuación, donde en cada vértice contamos el número de arcos que terminan en ese vértice. En cada caso, hemos contado cada arco precisamente una vez, por lo que ambos valores son iguales al lado derecho de la ecuación, el número de arcos en el dígrafo.
Ejercicio\(\PageIndex{1}\)
- Utilice la inducción para probar el lema de apretón de manos de Euler para dígrafos que no tienen bucles (arcos de la forma (\(v\),\(v\)) o multiarcos (más de un arco de algún vértice\(u\) a otro vértice\(v\)).
- Un isomorfismo dígrafo es una biyección en los vértices que preserva los arcos. Llegar con un dígrafo invariante, y demostrar que es un invariante.
- Enumere el grado y grado de grado de cada vértice del dígrafo del Ejemplo 12.1.1