Teoria dos Grafos: Conceitos e Terminologia na Prática
Na aula anterior, eu descrevi os principais conceitos e características de um grafo. Agora vamos ver alguns exemplos de grafos na tentativa de explorar tais ideias e colocar em prática as identificações de cada tipo de grafo.
Exemplo 1:
Inicialmente vamos identificar alguns conceitos dados na aula anterior. De acordo com o conceito 1, temos que as arestas a1 e a2 são arestas paralelas. No vértice 3 temos um loop da aresta a3. O vértice 5, é um vértice isolado, não há ligação alguma entre o vértice 5 e qualquer outro vértice do grafo. Por haver um vértice isolado, podemos afirmar que esse grafo é desconexo.
Grau dos vértices: (Discriminado no conceito nº6 – da aula de terminologia).
- Vértice 1: Possui as arestas a1,a2 e a5 ligadas a esse vértice ou seja 3 arestas: possui grau 3.
- Vértice 2: Possui as arestas a1, a2, a3, a3(LOOP) e a5 ligadas a esse vértice ou seja 5 arestas: possui grau 5.
- Vértice 3: Possui as arestas a4, a5 e a6 ligadas a esse vértice ou seja 3 arestas: possui grau 3.
- Vértice 4: Possui as arestas a6, possuindo grau 1.
- Vértice 5: Veja que esse vértice não tem ligação alguma com qualquer outro vértice, portanto possui grau 0.
A ordem do grafo acima é 5. (Conceito nº10);
O tamanho do grafo acima é 6 (Conceito nº11);
São exemplo de subgrafos do grafo acima (Conceito nº 16):
