1.2: Teoría de las Gráficas
- Page ID
- 114339
\( \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}}} \)
Cuando una matemática habla de teoría de grafos, no se refiere a los “gráficos” que aprendes en la escuela, que pueden ser producidos por una hoja de cálculo o una calculadora gráfica. Los “gráficos” que se estudian en teoría de grafos son modelos de redes.
Cualquier red se puede modelar usando puntos para representar los nodos de la red (las ciudades, computadoras, celulares, o lo que sea que se esté conectando) junto con líneas para representar las conexiones entre esos nodos (las carreteras, cables, conexiones inalámbricas, etc.). A este modelo se le llama gráfica. Es importante tener en cuenta que solo en un nodo puede pasar información, tráfico, etc. de un borde de una gráfica a otro borde. Si queremos modelar una red de carreteras usando una gráfica, y dos autopistas se cruzan en medio de la nada, aún debemos colocar un nodo en esa intersección. Si dibujamos una gráfica en la que los bordes se cruzan entre sí pero no hay ningún nodo en ese punto, deberías pensarlo como si ahí hubiera un paso elevado sin salidas de una autopista a otra: las carreteras pasan a cruzar, pero no están conectando en ningún sentido significativo.
Ejemplo\(\PageIndex{1}\)
El siguiente diagrama:
es una gráfica.
Muchas preguntas que tienen importantes aplicaciones del mundo real se pueden modelar con gráficos. Estas no siempre se limitan a preguntas que parecen aplicarse a las redes. Algunas preguntas se pueden modelar como gráficas usando líneas para representar restricciones o alguna otra relación entre ellas (por ejemplo, los nodos pueden representar clases, con una línea entre ellas si no se pueden programar al mismo tiempo, o algunos nodos pueden representar a estudiantes y otras clases, con una línea entre un estudiante y cada una de las clases que esté tomando).
Después de estudiar teoría de grafos en este curso, deberías ser capaz de resolver problemas como:
- ¿Cómo podemos encontrar una buena ruta para que los camiones de basura los lleven por una ciudad en particular?
- ¿Existe una ruta de entrega que visite cada ciudad de una zona en particular, sin repetición?
- Ante una colección de temas del proyecto y un grupo de estudiantes cada uno de los cuales ha expresado interés en algunos de los temas, ¿es posible asignar a cada alumno un tema único que le interese?
- Una ciudad tiene rutas de autobús todas las cuales comienzan y terminan en la terminal de autobuses, pero con horarios diferentes, algunos de los cuales se superponen. ¿Cuál es el menor número de autobuses (y conductores) requeridos para poder completar todas las rutas de acuerdo al horario?
- Crea un horario para un torneo de todos contra todos que utilice el menor número posible de franjas horarias.
Algunas de estas preguntas es posible que solo puedas responder para determinados tipos de gráficos.
La teoría gráfica es una rama relativamente “joven” de las matemáticas. Si bien algunos de los problemas e ideas que vamos a estudiar se remontan a unos cientos de años, no fue hasta la década de 1930 cuando estos problemas individuales se reunieron y comenzó a desarrollarse un estudio unificado de la teoría de las gráficas.