1/20

Introducao a ECI

Grafos e Combinatoria

Fabio Botler

Programa de Engenharia de Sistemas e ComputacaoUniversidade Federal do Rio de Janeiro

6 de outubro de 2020

2/20

Matematica Discreta

Matematica Discreta e o estudo de estruturas matematicas quesao fundamentalmente discretas em vez de contınuas. Emcontraste com os numeros reais que tem a propriedade de variar“suavemente”, os objetos estudados em matematica discreta -como numeros inteiros, grafos e declaracoes em logica - nao variamsuavemente dessa forma, mas tem valores distintos e separados.

2/20

Matematica Discreta

Matematica Discreta e o estudo de estruturas matematicas quesao fundamentalmente discretas em vez de contınuas. Emcontraste com os numeros reais que tem a propriedade de variar“suavemente”, os objetos estudados em matematica discreta -como numeros inteiros, grafos e declaracoes em logica - nao variamsuavemente dessa forma, mas tem valores distintos e separados.

3/20

Grafos

Um grafo e um par ordenado (V ,E ) onde V e um conjunto naovazio e E e um conjunto de pares de elementos de V .

Chamamos de vertices e arestas.

3/20

Grafos

Um grafo e um par ordenado (V ,E ) onde V e um conjunto naovazio e E e um conjunto de pares de elementos de V .

Chamamos de vertices e arestas.

3/20

Grafos

Um grafo e um par ordenado (V ,E ) onde V e um conjunto naovazio e E e um conjunto de pares de elementos de V .

Chamamos de vertices e arestas.

4/20

5/20

Coloracoes ımpares

E possıvel colorir as arestas de um grafo de forma que os graus decada cor sejam sempre ımpares?

5/20

Coloracoes ımparesE possıvel colorir as arestas de um grafo de forma que os graus decada cor sejam sempre ımpares?

6/20

Coloracoes ımpares

I E sempre possıvel colorir com quatro cores?

SIM Pyber, 1991

I Qual o comportamento mais comum?Quase certamente e possıvel colorir com

I duas cores se G tem um numero par de vertices

I tres cores se G tem um numero ımpar de vertices

Botler, Colucci, Kohayakawa, 2020

6/20

Coloracoes ımpares

I E sempre possıvel colorir com quatro cores?SIM Pyber, 1991

I Qual o comportamento mais comum?Quase certamente e possıvel colorir com

I duas cores se G tem um numero par de vertices

I tres cores se G tem um numero ımpar de vertices

Botler, Colucci, Kohayakawa, 2020

6/20

Coloracoes ımpares

I E sempre possıvel colorir com quatro cores?SIM Pyber, 1991

I Qual o comportamento mais comum?

Quase certamente e possıvel colorir com

I duas cores se G tem um numero par de vertices

I tres cores se G tem um numero ımpar de vertices

Botler, Colucci, Kohayakawa, 2020

6/20

Coloracoes ımpares

I E sempre possıvel colorir com quatro cores?SIM Pyber, 1991

I Qual o comportamento mais comum?Quase certamente e possıvel colorir com

I duas cores se G tem um numero par de vertices

I tres cores se G tem um numero ımpar de vertices

Botler, Colucci, Kohayakawa, 2020

7/20

Coloracoes modulo k

E se quisermos colorir de forma que os graus de cada cor sejamsempre 1 modulo k?

E possıvel colorir com 5k2 log k cores. Scott, 1997

E possıvel colorir com 200k cores.Mas quase certamente e possıvel colorir com k e k + 1 cores(dependendo da paridade do numero de vertices)

Botler, Colucci, Kohayakawa, 2020

E possıvel colorir com k + 2 cores?

7/20

Coloracoes modulo k

E se quisermos colorir de forma que os graus de cada cor sejamsempre 1 modulo k?

E possıvel colorir com 5k2 log k cores. Scott, 1997

E possıvel colorir com 200k cores.Mas quase certamente e possıvel colorir com k e k + 1 cores(dependendo da paridade do numero de vertices)

