Teoria dos Grafos

Question	Answer
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)

Next up

Description

Resource summary

Similar

	Created by Natalie Bravo over 6 years ago

	Copied by Mateus Ferro over 4 years ago