Scribd Logo
Carregar

Bem-vindo(a) ao Scribd!

  • 71 visualizações

    ALGORITMOS EM GRAFOS-plano de Aula

    Enviado por

    kamilly amancio
    O documento discute conceitos fundamentais de teoria dos grafos, incluindo formalização, conectividade, caminhos, buscas e coloração. As questões abordam propriedades de diferentes tipos de grafos e algoritmos como busca em profundidade, Bellman-Ford e Kruskal.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd

    ALGORITMOS EM GRAFOS-plano de Aula

    Enviado por

    kamilly amancio
    71 visualizações7 páginas
    O documento discute conceitos fundamentais de teoria dos grafos, incluindo formalização, conectividade, caminhos, buscas e coloração. As questões abordam propriedades de diferentes tipos de grafos e algoritmos como busca em profundidade, Bellman-Ford e Kruskal.

    Título original

    ALGORITMOS EM GRAFOS-plano de aula

    Direitos autorais

    © © All Rights Reserved

    Formatos disponíveis

    PDF, TXT ou leia online no Scribd

    Você considera este documento útil?

    Este conteúdo é inapropriado?

    O documento discute conceitos fundamentais de teoria dos grafos, incluindo formalização, conectividade, caminhos, buscas e coloração. As questões abordam propriedades de diferentes tipos de grafos e algoritmos como busca em profundidade, Bellman-Ford e Kruskal.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd
    Fazer download em pdf ou txt
    71 visualizações7 páginas

    ALGORITMOS EM GRAFOS-plano de Aula

    Enviado por

    kamilly amancio
    O documento discute conceitos fundamentais de teoria dos grafos, incluindo formalização, conectividade, caminhos, buscas e coloração. As questões abordam propriedades de diferentes tipos de grafos e algoritmos como busca em profundidade, Bellman-Ford e Kruskal.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd
    Fazer download em pdf ou txt
    de 7

    ALGORITMOS EM GRAFOS

    Tema ­1. CONCEITUAÇÃO E FORMALIZAÇÃO DE GRAFOS

    Questão 1: Marque a alternativa correta com relação a Teoria dos Grafos:


    a)Todo grafo (simples e não­simples) possui loops e arestas paralelas.
    b)Um grafo complementar G' de G' é um grafo resultante da retirada de todas as arestas restantes
    em G'.
    c)Um grafo ciclo é um grafo que possui obrigatoriamente n­1 arestas.
    d)Os digrafos podem ser desenhados através de um diagrama onde os vértices são representados
    por pontos e cada aresta (vi, vj) é representada por uma linha ligando vi a vj com uma seta
    apontando para vj.
    e) Um grafo árvore possui ciclos como subgrafo.

    Questão 2: Marque a alternativa incorreta com relação a Grafos Bipartidos:


    a)Todo grafo bipartido não possui ciclos ímpares.
    b)Na coloração de grafos, os vértices adjacentes são coloridos de forma diferente. Um grafo
    bipartido pode ser colorido com no mínimo, duas cores.
    c)Um grafo bipartido também é conhecido como bigrafo, é um grafo cujos vértices podem ser
    divididos em dois conjuntos disjuntos U e V tais que toda aresta conecta um vértice em U a um
    vértice em V; ou seja, U e V são conjuntos independentes.
    d)Todo grafo bipartido não possui ciclos pares.
    e)Todo grafo árvore é bipartido

    Questão 3: Considerem que existam 3 casas e que cada uma delas precisa ser ligada ao sistema de
    eletricidade, gás e água. Por questões de segurança, deseja­se saber se é possível fazer as ligações sem
    que haja cruzamento das tubulações. Esse problema pode ser representado através de qual tipo/classe
    de grafo?
    a) Qualquer grafo Bipartido
    b) Grafo Bipartido completo K_3,3
    c) Qualquer grafo planar
    d) Grafo desconexo
    c) Grafo k­regular.

    Questão 4: É comum utilizar do conceito de teoria dos grafos para representar uma decomposição
    topológica e um traçado de circuito elétrico. No caso de uma placa de circuito elétrico, o mesmo pode
    ser representado por qual classe de grafo?
    a) Qualquer grafo Bipartido
    b) Grafo Bipartido Planar
    c) Qualquer grafo planar
    d) Grafo desconexo
    c) Grafo k­regular.

    Questão 5: Representar graficamente a seguinte matriz de incidência. Implementar a matriz em


    Linguagem estruturada (C/C++):
    Além disso, marque a alternativa que indica qual tipo de grafo é resultante da construção através da
    Matriz de Incidência acima:
    a) Uma árvore
    b) Um ciclo par
    c) Um grafo conexo
    d) Um grafo completo
    e) Um ciclo ímpar

    Questão 6: Considere o conjunto de V de vértices e A de arestas abaixo. Construir o grafo resultante e


    realizar a implementação computacionalmente.
    V = {x1, x2, x3, x4}
    A ={(x1, x2), (x1, x3), (x2, x4), (x3, x4)}
    Além disso, marque a alternativa que indica qual tipo de grafo é resultante da construção acima:
    a) Uma árvore
    b) Um ciclo par
    c) Um grafo desconexo
    d) Um grafo completo
    e) Um ciclo ímpar

    Questão 7: Considere o seguinte conjunto de V de vértices e A de arestas abaixo. Construir a lista de adjacências
    resultante e a sua respectiva implementação em Linguagem C/C++.
    V = {x1, x2, x3, x4}
    A ={(x1, x2), (x1, x3), (x2, x4), (x3, x4)}
    Além disso, marque a alternativa que indica qual tipo de grafo é resultante da construção acima:
    a) Uma árvore
    b) Um ciclo par
    c) Um grafo desconexo
    d) Um grafo completo
    e) Um ciclo ímpar

    Questão 8:Seja a seguinte matriz de incidências. Implementar a sua respectiva Lista de Adjacências
    em Linguagem estruturada (C/C++):
    Além disso, marque a alternativa que indica qual tipo de grafo é resultante da construção acima:
    a) Uma árvore
    b) Um ciclo par
    c) Um grafo conexo
    d) Um grafo completo
    e) Um ciclo ímpar

    Tema ­2. CÁLCULO DE CONEXIDADE E DISTÂNCIA

    Questão 1: Marque a alternativa que indica qual propriedade de conectividade está descrita de forma
    correta:
    a) Um grafo conexo é separável se a conectividade de vértices é igual a 1
    b) Um grafo G ék­conexo em arestas (ou vértices) quando sua conectividade de arestas (ou
    vértices) é >=k
    c) Todo grafo floresta possui n­1 arestas, o que garante a conectividade dessa floresta.
    d) Um grafo tem um conector se e somente se ele é desconexo.
    e)Todos grafo tem um conjunto acíclico.

    Questão 2: Marque a alternativa que indica qual propriedade de conectividade está descrita de forma
    incorreta:
    a) Um grafo é conexo se seus vértices são ligados dois a dois. i.e., um grafo é conexo se o vértice v
    é ligado a w para cada par (v, w) de seus vértices.
    b) Todo caminho é um grafo conexo.
    c) Todo circuito é um grafo conexo.
    d) Todo grafo grade é um grafo desconexo.
    e) Todos grafo floresta é desconexo.

    Questão 3: Marque a alternativa que indica qual propriedade de conectividade está descrita de forma
    correta:
    a) Um grafo conexo é separável se a conectividade de vértices é igual a 1
    b) Um grafo G ék­conexo em arestas (ou vértices) quando sua conectividade de arestas (ou
    vértices) é >=k
    c) Todo grafo floresta possui n­1 arestas, o que garante a conectividade dessa floresta.
    d) Um grafo tem um conector se e somente se ele é desconexo.
    e)Todos grafo tem um conjunto acíclico.

    Questão 4: Marque a alternativa que indica qual propriedade de conectividade está descrita de forma
    incorreta:
    a) Um grafo é conexo se seus vértices são ligados dois a dois. i.e., um grafo é conexo se o vértice v
    é ligado a w para cada par (v, w) de seus vértices.
    b) Todo caminho é um grafo conexo.
    c) Todo circuito é um grafo conexo.
    d) Todo grafo grade é um grafo desconexo.
    e) Todos grafo floresta é desconexo.

    Tema ­3. CAMINHOS EM GRAFOS


    Questão 1: Assinale a opção correta a respeito de teoria dos grafos, caminhos e conexidade.
    (A) Um caminho é dito simples se passa exatamente uma vez por cada um dos vértices do grafo, e é
    unitário se passa exatamente uma vez por cada uma das arestas.
    (B) O comprimento de um percurso em um grafo não valorado corresponde à soma dos custos de
    percorrer cada aresta, e em um grafo valorado é igual ao número de arestas que o compõem.
    (C) Um ciclo que passa por todas as arestas de um grafo é dito hamiltoniano, e um circuito elementar
    que passa por todos os vértices denomina­se euleriano.
    (D) O problema do caixeiro viajante consiste em analisar todos os circuitos hamiltonianos existentes
    para n ­1 pontos.
    (E) Segundo o conceito de conexidade em grafos orientados, não é necessário que haja um caminho
    ligando qualquer par de vértices; se isso ocorrer, diz­se que o grafo é fortemente conexo, tal que,
    dados dois vértices, qualquer um pode ser atingido a partir do outro.

    Questão 2: Todo grafo circuito é _________________________________. Marque a alternativa


    correta referente a afirmação anterior.
    a) Uma árvore
    b) Aresta­biconexo
    c) Uma ponte
    d) Desconexo
    e) um caminho

    Questão 3: Uma companhia possui filiais em cinco cidades A, B, C, D e E. As tarifas para vôos diretos
    entre estas cidades são dadas na tabela abaixo:

    Qual é o custo de viajar entre cada par de cidades pela rota de menor custo?
    a) 80
    b) 75
    c) 55
    d) 53
    e) Nenhuma das anteriores

    Questão 4: Aplicando o Bellman­Ford no grafo resultante acima, o resultado dos caminhos gerados
    são:
    a) 50
    b) 75
    c) 52
    d) 53
    e) Nenhuma das anteriores
    Tema ­4. TÉCNICAS DE BUSCAS EM GRAFOS (ATIVIDADE PRÁTICA
    SUPERVISIONADA)

    Questão 1: Seja o seguinte grafo abaixo (representado por uma matriz de adjacência)

    Qual é o tempo de visita de cada vértice, aplicando o algoritmo de Busca em profundidade?


    a) A­0 / B­1 / C­1 / D­2 / E­3
    b) A­0 / B­1 / C­1 / D­3 / E­3
    c) A­1 / B­1 / C­1 / D­2 / E­3
    d) A­0 / B­1 / C­4 / D­2 / E­3
    e) Nenhuma das anteriores

    Questão 3: Seja o seguinte grafo abaixo (representado por uma matriz de adjacência):

    Qual é o tempo de término da visita de cada vértice, aplicando o algoritmo de Busca em profundidade?
    a) A­8 / B­8 / C­5 / D­7 / E­6
    b) A­2 / B­1 / C­1 / D­3 / E­4
    c) A­9 / B­8 / C­5 / D­7 / E­6
    d) A­4 / B­1 / C­2 / D­2 / E­3
    e) Nenhuma das anteriores

    Questão 4: Sobre as propriedades elementares de árvores e de árvores geradoras, marque a opção


    incorreta:
    a) Uma árvore é um grafo conexo e sem ciclos.
    b) Uma árvore geradora de um grafo G é um subgrafo que tem os mesmos vértices de G e é uma
    árvore.
    c) Um grafoK_4 possui 16 árvores geradoras.
    d) Uma árvores geradora possui n­1 arestas.
    e) Uma árvores geradora pode ter um ciclo par como subgrafo.

    Questão 5: Sobre as propriedades elementares de árvores, de árvores geradoras e dos algoritmos de


    Kruskal e Prim, marque a opção incorreta:
    a) Uma árvore T é chamada de árvore geradora de um grafo G se T é um subgrafo de G que possui
    todos os vértices de G..
    b) Todo grafo conexo contém pelo menos uma árvore geradora..
    c) O algoritmo de Kruskal tem por objetivo determinar uma árvore geradora mínima em um grafo
    qualquer.
    d) Uma árvores geradora possui n­1 arestas. O algoritmo de Prim, após executado, irá retornar
    uma árvores geradora com n­1 vértices.
    e) O algoritmo de Prim constrói uma árvore única ao longo da sua execução
    Questão 6: Seja o seguinte grafo abaixo (representado por uma matriz de adjacência):

    Qual é otempo de visitade cada vértice, aplicando o algoritmo de Busca em profundidade?


    a) A­0 / B­1 / C­1 / D­2 / E­3
    b) A­0 / B­1 / C­1 / D­3 / E­3
    c) A­1 / B­1 / C­1 / D­2 / E­3
    d) A­1 / B­1 / C­2 / D­2 / E­3
    e) Nenhuma das anteriores

    Questão 7: Seja o seguinte digrafo abaixo (representado por uma matriz de adjacência):

    Considerando que a Ordenação Topológica (DAG) é uma aplicação da busca em profundidade, marque abaixo o
    resultado da ordenação topológica realizada no digrafo acima?

    a) A­B­C­D
    b) C­D­B­A
    c) A­C­D­B
    d) A­A­C­D
    e) Nenhuma das anteriores

    Tema ­5. GRAFOS PLANARES E COLORAÇÃO

    Questão 1: Marque a opção que apresenta um grafo que não é planar:


    a) K_3,3
    b) K_4
    c) Um grafo ciclo de 3 vértices
    d) Grafo bipartido com 2 vértices em cada partição.
    e) Um grafo ciclo par
    Questão 2: Em cada um dos casos abaixo, determine os valores de n (número de vertices), m (número
    de arestas), e f (número de faces) considerando que o grafo seja planar. Desenhe, se possível, um grafo
    simples, conexo e planar que satisfaça a propriedade ou explique porque um grafo planar com tal
    propriedade não existe.
    (a) 7 vértices e 13 arestas;
    (b) 6 vértices e 8 faces;
    (c) 13 arestas e 9 faces;
    (d) 6 vértices e 14 arestas;
    (e) 5 faces 10 arestas

    Questão 3: Determine se cada uma das afirmações abaixo é verdadeira ou falsa. Justifique.
    (I) Todo subgrafo de um grafo planar é planar.
    (II) Todo subgrafo de um grafo não planar é não planar.
    (III) Todo grafo que contém um subgrafo planar é planar.
    Marque a opção que apresenta a sequencia com as afirmações corretas:
    a) I e II
    b) I, II e III
    c)I e III
    d)Todas são verdadeiras
    e)Todas são falsas.

    Questão 4: Dê um mapa e pergunte: Qual é o menor número de cores necessário para pintar os mapas
    de forma que duas regiões adjacentes não recebam a mesma cor?
    a) 3
    b) 4
    c) 5
    d) 6
    e) 7

    Você também pode gostar