Grafos, percursos e isomorfismos

Grafos

• Um grafo simples não dirigido usa pares não ordenados de vértices distintos, sem laços nem arestas repetidas. Os grafos deste tópico são finitos.
• Um dígrafo usa pares ordenados; $(u,v)$ e $(v,u)$ são ligações diferentes e o dígrafo pode ter laços.
• Um multigrafo admite arestas paralelas e tem de as distinguir.
• Um subgrafo conserva os extremos das arestas escolhidas. O subgrafo induzido por $U$ conserva todas as arestas entre vértices de $U$. O complemento, no caso simples, usa os pares distintos ausentes, no mesmo $V$.

Família	Arestas
$K_n$	$n(n-1)/2$
$P_n$	$n-1$
$C_n$, $n\ge3$	$n$
$K_{m,n}$	$mn$
$S_n$	$n$ vértices, $n-1$ arestas
$W_n$	ciclo de $n$ vértices mais centro; $2n$ arestas

$U\subseteq K_{m,n}$ induz $K_{|U\cap V_1|,|U\cap V_2|}$; escolher vértices de uma só parte dá zero arestas.

Graus e matriz

Para um grafo simples não dirigido:

$$\sum_{v\in V}\deg(v)=2|E|.$$

• O número de vértices de grau ímpar é par; cada grau satisfaz $\deg\le|V|-1$. Estas condições são necessárias, não suficientes.
• No dígrafo, a soma das entradas e a soma das saídas valem ambas $|E|$.

A matriz de adjacência usa a linha para a origem e a coluna para o destino. No caso não dirigido simples é simétrica com diagonal zero; cada linha soma o grau. No dígrafo, a linha soma a saída e a coluna soma a entrada.

Percursos

Percurso	Condição da repetição
Passeio	pode repetir arestas e vértices
Trilho	não repete arestas
Caminho	não repete vértices
Circuito	é um trilho fechado
Ciclo	é um caminho fechado, só repete a origem no fim

• O comprimento conta as arestas. No dígrafo, cada passo respeita a direção.
• Todo o caminho é um trilho; todo o trilho é um passeio. A expressão “caminho de Euler” num enunciado pode significar trilho; confere se o enunciado exige arestas distintas.

Conectividade

• Um grafo não dirigido é conexo quando há um caminho entre quaisquer dois vértices. As componentes são maximais; um vértice isolado conta como componente.
• Um dígrafo é fortemente conexo quando há um caminho dirigido para cada par ordenado. É fracamente conexo quando é conexo ao ignorar as direções.

O desenho é fracamente conexo, mas não fortemente conexo: não se regressa de $e$ a $a$.

Árvores

• Uma árvore é conexa e sem ciclos. Há exatamente um caminho entre cada par de vértices.
• Uma árvore com $n\ge1$ vértices tem $n-1$ arestas. Uma floresta com $n$ vértices e $c$ componentes tem $n-c$ arestas.
• Retirar uma aresta desconecta a árvore; juntar dois vértices já ligados cria um ciclo.
• Uma árvore abrangente mantém todos os vértices do grafo conexo e escolhe $n-1$ arestas sem ciclos.

Distâncias

A distância é o mínimo, com $d(u,u)=0$ e $\infty$ sem caminho. É simétrica no caso não dirigido e satisfaz $d(u,w)\le d(u,v)+d(v,w)$.

Dijkstra, só com pesos não negativos:

1. Põe a origem a $0$ e os restantes vértices a $\infty$.
2. Fixa o vértice provisório com menor distância ainda não fixado.
3. Melhora cada vizinho por $d(v)\gets\min(d(v),d(u)+w(u,v))$.

Um vértice fixado nunca melhora. Menos arestas não implica menor peso.

Isomorfismos

$f:V\to V'$ é isomorfismo quando $f$ é bijeção e preserva adjacência nos dois sentidos:

$$\{u,v\}\in E\Longleftrightarrow\{f(u),f(v)\}\in E'.$$

• Para provar o isomorfismo, apresenta a bijeção e verifica as ligações nos dois sentidos.
• Para refutar, compara invariantes: vértices, arestas, graus, componentes, ciclos. Graus iguais não bastam.

$C_6$ tem uma componente; os dois triângulos têm duas.

Percursos, árvores e exemplos de Dijkstra.