Introdução à Teoria dos Grafos - Gilvan...

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Introdução à Teoria dos GrafosCurso: Introdução à Análise de Redes

Pós-Graduação em Demografia - FACE - UFMG

Prof. Gilvan R. Guedes e Wesley H. S. Pereira

Departamento de Demografia - UFMG

16 de Setembro de 2017

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Informações do Curso

Disciplina: Introdução à Análise de Redes* Website: http://gilvanguedes.com/network-analysis/

* Carga-horária: 30 horas - 2 créditos* Número de aulas: 9 aulas* Início: 17/10/2017* Previsão de Término: 19/12/2017Professor: Gilvan Ramalho Guedes (CEDEPLAR/UFMG)* e-mail: grguedes@cedeplar.ufmg.br* Gabinete: FACE 3093Monitor: Wesley Henrique Silva Pereira (DEST/UFMG)* e-mail: wesleyhspereira@gmail.com

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Avaliações

Disciplina: Introdução à Análise de Redes* Exercício: Cálculo e interpretação de parâmetros (30

pontos)* Exercício: Representação visual da rede e intepretação (30

pontos)* Trabalho Final: Análise aplicada a um estudo de caso à

escolha do aluno (40 pontos)

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Sobre este material

Essas notas de aula são parcialmente baseadas em:* Kolaczyk (2009) Statistical analysis of network data-methods

and models;* Feofiloff (2016) Algorítmos para grafos e c via sedgewick (url

nas referências);* UFSC (UFSC) Conceitos básicos da Teoria dos Grafos (url

nas referências);* Notas de aula de Teoria dos Grafos - Urrutia, S.

(DCC/UFMG);* Notas de aula de Teoria dos Grafos - Nogueira, L. T

(IC/UFF);

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Definição de Análise de RedesDefinição de Teoria dos GrafosGrafos e redesMotivação

A Análise de Redes é a área da Tecnologia da Informação edas Ciências Sociais que trata do processo de analisar qualquertipo de rede por intermédio da Teoria das Redes;

Estuda interdisciplinarmente redes complexas, como porexemplo redes de computador, redes biológicas, redes cognitivase redes sociais;

É definida como “o estudo das representações de rede defenômenos físicos, biológicos e sociais, levando a modelospreditivos desses fenômenos.”, (Council et al., 2006)

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Definição de Análise de RedesDefinição de Teoria dos GrafosGrafos e redesMotivação

A Análise de Redes é a área da Tecnologia da Informação edas Ciências Sociais que trata do processo de analisar qualquertipo de rede por intermédio da Teoria das Redes;

Estuda interdisciplinarmente redes complexas, como porexemplo redes de computador, redes biológicas, redes cognitivase redes sociais;

É definida como “o estudo das representações de rede defenômenos físicos, biológicos e sociais, levando a modelospreditivos desses fenômenos.”, (Council et al., 2006)

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Definição de Análise de RedesDefinição de Teoria dos GrafosGrafos e redesMotivação

A Análise de Redes é a área da Tecnologia da Informação edas Ciências Sociais que trata do processo de analisar qualquertipo de rede por intermédio da Teoria das Redes;

Estuda interdisciplinarmente redes complexas, como porexemplo redes de computador, redes biológicas, redes cognitivase redes sociais;

É definida como “o estudo das representações de rede defenômenos físicos, biológicos e sociais, levando a modelospreditivos desses fenômenos.”, (Council et al., 2006)

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Definição de Análise de RedesDefinição de Teoria dos GrafosGrafos e redesMotivação

Teoria dos Grafos

A Teoria dos Grafos é um ramo da Matemática que estuda asrelações entre um conjunto de objetos;

“A Teoria dos Grafos estuda objetos combinatórios — os grafos— que são um bom modelo para muitos problemas em váriosramos da Matemática, da Informática, da Engenharia e daIndústria. Muitos dos problemas sobre grafos tornaram-secélebres porque são um interessante desafio intelectual eporque têm importantes aplicações práticas.” (Feofiloff et al.,2011).

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Definição de Análise de RedesDefinição de Teoria dos GrafosGrafos e redesMotivação

