Teoria dos gráficos é o estudo de pontos e linhas. Em particular, envolve as formas em que conjuntos de pontos, chamados vértices, podem ser conectados por linhas ou arcos, chamados bordas. Os gráficos neste contexto diferem dos gráficos de coordenadas mais familiares que retratam relações e funções matemáticas.
Gráficos são classificados de acordo com a sua complexidade, o número de arestas permitido entre quaisquer dois vértices, e se as direcções (por exemplo, para cima ou para baixo) são ou não atribuídas às arestas. Vários conjuntos de regras resultam em propriedades específicas que podem ser declaradas como teoremas.
A teoria do gráfico provou ser útil no projeto de circuitos integrados (ICs) para computadores e outros dispositivos eletrônicos. Estes componentes, mais frequentemente chamados de chip s, contêm microcircuitos complexos, em camadas, que podem ser representados como conjuntos de pontos interligados por linhas ou arcos. Usando a teoria gráfica, os engenheiros desenvolvem chips com densidade máxima de componentes e comprimento total mínimo do condutor de interconexão. Isto é importante para otimizar a velocidade de processamento e a eficiência elétrica.