·
Ciência da Computação ·
Matemática Discreta
Send your question to AI and receive an answer instantly
Recommended for you
Preview text
1 2 5222232 182 9 arestas 3 a A1 0 2 4 6 8 A2 0 1 2 3 4 A3 1 3 5 7 9 A4 5 6 7 8 9 A5 0 1 8 9 Resposta b A1 4 3 2 1 0 A2 2 1 0 1 2 A3 6 4 2 0 2 4 6 A4 5 3 1 1 3 5 A5 6 3 0 3 6 Resposta Resposta 9 ① Determine se todo grafo s bipartido A B s R E O a b s D bipartido b c a D E bipartido b c a b e m a D não bipartido a G não é bipartido F A b G A b C F H I D E d F G E 6 a b c d a b a c a c a d a b a b b d c d c d c a b c d a b c d a d a b a c d a c d a b c d a b c d a c d a b c d a c d a b a c d a b a c d a b a b c d a b a c d a b a 7 8a Resposta Não No primeiro grafo os vértices u3 e u6 que têm grau 3 são adjacentes a um vértice em comum u5 No segundo grafo os vértices v2 e v6 que têm grau 3 não são adjacentes a um vértice em comum 8b Resposta Os grafos são isomorfos Um possível isomor smo é fu1 v1 fu2 v9 fu3 v4 fu4 v3 fu5 v2 fu6 v8 fu7 v7 fu8 v5 fu9 v10 e fu10 v6 8c SimOs grafos são isomorfos ⑤ Identifique que os grafos sãoimportes a b c d a e b c d a b c d 10 Não o número mínimo de arestas para o grafo ser conexo é a quantidade de vértices menos 1 neste caso seriam necessárias sete arestas para o grafo ser conexo 11 tem n1 arestas 12a O grafo é completo R Sim 12b O grafo é conexo R Sim 12c É possível encontrar dois caminhos do nó 3 para o nó 6 R Sim A 3456 A 356 12d É possível encontrar um ciclo R A 354 12e É possível encontrar uma aresta cuja remoção transforma o grafo em um grafo acíclico 12f É possível encontrar uma aresta cuja remoção transforma o grafo em um grafo nãoconexo 13a Nas fotos abaixo estão as questões 13B 14 A e B e a questão 15 A e B 13 b 14 Desenhe o grafo a partir da matriz de adjacência a seguir a 1 2 3 4 5 1 2 1 0 0 0 2 0 0 0 0 0 3 2 0 219 1 4 0 0 0 0 2 5 0 0 0 0 0 b 1 2 3 4 1 0 1 0 0 2 1 0 1 1 3 0 1 0 1 4 0 1 1 0 x não ri 15 Escreva a lista de adjacência dos grafos a seguir a 1 2 5 6 2 3 3 4 4 5 7 5 3 7 7 7 5 perco 2 7 pero 1 3 pero 2 7 pero 2 7 pero 3 b A B C B pero 1 C D pero 3 A C F A pero 2 C pero 2 F pero 1 C A B D E A pB3 B p1 D pz E p4 D C E F C p2 E p1 F p2 E C D F C p4 D p4 E p1 F A E D A p1 E p2 D p2 Verificar questão 10 e 11 todos tem no PDF md 6 7
Send your question to AI and receive an answer instantly
Recommended for you
Preview text
1 2 5222232 182 9 arestas 3 a A1 0 2 4 6 8 A2 0 1 2 3 4 A3 1 3 5 7 9 A4 5 6 7 8 9 A5 0 1 8 9 Resposta b A1 4 3 2 1 0 A2 2 1 0 1 2 A3 6 4 2 0 2 4 6 A4 5 3 1 1 3 5 A5 6 3 0 3 6 Resposta Resposta 9 ① Determine se todo grafo s bipartido A B s R E O a b s D bipartido b c a D E bipartido b c a b e m a D não bipartido a G não é bipartido F A b G A b C F H I D E d F G E 6 a b c d a b a c a c a d a b a b b d c d c d c a b c d a b c d a d a b a c d a c d a b c d a b c d a c d a b c d a c d a b a c d a b a c d a b a b c d a b a c d a b a 7 8a Resposta Não No primeiro grafo os vértices u3 e u6 que têm grau 3 são adjacentes a um vértice em comum u5 No segundo grafo os vértices v2 e v6 que têm grau 3 não são adjacentes a um vértice em comum 8b Resposta Os grafos são isomorfos Um possível isomor smo é fu1 v1 fu2 v9 fu3 v4 fu4 v3 fu5 v2 fu6 v8 fu7 v7 fu8 v5 fu9 v10 e fu10 v6 8c SimOs grafos são isomorfos ⑤ Identifique que os grafos sãoimportes a b c d a e b c d a b c d 10 Não o número mínimo de arestas para o grafo ser conexo é a quantidade de vértices menos 1 neste caso seriam necessárias sete arestas para o grafo ser conexo 11 tem n1 arestas 12a O grafo é completo R Sim 12b O grafo é conexo R Sim 12c É possível encontrar dois caminhos do nó 3 para o nó 6 R Sim A 3456 A 356 12d É possível encontrar um ciclo R A 354 12e É possível encontrar uma aresta cuja remoção transforma o grafo em um grafo acíclico 12f É possível encontrar uma aresta cuja remoção transforma o grafo em um grafo nãoconexo 13a Nas fotos abaixo estão as questões 13B 14 A e B e a questão 15 A e B 13 b 14 Desenhe o grafo a partir da matriz de adjacência a seguir a 1 2 3 4 5 1 2 1 0 0 0 2 0 0 0 0 0 3 2 0 219 1 4 0 0 0 0 2 5 0 0 0 0 0 b 1 2 3 4 1 0 1 0 0 2 1 0 1 1 3 0 1 0 1 4 0 1 1 0 x não ri 15 Escreva a lista de adjacência dos grafos a seguir a 1 2 5 6 2 3 3 4 4 5 7 5 3 7 7 7 5 perco 2 7 pero 1 3 pero 2 7 pero 2 7 pero 3 b A B C B pero 1 C D pero 3 A C F A pero 2 C pero 2 F pero 1 C A B D E A pB3 B p1 D pz E p4 D C E F C p2 E p1 F p2 E C D F C p4 D p4 E p1 F A E D A p1 E p2 D p2 Verificar questão 10 e 11 todos tem no PDF md 6 7