Botler, Colucci, Kohayakawa, 2020

E possıvel colorir com k + 2 cores?

7/20

Coloracoes modulo k

E se quisermos colorir de forma que os graus de cada cor sejamsempre 1 modulo k?

E possıvel colorir com 5k2 log k cores. Scott, 1997

E possıvel colorir com 200k cores.

Mas quase certamente e possıvel colorir com k e k + 1 cores(dependendo da paridade do numero de vertices)

Botler, Colucci, Kohayakawa, 2020

E possıvel colorir com k + 2 cores?

7/20

Coloracoes modulo k

E se quisermos colorir de forma que os graus de cada cor sejamsempre 1 modulo k?

E possıvel colorir com 5k2 log k cores. Scott, 1997

E possıvel colorir com 200k cores.Mas quase certamente e possıvel colorir com k e k + 1 cores(dependendo da paridade do numero de vertices)

Botler, Colucci, Kohayakawa, 2020

E possıvel colorir com k + 2 cores?

7/20

Coloracoes modulo k

E se quisermos colorir de forma que os graus de cada cor sejamsempre 1 modulo k?

E possıvel colorir com 5k2 log k cores. Scott, 1997

E possıvel colorir com 200k cores.Mas quase certamente e possıvel colorir com k e k + 1 cores(dependendo da paridade do numero de vertices)

Botler, Colucci, Kohayakawa, 2020

E possıvel colorir com k + 2 cores?

8/20

Coloracoes localmente irregulares

E se quisermos colorir de forma que vertices adjacentes tenhamgraus diferentes?

Mas nem sempre da pra colorir desta forma:

8/20

Coloracoes localmente irregulares

E se quisermos colorir de forma que vertices adjacentes tenhamgraus diferentes?

Mas nem sempre da pra colorir desta forma:

8/20

Coloracoes localmente irregulares

E se quisermos colorir de forma que vertices adjacentes tenhamgraus diferentes?

Mas nem sempre da pra colorir desta forma:

8/20

Coloracoes localmente irregulares

E se quisermos colorir de forma que vertices adjacentes tenhamgraus diferentes?

Mas nem sempre da pra colorir desta forma:

8/20

Coloracoes localmente irregulares

E se quisermos colorir de forma que vertices adjacentes tenhamgraus diferentes?

Mas nem sempre da pra colorir desta forma:

9/20

Orientacoes

Uma orientacao de G e uma atribuicao de uma direcao para cadaaresta de G

9/20

Orientacoes

Uma orientacao de G e uma atribuicao de uma direcao para cadaaresta de G

9/20

Orientacoes

Uma orientacao de G e uma atribuicao de uma direcao para cadaaresta de G

9/20

Orientacoes

Uma orientacao de G e uma atribuicao de uma direcao para cadaaresta de G

10/20

Orientacoes

De quantas formas podemos orientar um grafo?

Cada aresta pode ser orientada em duas direcoes.

Entao sao 2|E(G)| formas.

Qual e o numero maximo de formas que podemos orientar umgrafo de forma a evitar um determinado padrao?

(Erdos, 1974)

10/20

Orientacoes

De quantas formas podemos orientar um grafo?

Cada aresta pode ser orientada em duas direcoes.

Entao sao 2|E(G)| formas.

Qual e o numero maximo de formas que podemos orientar umgrafo de forma a evitar um determinado padrao?

(Erdos, 1974)

10/20

Orientacoes

De quantas formas podemos orientar um grafo?

Cada aresta pode ser orientada em duas direcoes.

Entao sao 2|E(G)| formas.

Qual e o numero maximo de formas que podemos orientar umgrafo de forma a evitar um determinado padrao?

(Erdos, 1974)

10/20

Orientacoes

De quantas formas podemos orientar um grafo?

Cada aresta pode ser orientada em duas direcoes.

Entao sao 2|E(G)| formas.

