·
Engenharia de Biotecnologia ·
Estrutura de Dados
Send your question to AI and receive an answer instantly
Preview text
Lista Teoria dos Grafos 1 ListecincosituacoesqueaTeoriadosGrafospodeserutilizadonaturalmente 2 AvalieseosgrafosGeHsaoisomorfosCasosejaverdadeiroindiqueasesquivalˆenciasentreos 1 ListecincosituacoesqueaTeoriadosGrafospodeserutilizadonaturalmente 2 AvalieseosgrafosGeHsaoisomorfosCasosejaverdadeiroindiqueasesquivalˆenciasentreos vertices e arestas que provam a isomorfia u v x y w u v x y w v 1 v 2 v 3 v 4 v 5 G v 1 v 2 v 3 v 4 v 5 G H 3 3 Verifique as condições necessárias para Idomorfia entre os grafos e determine se realmente sao Justifique sua resposta 4 4 Seja G um grafo com os vertices V G abcdef e as arestas A G ab ae bc cc de ed Desenhe G G e simples Liste os graus de cada vertices Quais sao as arestas incidentes a b Quais sao os vizinhos de a Escreva a matriz de adjacˆencia de G 5 5 Considere V G abcdef A G ad ae bd bf cd ce cf a Escreva a matriz de adjacˆencia b Este grafo e bipartido Prove 6 6 Desenhe o Grafo das matrizes de adjacˆencias abaixo 7 7 Apresente as correspondˆencias entre os vertices dos dois grafos abaixo caso sejam isomorfos a c b a g f e d v u t z y x w c b a g f e d v u t z y x w c b a g f e d v u t z y x w c b a g f e d v u t z y x w a b c d e f g h a b c d e f g h 8 8 Descreva os grafos em notacao matricial e verifique sua biparticao K 3 K 4 K 5 K 1 3 K 3 2 K 4 3 K 4 3 K 3 3 9 9 Classifique como verdadeiro ou falso Qualquer dois grafos isomorficos tem a mesma sequˆencia de graus Qualquer grafos com a mesma sequˆencia de grais sao isomorficos Considere o Grafo abaixo A B C D E G H I J K B C D E G H I J K F Determine Matriz adjacˆencia do Grafo Grafo Complementar a este Grafo Subgrafo induzido pelos vertices ABCD Separac ao do Grafo em uma biparticao dos vertices se possıvel Defina o fluxos na rede abaixo que descrevem a maior transferˆencia do vertice Fonte para o vertice Sumidouro s B C D t F G 0 20 0 20 0 5 0 30 25 0 0 5 0 15 25 0 0 25 0 15 0 10 s B C D t F G 0 20 0 20 0 5 0 30 25 0 0 5 0 15 25 0 0 25 0 15 0 10 1 1 1
Send your question to AI and receive an answer instantly
Preview text
Lista Teoria dos Grafos 1 ListecincosituacoesqueaTeoriadosGrafospodeserutilizadonaturalmente 2 AvalieseosgrafosGeHsaoisomorfosCasosejaverdadeiroindiqueasesquivalˆenciasentreos 1 ListecincosituacoesqueaTeoriadosGrafospodeserutilizadonaturalmente 2 AvalieseosgrafosGeHsaoisomorfosCasosejaverdadeiroindiqueasesquivalˆenciasentreos vertices e arestas que provam a isomorfia u v x y w u v x y w v 1 v 2 v 3 v 4 v 5 G v 1 v 2 v 3 v 4 v 5 G H 3 3 Verifique as condições necessárias para Idomorfia entre os grafos e determine se realmente sao Justifique sua resposta 4 4 Seja G um grafo com os vertices V G abcdef e as arestas A G ab ae bc cc de ed Desenhe G G e simples Liste os graus de cada vertices Quais sao as arestas incidentes a b Quais sao os vizinhos de a Escreva a matriz de adjacˆencia de G 5 5 Considere V G abcdef A G ad ae bd bf cd ce cf a Escreva a matriz de adjacˆencia b Este grafo e bipartido Prove 6 6 Desenhe o Grafo das matrizes de adjacˆencias abaixo 7 7 Apresente as correspondˆencias entre os vertices dos dois grafos abaixo caso sejam isomorfos a c b a g f e d v u t z y x w c b a g f e d v u t z y x w c b a g f e d v u t z y x w c b a g f e d v u t z y x w a b c d e f g h a b c d e f g h 8 8 Descreva os grafos em notacao matricial e verifique sua biparticao K 3 K 4 K 5 K 1 3 K 3 2 K 4 3 K 4 3 K 3 3 9 9 Classifique como verdadeiro ou falso Qualquer dois grafos isomorficos tem a mesma sequˆencia de graus Qualquer grafos com a mesma sequˆencia de grais sao isomorficos Considere o Grafo abaixo A B C D E G H I J K B C D E G H I J K F Determine Matriz adjacˆencia do Grafo Grafo Complementar a este Grafo Subgrafo induzido pelos vertices ABCD Separac ao do Grafo em uma biparticao dos vertices se possıvel Defina o fluxos na rede abaixo que descrevem a maior transferˆencia do vertice Fonte para o vertice Sumidouro s B C D t F G 0 20 0 20 0 5 0 30 25 0 0 5 0 15 25 0 0 25 0 15 0 10 s B C D t F G 0 20 0 20 0 5 0 30 25 0 0 5 0 15 25 0 0 25 0 15 0 10 1 1 1