Teoria dos Grafos

A Teoria dos Grafos é um ramo da Matemática que estuda asrelações entre um conjunto de objetos;

“A Teoria dos Grafos estuda objetos combinatórios — os grafos— que são um bom modelo para muitos problemas em váriosramos da Matemática, da Informática, da Engenharia e daIndústria. Muitos dos problemas sobre grafos tornaram-secélebres porque são um interessante desafio intelectual eporque têm importantes aplicações práticas.” (Feofiloff et al.,2011).

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Definição de Análise de RedesDefinição de Teoria dos GrafosGrafos e redesMotivação

Desambiguação

Em termos práticos, a principal diferença entre uma rede e um grafoestá na motivação:

Em geral uma rede surge da observação de um fenômenorelacional e necessariamente está atrelada àquele fenômeno. Poroutro lado, um grafo não necessita de um motivo para existir: eleé como um número ou um segmento de reta em Matemática;

Uma rede pode ser representada por um grafo, isto é, ela dáorigem a um grafo. Em geral, não há sentido em dizer que umgrafo deu origem a uma rede;

A rede pode ser encarada como o objeto sobre o qual se baseia oestudo sobre um fenôneno relacional. Através dos grafos, aTeoria dos Grafos é uma ferramenta que nos permite estudar ocaráter relacional de um conjunto dados.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Definição de Análise de RedesDefinição de Teoria dos GrafosGrafos e redesMotivação

Desambiguação

Em termos práticos, a principal diferença entre uma rede e um grafoestá na motivação:

Em geral uma rede surge da observação de um fenômenorelacional e necessariamente está atrelada àquele fenômeno. Poroutro lado, um grafo não necessita de um motivo para existir: eleé como um número ou um segmento de reta em Matemática;

Uma rede pode ser representada por um grafo, isto é, ela dáorigem a um grafo. Em geral, não há sentido em dizer que umgrafo deu origem a uma rede;

A rede pode ser encarada como o objeto sobre o qual se baseia oestudo sobre um fenôneno relacional. Através dos grafos, aTeoria dos Grafos é uma ferramenta que nos permite estudar ocaráter relacional de um conjunto dados.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Definição de Análise de RedesDefinição de Teoria dos GrafosGrafos e redesMotivação

Desambiguação

Em termos práticos, a principal diferença entre uma rede e um grafoestá na motivação:

Em geral uma rede surge da observação de um fenômenorelacional e necessariamente está atrelada àquele fenômeno. Poroutro lado, um grafo não necessita de um motivo para existir: eleé como um número ou um segmento de reta em Matemática;

Uma rede pode ser representada por um grafo, isto é, ela dáorigem a um grafo. Em geral, não há sentido em dizer que umgrafo deu origem a uma rede;

A rede pode ser encarada como o objeto sobre o qual se baseia oestudo sobre um fenôneno relacional. Através dos grafos, aTeoria dos Grafos é uma ferramenta que nos permite estudar ocaráter relacional de um conjunto dados.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Definição de Análise de RedesDefinição de Teoria dos GrafosGrafos e redesMotivação

Desambiguação

Em termos práticos, a principal diferença entre uma rede e um grafoestá na motivação:

Em geral uma rede surge da observação de um fenômenorelacional e necessariamente está atrelada àquele fenômeno. Poroutro lado, um grafo não necessita de um motivo para existir: eleé como um número ou um segmento de reta em Matemática;

Uma rede pode ser representada por um grafo, isto é, ela dáorigem a um grafo. Em geral, não há sentido em dizer que umgrafo deu origem a uma rede;

A rede pode ser encarada como o objeto sobre o qual se baseia oestudo sobre um fenôneno relacional. Através dos grafos, aTeoria dos Grafos é uma ferramenta que nos permite estudar ocaráter relacional de um conjunto dados.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Definição de Análise de RedesDefinição de Teoria dos GrafosGrafos e redesMotivação

Então, por que estudar grafos?

Porque tanto a rede quanto o grafo estudam as relações entreobjetos;

Porque através deles modelamos fenômenos relacionais de todanatureza em um modelo matemático formalizado;

Porque embora tenhamos visto que uma rede não é um grafo,um grafo é a representação mais natural para uma rede.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Definição de Análise de RedesDefinição de Teoria dos GrafosGrafos e redesMotivação

Então, por que estudar grafos?

Porque tanto a rede quanto o grafo estudam as relações entreobjetos;

Porque através deles modelamos fenômenos relacionais de todanatureza em um modelo matemático formalizado;

Porque embora tenhamos visto que uma rede não é um grafo,um grafo é a representação mais natural para uma rede.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Definição de Análise de RedesDefinição de Teoria dos GrafosGrafos e redesMotivação

Então, por que estudar grafos?

Porque tanto a rede quanto o grafo estudam as relações entreobjetos;

Porque através deles modelamos fenômenos relacionais de todanatureza em um modelo matemático formalizado;

Porque embora tenhamos visto que uma rede não é um grafo,um grafo é a representação mais natural para uma rede.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

Definição de Análise de RedesDefinição de Teoria dos GrafosGrafos e redesMotivação

Então, por que estudar grafos?

Porque tanto a rede quanto o grafo estudam as relações entreobjetos;

Porque através deles modelamos fenômenos relacionais de todanatureza em um modelo matemático formalizado;

Porque embora tenhamos visto que uma rede não é um grafo,um grafo é a representação mais natural para uma rede.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

O problema das sete pontes de Königsberg

É possível atravessar as 7 pontes sem repetir nenhuma?

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Modelagem

Temos:

4 localidades e 7 pontes;4 pontos e 7 conexões;

Proposta A Proposta B Proposta C

Qual proposta acima representa corretamente o problema em questão?Resposta: Todas elas representam o mesmo fenômeno, as pontes deKönigsberg, corretamente.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Modelagem

Temos:4 localidades e 7 pontes;

4 pontos e 7 conexões;

Proposta A Proposta B Proposta C

Qual proposta acima representa corretamente o problema em questão?Resposta: Todas elas representam o mesmo fenômeno, as pontes deKönigsberg, corretamente.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Modelagem

Temos:4 localidades e 7 pontes;4 pontos e 7 conexões;

Proposta A Proposta B Proposta C

Qual proposta acima representa corretamente o problema em questão?Resposta: Todas elas representam o mesmo fenômeno, as pontes deKönigsberg, corretamente.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Modelagem

Temos:4 localidades e 7 pontes;4 pontos e 7 conexões;

Proposta A

Proposta B Proposta C

Qual proposta acima representa corretamente o problema em questão?Resposta: Todas elas representam o mesmo fenômeno, as pontes deKönigsberg, corretamente.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Modelagem

Temos:4 localidades e 7 pontes;4 pontos e 7 conexões;

Proposta A Proposta B

Proposta C

Qual proposta acima representa corretamente o problema em questão?Resposta: Todas elas representam o mesmo fenômeno, as pontes deKönigsberg, corretamente.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Modelagem

Temos:4 localidades e 7 pontes;4 pontos e 7 conexões;

Proposta A Proposta B Proposta C

Qual proposta acima representa corretamente o problema em questão?Resposta: Todas elas representam o mesmo fenômeno, as pontes deKönigsberg, corretamente.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Modelagem

Temos:4 localidades e 7 pontes;4 pontos e 7 conexões;

Proposta A Proposta B Proposta C

Qual proposta acima representa corretamente o problema em questão?

Resposta: Todas elas representam o mesmo fenômeno, as pontes deKönigsberg, corretamente.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Modelagem

Temos:4 localidades e 7 pontes;4 pontos e 7 conexões;

