Teoría de grafos
En matemáticas , la teoría de grafos es el estudio de grafos , que son estructuras matemáticas que se utilizan para modelar relaciones por pares entre objetos. Un gráfico en este contexto está formado por vértices (también llamados nodos o puntos ) que están conectados por bordes (también llamados enlaces o líneas ). Se hace una distinción entre gráficos no dirigidos , donde los bordes enlazan dos vértices simétricamente, y gráficos dirigidos , donde los bordes enlazan dos vértices asimétricamente. Los gráficos son uno de los principales objetos de estudio de las matemáticas discretas .
Las definiciones en la teoría de grafos varían. Las siguientes son algunas de las formas más básicas de definir gráficos y estructuras matemáticas relacionadas .
En un sentido restringido pero muy común del término, [1] [2] un gráfico es un par ordenado que comprende:
En el borde , los vértices y se denominan puntos finales del borde. El borde se dice que se unen y ya sea incidente en y en . Un vértice puede existir en un gráfico y no pertenecer a una arista. Las aristas múltiples , no permitidas bajo la definición anterior, son dos o más aristas que unen los mismos dos vértices.
En un sentido más general del término que permite múltiples aristas, [3] [4] un gráfico es un triple ordenado que comprende:
Un bucle es una arista que une un vértice consigo mismo. Los gráficos como se definen en las dos definiciones anteriores no pueden tener bucles, porque un bucle que une un vértice consigo mismo es el borde (para un gráfico simple no dirigido) o es incidente (para un multigraph no dirigido) que no está dentro . Entonces, para permitir bucles, las definiciones deben expandirse. Para gráficos simples no dirigidos, la definición de debe modificarse a . Para multigrafías no dirigidas, la definición de debe modificarse a . Para evitar la ambigüedad, estos tipos de objetos pueden denominarse bucles de permiso de gráfico simple no dirigido y bucles de permiso de gráfico múltiple no dirigido , respectivamente.