Qual e o numero maximo de formas que podemos orientar umgrafo de forma a evitar um determinado padrao?

(Erdos, 1974)

11/20

Orientacoes

Ex: K�3

11/20

Orientacoes

Ex: K�3

11/20

Orientacoes

Ex: K�3

12/20

Orientacoes

O numero maximo de formas de orientar sem K�3 um grafo com n

vertices e 2bn2/4c.

Alem disso, O (unico) grafo que maximiza o numero de taisorientacoes e o bipartido completo

Araujo–Botler–Mota, 2020

E se evitarmos outros padroes?

12/20

Orientacoes

O numero maximo de formas de orientar sem K�3 um grafo com n

vertices e 2bn2/4c.

Alem disso, O (unico) grafo que maximiza o numero de taisorientacoes e o bipartido completo

Araujo–Botler–Mota, 2020

E se evitarmos outros padroes?

13/20

Permutacoes

Uma permutacao e uma ordenacao do conjunto {1, . . . , n}.

ex: 1476235.

Sempre ha uma permutacao alternante?

Sim: 1726354.Mais geralmente: 1(n − 1)2(n − 2)3 · · ·.

13/20

Permutacoes

Uma permutacao e uma ordenacao do conjunto {1, . . . , n}.

ex: 1476235.

Sempre ha uma permutacao alternante?

Sim: 1726354.Mais geralmente: 1(n − 1)2(n − 2)3 · · ·.

13/20

Permutacoes

Uma permutacao e uma ordenacao do conjunto {1, . . . , n}.

ex: 1476235.

Sempre ha uma permutacao alternante?

Sim: 1726354.Mais geralmente: 1(n − 1)2(n − 2)3 · · ·.

13/20

Permutacoes

Uma permutacao e uma ordenacao do conjunto {1, . . . , n}.

ex: 1476235.

Sempre ha uma permutacao alternante?

Sim: 1726354.

Mais geralmente: 1(n − 1)2(n − 2)3 · · ·.

13/20

Permutacoes

Uma permutacao e uma ordenacao do conjunto {1, . . . , n}.

ex: 1476235.

Sempre ha uma permutacao alternante?

Sim: 1726354.Mais geralmente: 1(n − 1)2(n − 2)3 · · ·.

14/20

Permutacoes

Dada uma permutacao P = (x1, x2, . . . , xn), o vetor diferenca de Pe o vetor

diff (P) = (|x2 − x1|, |x3 − x2|, . . . , |xn − xn−1|)

Sempre ha uma permutacao para a qual diff (P) tambem e umapermutacao?

Sim: 1726354, pois diff (P) = 654321.

E se quisermos evitar alguns valores em diff (P)?

Qual a relacao disso com grafos?

14/20

Permutacoes

Dada uma permutacao P = (x1, x2, . . . , xn), o vetor diferenca de Pe o vetor

diff (P) = (|x2 − x1|, |x3 − x2|, . . . , |xn − xn−1|)

Sempre ha uma permutacao para a qual diff (P) tambem e umapermutacao?

Sim: 1726354, pois diff (P) = 654321.

E se quisermos evitar alguns valores em diff (P)?

Qual a relacao disso com grafos?

14/20

Permutacoes

Dada uma permutacao P = (x1, x2, . . . , xn), o vetor diferenca de Pe o vetor

diff (P) = (|x2 − x1|, |x3 − x2|, . . . , |xn − xn−1|)

Sempre ha uma permutacao para a qual diff (P) tambem e umapermutacao?

Sim: 1726354, pois diff (P) = 654321.

E se quisermos evitar alguns valores em diff (P)?

Qual a relacao disso com grafos?

14/20

Permutacoes

Dada uma permutacao P = (x1, x2, . . . , xn), o vetor diferenca de Pe o vetor

diff (P) = (|x2 − x1|, |x3 − x2|, . . . , |xn − xn−1|)

Sempre ha uma permutacao para a qual diff (P) tambem e umapermutacao?