Proposta A Proposta B Proposta C

Qual proposta acima representa corretamente o problema em questão?Resposta: Todas elas representam o mesmo fenômeno, as pontes deKönigsberg, corretamente.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Suponha que exista um percurso que atravesse as pontes semrepetir qualquer uma delas.

Façamos P o nosso ponto departida genérico e F o nosso ponto final genérico.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Suponha que exista um percurso que atravesse as pontes semrepetir qualquer uma delas. Façamos P o nosso ponto departida genérico e F o nosso ponto final genérico.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Suponha que exista um percurso que atravesse as pontes semrepetir qualquer uma delas. Façamos P o nosso ponto departida genérico e F o nosso ponto final genérico.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Vamos chamar de C o conjunto dos pontos pertencentes a essepercurso e que não são nem o ponto partida e nem oponto final. Como o caminho existe, C deve intermerdiar opercurso entre P e F .

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Vamos chamar de C o conjunto dos pontos pertencentes a essepercurso e que não são nem o ponto partida e nem oponto final. Como o caminho existe, C deve intermerdiar opercurso entre P e F .

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Já que o percurso existe, então existe uma ponte que vai de Ppara um ponto C1 genérico e uma ponte que vai de um pontoC2 genérico para F .

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Já que o percurso existe, então existe uma ponte que vai de Ppara um ponto C1 genérico e uma ponte que vai de um pontoC2 genérico para F .

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Já que o percurso existe, então existe uma ponte que vai de Ppara um ponto C1 genérico e uma ponte que vai de um pontoC2 genérico para F .

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Já que o percurso existe, então existe uma ponte que vai de Ppara um ponto C1 genérico e uma ponte que vai de um pontoC2 genérico para F .

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Sempre assumindo que o percurso existe, ele percorre um determinadonúmero de pontos entre P e F . Como este raciocínio é generalista,informações como o número de pontos visitados ou quantas visitas sãofeitas são desconhecidas.

Mas elas são realmente necessárias? Aresposta é NÃO.

Basta perceber que como os pontos de C estão no percurso de P paraF , toda vez que visitamos um ponto pertencente a C, então há umaponte deste ponto para um outro ponto. Em outras palavras, paracada ponte de entrada em Ci, necessariamente deve haveruma ponte de saída de Ci para todo Ci pertencente a C.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Sempre assumindo que o percurso existe, ele percorre um determinadonúmero de pontos entre P e F . Como este raciocínio é generalista,informações como o número de pontos visitados ou quantas visitas sãofeitas são desconhecidas. Mas elas são realmente necessárias?

Aresposta é NÃO.

Basta perceber que como os pontos de C estão no percurso de P paraF , toda vez que visitamos um ponto pertencente a C, então há umaponte deste ponto para um outro ponto. Em outras palavras, paracada ponte de entrada em Ci, necessariamente deve haveruma ponte de saída de Ci para todo Ci pertencente a C.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Sempre assumindo que o percurso existe, ele percorre um determinadonúmero de pontos entre P e F . Como este raciocínio é generalista,informações como o número de pontos visitados ou quantas visitas sãofeitas são desconhecidas. Mas elas são realmente necessárias? Aresposta é NÃO.

Basta perceber que como os pontos de C estão no percurso de P paraF , toda vez que visitamos um ponto pertencente a C, então há umaponte deste ponto para um outro ponto. Em outras palavras, paracada ponte de entrada em Ci, necessariamente deve haveruma ponte de saída de Ci para todo Ci pertencente a C.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Sempre assumindo que o percurso existe, ele percorre um determinadonúmero de pontos entre P e F . Como este raciocínio é generalista,informações como o número de pontos visitados ou quantas visitas sãofeitas são desconhecidas. Mas elas são realmente necessárias? Aresposta é NÃO.

