A Teoria dos Grafos é a área da matemática que estuda as relações entre objetos, ou seja, é através desse ramo que abstraímos a ideia comum existente por trás de problemas como, por exemplo, gerenciar as fronteiras de regiões em mapas, estabelecer uma comunicação eficiente entre torres de rádio, determinar os elementos de uma população de pessoas para serem vacinados contra uma doença contagiosa, descobrir o trajeto mais curto para realizar diversas entregas, estudar o alcance de uma notícia através das relações de amizade em redes sociais como o Facebook, criar uma rede inteligente de conexão entre computadores, dentre vários outros exemplos. A ideia existente por trás de todas essas relações é formalizada através do que chamamos de grafos. Um grafo é uma estrutura algébrica formada por dois conjuntos, sendo um desses chamado de conjunto de vértices do grafo, denotado por V, e o outro chamado de conjunto de arestas do grafo, denotado por E. Para determinarmos um grafo G = (V, E) é necessário que o conjunto de arestas E esteja contido no conjunto formado pelos pares não ordenados de V, ou seja, uma aresta é um par não ordenado de vértices. Tal maneira de construir arestas é justamente o que estabelece se dois vértices de V estão ou não relacionados entre si. É muito comum que os grafos sejam representados de maneira gráfica, ou seja, por meio de uma ilustração (desenho) em um plano no qual os vértices de V são representados por pontos e as arestas de E são representadas por linhas que ligam ou não pares de pontos. Tal ilustração é chamada de desenho do grafo. Devido à existência de redes de conexão mais elaboradas, outras vertentes de grafos surgiram. Ao considerarmos as arestas como sendo pares ordenados ao invés de não ordenados, estamos informando que cada aresta possui uma orientação, dizendo assim que um vértice x pode estar relacionado a um vértice y sem que y esteja relacionado com x, e nesse caso estaremos falando de um digrafo. Se permitirmos que as arestas sejam formadas por dois vértices iguais, então estaremos permitindo o que é chamado de looping, ou seja, um vértice que está relacionado com ele mesmo. Se as arestas conectarem mais vértices, como cinco ou oito, então estaremos falando de um hipergrafo. Existem diversos grafos que, por estarem presentes na construção e resolução de diversos problemas, recebem um nome e uma notação especial. A seguir alguns exemplos de grafos bem conhecidos serão descritos. É chamado de caminho um grafo cujos vértices podem ser enumerados de modo que o primeiro está conectado ao segundo, que está conectado ao terceiro, que está conectado ao quarto, e assim por diante até o último. Se em um caminho adicionarmos uma aresta conectando o último vértice ao primeiro, então o grafo obtido é chamado de ciclo. Chamamos de grafo completo aquele em que quaisquer dois de seus vértices constituem uma aresta. Além de grafos muito conhecidos, há também algumas classificações importantes que são consideradas em grafos. Dizemos que um grafo é bipartido se for possível particionar seu conjunto de vértices em duas classes de modo que dois vértices de mesma classe nunca formem uma aresta. Dizemos que um grafo é planar se for possível estabelecer um desenho do grafo sem que arestas se cruzem. Classificamos um grafo como conexo quando quaisquer dois de seus vértices são extremidades de um caminho, que conecta esses dois vértices. Diversos resultados são bem conhecidos em grafos e respondem muitas das questões envolvendo os problemas descritos acima. São conhecidas, por exemplo, as condições necessárias e suficientes para um grafo ser planar, ou para ser possível percorrer os vértices do grafo sem repetir aresta. Já se sabe também qual é o número mínimo de vértices que deve ser removido de um grafo para desconectá-lo. Apesar dos muitos resultados existentes, a Teoria dos Grafos é uma área que ainda está em grande crescimento no meio científico, tendo assim muitos problemas em aberto a serem investigados.