Índice
O que é um circuito em um grafo?
Um circuito (= circuit) num grafo não-dirigido é um ciclo dotado da seguinte propriedade: se um arco v-w pertence ao ciclo então o arco antiparalelo w-v não pertence ao ciclo. (Convém lembrar que ciclos não têm arcos repetidos, e portanto circuitos também não os têm.)
Qual o número máximo de arestas?
O número máximo de aresta é então: n(n − 1)/2. n − k ≤ m ≤ (n − k)(n − k + 1)/2.
Quando um grafo e hamiltoniano?
Um circuito hamiltoniano em um grafo conexo é um circuito que contém todos os vértices do grafo. Um grafo é chamado de grafo hamiltoniano se possui um circuito hamiltoniano. Um grafo não-hamiltoniano é semi-hamiltoniano se possui um caminho que contém todos os seus vértices. Os grafos abaixo não são hamiltonianos.
Como resolver o problema do carteiro chinês?
Para resolver o problema do carteiro chinês primeiro encontramos a menor junção-T. Nós fazemos o grafo virar euleriano pela duplicação da junção-T. A solução para o problema do carteiro chinês no grafo original é obtida por encontrar um circuito euleriano para o novo grafo.
O que é um grafo floresta?
Na teoria dos grafos, uma árvore é um grafo conexo (existe caminho entre quaisquer dois de seus vértices) e acíclico (não possui ciclos). Caso o grafo seja acíclico mas não conexo, ele é dito uma floresta. Uma floresta também é definida como uma união disjunta de árvores. Toda árvore é um grafo bipartido e planar.
Qual é o número máximo de arestas em um grafo completo?
Um grafo completo com v vértices, escrito Kv, é um grafo simples onde todo par de vértices é ligado por uma aresta. Em outras palavras, um grafo completo é um grafo simples que contém o número máximo de arestas. Teorema 1-1: O número de arestas em um grafo completo é n(n-1)/2.
O que é grau de um vértice?
O grau de um vértice é dado pelo número de arestas que lhe são incidentes. Em G1, por exemplo: grau(Pedro) = 3. grau(Maria) = 2.
Como definir se se o grafo e euleriano?
Um grafo conexo G(V,A) é euleriano se, e somente se, o grau de cada vértice de G é par. Seja T um trajeto euleriano fechado de G. Cada vez que um vértice v ocorre no trajeto T, há uma contribuição de duas unidades para o grau de v (uma aresta para chegar a v e outra para sair).
O que é o problema do carteiro chinês em roteirização?
O Problema do Carteiro Chinês caracteriza-se pela roteirização de arcos e tem como objetivo a cobertura de arcos de um grafo, criando uma rota que passe ao menos uma vez em cada um destes arcos.
Como saber se um grafo e conexo?
Um grafo é dito conexo se existir pelo menos um caminho entre cada par de vértices do grafo. Caso contrário, o grafo é chamado de desconexo.