6.1: Teoría gráfica

Última actualización
Guardar como PDF

Page ID: 109949

Maxie Inigo, Jennifer Jameson, Kathryn Kozak, Maya Lanzetta, & Kim Sonier
Coconino Community College

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

Existen varias definiciones que son importantes de entender antes de ahondar en la Teoría de los Grafos. Ellos son:

Una gráfica es una imagen de puntos llamados vértices y líneas llamadas bordes.
Un borde que comienza y termina en el mismo vértice se llama bucle.
Si hay dos o más aristas que conectan directamente los mismos dos vértices, entonces estos bordes se denominan múltiples aristas.
Si hay una manera de llegar de un vértice de una gráfica a todos los demás vértices de la gráfica, entonces la gráfica está conectada.
Si hay incluso un vértice de una gráfica al que no se puede alcanzar desde cualquier otro vértice, entonces la gráfica se desconecta.

Ejemplo\(\PageIndex{1}\): Graph Example

En la gráfica anterior, los vértices son U, V, W y Z y los bordes son UV, VV, VW, UW, WZ1 y WZ2.

Esta es una gráfica conectada. VV es un bucle. WZ1 y WZ2 son múltiples aristas.

Ejemplo\(\PageIndex{2}\): Graph Example

Figura\(\PageIndex{2}\): Gráfica 2 **Figura\(\PageIndex{3}\): Gráfica 3**

La gráfica de la Figura\(\PageIndex{2}\) está conectada mientras que la gráfica de la Figura\(\PageIndex{3}\) está desconectada.

Definición: Conceptos y Terminología Gráfica

Orden de una Red: el número de vértices en toda la red o gráfica
Vértices adyacentes: dos vértices que están conectados por una arista
Bordes adyacentes: dos aristas que comparten un vértice común
Grado de un vértice: el número de aristas en ese vértice
Trayectoria: una secuencia de vértices con cada vértice adyacente al siguiente que comienza y termina en diferentes vértices y viaja sobre cualquier borde solo una vez
Circuito: un camino que inicia y termina en el mismo vértice
Puente: un borde tal que si se eliminara de una gráfica conectada, la gráfica se desconectaría

Ejemplo\(\PageIndex{3}\): Graph Terminology

En la gráfica anterior es cierto lo siguiente:

El vértice A es adyacente al vértice B, al vértice C, al vértice D y al vértice E.
El vértice F es adyacente al vértice C y al vértice D.
Edge DF es adyacente al borde BD, borde AD, borde CF y borde DE.

Los grados de los vértices:

A	4
B	4
C	4
D	4
E	4
F	2

Aquí hay algunos caminos en la gráfica anterior: (hay muchos más que listados)

A, B, D

A, B, C, E

F, D, E, B, C

Aquí hay algunos circuitos en la gráfica anterior: (hay muchos más que listados)

B, A, D, B

B, C, F, D, B

F, C, E, D, F

La gráfica anterior no tiene puentes.