Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

Introdução à Teoria dos Grafos

Carlos Florentino1,2

1Departmento de Mathemática, FCUL,2CMAFcIO e GFM Univ. de Lisboa

Notas de Matemática Discreta / Finita

Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

Outline

1 Grafos e suas MatrizesOs vários tipos de grafosMatrizes associadas a grafos, sequências gráficas

2 Caminhos e conexidade em grafos simplesPasseios e Caminhos; conexidade, isomorfismosGrafos Eulerianos e Hamiltonianos

3 Grafos planaresGrafos Planares e a fórmula de EulerTeorema de Kuratowski

4 Árvores e árvores geradorasÁrvoresTeorema de Kirchhoff

5 O algoritmo da Google: “Pagerank”Matrizes estocásticasAplicação a “grafos de Markov”O algoritmo

Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

Grafos, multigrafos e pseudo-grafos

Grafo Γ = (V,A); vértice υ ∈ V, aresta α ∈ A,

Simples: α = {υ, ω} A ⊂ P2(V)

Multigrafo: arestas diferentes α2 6= α1 ∈ A podem ligar osmesmos vértices: φ : A → P2(V). φ(α1) = φ(α2).Pseudo-grafo: admite lacetes, φ : A → V ⊔ P2(V)φ(α) = {υ}

Dirigido: cada aresta está orientada ψ : A → V2 = V × V,ψ(α) = (υ, ω), υ início, ω fim.

Extremos da aresta α = {υ, ω} ∈ A são υ e ω (ou na imagemφ(α) ou ψ(α)); α incide em υ e em ωGrau de υ ∈ V: dυ := |{α ∈ A : υ ∈ α}| = #arestas incidentes.

Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

Matrizes associadas a Γ

Γ = (V,A) multigrafo, V = {υ1, · · · , υn}, A = {α1, · · · , αm}.Matriz de Incidência: matriz m × n = |A| × |V|

Mij =

