Grafos

Introdução

Um grafo é uma estrutura matemática usada para representar as relações entre as coisas, para facilitar sua visualização e sua compreensão, grafos são representados graficamente eles tem diversas aplicações e pode nos ajudar a resolver problemas práticos.
Este trabalho formaliza a definição de grafos, desde seus primeiros resultados, também mostra conceitos básicos, suas representações geométricas e exemplos de aplicação. Fala também sobre complementos , representação com matrizes e coloração de grafos e dígrafo (ou um grafo dirigido).

GRAFOS

O artigo de Leonhard Euler, publicado em 1736, sobre o problema das sete pontes de Königsberg, é considerado o primeiro resultado da teoria dos grafos. É também considerado um dos primeiros resultados topológicos na geometria; isto é, não dependente de quaisquer medidas. Isso ilustra a profunda conexão entre a teoria dos grafos e topologia.

1. Definição

Antes de mais nada, vamos tentar entender o que é um grafo. Um grafo é uma estrutura matemática usada para representar as relações entre as coisas.
Essas "coisas" que se relacionam entre si são chamados de nós do grafo. Cada relacionamento entre os nós é chamado de aresta. Normalmente, para facilitar sua visualização e sua compreensão, grafos são representados graficamente. Não confunda as duas palavras! Grafos são entidades matemáticas, abstratas, que possuem nós (coisas) e arestas (relacionamento entre essas coisas). Gráficos são imagens. Grafos podem ser representados graficamente, mas o grafo não é a sua representação gráfica - existem várias outras maneiras de representar grafos que não graficamente.
Um grafo é um tipo especial de dígrafo, também conhecido como grafo não-dirigido e grafo não-orientado. Um grafo é um dígrafo simétrico. Os arcos de um grafo andam aos pares: cada arco v-w é acompanhado do arco w-v.
Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio e