Uma Introdução Sucinta

à Teoria dos Grafos

Paulo Feofiloff

Yoshiharu Kohayakawa

Yoshiko Wakabayashi

IME–USP

www.ime.usp.br/˜pf/teoriadosgrafos/

25/10/2004 11:00

1

Prefácio

2

Grafos são bons modelos para muitos problemas em

• matemática e combinatória

• informática e computação

• física

• biologia

• engenharia

• pesquisa operacional

• muitos ramos da indústria

Trataremos de quatro temas

• conjuntos estáveis

• coloração de vértices

• emparelhamentos

• coloração de arestas

Outros temas: planaridade, isomorfismo, conexidade, fluxo, circuitoshamiltonianos, florestas e árvores, grafos aleatórios.Alguns aparecem em outros cursos da Bienal

3

AULA 1A

Conceitos básicos

4

Grafos

• conjunto de vértices

• conjunto de arestas

• aresta = par de vértices

• vértices adjacentes

• G = (V, A)

Vértices: u, v, w, x, y, z, t

Arestas: vw, uv , xw, xu, yz , xy

t t ttt

tt�������PPPPPPP�������P

PPPPPP

PPPPP�����v

u

w yx

z

t

G

• n = número de arestas

• m = número de arestas ≤(n2

)

5

25

15

14

35

13

24

23

3445

12

t ttt t

tt

t

tt

XXXXQ

QQ

QQQCCCCCCC

JJ

J

�������A

AAAAAA

��

��

��

�

ZZ

ZZ

ZZ

Z

�������

��

��

��

����

110

100101

111

000

010 011

001t t t

tt t tt@

@�

�

@@

��

completo Petersen cubo

AM

RR

RO

TO

MT

MS

PE

MS

PA

GO

PR

SP

BA SE

AL

CEPI

MA

ES

RJ

PA

RN

SC

RS

AP

MG

AC

estados adjacentes grafo da damabispo

6

t t tttt

ttt

2

3

1

1 2 3

s s

s

s s s

ssss�

��

���

BBBBBBB

BB

BBB@

@@

@@@�

��

���

������

�����

������

�����

������B

BBBBB

��

��

��

@@

@@

@@

BBBBBB

��

��

����

��

��

pontos no plano bipartido bipartido completouv ∈ A

ssed(u, v) < 2

0 1 0 11 0 1 00 1 0 11 0 1 0

matriz {0,1} simétrica cavalo (bipartido)

• grau de um vértice: g(v)

• grau máximo do grafo: ∆(G)

• grau mínimo do grafo: δ(G)

7

AULA 1B

Conjuntos estáveis

cliques

coberturas

8

Cliques

Clique : conj de vértices dois-a-dois adjacentes

X é clique sse G[X] é completo

t t t

tt t tt@

@�

�

@@

��

@@

@@

@��

��

�

• clique maximal

• clique máxima

• ω(G) := maxX |X|

Dama 4× 4

clique maximal clique máxima

9

Conjuntos estáveis

X ⊆ V (G)

X é estável se seus elementos são

dois-a-dois não-adjacentes

tt

ttt##

##cc

cc##

##cc

cc

tt t

ttt

��� S

SS�

��S

SS

• conj estável maximal

• conj estável máximo

• α(G) := maxX |X|

Fato: α(G) = ω(G)

10

Exemplo 1: postos de gasolina

Exemplos 2 e 3:

dama α = 5 cavalo α = 13

11

Conj estável máximo no grafo dos estados do Brasil?no grafo da rainha 100× 100?

Complexidade computacional

• Calcular α(G): tempo 2n(G)

• Isso não é aceitável na prática

• Mas não vamos tratar de algoritmos

• Nosso enfoque: delimitações de α(G)

• α(G) ≤ ?? α(G) ≥ ??

• Relação entre α(G) e outros parâmetros de G

Intuição: α tanto maior quanto menor for ∆

12

Delimitação inferior: α(G) ≥n(G)

∆(G) + 1

PROVA: Exibir cj estável grande

• Tome cj estável maximal X

• |∇(X)| =∑

x g(x) ≤ |X| ·∆• |V r X| ≤ |∇(X)|• n = |X|+ |V r X| ≤ |X|+ |∇(X)| ≤ |X| · (1 + ∆)

• |X| ≥ n∆+1

Comentários sobre ∇ e espaço dos cociclos

