2.6: Gráficas

Última actualización
Guardar como PDF

Page ID: 103767

\( \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:MathJaxZach

Un gráfico es un diagrama en el que los puntos, llamados “nodos” o “vértices” (plural de “vértice”), están conectados por bordes. Las gráficas son una herramienta omnipresente en las matemáticas discretas y en la informática. Son increíblemente útiles para representar, y visualizar, relaciones y estructuras, desde cosas concretas como redes de diversa índole hasta estructuras abstractas como los posibles resultados de las decisiones. Hay muchos tipos diferentes de gráficos en la literatura que difieren, por ejemplo, según si los bordes están dirigidos o no, tienen etiquetas o no, si puede haber bordes de un nodo al mismo nodo, múltiples bordes entre los mismos nodos, etc. Las gráficas dirigidas tienen una conexión especial con relaciones.

Definición\(\PageIndex{1}\): Directed graph

Una gráfica dirigida\(G = \tuple{V, E}\) es un conjunto de vértices\(V\) y un conjunto de aristas\(E \subseteq V^2\).

Según nuestra definición, una gráfica solo es un conjunto junto con una relación sobre ese conjunto. Por supuesto, cuando se habla de gráficas, es natural esperar que estén representadas gráficamente: podemos dibujar una gráfica conectando dos vértices\(v_1\) y\(v_2\) por una flecha iff\(\tuple{v_1, v_2} \in E\). La única diferencia entre una relación por sí misma y una gráfica es que una gráfica especifica el conjunto de vértices, es decir, una gráfica puede tener vértices aislados. El punto importante, sin embargo, es que cada relación\(R\) en un conjunto\(X\) puede verse como una gráfica dirigida\(\tuple{X, R}\), y a la inversa, una gráfica dirigida\(\tuple{V, E}\) puede verse como una relación\(E \subseteq V^2\) con el conjunto \(V\)especificado explícitamente.

Ejemplo\(\PageIndex{1}\)

La gráfica\(\tuple{V, E}\) con\(V = \{1, 2, 3, 4\}\) y\(E = \{\tuple{1,1}, \tuple{1, 2}, \tuple{1, 3}, \tuple{2, 3}\}\) se ve así:

2.6.1_gráfico.png

Esta es una gráfica diferente a\(\tuple{V', E}\) con\(V' = \{1, 2, 3\}\), que se ve así:

2.6.2_gráfico.png

Problema\(\PageIndex{1}\)

Considera la relación menor o igual\(\le\) en el conjunto\(\{1, 2, 3, 4\}\) como gráfica y dibuja el diagrama correspondiente.