Creado por Natalie Bravo
hace más de 6 años
|
||
Pregunta | Respuesta |
Grafo G=(V,E) | Estrutura matemática que consiste em 2 conjuntos finitos. 1º. conjunto dos vértices (V) 2º. conjunto das arestas (E) |
O que é uma extremidade? | Cada aresta consiste de um par não ordenado de elementos de V. Cada elemento de uma aresta é chamado extremidade. |
O que significa uma aresta e = (u,v) | Os vértices u, v estão ligados pela aresta e. u é vizinho de v e vice-versa |
Vizinhança Aberta de v N(v) | Conjunto de vértices vizinhos de v |
Vizinhança Fechada de v N[v] | N[v] = N(v) U {v} |
Aresta Própria | É aquela que une dois vértices distintos. |
Self-loop ou Laço | É a aresta que liga um vértice a ele mesmo. |
Multiaresta | Coleção de 2 ou mais arestas que têm as mesmas extremidades. |
Grafos Simples | É aquele que NÃO possui multiarestas e nem self-loops |
Multigrafo | É aquele que possui pelo menos uma multiaresta e NÃO possui self-loop |
Grafo Geral (pseudografo) | É aquele que pode apresentar self-loop e/ou multiaresta |
Grafo Nulo | É um grafo |
Grafo Trivial | É um grafo com 1 único vértice e 0 arestas |
Aresta Direcionada (arco) | É uma aresta que parece uma seta. |
Muti-Arco | É um conjunto de dois ou mais arcos que têm a mesma cabeça e calda. |
Digrafo (grafo direcionado) | É um grafo que possui todas as arestas direcionadas. |
Digrafo Simples | É aquele que NÃO possui multi-arcos e nem self-loop. |
Grafo Misto | Apresenta arestas e arcos. |
Grafo Subjacente (Grafo Base) | É um grafo obtido a partir da substituição dos arcos de um digrafo por arestas. |
Vértices Adjacentes | u e v são adjacentes se existe pelo menos uma aresta os ligando. |
Arestas Adjacentes | São aquelas que possuem pelo menos uma extremidade em comum. |
v é incidente em e & e é incidente em v | O vértice v é extremidade da aresta e |
Valência de v (grau) d(v) | Nº de arestas próprias incidentes em v + 2*nº de self-loops |
δ e Δ | δ = menor grau de um grafo Δ = maior grau de um grafo |
Sequência de Grau de G | Sequência formada pela disposição crescentes dos graus dos vértices de G |
Um grafo simples não trivial G deve ter... | ...pelo menos um par de vértices com o mesmo grau. |
A soma dos graus de um vértice... | ...é o dobro do número de arestas. |
Em um grafo, existe um número par de... | ...vértices de grau ímpar |
A sequência de grau de um grafo é finita e... | ...decrescente de inteiros não negativos cuja soma é par |
Toda sequência finita decrescente de inteiros não negativos que a soma é par... | ...é sequência de grau de algum grafo. |
Grau de Entrada d+(v) | Nº de arcos direcionados para v |
Grau de Saída d-(v) | Nº de arcos cuja origem é v |
Em um digrafo G, a soma dos graus de entrada e a soma dos graus de saída são ambas... | ...iguais ao número de arcos de G |
A ORDEM de um grafo G é... | |V| = n (nº de vértices de G) |
Cobertura de vértices de G... |
é um conjunto de vértices de G em que todas as arestas de G possui pelo menos uma ponta nesse conjunto
Image:
Image (binary/octet-stream)
|
Subconjunto independente de G... |
É um subconjunto de vértices de G que não possuem arestas em comum.
Image:
Image (binary/octet-stream)
|
Conjunto Dominante de G... |
É um subconjunto de vértices tal que todo vértice do grafo ou está no conjunto ou é adjacente a um vértice do conjunto.
Image:
Image (binary/octet-stream)
|
Emparelhamento ou matching... |
É um subconjunto de arestas de G que NÃO são mutuamente adjacentes.
Image:
Image (binary/octet-stream)
|
Kn |
Grafo completo de ordem n (n º de vértices)
Image:
Image (binary/octet-stream)
|
Um grafo Kn tem o nº de arestas = ... | nº arestas = n*(n-1)/2 |
K p,q |
É um gafo bipartido completo.
Image:
Image (binary/octet-stream)
|
Grafo REGULAR... | É um grafo em que todos os vértices tem o mesmo grau. |
Grafo K-regular... | Grafo regular cujo os nós tem grau K. |
Grafo de Pertson... |
Grafo 3-regular:
Image:
Image (binary/octet-stream)
|
Grafo caminho ou Grafo linear (Pn) |
É um grafo em que o |V| = |A| + 1
Image:
Image (binary/octet-stream)
|
Grafo círculo (Cn) |
É um grafo com um único vértice e um self-loop OU um grafo simples com
|V| = |A|
Image:
Image (binary/octet-stream)
|
Caminho ou passeio | É uma sequência alternada de vértices e arestas de um nó Vo até Vk. |
Caminho Simples | Um caminho que não repete vértices. |
Trilha | Um caminho que não repete arestas. |
Comprimento de um caminho | Nº de arestas da sequência que compoẽ o caminho. |
Caminho trivial | Apresenta comprimento 0, ou seja, possui um vértice e nenhuma aresta. |
Ciclo (caminho fechado) | Caminho não trivial que começa e termina no mesmo vértice. |
Circuito (caminho direcionado fechado) | É um caminho direcionado não trivial que começa e termina no mesmo vértice. |
Concatenação de dois caminhos | Sendo W1 ={ a, b} o caminho 1 e W2 ={x, y} o caminho 2: W1 o W2 = {a, b, x, y} |
Distância d(s, t) | A distância de um vértice s a um vértice t é o comprimento do menor caminho s-t, se existir caminho, caso contrário d(s, t) = infinito |
Excentricidade de um vértice exc(v) | É a distância de v ao seu vértice mais distante |
Diâmetro de G diam(G) | É o maior valor de excentricidade dentre todos os vértices de V. |
Raio de G rad(G) | É o menor valor de excentricidade dentre todos os vértices de G. |
Um vértice de G é CENTRAL se... | ...a sua excentricidade é igual ao raio de G, ou seja, se exc(v) = rad(G). |
Grafo Conexo | É aquele que possui um caminho entre quaisquer pares de vértices. |
Grafo fortemente conexo | Se para qualquer par de vértice u e v existe um caminho direcionado de u para v e vice versa. |
Componente conexa | Subconjunto maximal de vértices em que para qualquer vértice v e u existe um caminho. |
Ciclo hamiltoniano | um ciclo que inclui todos os vértices de um grafo. |
Grafo hamiltoniano |
Grafo que apresenta um ciclo hamiltoniano.
Image:
Image (binary/octet-stream)
|
Um grafo G é bipartido se e somente se... | ...não apresenta ciclo de tamanho ímpar. |
Trilha euclidiana | É aquela que contém todas as arestas de G. |
tour(ciclo) euclidiano | É uma trilha euclidiana fechada. |
Grafo euclidiano | É aquele que possui um ciclo euclidiano. |
Circunferência de um grafo | É o tamanho do maior ciclo de G. |
Árvore | É um grafo que não apresenta ciclos. |
Isomorfismo de grafo | Um isomorfismo dos grafos G e H é uma bijeção entre os conjuntos de vértices de G e H de tal forma que quaisquer dois vértices u e v de G são adjacentes em G se e somente se ƒ(u) e ƒ(v) são adjacentes em H. |
Seja G e H grafos isomorfos e u ∈ Vg, então... | d(v) = d(f(v)) |
Seja G e H grafos isomorfos, então... | ... G e H tem a mesma sequência de grau. |
Seja f : G --> H um isomorfismo e e ∈ Eg, então... | ...as extremidades de f(e) têm os mesmos valores de grau das extremidades de e. |
Um subgrafo H de um grafo conexo G é dito GERADOR de G se... | Vh = Vg e for conexo |
Árvore de cobertura | É um subgrafo gerador de G conexo que não apresenta ciclos. |
Floresta (grafo acíclico) |
¿Quieres crear tus propias Fichas gratiscon GoConqr? Más información.