{

1, αi incide em υj

0, αj não incide em υj, i ∈ [m], j ∈ [n].

Matriz de Adjacência: matriz quadrada simétrica n × n

Jij = k se υi e υj ligados por k arestas (= 0, se i = j)

Matriz de Valência (ou Matriz de Grau) matriz diagonal n × n:

D = diag(dυ1 , · · · , dυn), Dij = 0 para i 6= j

Teorema: Para Γ multigrafo MtM = J + D:

(

1i · · · 1i

· · · 1j 1j

)

i j

1i.

.

.

.

.

. 1j

1i 1j

=

(

di∑

1i1j

dj

)

Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

Graus e Sequências Gráficas

Proposição: Seja Γ grafo (ou pseudo-grafo).∑

υ∈V dυ = 2 |A|Definição: Diz-se que (d1, d2, · · · , dn) é sequência gráfica, seexiste um grafo simples Γ = (V,A), |V| = n, em que di é o grau dovértice υi ∈ V.Proposição: Se Γ é um grafo simples, com grausd1 ≤ d2 ≤ · · · ≤ dn, então:

1∑n

i=1 di é par,2 dn < n (implica todos di < n, e

∑ni=1 di ≤ n(n − 1))

3 (d1, · · · , dn, dn+1 = ∆) é seq. gráfica sse

(d1, · · · , dk, dk+1 − 1, · · · , dn − 1) é seq, gráfica, n = k +∆.

Exemplo: (1, 1, 2, 2, 3), (1, 2, 3, 4) não são sequências gráficas(2, 3, 3, 4, 4) é sequência gráfica (de grafo simples)?⇔ (1, 2, 2, 3) seq. gráfica? ⇔ (0, 1, 1) seq. gráfica? R: Sim!

Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

Passeios e Caminhos em Grafos

Seja Γ = (V,A) um grafo simples.Passeio em Γ: sequência alternada de vértices e arestas, tal que oelemento seguinte é adjacente/incidente ao anterior, começa etermina em vértices (chamados vértice inicial e final).Caminho em Γ: passeio que não repete vértices nem arestas (poderepetir o vértice final).Ciclo (ou caminho fechado): caminho que começa e termina nomesmo vértice.

Observação: Em grafos simples, basta dar a sequência de vértices!Exemplos: Passeio: (6, 4, 3, 4, 5, 1)Caminho: (6, 4, 5, 1)Ciclo: (4, 5, 1, 2, 3, 4)

Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

Grafos conexos, componentes, isomorfismos

Definição: Um grafo Γ = (V,A) é conexo se para quaisquer doisvértices (distintos) existe um passeio/caminho entre eles.

V = V1 ⊔ · · · ⊔ Vk, e A = A1 ⊔ · · · ⊔ Ak

onde Γi = (Vi,Ai) conexo, e Ai ⊂ A arestas que ligam os vértices deVi.Num grafo dirigido os passeios e caminhos têm que seguir assetas! Um ciclo orientado é um caminho fechado num grafodirigido.

Definição: Um isomorfismo entre os grafos Γ = (V,A) eΓ′ = (V ′,A′) é uma bijecção f : V → V ′ com {υi, υj} ∈ A sse{f (υi), f (υj)} ∈ A′.Facto: As matrizes de grafos isomorfos diferem apenas porpermutação de linhas e/ou colunas.

Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

Grafos Eulerianos e Hamiltonianos

Definição: Um passeio em Γ é Euleriano se passa por todas asarestas de Γ sem repetição (pode ser ou não fechado).

Teorema de Euler: Γ tem um passeio Euleriano fechado se e só seé conexo e todos os vértices têm grau par. Γ tem um passeioEuleriano se e só se é conexo, todos os vértices excepto 2 têm graupar (começa num dos vértices de grau ímpar, termina no outro).

Definição: Um grafo é Hamiltonianose tem um caminho que passa por

todos os vértices.

Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

Grafos planares e a fórmula de Euler

Definição: Um grafo Γ = (V,A) é planar se pode ser desenhadonum plano sem que as arestas se intersectem.Exemplos: Grafos sem ciclos são planares.O “esqueleto” de um poliedro convexo é planar!

Observação: Num grafo planar, para além de vértices e arestas,podemos considerar faces!Teorema [Fórmula de Euler] Um grafo planar conexo com vvértices, a arestas e f faces verifica:

v − a + f = 2,

contando com a face exterior.Demonstração por indução!

Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

Grafo dual de um grafo planar

Definição: Dado um grafo planar Γ, o grafo dual Γ∨ é obtidotrocando os vértices com as faces.Exemplos: Dois grafos e os seus duais:

Proposição (Majorante de arestas) Se Γ é um grafo planar conexocom v > 2 vértices e a arestas (e faces de ordem > 2) temos:

a ≤ 3v − 6.

Dem: Usar o facto de que2a =

∑

υ∈Γ∨ =∑

dfi ≥ 3f = 3a − 3v + 6.

Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

Grafos e poliedros

Definição: Um poliedro convexo é um sólido geométrico convexocuja fronteira é composta por polígonos (regulares ou não)Cada poliedro convexo define um grafo planar.Teorema de Steinitz: Um grafo planar provém de um poliedro see só se verifica a fórmula de Euler v − a + f = 2, a ≥ 6 ev, f ∈ [4, 2

3a].

Exemplo: Os sólidos platónicos: tetraedro, octaedro, cubo,dodecaedro e icosaedro.

Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

Teorema de Kuratowski

Definição: Um subgrafo do grafo simples Γ, é Γ′ ⊂ Γ obtidotomando só algumas arestas, e os seus vértices incidentes.Definição: Uma subdivisão de um grafo Γ é um novo grafo Γ′

obtido adicionando alguns vértices no meio de arestas de Γ.Exemplos: Grafo Γ (a) e uma subdivisão Γ′ (b):

Teorema (Kuratowski) Γ é um grafo planar se e só se Γ nãocontém nenhum subgrafo que é uma subdivisão de K5 ou de K3,3.

Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

Árvores

Seja Γ = (V,A) um grafo simples.Definição: Uma árvore é um grafo conexo e sem ciclos. Umafloresta é um grafo sem ciclos, ou seja, uma união disjunta deárvores.Teorema: Sendo |V| = n, são equivalentes:

Γ é uma árvore

Γ é conexo com n − 1 arestas

Γ não tem ciclos e tem n − 1 arestas

Corolário: (d1, · · · , dn) é a sequência gráfica de uma árvore sse

n∑

i=1

di = 2n − 2

Definição: Numa árvore, umafolha é um vértice de grau 1.

Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

Árvores geradoras e Teorema de Kirchhoff

Definição: Uma árvore geradora de um grafo simples Γ é umaárvore em Γ que contém todos os vértices de Γ.Definição: Matriz Laplaciana de Γ, com n vértices, é a matriz(quadrada n × n) L := D − J.Para cada v ∈ V, seja Lv o correspondente cofactor de L.

Teorema de Kirchhoff

Seja Γ conexo. Então:(i)det Lv = det Lw, para quaisquer v,w ∈ V(ii) det Lv é o número de árvores geradoras em Γ.

Example (O grafo ciclo Cn)

Lv = Cofv(D − J) =

2 −1 0 · · ·

−1. . . . . . . . .

0. . . 2 −1

.... . . −1 2

Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

Matrizes estocásticas (por colunas)

Vector estocástico (ou probabilístico) é v = (v1, v2, · · · , vn) comvi ≥ 0 e v1 + v2 + · · ·+ vn = 1.Definição: Uma matriz estocástica n × n é uma matriz cujascolunas são vectores estocásticos. Se além disso, nenhuma entradafor zero, a matriz diz-se estocástica positiva.

Proposição: Sejam A e B matrizes estocásticas. Então:(i) AB é estocástica.(ii) sA + tB é estocástica positiva ∀s, t > 0 com s + t = 1.

Theorem (Perron-Frobenius)

Seja M uma matriz estocástica positiva. Então:(i) 1 é valor próprio de M(ii) Há um único vector próprio estocástico p de valor próprio 1(iii) Mnv tende para p, para qualquer v estocástico.

Chamamos a p o vector de Perron-Frobenius.

Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

Matriz estocástica de um grafo dirigido

A partir de agora, Γ = (V,A) é um grafo dirigido. Notação “dot”:listar todas as flechas: 1 → {i, j, · · · }, 2 → {k, l, · · · }Definição: A matriz estocástica do grafo dirigido Γ com nvértices é uma matriz n × n estocástica e positiva que estipula igualprobabilidade de seguir as várias flechas de saída (e 1/n para osvértices sem saída).

1 → {2, 3, 4};2 → {3, 4};3 → 1;4 → ∅;

E =

0 0 1 14

13 0 0 1

413

12 0 1

413

12 0 1

4

Proposição: A probabilidade de transição do vértice i para o j emk passos é a entrada da coluna i e linha j da matriz Ek.

A probabilidade de transição do vértice 1 para o 4 em 2 passos é aentrada 4, 1 da matriz E2, ou seja 1

3(12 + 1

4) =14 .

Números Binomiais Caminhos e conexidade em grafos simples Grafos planares Árvores e árvores geradoras O algoritmo

O algoritmo Pagerank

Vamos supor que Γ = (V,A) é um grafo dirigido que representa ainternet: vértices são páginas da internet e flechas são links queapontam para outra página.

Algoritmo: Seja Γ grafo dirigido com N vértices e E a matriz

estocástica associada:

(1) Escolher vector estocástico inicial, usualmentev = 1

N (1, 1, · · · , 1)

(2) Escolher peso ρ ∈]0, 1[ e calcular M = (1 − ρ)E + ρ

N 1 (onde 1 éa matrix só com 1’s); usualmente ρ = 0.15.

(3) Calcular Mnv para n suficientemente grande.

O resultado dá um vector estocástico cuja entrada i é aprobabilidade de, ao navegar n passos, estarmos na página i.

Conclusão: Determinámos a importância relativa de cada página,usando apenas a estrutura interna do grafo Γ.