Grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (626 palavras )
  • Download(s) : 0
  • Publicado : 20 de maio de 2012
Ler documento completo
Amostra do texto
Grafos - uma aplicação da álgebra das matrizes

A teoria dos grafos é uma área da matemática aplicada que envolve matrizes, principalmente na representação de circuitos e redes de comunicação.
É oobjeto básico de estudo da teoria dos grafos. Tipicamente, um grafo é representado como um conjunto de pontos (vértices) ligados por retas (as arestas). Dependendo da aplicação, as arestas podem serdirecionadas, e são representadas por "setas".
Um vértice é representado por um círculo e uma curva é representada pela representação gráfica plana característica, ou seja, um segmento de reta.Quando uma curva possui indicação de sentido (uma seta), ela é chamada de arco, caso contrário é chamada de linha.



[pic]
Grafo simples (fonte da imagem: wikimédia_commons)


Veja a seguir algunstipos de grafos e suas definições

• Grafo simples: se entre cada par de vértices distintos existir no máximo uma aresta e se, além disso, não contiver lacetes, ou seja existir uma aresta queconecta um vertice a ele mesmo, ele é considerado simples. Ou seja, não contém nem laços nem arestas múltiplas.



Grafo simples (fonte da imagem: Wikimedia commons)
• Grafo orientado(dígrafo): quando os relacionamentos são direcionados, existindo apenas uma direção, sendo que as conexões entre os vértices são chamadas de arcos. .

[pic]
Grafo orientado (fonte da imagem: Wikipédia)• Grafo completo: é o grafo simples em que, para cada vértice do grafo, existe uma aresta conectando este vértice a cada um dos demais. Ou seja, todos os vértices do grafo possuem mesmo grau.[pic]
Grafo completo (fonte da imagem: Wikimedia commons)
• Grafo nulo ou grafo vazio: é o grafo sem nenhum vértice e (portanto) sem arestas, ou qualquer grafo sem arestas. O grafo nulo (no sentidooriginal) é o objeto inicial na categoria de grafos, de acordo com algumas definições de categoria de grafos. Não tendo nenhum vértice, o grafo nulo, portanto, também não tem componentes ligados....
tracking img