Basta perceber que como os pontos de C estão no percurso de P paraF , toda vez que visitamos um ponto pertencente a C, então há umaponte deste ponto para um outro ponto. Em outras palavras, paracada ponte de entrada em Ci, necessariamente deve haveruma ponte de saída de Ci para todo Ci pertencente a C.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Sempre assumindo que o percurso existe, ele percorre um determinadonúmero de pontos entre P e F . Como este raciocínio é generalista,informações como o número de pontos visitados ou quantas visitas sãofeitas são desconhecidas. Mas elas são realmente necessárias? Aresposta é NÃO.

Basta perceber que como os pontos de C estão no percurso de P paraF , toda vez que visitamos um ponto pertencente a C, então há umaponte deste ponto para um outro ponto. Em outras palavras, paracada ponte de entrada em Ci, necessariamente deve haveruma ponte de saída de Ci para todo Ci pertencente a C.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Sempre assumindo que o percurso existe, ele percorre um determinadonúmero de pontos entre P e F . Como este raciocínio é generalista,informações como o número de pontos visitados ou quantas visitas sãofeitas são desconhecidas. Mas elas são realmente necessárias? Aresposta é NÃO.

Basta perceber que como os pontos de C estão no percurso de P paraF , toda vez que visitamos um ponto pertencente a C, então há umaponte deste ponto para um outro ponto. Em outras palavras, paracada ponte de entrada em Ci, necessariamente deve haveruma ponte de saída de Ci para todo Ci pertencente a C.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Sempre assumindo que o percurso existe, ele percorre um determinadonúmero de pontos entre P e F . Como este raciocínio é generalista,informações como o número de pontos visitados ou quantas visitas sãofeitas são desconhecidas. Mas elas são realmente necessárias? Aresposta é NÃO.

Basta perceber que como os pontos de C estão no percurso de P paraF , toda vez que visitamos um ponto pertencente a C, então há umaponte deste ponto para um outro ponto. Em outras palavras, paracada ponte de entrada em Ci, necessariamente deve haveruma ponte de saída de Ci para todo Ci pertencente a C.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Sempre assumindo que o percurso existe, ele percorre um determinadonúmero de pontos entre P e F . Como este raciocínio é generalista,informações como o número de pontos visitados ou quantas visitas sãofeitas são desconhecidas. Mas elas são realmente necessárias? Aresposta é NÃO.

Basta perceber que como os pontos de C estão no percurso de P paraF , toda vez que visitamos um ponto pertencente a C, então há umaponte deste ponto para um outro ponto. Em outras palavras, paracada ponte de entrada em Ci, necessariamente deve haveruma ponte de saída de Ci para todo Ci pertencente a C.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Sempre assumindo que o percurso existe, ele percorre um determinadonúmero de pontos entre P e F . Como este raciocínio é generalista,informações como o número de pontos visitados ou quantas visitas sãofeitas são desconhecidas. Mas elas são realmente necessárias? Aresposta é NÃO.

Basta perceber que como os pontos de C estão no percurso de P paraF , toda vez que visitamos um ponto pertencente a C, então há umaponte deste ponto para um outro ponto. Em outras palavras, paracada ponte de entrada em Ci, necessariamente deve haveruma ponte de saída de Ci para todo Ci pertencente a C.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Sempre assumindo que o percurso existe, ele percorre um determinadonúmero de pontos entre P e F . Como este raciocínio é generalista,informações como o número de pontos visitados ou quantas visitas sãofeitas são desconhecidas. Mas elas são realmente necessárias? Aresposta é NÃO.

Basta perceber que como os pontos de C estão no percurso de P paraF , toda vez que visitamos um ponto pertencente a C, então há umaponte deste ponto para um outro ponto. Em outras palavras, paracada ponte de entrada em Ci, necessariamente deve haveruma ponte de saída de Ci para todo Ci pertencente a C.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Sempre assumindo que o percurso existe, ele percorre um determinadonúmero de pontos entre P e F . Como este raciocínio é generalista,informações como o número de pontos visitados ou quantas visitas sãofeitas são desconhecidas. Mas elas são realmente necessárias? Aresposta é NÃO.

