Introdução à Teoria dos Grafos

Um grafo G=(V,E) é um par: V é um conjunto finito de vértices, e E descreve as ligações. Cada ligação une dois vértices — par não ordenado {u,v} (aresta) ou par ordenado (u,v) (arco).

Graus, isomorfismo e Qₖ deste tópico — e caminhos, conectividade e árvores geradoras nos tópicos seguintes — partem desse par e da adjacência que ele registra.

As páginas se agrupam em quatro blocos. O primeiro fixa G=(V,E) e a ordem de V com que se preenche a matriz n×n ou se montam as listas de vizinhos.

O segundo conta incidências: um grau e a soma 2|E| sem orientação; deg⁻(v) e deg⁺(v), somas iguais a |E|, com orientação. O grafo misto mistura os dois tipos no mesmo V.

O terceiro casa os vértices por uma bijeção que preserva adjacência, depois de conferir |V|, |E| e a sequência de graus.

O quarto constrói objetos nomeados: o k-cubo Qₖ (vértices {0,1}ᵏ, d_H=1), o hipergrafo de aridade livre e a junção G₁+G₂ das cruzadas entre partes disjuntas.

Preencher a matriz pela ordem de V, ou reconstruir os arcos a partir dos bits, está em Introdução aos Grafos. A soma dos graus e |E(Kₙ)|=n(n−1)/2 estão em Grafos Indirecionados.

Aresta {u,v} e um só grau estão em Grafos Indirecionados. Arco (u,v), deg⁻, deg⁺ e o grafo misto estão em Grafos Dirigidos (Digrafos).

Ligação de dois extremos está em Introdução aos Grafos. A soma ∑ deg(v)=∑|e| está em Hipergrafos.

|Eₖ|=k·2ᵏ⁻¹ e distância igual a d_H estão em Hipercubos. O acréscimo deg(u)+|V₂| está em Junção de Grafos.

A bijeção que preserva incidência está em Isomorfismo de Grafos.