Please enable / Bitte aktiviere JavaScript!
Veuillez activer / Por favor activa el Javascript![ ? ]

Teoria dos Grafos: Conceitos Iniciais



Grafo

Estrutura matemática que busca expressar, de forma abstrata e discretizada, um conjunto de entidades e suas relações.

Grafos são formados por dois componentes básicos:

  • Nó ou vértice: que é o elemento de interesse a ser descrito pelo grafo.
  • Arco ou aresta: ligação entre dois vértices.  Uma aresta pode ter direção ou não.

Exemplo de um grafo onde A, B, C, D, E são os vértices, conectados por arestas não-direcionadas.


Para quê serve o uso de grafos ? 

Para expressar e compreender a relação entre elementos de interesse com relacionamentos. Exemplos incluem:

  • Uma empresa ou organização, onde os vértices podem ser pessoas ou departamentos e as arestas as relações de subordinação.
  • Uma rede social, onde os vértices representam as pessoas e as arestas apresentam as relações de amizade.
  • Um conjunto de lugares, onde as arestas representam os caminhos entre os lugares.

Definição formal

Chamaremos de \(V\) ao conjunto dos vértices.

Chamaremos de \(E\) ao conjunto das arestas.

Se dois vértices \(v\) e  \(w\) em  \(V\) estão relacionados, existe uma aresta pertencente a  \(E\) que é  descrita como \((v, w)\)[/latex].

Um grafo é, assim, representado como \(G=(V,E)\).


Conceitos relacionados

  • Ordem: número de vértices que o grafo possui.
  • Tamanho: número de arestas que o grafo possui.

Por exemplo, em:

Teremos um grafo de ordem 5 (os vértices A, B, C, D e E) e tamanho 5 (as arestas entre os vértices).

  • Grafo complementar: o grafo complementar \(G^c\) é o grafo que contém as arestas que não estão no grafo \(G\).
  • Subgrafo: é um grafo que está contido em outro grafo.
  • Vizinho: um vértice é vizinho de outro se há uma aresta que o ligue a este vértice.

Representação de grafos

Grafos podem ser representados sob diversas formas:

Forma gráfica

Na forma gráfica, vértices são representados por círculos e as arestas por linhas que conectam estes círculos. Por exemplo:

Matriz de adjacência

Uma forma de representar matrizes de forma computacional é o uso de matriz de adjacência. Considere o seguinte grafo não-direcionado abaixo. Construiremos uma matriz de adjacência, onde os nomes dos vértices são usados para linhas e colunas e, quando conectados, utiliza-se o valor 1 para expressar a conexão, 2 se um vértice se conecta com ele mesmo e  se não há conexão, o valor 0 será utilizado.

\(\begin{pmatrix}
2 & 1 & 0 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 1\\
1 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0
\end{pmatrix}\)

Matriz de incidência

Enquanto a matriz de adjacência conecta vértice a vértice, a matriz de incidência conecta vértice a aresta que está ligada ao vértice. Considere o seguinte grafo:

Se cada linha for associada a um vértice (1,2,3,4) e cada coluna a uma aresta (nomeada de e1,e2,e3,e4), poderemos criar uma matriz sob a forma:

\(\begin{pmatrix}
1 & 1 & 1 & 0 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 \\
0 & 0 & 1 & 1 \\
\end{pmatrix}\)


Para citar este artigo

REVISTABW. Teoria dos Grafos: Conceitos Iniciais.Revista Brasileira de Web: Tecnologia. Disponível em https://www.revistabw.com.br/revistabw/teoria-dos-grafos-conceitos-iniciais/. Criado em: 27/12/2017. Última atualização: 27/12/2017. Visitado em: 22/06/2018


Procurando mais conteúdos ? Utilize o campo de busca abaixo



Leia +



Você também deveria ler


O conteúdo da Revista Brasileira de Web é licenciado sob uma Licença Creative Commons Atribuição 3.0 Brasil, exceto quando especificado claramente em contrário. Este é um site de conteúdos diversos e dicas gerais e não substitui a consultoria de um profissional devidamente qualificado. Isto significa que os assuntos aqui abordados possuem caráter geral e podem não ser adequados no seu caso. Leia nossos Termos de Uso e Privacidade.