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 a las personas en una fiesta, y existe una arista entre dos personas si se dan la mano, entonces este gráfico está sin dirección, ya que cualquier persona A puede estrechar la mano de una persona B sólo si B también da la mano a una . 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. El primer tipo de gráfico se llama gráfico no dirigido, mientras que el último tipo de gráfico se llama gráfico dirigido .
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.
