• GRAFO

    Figura plana representando um objeto combinatório abstrato que relaciona 2 elementos para atribuir um par ordenado de vértices:
    . Elemento- conjunto de vertice (nó)
    . Relacionamento - conjunto de aresta que ligam pares de vertices distintos

    Aplicado a: mapas, circuitos elétricos, sequenciamento,emparelhamento, rede de dados, estrutura de programas.

    2017

  • SOLUÇÃO PARA PROBLEMAS COMBINACIONAIS... isomorfismo
    caminho mínimo
    circuito hamiltoniano
    circuito de comprimento máximo
    ciclo euleriano
    ciclo do carteiro chinês
    conjunto estável máximo
    emparelhamento máximo
    coloração de vértices
    coloração de arestas
    planaridade
    conexidade
    coleções disjuntas de caminhos (fluxo)


    TIPOS DE GRAFOS... Grafo simples é um grafo não direcionado, sem laços e existe no máximo uma aresta entre quaisquer dois vértices (sem arestas paralelas). Para um grafo simples, o número de vizinhos de um vértice é igual à sua valência.

    Grafo completo é o grafo simples em que, para cada vértice do grafo, existe uma aresta conectando este vértice a cada um dos demais. Ou seja, todos os vértices do grafo possuem mesmo grau. O grafo completo de n vértices é frequentemente denotado por Kn. Ele tem n(n-1)/2 arestas (correspondendo a todas as possíveis escolhas de pares de vértices).

    Grafo nulo é o grafo cujo conjunto de vértices é vazio.

    Grafo vazio é o grafo cujo conjunto de arestas é vazio.

    Grafo trivial é o grafo que possui apenas um vértice e nenhuma aresta.

    Grafo regular é um grafo em que todos os vértices tem o mesmo grau.

    Multigrafo é um grafo que permite múltiplas arestas ligando os mesmos vértices (arestas paralelas).

    Pseudografo é um grafo que contém arestas paralelas e laços.

    Grafo conexo um grafo é conexo se for possível estabelecer um caminho de qualquer vértice para qualquer outro vértice de um grafo. Se for sempre possível estabelecer um caminho de qualquer vértice para qualquer outro vértice mesmo depois de remover k-1 vértices, então diz-se que o grafo está k-conexo. Note que um grafo está k-conexo se, e somente se, contém k caminhos independentes entre qualquer par de vértices. O grafo de exemplo acima é conexo (e portanto 1-conexo), mas não é 2-conexo. Em um grafo genérico G, o corte associado a um conjunto X de vértices é o conjunto de todas as arestas que têm uma ponta em X e outra em V(G) - X, onde V(G) é o conjunto de todos os vértices pertencentes ao grafo G.

    Ponto de articulação ou Vértice de corte é um vértice cuja remoção desliga um grafo. Uma ponte é uma aresta cuja remoção desliga um grafo. Um componente biconectado é um conjunto máximo de arestas tal que qualquer par de arestas do conjunto fazem parte de um ciclo simples comum. O contorno de um grafo é o comprimento do ciclo simples mais curto no grafo. O contorno de um grafo acíclico é, por definição, infinito.

    Árvore é um grafo simples acíclico e conexo. Às vezes, um vértice da árvore é distinto e chamado de raiz. As árvores são muito usadas como estruturas de dados em informática (veja estrutura de dados em árvore).

    Floresta é um conjunto de árvores; equivalentemente a uma floresta, em algum grafo acíclico.

    Subgrafo de um grafo G é um grafo cujo conjunto dos vértices é um subconjunto do conjunto de vértices G, cujo conjunto de arestas é um subconjunto do conjunto de arestas de G, e cuja função w é uma restrição da função de G.

    Subgrafo gerador é aquele obtido pela remoção de uma ou mais arestas de um outro grafo, dizemos então que este novo grafo obtido é gerador do primeiro,

    Subgrafo induzido é obtido pela remoção de vértices e consequente das arestas relacionadas com ele de um outro grafo, dizemos que este novo grafo é um grafo induzido do original.

    Grafo parcial de um grafo G é um subgrafo com o mesmo conjunto de vértices que G. Uma árvore parcial é um grafo parcial que é árvore. Todo grafo tem pelo menos uma árvore parcial.

    Clique em um grafo é um subgrafo que também é um grafo completo. No grafo do exemplo acima, os vértices 1, 2 e 5 formam um clique.

    Conjunto independente em um grafo é um conjunto de vértices não adjacentes entre si. No exemplo acima, os vértices 1, 3 e 6 formam um conjunto independente e 3, 5 e 6 são outro conjunto independente.

    Grafo planar é aquele que pode ser representado em um plano sem qualquer intersecção entre arestas. O grafo do exemplo é planar; o grafo completo de n vértices, para n> 4, não é planar.

    Grafo bipartido é o grafo cujos vértices podem ser divididos em dois conjuntos, nos quais não há arestas entre vértices de um mesmo conjunto. Para um grafo ser bipartido ele não pode conter circuitos de comprimento ímpar.

    Se um grafo G é bipartido, todo o circuito de G possui comprimento par.Sejam V1 e V2 os dois conjuntos em que, de acordo com a definição de grafo bipartido, se particiona V(G). Toda a aresta de G conecta um vértice em V1 com outro em V2. Assim sendo, se X for um vértice de V1, para “voltar” a esse vértice terá de se ir a V2 e voltar a V1 um número indeterminado de vezes, e de cada vez serão percorridas duas arestas, uma de um vértice em V1 para um vértice em V2 e outra de um vértice em V2 para um vértice em V1. Logo, o número de arestas a percorrer será par, ou seja, o comprimento do circuito é par.

    Se todo o circuito de um grafo G possui comprimento par, então o grafo é bipartido.Seja G um grafo em que todo o circuito tem comprimento par, e seja X um vértice de G. Denotemos por V1 o conjunto formado por X e por todos os vértices cuja distância a X é par. Seja V2 = V(G)\V1 (isto é, o conjunto formado pelos vértices de G que não pertencem a V1). Pretende mostrar-se que não existe qualquer aresta que conecte vértices de V1 ou vértices de V2. Suponhamos a existência de tal aresta, isto é, suponhamos a existência de dois vértices em V1 (ou V2), digamos Xi e Xj, conectados por uma aresta. Ora existe já um caminho de comprimento par entre Xi e Xj, já que existem caminhos, ambos de comprimento par (ou ímpar, no caso de Xi e Xj pertencerem a V2), entre Xi e X e entre X e Xj. Se a esse caminho juntarmos a aresta {Xi;Xj} obtemos um circuito de comprimento ímpar o que contraria a hipótese de apenas existirem circuitos de comprimento par.

    Grafo bipartido completo é o grafo bipartido, cujo qualquer vértice do primeiro conjunto é adjacente a todos vértices do segundo conjunto.

    Grafo k-partido ou grafo de k-coloração é um grafo cujos vértices podem ser particionados em k conjuntos disjuntos, nos quais não há arestas entre vértices de um mesmo conjunto. Um grafo 2-partido é o mesmo que grafo bipartido.

    Emparelhamento de grafos consiste em partir o grafo em conjuntos de vértices a qual não compartilham nenhuma aresta entre eles.
  • SUB TÓPICO

    É um sub conjunto ou interseção de tópicos