Basta perceber que como os pontos de C estão no percurso de P paraF , toda vez que visitamos um ponto pertencente a C, então há umaponte deste ponto para um outro ponto. Em outras palavras, paracada ponte de entrada em Ci, necessariamente deve haveruma ponte de saída de Ci para todo Ci pertencente a C.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Sempre assumindo que o percurso existe, ele percorre um determinadonúmero de pontos entre P e F . Como este raciocínio é generalista,informações como o número de pontos visitados ou quantas visitas sãofeitas são desconhecidas. Mas elas são realmente necessárias? Aresposta é NÃO.

Basta perceber que como os pontos de C estão no percurso de P paraF , toda vez que visitamos um ponto pertencente a C, então há umaponte deste ponto para um outro ponto. Em outras palavras, paracada ponte de entrada em Ci, necessariamente deve haveruma ponte de saída de Ci para todo Ci pertencente a C.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Então, o número de pontes que conectam qualquer pontopertencente a C deve ser necessariamente par.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Então, o número de pontes que conectam qualquer pontopertencente a C deve ser necessariamente par.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Então, o número de pontes que conectam qualquer pontopertencente a C deve ser necessariamente par.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Então, o número de pontes que conectam qualquer pontopertencente a C deve ser necessariamente par.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Então, o número de pontes que conectam qualquer pontopertencente a C deve ser necessariamente par.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Então, o número de pontes que conectam qualquer pontopertencente a C deve ser necessariamente par.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Então, o número de pontes que conectam qualquer pontopertencente a C deve ser necessariamente par.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Então, o número de pontes que conectam qualquer pontopertencente a C deve ser necessariamente par.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Então, o número de pontes que conectam qualquer pontopertencente a C deve ser necessariamente par.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Então, o número de pontes que conectam qualquer pontopertencente a C deve ser necessariamente par.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Então, o número de pontes que conectam qualquer pontopertencente a C deve ser necessariamente par.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Então, o número de pontes que conectam qualquer pontopertencente a C deve ser necessariamente par.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Então, o número de pontes que conectam qualquer pontopertencente a C deve ser necessariamente par.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Como P é ponto de partida, então o número de pontes queconectam P deve ser necessariamente ímpar: a ponte queinicia o percurso mais um par de pontes para cada visita a P .O mesmo ocorre com F : um par de pontes para cada visita a Fmais a ponte que encerra o percurso.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Como P é ponto de partida, então o número de pontes queconectam P deve ser necessariamente ímpar: a ponte queinicia o percurso mais um par de pontes para cada visita a P .O mesmo ocorre com F : um par de pontes para cada visita a Fmais a ponte que encerra o percurso.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Como P é ponto de partida, então o número de pontes queconectam P deve ser necessariamente ímpar: a ponte queinicia o percurso mais um par de pontes para cada visita a P .O mesmo ocorre com F : um par de pontes para cada visita a Fmais a ponte que encerra o percurso.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Como P é ponto de partida, então o número de pontes queconectam P deve ser necessariamente ímpar: a ponte queinicia o percurso mais um par de pontes para cada visita a P .O mesmo ocorre com F : um par de pontes para cada visita a Fmais a ponte que encerra o percurso.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Como P é ponto de partida, então o número de pontes queconectam P deve ser necessariamente ímpar: a ponte queinicia o percurso mais um par de pontes para cada visita a P .O mesmo ocorre com F : um par de pontes para cada visita a Fmais a ponte que encerra o percurso.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Como P é ponto de partida, então o número de pontes queconectam P deve ser necessariamente ímpar: a ponte queinicia o percurso mais um par de pontes para cada visita a P .O mesmo ocorre com F : um par de pontes para cada visita a Fmais a ponte que encerra o percurso.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Como P é ponto de partida, então o número de pontes queconectam P deve ser necessariamente ímpar: a ponte queinicia o percurso mais um par de pontes para cada visita a P .O mesmo ocorre com F : um par de pontes para cada visita a Fmais a ponte que encerra o percurso.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Como P é ponto de partida, então o número de pontes queconectam P deve ser necessariamente ímpar: a ponte queinicia o percurso mais um par de pontes para cada visita a P .O mesmo ocorre com F : um par de pontes para cada visita a Fmais a ponte que encerra o percurso.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Na hipótese de P e F serem o mesmo ponto, o número de pontes queo conecta deve ser necessariamente par: um par para cada visita aP = F mais as pontes que iniciam e encerram o percurso.

