1. Grafo Hamiltoniano: Um grafo Hamiltoniano é um grafo simples que contém um ciclo Hamiltoniano, ou seja, um ciclo que passa por todos os vértices do grafo exatamente uma vez. Um caminho Hamiltoniano é um caminho que passa por todos os vértices do grafo exatamente uma vez. 2. Emparelhamento: Um emparelhamento em um grafo é um conjunto de arestas que não compartilham vértices em comum. Em outras palavras, é um conjunto de arestas que não se intersectam. 3. Cobertura por vértices: Uma cobertura por vértices em um grafo é um conjunto de vértices que cobre todas as arestas do grafo. Em outras palavras, é um conjunto de vértices tal que cada aresta do grafo tem pelo menos uma extremidade nesse conjunto. 4. Fecho Hamiltoniano: O fecho Hamiltoniano de um grafo é um grafo que contém um ciclo Hamiltoniano, mas pode ter mais arestas do que o grafo original. Em outras palavras, é um grafo que pode ser obtido adicionando arestas ao grafo original de forma a formar um ciclo Hamiltoniano. 5. Árvore Geradora: Uma árvore geradora de um grafo é uma sub-árvore que contém todos os vértices do grafo original e é uma árvore, ou seja, é um grafo conexo e acíclico. 6. k-fator: Um k-fator em um grafo é um subgrafo que é k-regular, ou seja, cada vértice tem grau k. Em outras palavras, é um subgrafo que contém k arestas incidentes em cada vértice.
Para escrever sua resposta aqui, entre ou crie uma conta
Compartilhar