Grafos

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.
É o objeto 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 ser direcionadas, 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 alguns tipos 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 que conecta 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 sentido original) é 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.