Generalização: α(G) ≥∑v

1

g(v) + 1

13

Delimitação superior: α(G) ≤m(G)

δ(G)

PROVA: Para qualquer conj estável X

m ≥ |∇(X)| =∑

x g(x) ≥ |X| · δ

Importância de delimitações superiores:

se X é estável e |X| =⌊mδ

⌋então X é máximo

Ciclo C2p+1 : |X| = p = bmδc

Bipartido Kp,q (p ≤ q): |X| = q = pqp

= mδ

14

Delimitação superior: α(G) ≤ n(G)− p(G)/2

p(G) := posto da matriz de adjacências

Exemplo:

t tttt�������PPPPPPP�������P

PPPPPP

PPPPP2

1

3 54

M(G) =

0 1 0 1 01 0 1 0 00 1 0 1 01 0 1 0 10 0 0 1 0

Delimitação superior: α(G) ≤ maxX

e′Xe

uv ∈ A(G) ⇒ Xuv = 0∑v Xvv = 1

X � 0

15

Maioria dos grafos têm α pequeno:

α(G) < 2.2 log2 n

para quase todo G

limn→∞|P||G| = 1

Exemplo: 99.9% dos grafos com 1024 vérticestêm α < 22 = 2.2 log2 1024

Grafos aleatórios

16

Por menor que seja ε > 0, α(G) < (2 + ε) log2 n

para quase todo G

PROVA:

• k :=⌈(2 + ε) log2 n

⌉• Mostrar que lim

n→∞|G r P||G|

= 0

• X ⊆ V (G), |X| = k, N =(n2

), K =

(k2

)• X é estável em 2N−K dos grafos

• |G r P| ≤ nk 2N−K

•|G r P||G|

≤nk

2K

17

Cliques vs cjs estáveis: números de Ramsey

Intuição: se α é pequeno estão ω é grande

Teorema de Ramsey: Para todo s e t todo G tem

α(G) ≥ s ou ω(G) ≥ t

desde que n(G) ≥ R(s, t)

• Prove que R(s, t) ≤(s+t−2

s−1

)• Dica R(s, t) ≤ R(s− 1, t) + R(s, t− 1)

Exemplo: R(3,3) = 6

18

Coberturas

X ⊆ V (G) é uma cobertura se

toda aresta tem pelo menos uma ponta em X

tt

ttt##

##cc

cc##

##cc

cc

tt t

ttt

��� S

SS�

��S

SS

• cobertura minimal

• cobertura mínima

• β(G) := minX |X|

Fato: β = n− α

PROVA: X é cobertura ⇔ V r X é estável

s s

s

s s s

ssss�

��

���

BBBBBBB

BB

BBB@

@@

@@@�

��

���

������

�����

������

�����

������B

BBBBB

��

��

��

@@

@@

@@

BBBBBB

��

��

����

��

��

19

Exercícios para amanhã

• Conj estável máximo do grafo da dama 8× 8

• Conj estável máximo do grafo do bispo t× t

20

AULA 2

Emparelhamentos

21

Emparelhamentos

E ⊆ A(G)

E é emparelhamento se |E ∩∇(v)| ≤ 1 para todo v

tt

ttt##

##cc

cc##

##cc

cc

tt t

ttt

��� S

SS�

��S

SS

Grafo das arestas de G:emparelhamento >>> conj estável

t t ttt

tt�������PPPPPPP�������P

PPPPPP

PPPPP�����v

u

w yx

z

t

G

tt t

t t tHHHH�

���

vu

yzvw wx

uxxy

G′

• emp maximal

• emp máximo

• α′(G) := maxE |E|22

maximal máximo

Delimitação: α′(G) ≤ β(G)

PROVA: |E| ≤ |C| para qquer emp E e qquer cob C

t t ttttt

t tt tt t t

Se |E| = |C| então E é máximo

23

Infelizmente, α′ < β para muitos grafos

Mas. . .

Teorema de König:

Se G é bipartido então α′(G) = β(G)

Antes de provar o teorema:desvio para estudar emps que saturam um lado da bipartição

24

Caso bipartido

• Grafo (U, W )-bipartido

• Queremos emp que satura U

• Condições de existência?

s s

s

s s s

ssss�

��

���

BBBBBBB

BB

BBB@

@@

@@@�

��

���

������

������

�����

������

�����B

BBBBB

��

��

��

@@

@@

@@

