Glosario

Seleccione una de las palabras clave de la izquierda ...

Gráficos y RedesIntroducción

Tiempo de leer: ~10 min

Todos los días estamos rodeados de innumerables conexiones y redes: carreteras y vías férreas, líneas telefónicas, Internet, circuitos electrónicos e incluso enlaces moleculares. Incluso hay redes sociales entre amigos y familiares. ¿Se te ocurren otros ejemplos?

Redes de carreteras y ferrocarriles

Chips de ordenador

Cadenas de suministro

Amistades

Conexiones neuronales

La Internet

En matemáticas, todos estos ejemplos pueden representarse como gráficos (no confundir con el gráfico de una función). Un gráfico consta de ciertos puntos llamados , algunos de los cuales están conectados por .

La teoría de grafos es el estudio de los grafos y sus propiedades. Es una de las áreas más emocionantes y visuales de las matemáticas, y tiene innumerables aplicaciones importantes.

Podemos dibujar el diseño de gráficos simples usando círculos y líneas. La posición de los vértices y la longitud de los bordes es irrelevante: solo nos importa cómo están conectados entre sí. Los bordes incluso pueden cruzarse entre sí, y no tienen que ser rectos.

En algunos gráficos, los bordes solo van en una dirección. Estos se llaman gráficos dirigidos .

Algunos gráficos consisten en múltiples grupos de vértices que no están conectados entre sí por bordes. Estos gráficos están desconectados .

Otros gráficos pueden contener múltiples aristas entre los mismos pares de vértices, o vértices que están conectados entre sí (bucles).

Podemos crear nuevos gráficos a partir de un gráfico existente eliminando algunos de los vértices y bordes. El resultado se llama subgrafo . Aquí puede ver algunos ejemplos más de gráficos, con bordes y vértices de colores que indican un posible subgrafo:

Decimos que el orden de un gráfico es el número de vértices que tiene. El grado de un vértice es el número de aristas que se encuentran en ese vértice.

Orden:

Orden:

Grado:

Grado:

Los gráficos que consisten en un solo bucle de vértices se denominan ciclos . Todos los ciclos tienen .

Equipado con estas nuevas definiciones, exploremos algunas de las fascinantes propiedades y aplicaciones de los gráficos.