===== Grafos: Introdução e algumas Aplicações =====
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 [[.brickfactory | Problema da Fábrica de Tijolos]], o [[.numerdecores | Número de cores de um grafo]], e, é claro,o clássico problema das [[.historiaGrafos| 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.
=====Mas afinal, o que é um grafo?=====
Antes de descrevermos um grafo propriamente, porém, é importante deixar claro algumas coisas sobre um conjunto que iremos usar nesta descrição.
//Seja $V$ um conjunto qualquer, denotaremos por $V^2$ o conjunto de todos os pares não ordenados de elementos de $V$. Os elementos de $V^2$ serão identificados com os subconjuntos de $V$ que possuem cardinalidade 2, isto é, cada elemento de $V^2$ terá a forma $\{v,w\}$, sendo $v$ e $w$ dois elementos distintos de $V$.//
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.
{{:grafos:graph.png?200 |}}
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:
=== Definição===
//Um grafo (simples) $G$ consiste em um conjunto finito e não vazio $V(G)$ de objetos chamados vértices, juntamente com um conjunto $A(G) ($ou, equivalentemente, $E(G))$ de pares não ordenados de vértices; os elementos de $A(G)$ são chamados de arestas. Podemos representá-lo por $G = (V ; A) (G=(V,E))$, onde $V = V (G)$ e $A = A(G) ($ou, equivalentemente, $E=E(G))$.//
=== Definição: Ordem de um grafo===
//O número de vértices de um grafo $G$ é a sua **ordem**. Grafos são finitos, infinitos, contáveis e assim por diante de acordo com sua ordem.//
===== O que é isso? Grafos com setas? =====
{{:grafos:graph_2_.png?200 |}}
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 [[.tiposGrafos| Tipos Básicos de Grafos]]
=== Referências ===
* Gildson S. de Melo. [[https://repositorio.ufpb.br/jspui/bitstream/tede/7549/5/arquivototal.pdf|"Introdução à Teoria dos Grafos"]] .Universidade Federal da Paraíba- UFPB. Acesso em 16/09/2022.
* M. Cristina, et al. [[http://wiki.icmc.usp.br/images/a/a2/SCC603-2013-01-IntroducaoGrafos.pdf|"Introdução da Grafos"]] .Instituto de Ciências Matemáticas e da Computação(ICMC)2010-2013. Acesso em 16/09/2022.
* P. Feofiloff, Y. Kohayakawa, Y. Wakabayashi. [[https://www.ime.usp.br/~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf| "Uma Introdução Sucinta à Teoria dos Grafos"]] .2011. Acesso em 16/09/2022.
* Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf|“Graph Theory”]] .5th Electronic Edition 2016, pp. 01–03. Acesso em 16/09/2022.
* Valeriano A. de Oliveira, Socorro Rangel, Silvio A. de Araújo. [[https://www.ibilce.unesp.br/Home/Departamentos/MatematicaAplicada/docentes/socorro/grafosdirecionados.pdf|"Teoria dos Grafos: Grafos Direcionados"]] .2002-2013. Acesso em 16/09/2022.