Es una estructura discreta que consiste de vértices (representados por puntos) y aristas (segmentos de recta que unen dos vértices). La metáfora originaria es el poliedro. Desde el punto de vista de aplicaciones, los grafos son útiles para modelar relaciones entre pares de elementos de un conjunto discreto. En un poliedro la relación entre vértices es de adyacencia: dos vértices son adyacentes si están unidos por (son los extremos de) una arista.
Nota: A los vértices de un grafo se les llama también nodos y a las aristas también se les llama arcos. Ver mi post grafos --y la modelación de relaciones.
Nota 2: A un grafo se le llama también gráfica, un término que es la traducción directa de graph. En español se prefiere grafo para que no se confunda con la gráfica de una función. Sin embargo, la terminología no está unificada --ni siquiera en inglés.