A teoria dos grafos estudam objetos combinatórios abstratos, chamados grafos, que é usado em diversas áreas da Matemática, da Computação, da Engenharia e do Mercado para modelagem e resolução de problemas. Muitos desses problemas se tornaram,e ainda se tornam, famosos pela sua ampla aplicação e pela sua complexidade computacional, como o Problema da Fábrica de Tijolos, o Número de cores de um grafo, e, é claro,o clássico problema das Sete Pontes de Königsberg. Além desses problemas, há aqueles envolvendo a natureza do próprio grafo, como veremos mais adiante.

Na realidade, há inúmeros sistemas que podem ser representados através de grafos, pela sua representação abstrata muito flexível. Assim, podem ser usados para representar circuitos elétricos, na Física; redes de distribuição, na Otimização e na Indústria; redes sociais(não apenas pela internet); rede de estradas/voos entre cidades, além, é claro, das redes físicas e lógicas de computadores.

Como exemplos mais amplos, na Sociologia, os grafos podem ser utilizados na construção da representação de uma rede social complexa com ligações das mais diversas possíveis, como grupos de amizades, de trabalho, bem como grupos sociais. Para a internet e para a computação em geral, a utilização dos grafos é uma ótima maneira de apresentar determinados dados que deverão ser analisados cuidadosa e metodicamente. Ademais, a aplicação desta teoria é absurdamente valiosa, com uma rede que abrange quase todo o globo e com focos que servem para estudos sociais, econômicos e políticos, por exemplo.

Antes de descrevermos um grafo propriamente, porém, é importante deixar claro algumas coisas sobre um conjunto que iremos usar nesta descrição.

Agora, vamos aos grafos!

Um grafo $G = (V, A)$ é uma estrutura matemática composta por dois conjuntos, $V$ e $A$. $V$ é o conjunto arbitrário em que falamos acima, e $A ⊆ V^2$ , isto é, $A$ é subconjunto de $V$. Os elementos de $V$ são chamados vértices (ou nós) do grafo $G$, e os elementos de $A$ são suas arestas (ou linhas). Uma aresta como $\{v, w\}$ será denotada simplesmente por $vw$ ou por $wv$. Assim, os elementos de $A$ são subconjuntos de $2$ elementos de $V$.

O conjunto $A$ também pode ser representado pelo conjunto $E \subseteq V^2$(“edges”,do inglês, arestas), assim um grafo também pode ser representado como sendo $G=(V,E)$, assim $A=E$. Mais adiante faremos uso desta notação ao invés de $G=(V,A)$ por motivos práticos.

A figura ao lado ilustra um grafo simples, com 6 nós, ou vértices, representados pelas “bolinhas” numeradas, e 8 arestas, representadas pela ligação entre essas “bolinhas”.

Além disso, o grafo pode ser chamado como um todo, por conveniência. Se temos o grafo $G$, o conjunto dos seus vértices pode ser denotado por $V(G)$ e o conjunto de suas arestas por $A(G)$(ou por $E(G)$). Repare que no grafo ainda ao lado o conjunto $V(G) = \{0, 1, 2, 3, 4, 5\}$, e o conjunto $A(G) = \{\{0,4\}, \{0,5\}, \{1,4\}, \{1,5\}, \{2,0\}, \{2,3\}, \{2,4\}, \{4,5\}\}$.

Assim sendo, um grafo 'simples' não pode ter duas arestas diferentes com o mesmo par de pontas, ou seja, não pode ter arestas “paralelas”. Também não é possível um grafo simples ter uma aresta com pontas coincidentes, ou seja , não pode ter “laços”.

Com tudo isso, podemos escrever a seguinte definição:

Acima tratamos apenas do grafo não orientado, um grafo simples. Porém, existem também os grafos que possuem orientações nas arestas, conhecidos como grafos orientados, grafos direcionados ou apenas digrafos (sem acento mesmo, senão remete a outro grupo abstrato, só que da Língua Portuguesa).

O grafo $G$ ao lado é um exemplo de um digrafo, com $V(G) = \{0, 1, 2, 3, 4\}$ e $A(G) = \{(0, 1), (1, 3), (2, 0), (2, 3), (3, 0), (3, 4), (4, 0)\}$.

Para grafos orientados, o grau de entrada de um vértice é o número de arestas que chegam nele e denota-se por $d^-(v)$. O grau de saída é o número de arestas que partem do vértice em direção aos outros, denotado por $d^+(v)$.

Quando o grau de entrada é igual a zero, o vértice é chamado de fonte, e quando o grau de saída é igual a zero é chamado de sumidouro, ou sorvedouro.

Além da orientação, é possível atribuir custo para o vértice, para a aresta ou para ambos. O grafo que recebe esses valores são os grafos ponderados, como veremos mais adiante em Tipos Básicos de Grafos