14.1: Conceptos básicos y ejemplos

Última actualización
Guardar como PDF

Page ID: 118021

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

Definición: gráfico (definición de trabajo)

un diagrama que consiste en una colección finita de puntos conectados por segmentos de línea o arcos

Ejemplo\(\PageIndex{1}\)

Supongamos que tenemos jarras\(A,B,C\) con capacidades\(8,5,3\) litros, respectivamente. \(A\)La jarra está llena de agua y las jarras\(B,C\) están vacías. ¿Podemos dividir el agua en dos partes exactamente iguales? Si es así, encuentra la secuencia de vertido más eficiente.

Solución

Construir una gráfica con puntos etiquetados por elementos\((a,b,c) \in \mathbb{N} \times \mathbb{N} \times \mathbb{N}\text{,}\) donde\(a,b,c\) están los volúmenes de agua en jarras\(A,B,C\text{,}\) respectivamente. Unir dos puntos con un segmento de línea si podemos obtener un conjunto de volúmenes del otro en un solo vertido. Ignoraremos los vertidos que nos devuelven a una configuración previamente alcanzable por menos vertidos.

Figura\(\PageIndex{1}\): Gráfica para rastrear posibles estados de llenado de jarra.

Siguiendo la pata izquierda de la gráfica nos lleva a la configuración deseada en\(7\) vertidos.

Definición: graph (definición formal)

un par ordenado\((V,E)\text{,}\) donde\(V\) es un conjunto finito y\(E\) es una lista finita, desordenada de subconjuntos de\(V\text{,}\) cada uno de los cuales tiene exactamente\(1\) o\(2\) elementos

Definición: Vertex

un punto en una gráfica (es decir, un elemento de\(V\))

Definición: Nodo

sinónimo de vértice

Definición: Edge

una línea o arco de conexión entre dos vértices (es decir, un elemento de\(E\))

Definición: Gráfico vacío

la gráfica\((\emptyset,\emptyset)\text{,}\) sin vértices y sin aristas

Advertencia\(\PageIndex{1}\)

La lista no\(E\) es un conjunto, ya que las entradas duplicadas en esta lista tienen un significado gráfico; ver abajo.

Un elemento\(e \in E\) representa una arista de la siguiente manera. Si\(e\) consiste en exactamente dos elementos de\(V\text{,}\) dibujar una línea entre estos dos vértices. Si\(e\) consiste en exactamente un elemento de\(V\text{,}\) dibujar una línea desde este vértice a sí mismo.

Ejemplo\(\PageIndex{2}\): A very basic graph.

La gráfica\(G = (V,E)\text{,}\) donde

\ begin {align*} V & =\ {v_1, v_2, v_3\}, & E & =\ bigl\ {\ {v_1, v_2\},\ {v_1, v_3\},\ {v_2, v_3\}\ bigr\},\ end {align*}
tiene tres vértices y tres aristas.

Figura\(\PageIndex{2}\): Diagrama de la gráfica\(G = (V,E)\text{.}\)

Ejemplo\(\PageIndex{3}\): A slightly more complicated example graph.

La gráfica\(G = (V,E)\text{,}\) donde

\ begin {align*} V & =\ {v_1, v_2, v_3, v_4\}, & E & =\ bigl\ {\ {v_1, v_2\},\ {v_1, v_2\},\ {v_1, v_2\},\ {v_3\},\ {v_3\}\ bigr\},\ end align*}
tiene cuatro vértices y cinco aristas.

Figura\(\PageIndex{3}\): Diagrama de la gráfica\(G = (V,E)\text{.}\)