Actualizado por ultima vez el 18 de octubre de 2022, por Luis Benites.
La teoría de grafos es el estudio de líneas y puntos.
Es un subcampo de las matemáticas que se ocupa de los gráficos: diagramas que involucran puntos y líneas y que a menudo representan pictóricamente verdades matemáticas. La teoría de grafos es el estudio de la relación entre aristas y vértices . Formalmente, un grafo es un par (V, E), donde V es un conjunto finito de vértices y E un conjunto finito de aristas.
Un árbol de expansión mínimo. Los bordes forman líneas rectas entre los vértices (nodos).
Definiciones en teoría de grafos
La teoría de grafos tiene un vocabulario único:
- Un arco es una línea dirigida (un par de vértices ordenados).
- Una arista es la línea que une un par de nodos.
- Los bordes incidentes son bordes que comparten un vértice. Una arista y un vértice son incidentes si la arista conecta el vértice con otro.
- Un bucle es una arista o arco que une un vértice consigo mismo.
- Un vértice , a veces llamado nodo , es un punto o un círculo. Es la unidad fundamental a partir de la cual se realizan los gráficos.
- Los vértices adyacentes son vértices que están conectados por un borde.
- El grado de un vértice es simplemente el número de aristas que se conectan a ese vértice. Los bucles cuentan dos veces.
- Un predecesor es el nodo (vértice) antes de un vértice dado en un camino.
- Un sucesor es el nodo (vértice) que sigue a un vértice dado en un camino.
- Un paseo es una serie de vértices y aristas.
- Un circuito es un paseo cerrado con cada borde distinto.
- Un paseo cerrado es un paseo desde un vértice hacia sí mismo; una serie de vértices y aristas que comienza y termina en el mismo lugar.
- Un ciclo es una caminata cerrada sin vértices repetidos (excepto que el primer y el último vértice son iguales).
- Un camino es un paseo donde no se repiten los vértices. Un camino uv es un camino que comienza en u y termina en v.
- Una caminata uv sería una caminata que comienza en u y termina en v.
Más definiciones:
- Una contracción de borde implica eliminar un borde de un gráfico fusionando los dos vértices que solía unir.
- En informática y teoría de gráficos basada en computadora, un recorrido de gráfico es una exploración de un gráfico en el que los vértices se visitan o actualizan uno por uno.
- Un ciclo hamiltoniano es un ciclo cerrado en el que cada nodo se visita exactamente una vez.
Tipos de gráficos
- Un gráfico dirigido acíclico es un gráfico dirigido finito que no tiene ciclos dirigidos.
- Un gráfico dirigido es un gráfico donde los bordes tienen dirección; es decir, son pares ordenados de vértices.
- Una condensación de un multigrafo es el gráfico que resulta cuando eliminas cualquier arista múltiple, dejando solo una arista entre dos puntos cualesquiera.
- Si un grafo tiene un camino entre cada par de vértices (no hay vértice que no esté conectado con una arista), el grafo se llama grafo conexo .
- Si un grafo G’ puede construirse a partir de un grafo G mediante contracciones o eliminaciones de bordes repetidas, el grafo G’ es un grafo menor de G.
- Un grafo invertido G’ de G es un grafo con los mismos vértices pero ninguno de los mismos bordes; dos vértices en G’ son adyacentes si y solo si no lo eran en G.
- Un multigrafo es un grafo sin bucles, pero que puede tener múltiples aristas.
- Un gráfico nulo es un gráfico sin bordes. Puede tener uno o más vértices.
- Un gráfico orientado es un gráfico dirigido que no tiene pares simétricos de aristas dirigidas.
- Un gráfico simple es un gráfico que no tiene bucles ni aristas múltiples. Sin múltiples aristas significa que no hay dos aristas que tengan los mismos puntos finales.
- Un subgrafo es un grafo cuyos vértices y aristas están incluidos en los vértices y aristas de otro grafo (el supergrafo ).
- Un grafo simétrico es un grafo dirigido D donde, para cada arco (x,y), el arco invertido (y,x) también está en D.
- Un grafo trivial es un grafo con un solo vértice.
- Un gráfico no dirigido es un gráfico donde ninguno de los bordes tiene dirección; los pares de vértices que forman cada arista están desordenados.
Teoría de grafos en la historia
La Teoría de Grafos se remonta a 1735 y los Siete Puentes de Königsberg de Euler . La ciudad de Königsberg era un pueblo con dos islas, conectadas entre sí y con el continente por siete puentes. La pregunta planteada era si era posible dar un paseo y cruzar cada puente exactamente una vez. En una primera demostración de la teoría de grafos, Euler demostró que no era posible.
De: ‘Solutio problematis ad geometriam situs pertinentis’, Eneström 53 [fuente: MAA Euler Archive ]
Teorema de Mantel
El teorema de Mantel, publicado en 1907, nos dice el mayor número de aristas que puede tener un grafo con un número dado de vértices sin tener un triángulo por subgrafo. Se puede afirmar como:
Un grafo con n vértices y m aristas contendrá un triángulo como subgrafo si y solo si m > n 2/4 .
Artículos relacionados
Árboles binarios.
El problema del viajante de comercio .
Referencias
Introducción a la Combinatoria y la Teoría de Grafos. Recuperado el 11/8/2017 de: https://www.whitman.edu/mathematics/cgt_online/cgt.pdf
Teorema de Turan
Matemáticas de bioinformática