Sim: 1726354, pois diff (P) = 654321.

E se quisermos evitar alguns valores em diff (P)?

Qual a relacao disso com grafos?

14/20

Permutacoes

Dada uma permutacao P = (x1, x2, . . . , xn), o vetor diferenca de Pe o vetor

diff (P) = (|x2 − x1|, |x3 − x2|, . . . , |xn − xn−1|)

Sempre ha uma permutacao para a qual diff (P) tambem e umapermutacao?

Sim: 1726354, pois diff (P) = 654321.

E se quisermos evitar alguns valores em diff (P)?

Qual a relacao disso com grafos?

15/20

PermutacoesQual a relacao disso com grafos?

1

2

3

4

5

6

7

8

15/20

PermutacoesQual a relacao disso com grafos?

1

2

3

4

5

6

7

8

16/20

17/20

Permutacoes Montanha-Russa

Uma permutacao π = x1x2 · · · xn e alternante se

x1 > x2 < x3 > x4 < · · ·

oux1 < x2 > x3 < x4 > · · ·

ex: 18273645.

Possui 4 picos e 4 vales.

E se quisermos picos e vales de todas as subsequencias?

17/20

Permutacoes Montanha-Russa

Uma permutacao π = x1x2 · · · xn e alternante se

x1 > x2 < x3 > x4 < · · ·

oux1 < x2 > x3 < x4 > · · ·

ex: 18273645.

Possui 4 picos e 4 vales.

E se quisermos picos e vales de todas as subsequencias?

17/20

Permutacoes Montanha-Russa

Uma permutacao π = x1x2 · · · xn e alternante se

x1 > x2 < x3 > x4 < · · ·

oux1 < x2 > x3 < x4 > · · ·

ex: 18273645.

Possui 4 picos e 4 vales.

E se quisermos picos e vales de todas as subsequencias?

17/20

Permutacoes Montanha-Russa

Uma permutacao π = x1x2 · · · xn e alternante se

x1 > x2 < x3 > x4 < · · ·

oux1 < x2 > x3 < x4 > · · ·

ex: 18273645.

Possui 4 picos e 4 vales.

E se quisermos picos e vales de todas as subsequencias?

17/20

Permutacoes Montanha-Russa

Uma permutacao π = x1x2 · · · xn e alternante se

x1 > x2 < x3 > x4 < · · ·

oux1 < x2 > x3 < x4 > · · ·

ex: 18273645.

Possui 4 picos e 4 vales.

E se quisermos picos e vales de todas as subsequencias?

18/20

Permutacoes Montanha-Russa

Uma permutacao e dita montanha russa se maximiza a soma onumero de picos e vales sobre todas as suas subsequencias.

1

8

2

7

3

6

4

5

594 picos e vales totais

4

6

2

8

1

7

3

5

653 picos e vales totais

18/20

Permutacoes Montanha-Russa

Uma permutacao e dita montanha russa se maximiza a soma onumero de picos e vales sobre todas as suas subsequencias.

1

8

2

7

3

6

4

5

594 picos e vales totais

4

6

2

8

1

7

3

5

653 picos e vales totais

18/20

Permutacoes Montanha-Russa

Uma permutacao e dita montanha russa se maximiza a soma onumero de picos e vales sobre todas as suas subsequencias.

1

8

2

7

3

6

4

5

594 picos e vales totais

4

6

2

8

1

7

3

5

653 picos e vales totais

19/20

Permutacoes Montanha-Russa

1

20

2

19

3

18

4

17

5

16

6

15

7

14

8

13

9

12

10

11

6757290 picos e vales totais

10

15

5

18

2

12

8

20

4

14

7

17

1

13

9

19

3

16

6

11

7588303 picos e vales totais

20/20

Introducao a ECI

Grafos e Combinatoria

Fabio Botler

Programa de Engenharia de Sistemas e ComputacaoUniversidade Federal do Rio de Janeiro

6 de outubro de 2020