Ludmila Maciel Rocha de Souza

Um grafo G=(V,E) é completo se para cada par de vértices v_i e v_j existe uma aresta entre v_i e v_j . Em um grafo completo quaisquer dois vértices distintos são adjacentes (K_n).

Arestas no grafo completo - Seja K_n um grafo completo com n vértices. O número de arestas é:

Observações: 

* (n - 1) é igual ao número de incidências nesse vértice.

* Em grafos não direcionados, para cada par de vértices existe uma aresta.

Grafo Conexo: Existe pelo menos um caminho entre todos os pares de vértices.

Grafo Bipartido: Um grafo é dito ser bipartido quando seu conjunto de vértices V puder ser particionado em dois subconjuntos V₁ e V₂, tais que toda aresta de G une um vértice de V₁ a outro de V₂.

Um grafo é dito ser bipartido completo quando seu conjunto de vértices V puder ser particionado em dois subconjuntos V₁ e V₂, tais que toda aresta de G une um vértice de V₁ a outro de V₂, e que todo vértice de V₁ é adjacente a todo vértice de V₂.

Arestas no grafo bipartido completo - Seja K_mn um grafo bipartido completo com n vértices em V₁ e m
vértices em V₂. O número de arestas é:

Grau: O número de arestas incidentes a um vértice v_i é chamado de grau, d(v_i ), do vértice i. A soma dos graus de todos os vértices de um grafo G é duas vezes o número de arestas de G.

TEOREMA - Vértice de grau ímpar: O número de vértices de grau ímpar em um grafo é par.

O grafo complementar é o grafo nulo somado as arestas que faltam para o grafo em questão ser completo.

Definição formal: 

* Seja G = (V, E) um grafo simples dirigido ou não-dirigido;

* O complemento de G, C(G), é um grafo formado da seguinte maneira:

- Os vértices de C(G) são todos os vértices de G;

- As arestas de C(G) são exatamente as arestas que faltam em G para formarmos um grafo completo.

- Um grafo g é dito ser um subgrafo de um grafo G se todos os vértices e todas as arestas de g estão em G;

- Observações:

* Todo grafo é subgrafo de si próprio; * O subgrafo de um subgrafo de G é subgrafo de G;

* Um vértice simples de G é um subgrafo de G; * Uma aresta simples de G (juntamente com suas extremidades) é subgrafo de G.

- Subgrafos disjuntos de arestas: dois (ou mais) subgrafos G₁ e G₂ de um grafo G são disjuntos de arestas se G₁ e G₂ não tiverem nenhuma aresta em comum.

- Subgrafos disjuntos de vértices: dois (ou mais) subgrafos G1 e G2 de um grafo G são disjuntos de vértices se G1 e G2 não tiverem nenhum vértice em comum.

Se G₂ = (V₂, A₂) é um subgrafo de G₁ = (V₁, A₁) e possui toda aresta (v,w) de G₁ tal que ambos, v e w, estejam em V₂, então G₂ é o subgrafo induzido pelo subconjunto de vértices V₂.

Exemplo:

Dado um grafo direcionado G = (V, E), seu grafo transposto G_t = (V, E1), tal que E₁ é o conjunto de arestas de G (E), com sentido oposto.

Abaixo o grafo transposto de um grafo direcionado:

​​​​​​​​​​​​

Algoritmos em Grafos - Transparências por Almeida e Ziviani​​​​​​​