Gráfico (matemáticas discretas)
En matemáticas , y más específicamente en teoría de grafos , un gráfico es una estructura que equivale a un conjunto de objetos en los que algunos pares de objetos están en algún sentido "relacionados". Los objetos corresponden a abstracciones matemáticas llamadas vértices (también llamados nodos o puntos ) y cada uno de los pares de vértices relacionados se llama arista (también llamado enlace o línea ). [1] Por lo general, un gráfico se representa en forma de diagramacomo un conjunto de puntos o círculos para los vértices, unidos por líneas o curvas para los bordes. Los gráficos son uno de los objetos de estudio de las matemáticas discretas .
Los bordes pueden ser dirigidos o no dirigidos. Por ejemplo, si los vértices representan personas en una fiesta y hay un borde entre dos personas si se dan la mano , entonces este gráfico no está dirigido porque cualquier persona A puede darle la mano a una persona B solo si B también le da la mano a A. Por el contrario, si cualquier arista de una persona A a una persona B corresponde a que A le debe dinero a B , entonces este gráfico es dirigido, porque la deuda no es necesariamente recíproca.
Los grafos son el tema básico estudiado por la teoría de grafos . La palabra "gráfico" fue utilizada por primera vez en este sentido por JJ Sylvester en 1878 en una relación directa entre las matemáticas y la estructura química (lo que él llamó imagen químico-gráfica). [2] [3]
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 .
Un grafo (a veces llamado grafo no dirigido para distinguirlo de un grafo dirigido , o grafo simple para distinguirlo de un multigrafo ) [4] [5] es un par G = ( V , E ) , donde V es un conjunto cuyos elementos se llaman vértices (singular: vértice), y E es un conjunto de vértices apareados, cuyos elementos se llaman aristas (a veces enlaces o líneas ).
Los vértices x e y de una arista { x , y } se denominan extremos de la arista. Se dice que la arista une x e y y que incide sobre x e y . Un vértice puede no pertenecer a ninguna arista, en cuyo caso no está unido a ningún otro vértice.
