grafos:tiposgrafos [WikiMat]

===== Tipos básicos de grafos =====

Há vários tipos de grafos, vamos enumerar alguns deles e apresentar algumas propriedades. Alguns, inclusive, já tiveram, ou terão sua própria documentação com uma descrição mais abrangente. Vamos começar pelos **Grafos Triviais.**

====Grafos Triviais====

<WRAP round box 90%>
=== Definição ===
//Um grafo trivial é um grafo no qual $G = (V ; \emptyset)$, ou seja, é um grafo que possui $n$ vértices, podendo ser representado por conjunto de $n$ pontos no plano, sem quaisquer arestas.//
</WRAP>

Assim sendo, um grafo de **ordem $0$ ou $1$** é chamado **grafo trivial**. Geralmente, por definição, tratamos os grafos triviais de forma despreziva, pois formam contra-exemplos bobos e se tornam um incomômdo, mas não se engane, em algumas situações, para iniciar uma indução,por exemplo, grafos triviais podem ser muito úteis. O grafo $G$ vazio pode ser representado somente por $G = \emptyset$.

==== Grafos Simples ====

Já falamos deste tipo de grafo e o usamos para apresentar uma definição em [[.definicaoGrafos| Definições de grafos]]. Relembremos:

<WRAP round box 100%>

=== Definição===
//Um grafo (simples) $G$ consiste de um conjunto finito e não vazio $V(G)$ de objetos chamados vértices, juntamente com um conjunto $A(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)$, onde $V = V (G)$ e $A = A(G)$.//
</WRAP>

Assim sendo, um grafo simples é um grafo não direcionado, não ponderado, que não possuem [[.loopsmultigraph |laços]] nem mais de uma aresta ligando dois vértices,isto é, sem arestas “paralelas”. Assim, um grafo simples é um grafo que não possui arestas múltiplas. Como ,por exemplo, o grafo abaixo:

{{ :grafos:grafo_1.png?250 |}}

==== Digrafos ====

Um **grafo orientado**, ou **digrafo**, são grafos com uma diferença fundamental em relação aos grafos simples: as arestas possuem uma direção. Isso muda muito a situação e o significado do grafo estudado. Além disso, há a possibilidade da existência de **arestas paralelas**, ou seja, as arestas incidem nos mesmos vértices e possuem a mesma orientação. Para tanto, podemos usar a seguinte definição:

<WRAP round box 100%>

=== Definição===
//Um grafo direcionado $G(V, A)$ é constituído por um conjunto $V = \{v_1, v_2, …, v_n\}$ não vazio de vértices, e um conjunto $A = \{a_1, a_2, …, a_n\}$ de arestas, e uma aplicação que associa cada arestas a um par ordenado de vértices.//
</WRAP>

O grafo abaixo é um exemplo de um digrafo. Repare que há arestas paralelas representadas por uma seta dupla, como por exemplo,$\{5, 3\}, \{3, 5\}$.

{{ :grafos:graph_10_.png?250 |}}

<WRAP tip round box 100%>
=== Nota ===
Quando um grafo possui mais de uma aresta interligando os mesmo dois vértices diz-se que este grafo possui arestas múltiplas(ou arestas paralelas). Ele é chamado de multigrafo ou grafo múltiplo. O grafo acima, observe, além de ser orientado, ele pode ser chamado de **multigrafo** também. Mas cuidado, nem todo grafo orientado pode ser dito multigrafo.

Em um multigrafo, se houver uma aresta $e$ de um grafo $G$ que possui o mesmo vértice como extremos, ou seja, $e = \{x,x\}$, então é dito que este grafo possui um **laço**. Observe que no exemplo a seguir o grafo possui um laço localizado no vértice $(1)$:

{{:grafos:graphs_7_.png?150 |}}
</WRAP>

==== Grafos Valorados, ou Ponderados ====

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 chamados **grafos ponderados**. Um grafo valorado $G(V,A)$ consiste de um conjunto finito não vazio de vértices $V$, ligados por um conjunto $A$ de arestas com pesos.

O conjunto $A$ consiste de triplas distintas da forma $(v,w, valor)$, em que $v$ e $w$ são vértices pertencentes a $V$ e $valor$ é um número real$(ℝ)$.

{{ :grafos:graph21.png?250 |}}

O grafo acima é um exemplo de grafo ponderado, com vértices $x, y,w ∈ V$, com as arestas $xy$, $xw$ e $yw$, recebendo os valores 5,9 e 4, respectivamente. Podemos também colocar valores para os vértices caso deja do nosso interesse, logo os valores de $x,y$ e $w$ são mutáveis.


====Grafos Completos ====

Um grafo completo é aquele em que todos os seus vértices são adjacentes aos pares, ou seja, existem arestas presentes entre todos os pares de vértices. Um grafo completo $K_n$ possui $$\frac{n(n-1)}{2}$$ arestas, como veremos mais a frente como um resultado do [[grafos:numtotaldearestas#corolario |corolário do Lema do Aperto de Mão]].

Abaixo um exemplo de grafo completo:

{{ :grafos:graph_11_.png?250 |}}

<WRAP tip round box 60%>
Material complementar em: [[.conexidad|Conexidade]].
</WRAP>
==== Grafos Conexos e Desconexos ====

<WRAP round box 80%>
=== Definição ===
//Um grafo é dito **conexo** se existir pelo menos um caminho entre cada par de vértices do grafo. Caso contrário, o grafo é chamado de **desconexo**.//
</WRAP>

O grafo abaixo por exemplo é um **grafo conexo:**

{{:grafos:graph_13_.png?300|}}

E o pŕoximo, é um exemplo de **grafo desconexo:**

{{:grafos:graph_14_.png?300|}}


----
<WRAP round info 100%>
=== Referências ===
  * [[https://www.inf.ufsc.br/grafos/definicoes/definicao.html | "Conceito Básicos da Teoria de Grafos"]]. Universidade Federal de Santa Catarina- UFSC. Acesso em 23/09/2022.
  * Elias de O. Boaventura. Eugenia B. O. Uribe. [[http://www.unoeste.br/site/enepe/2016/suplementos/area/Exactarum/Matem%C3%A1tica/ESTUDO%20SOBRE%20GRAFOS%20E%20ALGUMAS%20APLICA%C3%87%C3%95ES.pdf | "Estudo sobre grafos e algumas aplicações"]] . Universidade Federal de Mato Grosso do Sul – UFMS. Acesso em 23/09/2022.
  * M. Cristina, et al. [[http://wiki.icmc.usp.br/images/a/a2/SCC603-2013-01-IntroducaoGrafos.pdf | "Introdução a grafos"]] .Instituto de Ciências Matemáticas e da Computação- ICMC. Acesso em 23/09/2022.
  * Paulo Feofiloff. [[https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/graphs.html | "Grafos"]]. Instituto de Matemática e Estatística da Universidade de São Paulo- IME-USP. Acesso em 23/09/2022.
  * Samuel Jurkiewicz. [[http://www.obmep.org.br/docs/apostila5.pdf | "Grafos: uma Introdução"]] . Olimpíada Brasileira de Matemática das Escolas Públicas- OBMEP. Acesso em 23/09/2022.
  * Valeriano A. de Oliveira, Socorro Rangel, Silvio A. de Araújo.[[https://www.ibilce.unesp.br/Home/Departamentos/MatematicaAplicada/docentes/socorro/grafosconexos.pdf|"Teoria dos Grafos: Grafos Conexos"]] .2002-2013. Acesso em 16/09/2022.
</WRAP>