Para o maior entendimento da teoria dos grafos, temos um número grande de conceitos e definições. Tais características, são utilizadas para definir um grafo, podemos ter inúmeros tipos de grafos e esses conceitos são a base para entender e construir um diagrama de um determinado problema a partir da maravilhosa ferramenta conhecida então como grafos.
O meu conselho é estar com essa tabela sempre em mãos quando estiver estudando, de modo a sempre relembrar de tais conceitos.
Conceito nº1 – Aresta Múltiplas ou Paralelas: Quando duas arestas (ou arcos) ligam dois vértices iguais.
Conceito nº2 – Multigrafos: Chamamos de Multigrafo um grafo no qual possui arestas múltiplas ou paralelas, de acordo com o conceito 1.
Conceito nº3 – Grafos Simples: São grafos que não possuem loops e, ou arestas paralelas.
Conceito nº4 – Pseudografo: São grafos que possuem no mínimo um laço.
Conceito nº4 – Grafo Reflexivo: São pseudografos (dado no conceito 4) no qual todos os vértices possuem pelo menos um laço.
Conceito nº5 – Vértice Isolado: São vértices que não possuem ligação alguma com outros pontos, então não possuem vértices adjacentes.
Conceito nº6 – Grau de um Vértice: É o número de arestas que o vértice tem como ponto extremo.
Conceito nº7 – Grafo Regular de Grau K ou K-Regular: Se todos os vértices de um grafo possuir um grau K (dado no conceito 6), então podemos chamar esse grafo de regular de grau K. Podemos concluir que todos os vértices possuem o mesmo grau.
Conceito nº8 – Grafo Trivial: Chamamos de grafo trivial aquele que é um grafo 0-regular, de acordo com os conceitos número 6 e 7.
Conceito nº9 – Grafo Conexo: Um grafo é dito conexo se existir um caminho por quaisquer dois vértices, ou seja, não há um vértice isolado, assim explicitado no conceito número 5.
Conceito nº10 – A ordem de um grafo: A ordem de um grafo é o número de vértices de esse grafo possui.
Conceito nº11 – O tamanho de um grafo: É o número de arestas que esse grafo possui.
Pré-Conceito para o conceito nº12: Um grafo G possui dois conjuntos de elementos. O conjunto V de vértices e o conjunto A de arestas e uma função g que define as ligações que ocorrem em uma par de vértices.
Conceito nº12 – Função g Injetiva: Uma função g injetora (assim como dado nas teorias de função na matemática) são funções em que formam um grafo no qual cada aresta liga cada par de vértices.
Conceito nº13 – Grafo Vazio: É um grafo no qual somente existem vértices.
Conceito nº14 – Grafo Nulo: É um grafo no qual não existem vértices.
Conceito nº15 – Grafo Completo: Um grafo completo é aquele que todos seus vértices distintos são adjacentes entre si. Ou seja, escolhendo um vértice qualquer em um grafo completo, podemos ir para qualquer outro vértice pertencente ao grafo. Geralmente chamamos esse grafo de Kn, ou seja um grafo completo de n vértices. Vale ressaltar que um grafo completo é necessariamente um grafo simples (Conceito número 3).
Conceito nº16 – Subgrafo de um Grafo: Considerando um grafo G que possui um conjunto de vértices V e um conjunto de arestas A, um subgrafo de um grafo é um subconjunto de vértices e arestas que pertencentes ao mesmo grafo. Imagine um grafo, agora apague alguns vértices e algumas arestas, o resultado será um subgrafo desse grafo antes imaginado.
Conceito nº17 – Clique: Um clique é um subgrafo completo, ou seja, todos os vértices desse subgrafo conectam-se entre si. (Engloba o conceito número 6 e 15). Podemos dizer que um clique é um tipo especial de subgrafo.