Teoria dos grafos

Question book-4.svg
Esta página ou secção cita fontes confiáveis e independentes, mas que não cobrem todo o conteúdo, comprometendo a sua verificabilidade(desde Agosto de 2013). Por favor, mais referências inserindo-as no texto. Material sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)
Ambox rewrite.svg
Esta página precisa ser reciclada de acordo com o livro de estilo (desde fevereiro de 2013).
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.
Grafo com quatro vértices e 6 arestas. É um grafo completo, conexo e planar.

A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal são empregadas estruturas chamadas de grafos, G(V,E), onde V é um conjunto não vazio de objetos denominados vértices e E é um subconjunto de pares não ordenados de V, chamados arestas.

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 vértices e/ou arestas podem ter um peso (numérico) associado. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um dígrafo (grafo orientado). Um grafo com um único vértice e sem arestas é conhecido como grafo trivial.

Estruturas que podem ser representadas por grafos estão em toda parte e muitos problemas de interesse prático podem ser formulados como questões sobre certos grafos. Por exemplo, a estrutura de ligações da Wikipédia pode ser representada por um dígrafo: os vértices são os artigos da Wikipédia e existe uma aresta do artigo A para o artigo B se e somente se A contém um link para B. Dígrafos são também usados para representar máquinas de estado finito. O desenvolvimento de algoritmos para manipular grafos é um tema importante da ciência da computação.

Histórico

O problema das pontes de Königsberg

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. [1] É 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.

Mais de um século após a publicação do artigo de Euler sobre as pontes de Königsberg e enquanto Listing introduzia o conceito de topologia, Cayley foi levado por um interesse em formas analíticas particulares decorrentes do cálculo diferencial para estudar uma classe particular de grafos, as árvores [2]. Esse estudo teve diversas implicações na química teórica. As técnicas usadas por ele eram relacionadas a enumeração de grafos com propriedades particulares.

O primeiro livro didático sobre teoria dos grafos foi escrito por Dénes König e publicado em 1936 [3].

Um dos problemas mais conhecidos em teoria dos grafos é problema das quatro cores: "É possível que qualquer mapa desenhado num plano, dividido em regiões, possa ser colorido com apenas quatro cores de tal forma que as regiões vizinhas não partilhem a mesma cor?". O primeiro a notar o problema das quatro cores foi August Ferdinand Möbius em 1840. Em 1852, Francis Guthrie escreveu em uma carta para seu irmão Frederick, estudante na University College London, sobre o problema. Mas nenhum deles conseguiu resovê-lo. Então Frederick perguntou a um de seus professores, DeMorgan [4].

En otros idiomas
አማርኛ: ሥነ ግራፍ
беларуская: Тэорыя графаў
čeština: Teorie grafů
dansk: Grafteori
Ελληνικά: Θεωρία γράφων
English: Graph theory
Esperanto: Grafeteorio
euskara: Grafo teoria
Bahasa Indonesia: Teori graf
íslenska: Netafræði
日本語: グラフ理論
한국어: 그래프 이론
lietuvių: Grafų teorija
latviešu: Grafu teorija
монгол: Графын онол
Bahasa Melayu: Teori graf
Nederlands: Grafentheorie
norsk nynorsk: Grafteori
norsk: Grafteori
sicilianu: Tiuria dî grafi
srpskohrvatski / српскохрватски: Teorija grafova
Simple English: Graph theory
slovenčina: Teória grafov
slovenščina: Teorija grafov
српски / srpski: Теорија графова
svenska: Grafteori
Türkçe: Çizge teorisi
українська: Теорія графів
Tiếng Việt: Lý thuyết đồ thị
中文: 图论
粵語: 圖論