BBBBBB

��

��

����

��

��

Exemplos:

• moças e rapazes• representantes distintos

Condição de Hall: |Γ(X)| ≥ |X| para todo X ⊆ U

Fato: Se existe emp E que satura U

então vale cond de Hall

PROVA:• H := (V (G), E)

• |ΓG(X)| ≥ |ΓH(X)| = |X| para todo X

25

Teorema de Hall:Se vale cond de Hall então existe emp que satura U

PROVA, por indução em |U |:Se |U | = 1 então temos emp q satura U

Suponha agora que |U | > 1

ALTERNATIVA 1: |ΓG(X)| > |X| para todo ∅ ⊂ X ⊂ U

• Escolha uw ∈ A(G)

• G′ := (G− u)− w satisfaz condição de Hall

• Hip de indução: G′ tem emp E′ que satura U ′

• E′ ∪ {uw} é emp em G que satura U

u

uu

u u

u

u

uu

u

������

������

��AAAAAAA

��

��

���

��

��

���

AAAAAAA

��

��

���

aaaaaaaaaaaaaaaaa!!!!!!!!!!!!!!!!!HHHH

HHHHHH

HHHH

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

..

..

..

..

..

..

..

..

..

..

..

..u

w

X ′ U ′

W ′

G′

26

ALTERNATIVA 2: |ΓG(Y )| = |Y | para algum ∅ ⊂ Y ⊂ U

• H := G[Y ∪ ΓG(Y )] satisfaz condição de Hall

• Hip de indução: H tem emp F que satura Y

• G′ := G− V (H) satisfaz condição de Hall

• Hip de indução: G′ tem emp E′ que satura U ′

• F ∪ E′ é emp em G que satura U . �

u

u

uuuu

u

u

uu uuAAAAAAA

��

��

���

��

��

���

AAAAAAA

��

��

���!!!!!!!!!!!!!!!!!

��

��

��� A

AA

AA

AA

!!!!!!!!!!!!!!!!!Y

Γ(Y )

H G′

De volta ao emp máximo. . .

27

Emparelhamento máximo

em grafos bipartidos

Teorema de König:Se G é bipartido então α′(G) = β(G)

PROVA: Basta encontrar E e C tq |E| = |C|

• Cobertura mínima C

• H := G[(U ∩ C) ∪ (W r C)]

• H satisfaz condições de Hall (se |ΓH(X)| < |X|então (C r X) ∪ ΓH(X) seria cobertura de G menor que C )

• H tem um emp F que satura U ∩ C

• H ′ := G[(W ∩ C) ∪ (U r C)]

• H ′ tem emp F ′ que satura W ∩ C

• F ∪ F ′ é um emp em G e |F ∪ F ′| = |C|

u u

u

u

u u u u

uu�

��

��

��

BBBBBBBB

BB

BB

BB@

@@

@@

@@�

��

��

��

�������

���������������������

��

��

��

BBBBBBB

��

��

���

��

��

��

�

@@

@@

@@@

BBBBBBB���������������������

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

..

..

..

..

.

..

..

..

..

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

..

..

..

..

.

..

..

..

..

.

C

C

HH ′

28

Teorema de König é um “teorema min-max”

De volta aos grafos arbitrários . . .

29

Emparelhamento perfeito

Um emp é perfeito se satura todos os vértices

Condições de existência?

Exemplos:

• estados do Brasil• grade• slither

t t ttttt

t t

t

t t

30

Condição de Tutte:i(G− S) ≤ |S| para todo S ⊆ V (G)

Exercício: condição de Tutte implica n par

Fato: Se G tem emp perfeitoentão condição de Tutte satisfeita

Teorema de Tutte: Se condição satisfeitaentão G tem emp perfeito

31

Emparelhamento máximo

Teorema de Tutte-Berge: Para qquer G

α′(G) =n(G)

2− max

S⊆V

i(G− S)− |S|2

PROVA: Basta encontrar E e S tais queno máximo i(G− S)− |S| vértices ficam insaturados

Esse é um “teorema minimax”

32

Exercício para amanhã:

• Todo grafo bipartido k-regular tem um emp perfeito

• Em qquer grafo G, se X é emp maximal então|X| ≥ 1

2 α′

33

AULA 3A

Coloração de vértices

34

Coloração de vértices

35

AULA 3B

Coloração de arestas

36

Coloração de arestas

37