P3 Matematica Discreta - Analise de Grafos Relacionamento Colaboracao e Isomorfismo

P3 Matematica Discreta Leia com atencao Justifique suas respostas 1 Neste problema refirase aos exemplos da secao 91 do livrotexto Ma 10 tematica Discreta e suas Aplicacoes O que representam i o grau de um vertice ii vertices isolados iii vertices incidentes numa unica aresta em grafos de a relacionamento b colaboracao 2 Construa se possıvel um grafo nao orientado com 7 vertices em que 3 10 desses vertices tˆem grau 1 ou 3 Pode usar arestas multiplas ou lacos 3 Na escola Paul Erdos para completar um projeto de ensino realizamse 20 todas as seguintes tarefas escrita verificacao inscricao implementacao Num grupo de quatro professoras dessa escola a relacao de tarefas que cada uma pode realizar e a seguinte Ana inscricao e verificacao Beatriz escrita implementacao e verificacao Carla inscricao escrita e implementacao Diana inscricao a Considere o grafo em que os vertices representam as professoras ou as tarefas e as arestas indicam que determinada professora pode realizar determinada tarefa Qual dos seguintes G ou H representa o grafo descrito b E possıvel completar o projeto atribuindo uma unica tarefa a cada professora 1 4 Determine se os grafos sao isomorfos 20 a b 5 Determine se o grafo tem um ciclo euleriano e construao se existir Se 20 nao existir nenhum ciclo euleriano determine se o grafo tem um caminho euleriano e construa um caminho desses se existir 6 Determine se o grafo admite um ciclo hamiltoniano 20 2 1 Grafo de Relacionamento i Grau de um vértice Significa o número de pessoas que se relacionam com aquela ii Vértice Isolado Pessoa que não se relaciona com ninguém iii Vértices Incidentes numa única aresta Pessoa que só se relaciona com uma única pessoa Grafo de Colaboração i Grau de um vértice Número de autores que colaboram com aquele autor ii Vértice Isolado Autor que não colabora com nenhum outro iii Vértices Incidentes numa única aresta Autor que colabora apenas com outro autor fixado a Resposta G b Subgrafo de G Resposta Sim é possível 2 G grafo orientado com 7 vértices em que 3 vértices têm grau 1 ou 3 Vértices A F E de grau 3 O grafo é semieuleriano pois todos os vértices tem grau par exceto 1 e 3 Isso significa que existe um caminho euleriano começando em 1 e terminando em 3 Caminho Euleriano 12 29 93 35 54 47 76 65 58 84 43 32 29 81 19 98 87 73 Ciclo Hamiltoniano Não repete vértice Esse grafo não é hamiltoniano pois como os vértices C e G têm grau 2 qualquer caminho hamiltoniano precisa passar por um dos dois vértices mais de uma vez