View
0
Download
0
Category
Preview:
Citation preview
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
Recommended