===== Adjacência =====

<WRAP round box 100%>
=== Definição ===
//Seja $G$ um grafo simples, dois vértices $x$ e $y$ são **adjacentes**, ou **vizinhos**, se $\{ x,y \}$ é uma aresta de $G$. Tal aresta é dita //**incidente**// a ambos, $x$ e $y$. Além, duas arestas $e \neq f$ são adjacentes se possuem um extremos em comum.//
</WRAP>

{{:grafos:graph_5_.png?200 |}}


Na figura ao lado temos que os vertices $0$ e $1$ são adjacentes. A aresta que os liga, denotada por $a$ diz-se **incidente** de cada um desses vértices.

Os vértices ou arestas não adjacentes aos pares são chamados de **independentes**. 

Formalmente, temos que um conjunto de vértices ou de arestas é independente se não houver dois de seus elementos adjacentes. Os [[.conjuntoindependente| conjuntos independentes]] de vértices também são chamados de **conjuntos estáveis.**

Se todos os vértices de $G$ são adjacentes aos pares, $G$ é dito [[.defCompleto|completo]]. Esses grafos são designados por $K^{n}$ , onde $n$ é a ordem do grafo. A título de curiosidade um grafo de ordem $3 (K^{3})$ é chamado de **triângulo**.

----


===== Está ficando um pouco quente, não? Grafo tem grau? =====

{{:grafos:graph_1_.png?200 |}}


Brincadeiras a parte, uma das informação mais importantes e útil sobre um grafo é o [[.grauV| grau de um vértice]]. Seja $G$ um grafo ,  definimos o grau, **//degree//** do inglês,  de um vértice $v$ de $G$ como a **quantidade de arestas que incidem nele**, e denotamos tal quantidade como $d(v)$.

O vertice $(1)$ presente no grafo ao lado, por exemplo, tem duas arestas incidentes, portanto seu grau é $2$. Os vértices $0$ e $2$ tem apenas uma aresta incidente cada, sendo assim, ambos são de grau $1$. 

Dessa forma, o [[.grauMaximo| grau máximo]] do grafo é $2$ e o [[.grauMinimo| grau mínimo]] deste é $1$.

A **ordem** de um grafo $G$ é dada pela cardinalidade do conjunto de vértices $|V(G)|$, ou seja, pelo número de vértices de $G$. Além disso, o número de arestas de um grafo é dado por $|A(G)|$.

**OBS:** Um grafo é dito ser [[.karegular | regular]] quando todos os seus vértices têm o mesmo grau.

<WRAP round tip box 100%>
=== Veja também: ===

[[.grauMedio| Grau médio]] de um grafo.
</WRAP>
----

<WRAP round info 100%>
=== 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.
</WRAP>