Informações que irão auxiliá-lo a cursar bem a disciplina e a compreender sua importância para o curso.

Ementa

• Definição formal de grafo e representações

• Tipos de grafos

  • Simples
  • Direcionado
  • Completo
  • Conectado
  • Multigrafo
  • Bipartido
  • Caminho
  • Ciclo
  • Subgrafo
  • Ponderado
  • Gerador
  • Induzido
  • Árvore
  • Árvore geradora
  • Aleatório

• Definição, propriedades, operações e algoritmos associados a conceitos de grafos

  • Grau e vizinhança
  • União e intersecção de grafos
  • Isomorfismo
  • Decomposição
  • Corte
  • Cobertura
  • Ponte
  • Passeio
  • Trilha
  • Circuito
  • Cintura
  • Clustering
  • Busca em árvores
  • Co-árvore
  • Matróides
  • Vértice de corte
  • Separações e blocos
  • Orientações
  • Conectividade
  • Contração

• Tópicos Avançados

  • Circuitos de Euler e Hamiltoniano
  • Fluxos em redes
  • Grafos planares
  • Estabilidade e cliques
  • Coloração
  • Casamento
• Noções básicas de complexidade de algoritmos e aproximações

Visão Geral

A disciplina é pautada em apresentar a teoria que embasa todo o estudo e as aplicações dos grafos na Ciência da Computação, porém não está focada apenas em aspectos teóricos. Também são apresentadas ferramentas para o desenvolvimento de aplicações, visualização e fixação dos conceitos ministrados. São estas:

• yEd

  • Esta é a primeira ferramenta que o aluno tem contato, com ela é possível construir vários tipos de representações, dos tipos de grafos mais simples até um dos mais complexos principalmente em termos de visualização.

• API JgraphT

  • É uma API desenvolvida em Java e que traz todos os conceitos estudados modelados e em sua grande maioria implementados e disponíveis para uso. Ao usá-la é possível enxergar resultados e aplicações práticas dos conceitos expostos em sala de aula

• Neo4J e Cypher

  • O Neo4j é um sistema de gerenciamento e armazenamento de dados através de grafos (graph database).
  • Cypher é uma linguagem de consulta semelhante a SQL que se baseia no uso de padrões de nós e relacionamentos em um grafo.

Avaliação

Não há provas na disciplina, a avaliação é realizada através de:

• MTI - Minitestes teóricos individuais (escritos).
• MTG - Minitestes teóricos (escritos) em grupo de 3 a 4 integrantes.
• EPG - Exercícios práticos em grupo, que consiste na resolução de problemas utilizando a teoria ministrada e a(s) ferramenta(s) disponibilizada(s). O EPG é dividido em duas etapas, a primeira etapa é realizada em sala, onde o planejamento da solução é feito, registrado e entregue à professora, a segunda etapa consiste na implementação da solução propriamente dita.

A nota é acumulativa e calculada da seguinte maneira:

• Média: ((MTG1+MTI1+MTG2) + (MTI2+MTG3+MTG4) + (MTI3+MTG5+MTG6) + (EPG1+EPG2+EPG3+EPG))/4

Ao final da disciplina o aluno terá aprendido conceitos e algoritmos importantes que o tornarão capaz de desenvolver aplicações eficientes para resolução, representação e otimização de problemas utilizando grafos.

Dicas

• Tente não deixar o conteúdo acumular, pois uma aula precisa e utiliza o conteúdo da aula anterior, o assunto é totalmente acumulativo e os conceitos aprendidos serão utilizados durante toda a disciplina.
• Faça resumos, leitura ativa das notas de aula e slides e sempre procure se aprofundar nos conceitos.
• Procure sempre tirar suas dúvidas, faça uso da monitoria. Converse com o(a) monitor(a) e/ou com a professora, não guarde suas dúvidas.
• Pratique bastante! Ao praticar utilizando os exercícios conceituais e em paralelo utilizar as ferramentas propostas, você irá fixar muito mais cada conceito e saberá pô-los em prática.
• Não deixe de fazer os quizzes, e tente fazê-los logo após as aulas, pois desse modo você consegue também perceber suas dificuldades e assim focar seus estudos nelas, além de estar praticando.
• Sempre faça uso do repositório da disciplina, nele há exemplos de todos os conceitos vistos implementados utilizando a JgraphT. Se possível, depois de estudar a teoria, tente implementar estes exemplos também, pois assim você poderá comparar com as suas soluções, e assim você estará testando seus conhecimentos e adquirindo novos.
• Faça uso da JgraphT, além de você está se aperfeiçoando também na linguagem Java, você aprenderá sobre classes e métodos que poderão facilitar a resolução de problemas comuns, além de tornar a sua aplicação eficiente e prática usando grafos.
• Teoria dos grafos é uma disciplina muito importante, pode-se apontá-la como um dos pilares da Ciência da Computação, não negligencie! Todo o aprendizado adquirido, facilitará o seu entendimento em outras disciplinas e áreas da computação. Um profissional que consegue modelar problemas utilizando os conceitos e a estrutura de grafos, é muito valorizado no mercado, além de desenvolver ótimas soluções para problemas, pois seu pensamento abstrato e o seu conhecimento sobre padrões e ferramentas são eficientes, e tudo isso pode ser concretizado com a ajuda dos conceitos da teoria dos grafos.
• Recomendo que você escute este podcast sobre a A beleza matemática dos Grafos, vai lhe dar uma ótima dimensão sobre aplicações da teoria dos grafos.