Então, chegamos à conclusão de que, para que o caminho exista, nomáximo 2 pontos podem ser conectados por um número ímpar depontes.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Na hipótese de P e F serem o mesmo ponto, o número de pontes queo conecta deve ser necessariamente par: um par para cada visita aP = F mais as pontes que iniciam e encerram o percurso.

Então, chegamos à conclusão de que, para que o caminho exista, nomáximo 2 pontos podem ser conectados por um número ímpar depontes.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Na hipótese de P e F serem o mesmo ponto, o número de pontes queo conecta deve ser necessariamente par: um par para cada visita aP = F mais as pontes que iniciam e encerram o percurso.

Então, chegamos à conclusão de que, para que o caminho exista, nomáximo 2 pontos podem ser conectados por um número ímpar depontes.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Na hipótese de P e F serem o mesmo ponto, o número de pontes queo conecta deve ser necessariamente par: um par para cada visita aP = F mais as pontes que iniciam e encerram o percurso.

Então, chegamos à conclusão de que, para que o caminho exista, nomáximo 2 pontos podem ser conectados por um número ímpar depontes.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Na hipótese de P e F serem o mesmo ponto, o número de pontes queo conecta deve ser necessariamente par: um par para cada visita aP = F mais as pontes que iniciam e encerram o percurso.

Então, chegamos à conclusão de que, para que o caminho exista, nomáximo 2 pontos podem ser conectados por um número ímpar depontes.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Na hipótese de P e F serem o mesmo ponto, o número de pontes queo conecta deve ser necessariamente par: um par para cada visita aP = F mais as pontes que iniciam e encerram o percurso.

Então, chegamos à conclusão de que, para que o caminho exista, nomáximo 2 pontos podem ser conectados por um número ímpar depontes.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Na hipótese de P e F serem o mesmo ponto, o número de pontes queo conecta deve ser necessariamente par: um par para cada visita aP = F mais as pontes que iniciam e encerram o percurso.

Então, chegamos à conclusão de que, para que o caminho exista, nomáximo 2 pontos podem ser conectados por um número ímpar depontes.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Problema: É possível atravessar as 7 pontes sem repetir nenhuma?

Análise:Território A : 5 pontes;Território B, C e D: 3 pontes.

Conclusão: Não existe um percurso que satisfaça o problema emquestão.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Problema: É possível atravessar as 7 pontes sem repetir nenhuma?

Análise:Território A : 5 pontes;Território B, C e D: 3 pontes.

Conclusão: Não existe um percurso que satisfaça o problema emquestão.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Problema: É possível atravessar as 7 pontes sem repetir nenhuma?Análise:

Território A : 5 pontes;Território B, C e D: 3 pontes.

Conclusão: Não existe um percurso que satisfaça o problema emquestão.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes

IntroduçãoTeoria dos Grafos

Aplicações em redesReferências

As sete pontes de KönigsberbConceitos básicosEstruturas em grafosRepresentações de um grafo

Solução

Problema: É possível atravessar as 7 pontes sem repetir nenhuma?Análise:

Território A : 5 pontes;Território B, C e D: 3 pontes.

Conclusão: Não existe um percurso que satisfaça o problema emquestão.

Prof. Gilvan R. Guedes e Wesley H. S. Pereira Aula 01 - Introdução à Análise de Redes